Solving Geometric Constraint Systems

Glenn 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 page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.