Font Size: a A A

Research On Methods Of Analysis And Solution Of 3D Geometric Constraint System

Posted on:2012-04-25Degree:DoctorType:Dissertation
Country:ChinaCandidate:X L HuangFull Text:PDF
GTID:1118330362955251Subject:Mechanical design and theory
Abstract/Summary:PDF Full Text Request
Geometric constraint solving plays an important role in developing intelligent or parametric CAD systems. Also, it can be used in other fields such as robotics, molecular modeling, teaching geometry, virtual reality, etc. Although the problem of solving geometric constraint system (GCS) has been studied extensively and intensively in the past few decades, there is still a lack of effective 3D geometric constraint solvers that scale to large problem sizes and can be used interactively by the designer as conceptual tools throughout the design process. In this dissertation, several key issues of developing an effective 3D geometric constraint solver have been investigated. The contents and contributions of this dissertation can be concluded as follows:(1) We introduce several basic geometric constraints to establish the unified representation of a wide variety of 3D geometric constraints. Based on the unified representation, the diverse 3D geometric constraints can be classified to eleven categories. In order to support the modeling and solution of the hybrid system containing geometric constraints and engineering constraints, we adopt a hierarchical bipartite graph to represent 3D GCS, which can integrate the equation-oriented representation of GCS with the object-oriented representation of GCS.(2) We point out that the graph-based structural decomposition method must be closely integrated with redundancy analysis method to ensure the correctness of the decomposition result. Using techniques from algebraic geometry theory, we prove that Jacobian matrix at a random configuration of the variable space can not be used to detect redundant constraints unless the constraint equations derived from GCS satisfy some special conditions. We also prove that the Jacobian matrix at random configuration of the solution space is row rank defect is a necessary though not a sufficient condition to determine whether there are redundant constraints. We give the conditions to detect redundant constraint with the Jacobian matrix which is computed at a random configuration of the variable space. Then, we make a comparative analysis of the existing redundancy analysis methods, and adopt a hybrid algorithm combining the efficiency of Jacobian matrix method and the accuracy of numerical perturbation method to determine the numerical redundant constraints.(3) In order to overcome the shortcomings of the graph-based structural decomposition methods, we propose an equivalence analysis approach to deal with the decomposition of 3D GCS which may be over-constrained, well-constrained, and under-constrained problem without removing the redundant constraints. Differ to the existing structural decomposition methods which only exploit the structural information of geometric constraint graph, the equivalence analysis approach makes good use of geometric domain knowledge and topological structural information to transform a 3D GCS into its equivalent one which has the better topological structure of geometric constraint graph. Therefore, the equivalent analysis approach can decompose the 3D GCS which can not be reduced by the existing structural decomposition methods, and can usually achieve the geometrically maximal decomposition of 3D GCS.(4) With the equivalent analysis method, the 3D GCS can be decomposed into some subsystems which can be classified to two categories: the open-loop GCS between two rigid bodies and the closed-loop GCS among three or more rigid bodies. In the case of the open-loop GCS, based on the decoupling analysis and combinatorial analysis, we present a hybrid algorithm combining geometric reasoning and numerical method to improve the efficiency and robustness. It is found that the geometric reasoning can be used to obtain the analytical solutions to all open-loop GCS consisting of the geometric constraints whose degree of constraint are not less than two. It is also discussed that auxiliary direction constraints, redundant constraints and contradictory constraints have the bad influence on numerical solution. With respect to the closed-loop GCS, we propose a constraint transformation method which converts the representation of geometric elements and geometric constraints from Cartesian coordinate space to the relative coordinate space. By using screw theory to recognize the kinematic joint from geometric constraint combination and computing the maximal spanning tree of kinematic joint graph to determine the cut-constraints, the constraint transformation approach can minimize the number of equations and variables which have to be solved simultaneously.(5) We present a novel decomposition method based on the equivalent substitution of the structural constraint of serial kinematic chain to deal with the closed-loop GCS. In this approach, the equivalent geometric constraints are introduced to substitute the serial kinematic chain so that the geometric constraint subsystem corresponding to the serial kinematic chain can be separated from the closed-loop GCS. After the recursive equivalent substitution of serial kinematic chain, the closed-loop GCS which can not be reduced by the existing decomposition method will be decomposed into some open-loop GCS in most cases. It is undoubtedly a historic breakthrough that the explicit geometric reasoning can be employed to solve the closed-loop GCS which previously have to be solved by numerical iteration method.(6) We propose a projection transformation approach to solve the 3D closed-loop geometric constraint problem which is planar configuration. The basic idea of this approach is to convert a complicated 3D geometric constraint problem to an equivalent 2D geometric constraint problem. As a result, it can downsize the constraint equations and variables which have to be solved simultaneously and reduce the complexity of constraint equations. Finally, on the basis of above proposed methods, a 3D geometric constraint solver named CBABench has been developed. The experimental examples show the correctness and effectiveness of the reseach.
Keywords/Search Tags:3D Geometric Constraint Solving, Hierarchical Bipartite Graph, Maximal Decomposition, Redundant Constraint Analysis, Equivalent Geometric Constraint, Closed-loop
PDF Full Text Request
Related items