【作者】 黄学良；

【导师】 陈立平；

【作者基本信息】 华中科技大学 ， 机械设计及理论， 2011， 博士

【摘要】 几何约束求解技术作为现代CAD系统的核心技术之一,广泛应用于产品造型、装配设计、运动学分析和虚拟现实等诸多领域。尽管在过去几十年中有大量文献研究几何约束系统的求解,但仍然有许多问题没有得到解决,特别是在三维几何约束求解领域。为此,本文对三维几何约束系统的建模、分析、分解和求解等方面的关键问题进行了深入系统的研究,主要内容和研究成果可归纳为如下几个方面:(1)通过从几何角度构建若干基本几何约束方程,将多样性的三维几何约束映射为这些基本几何约束方程的组合表达,总结归纳出11种不同的三维几何约束,为几何约束系统的组合分析奠定基础。揭示了几何约束系统的冗余性分析和结构分解必须综合考虑变量层面的方程表达和对象层面的约束图表达,并为此提出几何约束层次偶图表达三维几何约束系统,不仅可以兼容现有的各种结构分解方法,而且为几何约束和工程约束的混合建模与求解以及将几何约束求解扩展到多体系统动力学分析计算奠定基础。(2)通过对比分析现有几何约束系统结构分解方法的优势和不足,揭示了几何约束系统结构分解的内在机理,明确指出结构分解方法必须和冗余性分析方法紧密结合才能保证结构分解结果的正确性。引入代数几何理论研究几何约束系统的雅可比矩阵行秩亏损与冗余约束的关系,揭示了雅可比矩阵方法是判定冗余约束问题的概率性方法,指出不能采用变量空间任意位置的雅可比矩阵来判定冗余约束;在对比分析现有冗余约束判定方法的基础上,给出了判定三维几何约束系统中冗余约束的混合策略。(3)为克服现有结构分解方法的缺点,通过充分挖掘三维几何领域知识,分析几何约束系统的内在等价性,结合几何约束图的结构分析,提出了三维几何约束系统的等价性分析方法。该方法以优化几何约束图的拓扑结构为目的,采用等价几何约束替换原有几何约束以拆解伪约束闭环、缩减约束闭环和分离约束闭环,实现现有方法无法分解的几何约束系统的进一步分解。与现有结构分解方法不同,等价性分析方法无须剔除冗余约束就能自然地处理过约束、完整约束和欠约束的三维几何约束系统,而且可以实现大部分三维几何约束系统在几何意义上的最大分解。(4)等价性分析方法可以将三维几何约束系统分解为一系列的子系统,这些子系统可以分为两个刚体之间的开环几何约束系统和多个刚体构成的闭环几何约束系统。针对两个刚体之间的开环几何约束系统,本文全面地分析了角度约束和距离约束的可解耦求解的条件,指出大量的几何约束组合中的角度约束和距离约束可分开求解的同时,仍然存在许多常见几何约束组合无法解耦求解;依据三维几何约束可以归类为11种的事实,对几何约束系统进行组合分析,发现约束度不小于2的几何约束构成的约束组合只有几十种。通过阐明附加方向约束、冗余几何约束和矛盾几何约束对数值求解的不利影响,给出了两个刚体之间几何约束系统的分类求解方法。针对多个刚体构成的闭环几何约束系统,采用螺旋理论识别出两个刚体之间的几何约束组合对应的运动副约束,将几何约束闭环图转换为运动副约束图,通过求取运动副约束图的最大生成树来选择切除几何约束并计算相对坐标,将几何约束闭环系统的整体迭代求解转换为切除部分几何约束与相对坐标的迭代求解,实现必须迭代求解的约束方程和坐标变量数量的最小化,而且降低了附加方向约束和冗余约束对数值求解的不利影响。(5)提出运动链结构约束的等价替换方法分解三维几何约束闭环系统。该方法通过对三维几何约束闭环系统的运动副约束图进行结构分析,在串联运动链的首尾刚体之间引入与其结构约束等价的几何约束组合将串联运动链从几何约束闭环系统中分离出来,实现此前被认为无法分解的几何约束闭环系统的进一步分解;在大部分情况下,该方法可以将三维几何约束闭环系统分解为一系列两个刚体之间的几何约束系统,这意味着此前必须数值迭代求解的几何约束闭环系统可以采用几何推理方法进行求解。(6)提出投影变换方法求解三维几何约束闭环系统中的平面构型。该方法首先采用螺旋理论和几何推理的方法识别出几何约束闭环系统中的平面构型,然后将这些平面构型投影到二维平面转换为二维几何约束系统,最后通过求得二维几何约束系统的解反算三维几何约束闭环系统的解。投影变换方法降低了约束方程的规模和复杂性,使得约束求解效率和稳定性得到显著提升。最后,在上述理论研究成果的基础上,开发了三维几何约束求解器——CBABench,并给出了多个典型实例以验证本文研究成果的正确性和有效性。更多还原

【Abstract】 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.更多还原