The University of Sussex

Solving geometric constraint systems

Glen A. Kramer

Finding the configurations of a set of rigid bodies that satisfy a set of geometric constraints is a problem traditionally solved by reformulating the geometry and constraints as algebraic equations which are solved symbolically or numerically. But many such problems can be solved by reasoning symbolically about the geometric bodies themselves using a new technique called degrees of freedom analysis. In this approach, a sequence of actions is devised to satisfy each constraint incrementally, thus monotonically decreasing the system's remaining degrees of freedom. This sequence of actions is used metaphorically to solve, in a maximally decoupled form, the equations resulting from an algebraic representation of the problem. Degrees of freedom analysis has significant computational advantages over conventional algebraic approaches. The utility of the technique is demonstrated with a program that assembles and kinematically simulates mechanical linkages.

This paper is not available online