Tutorial

 

whitebrd.gif (2067 bytes)One of the most striking features of QOCA is its simple interface.  To understand the interface design, consider a simple application, that of a constraint-based graphics editor. The editor essentially provides three operations: the user may add objects or constraints, the user may delete an object or constraint, and finally the user may edit or directly manipulate an object.  At any point in time, the configuration of the editor consists of a set of graphic objects, a set of constraints over variables in the objects and a current solution which is an assignment to the variables that satisfies the constraints.  The variables correspond to graphical attributes of the objects in the diagram and the diagram on the graphics display is, therefore, simply a visual representation of the current solution.

Reflecting this discussion, the QOCA toolkit is based on the metric space model, a new metaphor for constraint interaction.   In this model, there is a metric which gives the distance between two assignments to the variables, and at any time there is a current set of constraints and a current solution. Mirroring the operations in the graphic editor, interaction in the metric space model can occur in three ways.  First, a constraint may be added to the current set of constraints in which case the new solution is the assignment which is closest to the old assignment and which satisfies the new constraint set.  Second, a constraint may be deleted from the current set of constraints, in which case the current solution remains unchanged.  Finally, the current solution may be manipulated by "suggesting"  values for some of the variables. The new solution is the assignment which is closest to the old assignment and to the requested variable values and which satisfies the constraint set.  The constraint set remains unchanged.

The metric space model is closely related to the now classic hierarchical constraints approach. The reason that we have based the toolkit on the metric space model rather than directly on the constraint hierarchy model is that in the metric space model editing a variable value is viewed as a different operation to constraint deletion and addition while the natural way to model variable editing in the constraint hierarchy approach is as a sequence of constraint deletion and additions. The advantage of having an explicit operation for editing is that the speed requirements for editing are much more stringent than for constraint deletion and addition because of the need to provide continuous feedback during direct manipulation.  Thus for efficiency it is important to provide a specialized algorithm for editing which can take advantage of the fact that the current solution is "close" to the next solution rather than using algorithms for arbitrary constraint deletion and addition. A related advantage of the metric space model is that we believe it more directly matches the application program needs, so it provides a simpler and more natural interface for the application programmer.

QOCA implements the metric space model by means of three main components: constrained variables, called CFloats, linear arithmetic constraints, called LinConstraints, and constraint solvers, called Solvers.

Internally a CFloat, v, has a value, a desired value, both of which are floating point numbers as well as a stay weight, and an edit weight, which, respectively, indicate the importance of leaving the variable unchanged if it is not being edited and the importance of changing it to the desired value when the variable is being edited.  Both weights are non-negative floats. The weights are set by the application programmer when the CFloat is created and cannot be subsequently changed.  Applications set the desired value when the variable is created and also when the variable is selected for editing. The solver is responsible for setting the actual value and will also update the desired value to be the actual value when appropriate.  To the application programmer the CFloat appears to have a single value, since they set the desired value using the method SuggestValue, call the solver, and then read the actual value using GetValue. However, for book keeping reasons, the solver requires CFloats to keep the two values separate.

There are a number of different types of CFloats.  The standard CFloat used by the application programmer is the unrestricted CFloat whose value can range over all reals. Internally the solvers also make use of restricted CFloats whose value must be non-negative and which are used to represent slack variables and artificial variables.

Linear arithmetic constraints, that is LinConstraints, can be constructed from CFloats.   They have the standard form:

(a1 * x1) + ... + (an * xn) op c

where op is one of <, >, >=, <= or ==, c is a float and the ais are floats and the xis are CFloats.  Note that QOCA takes advantage of the C++ facilities for overloading operators so as to allow the natural specification of constraints.

Actually, neither CFloats nor LinConstraints are directly manipulated by the programmer.  Instead, for efficiency and safeness they are manipulated by means of the reference-counted "handles,"  CFloatHandle and ConstraintHandle respectively.  These can be assigned and constructed in the obvious ways.

Constraint solvers form the heart of QOCA.   Interaction with a solver has two modes: constraint manipulation and editing.

Each solver provides the following Boolean methods for constraint manipulation.  Linear constraints can be added to the solver one at a time using AddConstraint.  Each time the solver checks that the new constraint is compatible with the current constraints.  If it is not, the constraint is not added and false is returned.  The solver methods RemoveConstraint allows the application programmer to remove a constraint which is currently in the solver or indicate that it has been changed.  After the application programmer has finished adding or removing constraints from the solver they must call the solver method Solve to find a new assignment for the variables which is as close as possible to the current solution. The desired values are then updated to the new solution.  The reason for requiring the programmer to perform an explicit call to Solve rather than implicitly calling Solve after each addition or deletion is that it may be quite expensive, so should only be called when needed.

