A Geometric Constraint Solving Approach Based On Graph Decomposition-reduction

Parametric and variational capability plays an important role in CAD systems. Geometric constraint solving is the core technology of CAD systems to achieve parametric and variational design, and also widely used in other associated engineering field. The research on geometric constraint solving is of great significance for the development of parametric and variational CAD software with independent copyrights.In this paper, an approach to solving geometric constraint problems based on graph decomposition-reduction is proposed on the basis of degree of freedom analysis and graph reduction theory. The constraint graph of a geometric constraint problem is decomposed into multiple simple subgraphs, greatly decreasing the solving scale and difficulty. The presented algorithm introduces four kinds of rigid body reducing mode which solves the cyclic constraint problems effectively. The process of decomposition and reduction is guided by the set of priority rules to ensure the solution sequence unique, and as much as possible consistent with the user’s design intent.Geometric elements in the sequence are sovled by an algebraic or numerical method. For mutilple solutions in algebraic solving, we capture the user’s design intent by dividing the positional relationship of geometric elements. An effective solution is selected from the multiple ones according to the principles of minimal location changes or topological relations remaining unchanged of the geometric elements. BFGS method is used in numerical solving which is quite stable and fast. For under constrain and over constraint problems, this method can also get a reasonable solution.Based on the theory and algorithm mentioned above, a two-dimensional geometric constraint solver is developed using object-oriented programming techniques in the three-dimensional solid modeling software, JHSOLID. The functions of dimension-driven, adding geometric constraints and dragging geometric elements are developed, and the parametric and variational design in two-dimensional sketch is basicly realized. The examples show the effectiveness and feasibility of the research in this paper.