The SkyBlue Constraint Solver

Author: Michael Sannella

Published as UW Tech Report 92-07-02.


A constraint describes a relationship that should be maintained, for example that the equality A+B=C holds between three variables, that a set of displayed objects are aligned, or that the elements in a data structure are consistent with a graphic display of this structure. Constraint solvers have been successfully applied to problems in computer graphics including geometric design and user interface construction. This paper presents the SkyBlue constraint solver, an efficient incremental algorithm that uses local propagation to maintain sets of required and preferential constraints. SkyBlue is a successor to the DeltaBlue algorithm, which was used as the constraint solver in the ThingLab II user interface development environment. DeltaBlue has two limitations: cycles of constraints are prohibited, and the procedures used to satisfy a constraint can only have a single output. SkyBlue relaxes these restrictions, allowing cycles of constraints to be constructed (although SkyBlue may not be able to satisfy all of the constraints in a cycle) and supporting multi-output methods. The SkyBlue algorithm has been incorporated into Multi-Garnet, an extended version of the Garnet user interface development system that supports multi-way constraints. Multi-Garnet has been used to build several user interfaces exploiting the features of SkyBlue that would have been difficult to build within Garnet. This paper describes the basic SkyBlue algorithm and outlines several techniques that significantly improve its performance for large constraint graphs. Performance measurements are presented demonstrating that SkyBlue is efficient enough to use in interactive user interfaces.

full tech report (compressed postscript)

Constraints home page