METHOD FOR SOLVING GEOMETRIC CONSTRAINT SYSTEMS

A method, useful in computer-aided design, for finding possible configurations of a system having a collection of geometric entities and constraints. The method represents the geometric entities in terms of degrees of freedom and systematically satisfies the constraints reducing the degrees of freedom of the geometric entities. The method uses a number of specialized routines, called plan fragments, which satisfy a particular constraint relating to a particular geometric entity. Each plan fragment changes the configuration of a geometric entity in space--i.e. the location and orientation--satisfying a constraint and reducing a degree of freedom. The series of plan fragments which reduce the degrees of freedom and satisfy the constraints comprise an assembly plan for possible configurations of the system. The method identifies overconstrained, fully constrained, and underconstrained systems to the user and assists in finding possible configurations if the constraints are changed, added, or deleted. The method is useful in solving any geometric constraint problem, such as describing mechanical assemblies constraint-based sketching and design, geometric modeling for CAD, and kinematic analysis of robots and linkage mechanisms. By reasoning symbolically about the geometry of the system, the method provides faster solutions, numerical stability, user feedback, and the ability to handle redundant constraints.