The editing mode is used to modify the values of the "edit" variables.  Typically this occurs during direct manipulation.  First the application programmer tells the solver which variables are to be edited using multiple calls to SetEditVar.  Next BeginEdit is called.  This initializes internal data structures for fast "resolving" of the constraints.  Now during manipulation the application programmer repeatedly sets the desired values of the edit variables and then calls the solver function Resolve which efficiently computes the new solution to the constraints which is as close as possible to the old solution and to the new desired values of the edit variables.  Finally the application programmer calls EndEdit to signal the end of the edit phase.

Consider a diagram consisting of a point (xm, ym) and a line from (xl, yl) to (xu, yu) in which the point is constrained to lie at the midpoint of the line.  The following program fragment creates the variables and constraints, adds them to the solver and calls Solve to compute the initial position. The constructor for CFloatHandles takes three arguments: the stay and edit weights together with an initial desired value.  Note that both xm and ym have a stay weight of zero indicating that they are "dependent variables," although they have a non-zero edit weight (otherwise, editing could never change their value!).  Next the program chooses xm and ym to be the edit variables, and then repeatedly samples the mouse to find the desired values and calls Resolve to compute the new value until the user releases the mouse button, which finishes the edit cycle.

CFloatHandle xl(1,1000,45.5);midadjust.jpg (5752 bytes)
CFloatHandle xl(1,1000,45.5);
CFloatHandle xm(0,1000,0);
CFloatHandle xu(1,1000,60);
CFloatHandle yl(1,1000,45.5);
CFloatHandle ym(0,1000,0);
CFloatHandle yu(1,1000,60);

ConstraintHandle xcon = (1*xl + 1*xu - 2*xm == 0;
ConstraintHandle ycon = (1*yl + 1*yu - 2*ym == 0);

CassSolver solver;

solver.AddConstraint(xcon);
solver.AddConstraint(ycon);
solver.Solve();

DrawLine(xl.GetValue(),yl.GetValue(),xu.GetValue(),yu.GetValue());

solver.SetEditVar(xm);
solver.SetEditVar(ym);
solv.BeginEdit();

while (mouse.button.down) {
     xm.SuggestValue(mouse.x);
     ym.SuggestValue(mouse.y);
     solver.Resolve();
     DrawLine(xl.GetValue(),yl.GetValue(),xu.GetValue(),yu.GetValue());
}

solver.EndEdit();

The above example is for the C++ version of QOCA.  Apart from the lack of overloaded operators and slight differences in the naming conventions, the interface to the Java version is similar.  CFloats and LinConstraints are used directly since pointer variables in Java are reference counted.  The following is the corresponding Java code for the above example.

QcCFloat xl = new QcCFloat(1, 1000, 45.5f);
QcCFloat xm = new QcCFloat(0, 1000, 0);
QcCFloat xu = new QcCFloat(1, 1000, 60);
QcCFloat yl = new QcCFloat(1, 1000, 45.5f);
QcCFloat ym = new QcCFloat(0, 1000, 0);
QcCFloat yu = new QcCFloat(1, 1000, 60);

QcLinConstraint xcon = new QcLinConstraint();
QcLinPoly xpoly = new QcLinPoly();
xpoly.addTerm(new QcLinPolyTerm(1, xl));
xpoly.addTerm(new QcLinPolyTerm(1, xu));
xpoly.addTerm(new QcLinPolyTerm(-2, xm));
xcon.makeEq(xpoly, 0);

QcLinConstraint ycon = new QcLinConstraint();
QcLinPoly ypoly = new QcLinPoly();
ypoly.addTerm(new QcLinPolyTerm(1, yl));
ypoly.addTerm(new QcLinPolyTerm(1, yu));
ypoly.addTerm(new QcLinPolyTerm(-2, ym));
ycon.makeEq(ypoly, 0);

QcCassSolver solv;

solver.addConstraint(xcon);
solver.adConstraint(ycon);
solver.solve();

drawLine(xl.getValue(),yl.getValue(),xu.getValue(),yu.getValue());

solver.setEditVar(xm);
solver.setEditVar(ym);
solver.beginEdit();

while (mouse.button.down) {
     xm.suggestValue(mouse.x);
     ym.suggestValue(mouse.y);
     solver.resolve();
     drawLine(xl.getValue(),yl.getValue(),xu.getValue(),yu.getValue());
}

solver.endEdit();