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 objectoriented
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 realtime 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
nonquadratic 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.
