Geometric Constraint Decomposition and Manipulation

The aim is to develop a key, missing technology for flexible decomposition of geometric constraint systems into small, compact subsystems whose solutions can be recombined. Due to the current lack of such decomposition-recombination techniques,

• there are essentially no spatial variational constraint solvers that scale to very large problem sizes;
• constraint propagation based solvers cannot decompose cyclically constrained problems, an essential feature of variational problems; and
• assembly constraint solvers are seriously limited.

This basic inadequacy in spatial constraint solving seriously hinders progress in the development of intelligent CAD/CAM/CAE systems.

Initial research (see recent paper) has uncovered a new and efficient approach for isolating small, solvable subsets of geometric constraint systems. The approach is based on a simple but unconventional modification of network flow. It is completely general, handles all constraint systems, is easy to implement as well as to modularize and hence has the potential to become the key component of a new generation of constraint solvers in CAD/CAM/CAE systems. The decomposition technology to be developed by the proposed project will be based on this recent break-through. Applications would extend to all contexts where geometric constraints arise, including virtual reality, graphics, robotics, teaching geometry, etc.

The decomposition problem has geometric, algebraic as well as graph-theoretic components, and consists of three broadly defined subproblems:

• to solve the recombination problem by treating the partially solved subsystem as a rigid body,
• to address the problems of underconstrained systems, a high priority in many applications, and of consistently overconstrained systems, which arise in assemblies;
• to investigate the inclusion of other equational constraints that express relationships between parameters of a geometric constraint system.

We will continue to perform rigorous complexity analyses on the new algorithms as well as develop prototype implementations. To assess the practicality of the prototypes, we will compare them with benchmarks, both in terms of stand-alone performance, and the ease of incorporation as modular components into existing geometric constraint solvers.