Since the very infancy of computer graphics there has been interest in the use of constraints.  However, despite the utility of constraints, they are still not widely used in interactive graphical applications.  We feel that the reasons for this are twofold.  First there is the problem of efficiency.  Efficient constraint solving techniques, such as those based on local propagation, are suitable for some applications such as simulation but are not powerful enough for many graphical application since these require inequalities or cyclic constraints.  On the other hand, general arithmetic constraint solving techniques are sufficiently expressive but naive implementations are too slow, in particular for real time direct manipulation.  The second reason is that, perhaps because of concerns about efficiency, most existing constraint solvers are tightly integrated with the graphical application making reuse of the solver in other applications difficult.  This means that an application builder who wishes to provide constraints must spend considerable effort and time building their own specialized constraint solver, something most graphical application programmers do not have the time or necessary background in constraint solving to do.

Over the last 7 years we have been developing an object-oriented constraint solving toolkit, called QOCA, which is expressly designed for interactive graphical applications and which is intended to overcome the above two problems.  It is written in C++ and also has a Java version.  A major design goal has been to provide an interface which is simple yet flexible enough to be used in a wide variety of applications and which treats constraints as first class objects.  The other goal has been to provide constraints which are expressive enough to be useful and yet which can be solved sufficiently quickly for real-time direct manipulation.

Currently QOCA provides three different solvers.  All are based on keeping the current constraints in a tableau and using pivoting to keep them in a solved form.  The first, QcLinEqSolver, provides linear equalities and uses the square of the (weighted) Euclidean distance to compare solutions.  The second, QcLinInEqSolver, also uses the square of the Euclidean distance but also allows linear inequalities.  It is based on linear complementary pivoting.  The third, QcCassSolver, is based on the Cassowary algorithm.  It also provides linear equalities and inequalities but instead uses the (weighted) Manhattan distance to compare solutions.

We have used QOCA in a number of other graphical applications.  It has been employed for two different purpose in the Penguins system.  Given a grammatical specification of a visual language, such as state transition diagrams or mathematical equations, the Penguins system automatically generates an incremental parser for the visual language which is integrated into a graphics editor.  One use of QOCA is for geometric error correction during parsing.  The second use of QOCA in Penguins system is to support direct manipulation during editing of diagrams.  Constraints inferred during parsing are maintained during manipulation, thus providing an editor which behaves as if it understands the semantics of the visual language.  One pleasing observation has been that linear equations and inequalities have proven sufficient to approximate the constraints in a very wide variety of visual languages, namely, state transition diagrams, flow charts, mathematical equations, trees and message sequence charts.

Another application in which we have employed QOCA is for the dynamic layout of multiple column web documents composed of text, images and tables.  As the viewer changes font selection or resizes the browser, the layout of the document is modified.  Geometric constraints ensure that the layout is appropriate.  Again linear equality and inequality constraints have proven powerful enough.  More information about this application can be obtained here.

The final applications we have used QOCA for are in graph layout.  Currently QOCA is not suitable for arbitrary graph layout since this requires minimization of a complex non-quadratic objective function which captures aesthetics like reducing the number of edge crossings.  However, QOCA has proven suitable for tree layout.  Since it also allows arbitrary linear constraints on node placement it is more flexible than other approaches to tree layout.  QOCA has also proven useful for quickly finding an initial graph layout, before using more expensive optimization techniques to improve the layout.  Finally, it has proven useful for removing node overlapping from a graph layout.

The Cassowary algorithm was developed jointly with Alan Borning and Peter Stuckey. and other information about the Cassowary algorithm is available here.