A geometric constraint solver accepts instances of geometric constraint problems. A geometric constraint problem instance consists of a set of geometric elements, such as points, lines and planes, and constraints upon them, such as constraints of distance, angle, coincidence, and so on. The constraint solver then computes a suitable set of coordinates for each geometric element such that the constraints are satisfied, or else announces that no solution could be found.
Applications of geometric constraint solving abound in solid modeling, graphics, engineering, and many other fields (Durand, 1998). We are especially interested in applications in solid modeling, hence we concentrate on solvers that have to tackle nonlinear problems to satisfies the constraints. Incremental constraint satisfaction, an important subject in graphics and simulation, is not addressed in this paper.
A geometric constraint solver can operate in a single phase or in two phases. Single-phase solvers, also called instance solvers, directly translate the constraint problem instance into a representation suitable for solving the problem instance immediately—and then solve the instance. Two-phase solvers first preprocess the constraint system instance, making use of the structure of the constraints and using the constraints symbolically. A fundamental advantage of generic solvers is their ability to create templates to solve classes of constraint problems, e.g. Hoffmann and Vermeer (1994).
After a two-phase solver has preprocessed the problem, a second phase is required to determine actual coordinate values for the geometric elements subjected to the constraints. The work of this second phase differs from the work of single-phase solvers only in that the preprocessing has decomposed the constraint problem and possibly recognized characteristic patterns that are solvable by a repertoire of templates. The second phase has been described in Fudos (1995).