Ultraviolet: A Constraint Satisfaction Algorithm for Interactive Graphics

Authors: Alan Borning and Bjorn N. Freeman-Benson

In CONSTRAINTS: An International Journal, Special Issue on Constraints, Graphics, and Visualization, Vol. 3 No. 1, April 1998, pages 9-32.


Ultraviolet is a constraint satisfaction algorithm intended for use in interactive graphical applications. It is capable of solving constraints over arbitrary domains using local propagation, and inequality constraints and simultaneous linear equations over the reals. To support this, Ultraviolet is a hybrid algorithm that allows different subsolvers to be used for different parts of the constraint graph, depending on graph topology and kind of constraints. In addition, Ultraviolet and its subsolvers support plan compilation, producing efficient compiled code that can be evaluated repeatedly to resatisfy a given collection of constraints for different input values.

full paper: pdf; compressed postscript

Constraints home page