三维几何约束系统的分析与求解方法研究
|
摘要
几何约束求解技术作为现代CAD系统的核心技术之一,广泛应用于产品造型、装配设计、运动学分析和虚拟现实等诸多领域。尽管在过去几十年中有大量文献研究几何约束系统的求解,但仍然有许多问题没有得到解决,特别是在三维几何约束求解领域。为此,本文对三维几何约束系统的建模、分析、分解和求解等方面的关键问题进行了深入系统的研究,主要内容和研究成果可归纳为如下几个方面:
(1)通过从几何角度构建若干基本几何约束方程,将多样性的三维几何约束映射为这些基本几何约束方程的组合表达,总结归纳出11种不同的三维几何约束,为几何约束系统的组合分析奠定基础。揭示了几何约束系统的冗余性分析和结构分解必须综合考虑变量层面的方程表达和对象层面的约束图表达,并为此提出几何约束层次偶图表达三维几何约束系统,不仅可以兼容现有的各种结构分解方法,而且为几何约束和工程约束的混合建模与求解以及将几何约束求解扩展到多体系统动力学分析计算奠定基础。
(2)通过对比分析现有几何约束系统结构分解方法的优势和不足,揭示了几何约束系统结构分解的内在机理,明确指出结构分解方法必须和冗余性分析方法紧密结合才能保证结构分解结果的正确性。引入代数几何理论研究几何约束系统的雅可比矩阵行秩亏损与冗余约束的关系,揭示了雅可比矩阵方法是判定冗余约束问题的概率性方法,指出不能采用变量空间任意位置的雅可比矩阵来判定冗余约束;在对比分析现有冗余约束判定方法的基础上,给出了判定三维几何约束系统中冗余约束的混合策略。
(3)为克服现有结构分解方法的缺点,通过充分挖掘三维几何领域知识,分析几何约束系统的内在等价性,结合几何约束图的结构分析,提出了三维几何约束系统的等价性分析方法。该方法以优化几何约束图的拓扑结构为目的,采用等价几何约束替换原有几何约束以拆解伪约束闭环、缩减约束闭环和分离约束闭环,实现现有方法无法分解的几何约束系统的进一步分解。与现有结构分解方法不同,等价性分析方法无须剔除冗余约束就能自然地处理过约束、完整约束和欠约束的三维几何约束系统,而且可以实现大部分三维几何约束系统在几何意义上的最大分解。
(4)等价性分析方法可以将三维几何约束系统分解为一系列的子系统,这些子系统可以分为两个刚体之间的开环几何约束系统和多个刚体构成的闭环几何约束系统。针对两个刚体之间的开环几何约束系统,本文全面地分析了角度约束和距离约束的可解耦求解的条件,指出大量的几何约束组合中的角度约束和距离约束可分开求解的同时,仍然存在许多常见几何约束组合无法解耦求解;依据三维几何约束可以归类为11种的事实,对几何约束系统进行组合分析,发现约束度不小于2的几何约束构成的约束组合只有几十种。通过阐明附加方向约束、冗余几何约束和矛盾几何约束对数值求解的不利影响,给出了两个刚体之间几何约束系统的分类求解方法。针对多个刚体构成的闭环几何约束系统,采用螺旋理论识别出两个刚体之间的几何约束组合对应的运动副约束,将几何约束闭环图转换为运动副约束图,通过求取运动副约束图的最大生成树来选择切除几何约束并计算相对坐标,将几何约束闭环系统的整体迭代求解转换为切除部分几何约束与相对坐标的迭代求解,实现必须迭代求解的约束方程和坐标变量数量的最小化,而且降低了附加方向约束和冗余约束对数值求解的不利影响。
(5)提出运动链结构约束的等价替换方法分解三维几何约束闭环系统。该方法通过对三维几何约束闭环系统的运动副约束图进行结构分析,在串联运动链的首尾刚体之间引入与其结构约束等价的几何约束组合将串联运动链从几何约束闭环系统中分离出来,实现此前被认为无法分解的几何约束闭环系统的进一步分解;在大部分情况下,该方法可以将三维几何约束闭环系统分解为一系列两个刚体之间的几何约束系统,这意味着此前必须数值迭代求解的几何约束闭环系统可以采用几何推理方法进行求解。
(6)提出投影变换方法求解三维几何约束闭环系统中的平面构型。该方法首先采用螺旋理论和几何推理的方法识别出几何约束闭环系统中的平面构型,然后将这些平面构型投影到二维平面转换为二维几何约束系统,最后通过求得二维几何约束系统的解反算三维几何约束闭环系统的解。投影变换方法降低了约束方程的规模和复杂性,使得约束求解效率和稳定性得到显著提升。
最后,在上述理论研究成果的基础上,开发了三维几何约束求解器——CBABench,并给出了多个典型实例以验证本文研究成果的正确性和有效性。
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.
(1)通过从几何角度构建若干基本几何约束方程,将多样性的三维几何约束映射为这些基本几何约束方程的组合表达,总结归纳出11种不同的三维几何约束,为几何约束系统的组合分析奠定基础。揭示了几何约束系统的冗余性分析和结构分解必须综合考虑变量层面的方程表达和对象层面的约束图表达,并为此提出几何约束层次偶图表达三维几何约束系统,不仅可以兼容现有的各种结构分解方法,而且为几何约束和工程约束的混合建模与求解以及将几何约束求解扩展到多体系统动力学分析计算奠定基础。
(2)通过对比分析现有几何约束系统结构分解方法的优势和不足,揭示了几何约束系统结构分解的内在机理,明确指出结构分解方法必须和冗余性分析方法紧密结合才能保证结构分解结果的正确性。引入代数几何理论研究几何约束系统的雅可比矩阵行秩亏损与冗余约束的关系,揭示了雅可比矩阵方法是判定冗余约束问题的概率性方法,指出不能采用变量空间任意位置的雅可比矩阵来判定冗余约束;在对比分析现有冗余约束判定方法的基础上,给出了判定三维几何约束系统中冗余约束的混合策略。
(3)为克服现有结构分解方法的缺点,通过充分挖掘三维几何领域知识,分析几何约束系统的内在等价性,结合几何约束图的结构分析,提出了三维几何约束系统的等价性分析方法。该方法以优化几何约束图的拓扑结构为目的,采用等价几何约束替换原有几何约束以拆解伪约束闭环、缩减约束闭环和分离约束闭环,实现现有方法无法分解的几何约束系统的进一步分解。与现有结构分解方法不同,等价性分析方法无须剔除冗余约束就能自然地处理过约束、完整约束和欠约束的三维几何约束系统,而且可以实现大部分三维几何约束系统在几何意义上的最大分解。
(4)等价性分析方法可以将三维几何约束系统分解为一系列的子系统,这些子系统可以分为两个刚体之间的开环几何约束系统和多个刚体构成的闭环几何约束系统。针对两个刚体之间的开环几何约束系统,本文全面地分析了角度约束和距离约束的可解耦求解的条件,指出大量的几何约束组合中的角度约束和距离约束可分开求解的同时,仍然存在许多常见几何约束组合无法解耦求解;依据三维几何约束可以归类为11种的事实,对几何约束系统进行组合分析,发现约束度不小于2的几何约束构成的约束组合只有几十种。通过阐明附加方向约束、冗余几何约束和矛盾几何约束对数值求解的不利影响,给出了两个刚体之间几何约束系统的分类求解方法。针对多个刚体构成的闭环几何约束系统,采用螺旋理论识别出两个刚体之间的几何约束组合对应的运动副约束,将几何约束闭环图转换为运动副约束图,通过求取运动副约束图的最大生成树来选择切除几何约束并计算相对坐标,将几何约束闭环系统的整体迭代求解转换为切除部分几何约束与相对坐标的迭代求解,实现必须迭代求解的约束方程和坐标变量数量的最小化,而且降低了附加方向约束和冗余约束对数值求解的不利影响。
(5)提出运动链结构约束的等价替换方法分解三维几何约束闭环系统。该方法通过对三维几何约束闭环系统的运动副约束图进行结构分析,在串联运动链的首尾刚体之间引入与其结构约束等价的几何约束组合将串联运动链从几何约束闭环系统中分离出来,实现此前被认为无法分解的几何约束闭环系统的进一步分解;在大部分情况下,该方法可以将三维几何约束闭环系统分解为一系列两个刚体之间的几何约束系统,这意味着此前必须数值迭代求解的几何约束闭环系统可以采用几何推理方法进行求解。
(6)提出投影变换方法求解三维几何约束闭环系统中的平面构型。该方法首先采用螺旋理论和几何推理的方法识别出几何约束闭环系统中的平面构型,然后将这些平面构型投影到二维平面转换为二维几何约束系统,最后通过求得二维几何约束系统的解反算三维几何约束闭环系统的解。投影变换方法降低了约束方程的规模和复杂性,使得约束求解效率和稳定性得到显著提升。
最后,在上述理论研究成果的基础上,开发了三维几何约束求解器——CBABench,并给出了多个典型实例以验证本文研究成果的正确性和有效性。
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.
引文
[1]唐荣锡. CAD/CAM技术.北京:航空航天大学出版社, 1994
[2] http://en.wikipedia.org/wiki/D-Cubed
[3] http://www.plm.automation.siemens.com/en_us/products/open/d-cubed/customers/index.shtml
[4] Oung J J, Sitharam M, Moro B. Frontier: fully enabling geometric constraints for feature based modeling and assembly. In Proceedings of the Sixth ACM Symposium on Solid Modeling and Applications, 2001
[5] Sitharam M. Frontier, an opensource 3d geometric constraint solver: architecture (Part I). In: http://www.cise.ufl.edu/~sitharam/partone.pdf, 2005
[6]向文.参数化特征造型系统的研究: [博士学位论文],武汉:华中理工大学, 1993
[7]陈立平.几何约束系统最大归约理论与应用研究: [博士学位论文],武汉:华中理工大学, 1995
[8]罗浩.基于约束的工程图形参数化设计系统的理论与实践: [博士学位论文],武汉:华中理工大学, 1996
[9]康友树.变量装配设计原理及方法研究: [博士学位论文],武汉:华中理工大学, 1996
[10]王波兴.几何约束系统若干关键技术的研究与实践: [博士学位论文],武汉:华中科技大学, 2001
[11]彭小波.二、三维几何约束统一求解器原理与方法研究: [博士学位论文],武汉:华中科技大学, 2002
[12]王彦伟.实体造型中的变量化技术研究: [博士学位论文],武汉:华中科技大学, 2004
[13]石志良.几何约束求解建模与求解方法研究: [博士学位论文],武汉:华中科技大学, 2006
[14]龚雄.陈述式几何约束系统的原理与方法研究: [博士学位论文],武汉:华中科技大学, 2007
[15] Lin V C, Gossard D. Variational geometry modification in computer aided design. In: Proceedings of the 8th Annual ACM SIGGRAPH Conference on Computer Graphics and Interactive Techniques, 1981, 15(3): 171~177
[16] Light R., Gossard D. Modification of geometric models through variational geometry. Computer-Aided Design, 1982, 14(4): 208~214
[17] Serrano D, Gossard D. Combining mathematical models with geometric models in CAE Systems. In: Proceedings of ASME Computer in Engineering Conference and Exhibit,Chicago, July, 1986
[18] Gossard D, Zuffante R P, Sakurai H. Representing dimensions, tolerances and features in MCAE Systems. IEEE Computer Graphics and Applications, 1988, 8(2): 51~59
[19] Serrano D. Constraint Management in Conceptual Design. Ph.D. Thesis. Massachusetts Institute of Technology, 1987
[20] Owen J C. Algebraic solution for geometry from dimensional constraints. In: Proceedings of the ACM Symposium on Solid Modeling Foundation, Austin, TX, 1991, 397~407
[21] Owen J C. Constraints on simple geometry in two and three dimensions. International Journal of Computational Geometry & Applications, 1996, 6, 421~434
[22] Bouma W, Fudos I, Hoffmann C M, et al. Geometric constraint solver. Computer-Aided Design, 1994, 27(6): 487~501
[23] Latham R S, Middleditch A E. Connectively analysis: a tool for processing geometric constraints. Computer-Aided Design, 1996(28): 917~928
[24]董金祥,葛建新,高屹,等.变参绘图系统中约束求解的新思路.计算机辅助设计与图形学学报, 1997, 9(6): 513~519
[25]陈立平,王波兴,彭小波,等.通用几何约束求解引擎关键技术研究.计算机学报, 2000, 23(5): 523~530
[26]陈立平,王波兴,彭小波,等.一种面向欠约束几何系统求解的二部匹配优化处理方法.计算机学报, 2000, 23(5): 523~530
[27]高小山,蒋鲲.几何约束求解研究综述.计算机辅助设计与图形学学报, 2004, 16(4): 385~396
[28] Podgorelec D, Salix B, Domiter V. Dealing with redundancy and inconsistency in constructive geometric constraint solving. Advances in Engineering Software, 2008, 39(9): 770~786
[29] Ait-Aoudia S, Jegou R, Michelucci D. Reduction of constraint systems. In: Proceedings of the Compugraphics, 1993, 83~92
[30] Li Y T, Hu S M, Sun J G. A constructive approach to solving 3D geometric constraint systems using dependence analysis. Computer-Aided Design, 2002, 34(2): 97~108
[31] Michelucci D, Foufou S. Detecting all dependences in systems of geometric constraints using the witness method. F. Botana and T. Recio (Eds.): ADG 2006, LNAI 4869, 2007: 98~112
[32] Haug E J.机械系统的计算机辅助运动学和动力学(第一卷基本方法).刘兴祥译,北京:高等教育出版社, 1996
[33]王波兴,陈立平,周济.传统绘图系统的几何约束驱动关键技术研究与实践.计算机研究与发展, 1998, 35(10): 935~940
[34]王波兴,陈立平,彭晓波,等.几何约束奇异性判定的残量扰动算法.华中科技大学学报, 2001, 29(5): 7~11
[35] Peng X B, Chen L P, Zhou F L, et al. Singularity analysis of geometric constraint system. Journal of Computer Science and Technology, 2002, 17(3): 314~323
[36]石志良,陈立平.快速判定几何约束奇异性的切面扰动法.计算机学报, 2006, 29(10): 1843~1849
[37] Gao X S, Chou S C. Solving geometric constraint systems I. a global propagation approach. Computer-Aided Design, 1998, 30(1):47-54. Solving geometric constraint systems II. a symbolic approach and decision of Rc-constructibility. Computer-Aided Design, 1998, 30(2):115~122
[38] Michelucci D, Foufou S. Geometric constraint solving: The witness configuration method. Computer-Aided Design, 2006, 38(4): 284~299
[39] Michelucci D, Foufou S. Interrogating witness for geometric constraint solving. In: Proceeding of SIAM/ACM Joint Conference on Geometric and Physical Modeling, 2009
[40] Duff I S, Reid J K. An implementation of Tanjan's algorithm for the blocking triangular form of a matrix. ACM Trans Math. Soft, 1978, 4(2): 137~147
[41] Duff I S, Reid J K. Direct Method for Sparse Matrices. Clarendon Press, UK, 1986
[42] Pothen A, Fan CJ. Computing the block triangular form of a sparse matrix. ACM Transactions on Mathematical Software, 1990, 16(4): 303~324
[43] Dulmage A L, Mendelsohn N S. Two algorithms for bipartite graphs. Journal of the Society for Industrial and Applied Mathematics, 1963, 11(1): 183~194
[44] K?nig D. Uber Graphen und ihre anwendung auf determinantentheorie und mengenlehre. Mathematische Annalen, 1916, 77: 453~465
[45] Hopcroft J E, Karp R M. An n5/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal of Computing, 1973, 2(4): 225~231
[46] Tarjan R E. Depth first search and linear graph algorithms. SIAM Journal of Computing, 1972, 1(2): 146~160
[47] Esko N, Eljas S S. On finding the strongly connected components in a directed graph. Information Processing Letters, 1994, 49 (1): 9~14
[48] Edmonds Jack. Paths, trees, and flowers. Canadian Journal of Mathematics. 1965, 17: 449~67
[49] Cunningham W H, Marsh A B. A primal algorithm for optimum matching. Mathematical Programming Studies, 1978, 8: 50~72
[50]彭小波,陈立平,周济.一种基于有向图的几何约束系统分解方法.计算机科学, 2002, 29(4): 41~44
[51]彭小波,陈立平,周济.几何约束有向图的规划分解方法.计算机工程, 2002, 03:56~59
[52] Gao X S, Lin Q, Zhang G F. A C-tree decomposition algorithm for 2D and 3D geometric constraint solving. Computer-Aided Design, 2006, 38(1): 1~13
[53] Joan-Arinyo R, Soto-Riera A, Vila-Marta S, et al. Revisiting decomposition analysis of geometric constraint graphs. Computer-Aided Design, 2004, 36(2): 123~140
[54] Zhang G F, Gao X S. Spatial Geometric Constraint Solving Based on k-connected Graph Decomposition. In: Proceedings of the 21st Annual ACM Symposium on Applied Computing, Dijon, France, 2006
[55] Fudos I, Hoffmann, C M. A graph-constructive approach to solving systems of geometric constraints. ACM Transactions on Graph, 1997, 16(2): 179~216
[56] Hoffmann C M, Joan-Arinyo R. Symbolic constraints in constructive geometric constraint solving. Journal of Symbolic Computation, 1997, 23(2-3): 287~299
[57] Lee J Y, Kim K. A 2-D geometric constraint solver using DOF-based graph reduction. Computer-Aided Design, 1998, 30(11): 883~896
[58] Podgorelec D. A new constructive approach to constraint-based geometric design. Computer-Aided Design, 2002, 34(11):769~785
[59] Gao X S, Jiang K, Zhu C C. Geometric constraint solving with conics and linkages. Computer-Aided Design, 2002, 34(6): 421~433
[60] Gao X S, Zhu C C. Geometric constraint solving with linkages. Journal of Software, 2000, 11(9): 1511~1518
[61] Jiang K, Gao X S. 3D geometric constraint solving with conicoid. Journal of Software, 2002, 13(4): 482~489
[62] Gao X S, Lei D L, Liao Q, et al. Generalized Stewart-Gough platforms and their direct kinematics. IEEE Transaction on Robotics, 2006,21(2): 141~151
[63] Zhang G F, Gao X S. Planar generalized Stewart-Gough platforms and their direct kinematics, ADG 2004, LNAI 3763, 198-211, Springer-Verlag, Berlin, 2006
[64] Gao X S, Hoffmann C M, Yang W. Solving spatial basic geometric constraint configurations with locus intersection. Computer-Aided Design, 2004, 36(2): 111~122
[65]高小山,黄磊东,蒋鲲.求解几何约束问题的几何变换法.中国科学(E辑), 2001, 31(2): 182~192
[66]高小山,张桂芳,杨伟强.几何约束求解与复杂连杆机构的模拟.计算机辅助设计与图形学学报, 2003, 15(5): 517~522
[67] Kramer G. Using degrees of freedom analysis to solve geometric constraint system. In: Proceedings of the First ACM Symposium on Solid Modeling Foundations and CAD/CAM Applications. New York: ACM Press, 1991: 371~378
[68] Kramer G. Solving Geometric Constraints System: A Case Study in Kinematics[M]. Cambridge, MA: MIT Press, 1992
[69] Anantha R, Kramer G, Crawford R H. Assembly modelling by geometric constraint satisfaction. Computer-Aided Design, 1996, 28(9): 707~722
[70] Hoffmann C M, Lomonosov A, Sitharam M. Finding solvable subsets of constraint graphs. In: LNCS, No. 1330; 1997: 163~197
[71] Hoffmann C M, Lomonosov A, Sitharam M. Decomposition plans for geometric constraint system, I. Performance measures for CAD. Journal of Symbolic Computation, 2001,31(4): 367~408
[72] Hoffmann C M, Lomonosov A, Sitharam M. Decomposition plans for geometric constraint system, II. New algorithms. Journal of Symbolic Computation, 2001, 31(4): 409~427
[73] Joan-Arinyo R, Soto-Riera A, Vila-Marta S, et al. Transforming an under-constrained geometric constraint problem into a well-constrained one. In: Proceedings of ACM Symposium on Solid Modeling and Applications, USA, Washington, Seattle, 2003, 33~44
[74] Zhang G F, Gao X S. Well-constrained completion and decomposition for under- constrained geometric constraint problems. International Journal of Computational Geometry and Applications, 2006, 16: 461~478
[75] Lee K Y, Kwon O H, Lee J Y, et al. A hybrid approach to geometric constraint solving with graph analysis and reduction. Advances in Engineering Software, 2003, 34(2): 103~113
[76] Laman G. On graphs and rigidity of plane skeletal structures. Journal of Engineering Mathematics, 1970, 4(4): 331~340
[77] Jermann C, Neveu B, Trombettoni G. A New Structural Rigidity for Geometric Constraint Systems. In: 5th International Workshop on Automated Deduction in Geometry (ADG 2002), Linz, Hagenberg, 87~106
[78] Jermann C, Neveu B, Trombettoni G. Algorithms for Identifying Rigid Subsystems in Geometric Constraint Systems. In: Proceedings of the 18th International joint conference on Artificial Intelligence, Acapulco, Mexico. 2003
[79] Meera Sitharam, Yong Zhou. A tractable, approximate, combinatorial 3D rigidity characterization. In Automated Deduction in Geometry, 2004
[80] Chen J L, Sitharam M, Streinu I. Nucleation-free 3D rigidity. In: Proceedings of the 21st Canadian Conference on Computational Geometry, Univ. British Columbia, Vancouver, Canada, 2009
[81] Haller K, Lee A, Sitharam M, et al. Body-and-cad geometric constraint system. In: Proceedings of 24th Annual ACM Symposium on Applied Computing, Technical Track on Geometric Constraints and Reasoning, Honolulu, HI, 2009
[82] Lee A. Geometric constraint systems with applications in CAD and Biology. Ph,D. Thesis, University of Massachusetts Amherst, 2008
[83] Lee A, Streinu I. Angular rigidity in 3D: Combinatorial characterization and algorithms. In: Proceedings of the 21st Canadian Conference on Computational Geometry, Univ. British Columbia, Vancouver, Canada, 2009
[84] Schulze B. Combinatorial and geometric rigidity with symmetry constraints. Ph.D. Thesis, York University, 2009
[85] Whiteley W. The Union of matroids and rigidity of frameworks. SIAM Journal of Discrete Math. 1988, 1(2): 237~255
[86] Whiteley W. Predicting the flexibility and rigidity of proteins: geometry, combinatorics,conjectures, and algorithm. In: Proceedings of the 21st Canadian Conference on Computational Geometry, Univ. British Columbia, Vancouver, Canada, 2009
[87] Connelly R, Whiteley W. Global rigidity: the effect of coning. Discrete & Computational Geometry, 2010, 43(4): 717~735
[88] Owen J C, Power S C. Infinite bar-joint frameworks, crystals and operator theory. In http:// www.maths.lancs.ac.uk/~power/
[89] Owen J C, Power S C. Frameworks, symmetry and rigidity. In http://www.maths.lancs. ac.uk/~power/
[90]孟祥旭,汪嘉业,刘慎权.基于有向超图的参数化表示模型及其实现.计算机学报, 1997, 20(11): 982~988
[91]蒋丹东,何援军,杨东等.基于点簇归约的几何约束求解器研究.高技术通讯, 2002, 12(6): 49~53
[92]李彦涛,胡事民,孙家广.一个几何约束系统分解的新算法.计算机辅助设计与图形学学报, 2000, 12(12): 926~930
[93]李彦涛,陈玉键,孙家广.混合式几何约束满足的研究.计算机学报, 2001, 24(4): 347~353
[94] Sutherland I E. Sketchpad: a man machine graphical communication system. Ph.D. Thesis, Massachusetts Institute of Technology, 1963
[95] Hillard R C, Braid I C. Analysis of dimensions and tolerance in Computer-Aided mechanical design. Computer-Aided Design, 1978, 10(3): 161~166
[96] Borning A. The programming of language aspects of Thinglab: a constraint oriented simulation laboratory. ACM Transaction on Programming Language and System, 1981, 3(4): 353~387
[97]蒋正新,施国梁.矩阵理论及其应用.北京航空航天出版社, 1988.
[98] Press W H, Teukolsky S A, Vetterling W T, et al. Numerical Recipes, The Art of Scientific Computing, Third Edition [M]. Cambridge University Press, 2007
[99] Ge J X, Chou S C, Gao X S. Geometric constraint satisfaction using optimization methods. Computer-Aided Design, 1999, 31(14): 867~879
[100]欧阳应秀,唐敏,董金祥,等.几何约束求解的BFGS-混沌混合算法.浙江大学学报(工学版), 2005, 39(9): 1334~1338
[101]王则柯,高安堂.同伦方法引论.重庆:重庆出版社, 1990
[102]廖世俊.同伦分析方法:一种新的求解非线性问题的近似解析方法.应用数学和力学, 1998, 19(10): 885~890
[103] Morgan A P. Solving Polynomial Systems using Continuation for Scientific and Engineering Problems. Englewood Cliffs, N.J.: Prentice-Hall, 1987
[104] Wampler C W, Morgan A P, Sommese A F. Numerical continuation methods for solving polynomial systems arising in kinematics, ASME Journal of Mechanical Design, 1990, 112(1): 59~68
[105] Lamure H, Michelucci D. Solving geometric constraints by homotopy. IEEE Transactions on Visualization and Computer Graphics, 1996, 2(1): 28~34
[106] Durand C. Symbolic and Numerical Techniques for Constraint Solving. Ph.D. Thesis, Purdue University, 1998
[107]彭小波,陈立平,周济.面向欠约束几何系统的一种同伦求解方法.中国图象图形学报, 2002. 7(9): 956~961
[108] Peng X B, Lee K W, Chen L P. A geometric constraint solver for 3-D assembly modeling. International Journal of Advanced Manufacturing Technology, 2006, 28(5/6): 561~570
[109]吴文俊.几何定理机器证明的基本原理.北京:科学出版社, 1984
[110] Wu W T. Basic principle of mechanical theorem proving in elementary geometries. Journal of Automated Reasoning, 1987, 2(3): 221~252
[111]刘木兰. Gr?bner基理论及其应用.北京:科学出版社, 2000
[112] Buchberger B. Algebraic methods for non-linear computational geometry. In Proceedings of the Fourth Annual ACM Symposium on Computational Geometry, Urbana-Champaign, IL. 1988
[113] Kondo K. PIGMOD: parametric and interactive geometric modeler for mechanical design. Computer -Aided Design, 1990, 22(10): 633~644
[114] Kondo K. Algebraic method for manipulation of dimensional relationships in geometric models. Computer-Aided Design, 1992, 24(3): 141~147
[115] Buchanan S A, Pennington D A. Constraint definition system: a computer-algebra based approach to solving geometric-constraint problems. Computer Aided Design, 1993, 25(12): 740~750
[116] Tomas F, Torras C. A group-theoretic approach to the computation of symbolic part relations. IEEE Transactions on Robotics and Automation, 1988, 4(6): 622~634
[117] Ruiz O E, Ferreira P M. Algebraic geometry and group theory in geometric constraint satisfaction. In: Proceedings of the International Symposium on Symbolic and Algebraic Computation. Oxford: ACM Press, 1994, 224~233
[118] Deepark K. Automatic geometry reasoning: Dixon resultant, Gr?bner basis, and characteristic set. Technical report, Institute for programming and logics department of computer science, State University of New York, 1995
[119]杨路,张景中,候晓荣.非线性代数方程组与定理机器证明.上海:上海科技教育出版社, 1996
[120] Kim D, Kim D S, Sugihara K. Apollonius tenth problem via radius adjustment and M?bius transformations. Computer-Aided Design, 2006, 38(1): 14~21
[121]乔雨,王波兴,向文.基于自由度分析的三维几何约束推理求解.计算机辅助设计与图形学学报, 2002, 14(6):557~561
[122]姜勇,王波兴,陈立平.三维几何约束求解的自由度归约算法.计算机辅助设计与图形学学报, 2003, 15(9): 1128~1133
[123] Kim J, Kim K, Chio K, et al. Solving 3D geometric constraints for assembly modeling. International Journal of Advanced Manufacture Technology, 2000, 16(11): 843~849
[124] Kumar Ashok V, Yu Lichao. Sequential constraint imposition for dimension-driven solid models. Computer-Aided Design, 2001, 33(6): 475~486
[125]王小刚,陈立平,赵建军,等.三维几何约束的球面几何求解.计算机辅助设计与图形学学报, 2005, 17(11): 2433~2440
[126]石志良,陈立平,王小刚.三维装配约束推理的球面几何和球面机构法.计算机辅助设计与图形学学报, 2006, 18(7): 942~947
[127]石志良,陈立平.装配位置约束建模及求解.计算机辅助设计与图形学学报, 2007, 19(5): 553~557
[128]洪嘉振.计算多体系统动力学.北京:高等教育出版社, 1999
[129] David A. Cox, John B. Little, Don O’Shea. Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra (Third Edition). Springer, 2007
[130] Li Y T, Hu S M, Sun J G. On the numerical redundancies of geometric constraint systems. In: Proceedings of the IEEE 9th Pacific Conference on Computer Graphics and Applications, Tokyo, Japan, 2001, 118~123
[131]石志良,陈立平.几何约束的简化迭代算法研究.计算机辅助设计与图形学学报, 2006, 18(6): 787~792
[132]石志良,陈立平.几何约束等价性及等价迭代研究.机械科学与技术, 2007, 9(26): 1207~1211
[133]夏鸿建,王波兴,陈立平.三维几何约束求解的变分方法[J].计算机辅助设计与图形学学报, 2006, 18(12): 1878~1883
[134]刘勇,雍俊海,王斌.一类闭环约束的装配约束问题求解.计算机辅助设计与图形学学报, 2008, 20(9): 1171~1175
[135]肖位枢.图论及其算法.北京:航空工业出版社, 1993
[136] Edoardo Amaldi. An improved algorithm for finding minimum cycle bases in undirected graphs, http://www.lamsade.dauphine.fr/~poc/Edmonds/Exposes/Amaldi.pdf
[137] Horton J. A polynomial-time algorithm to find the shortest cycle basis of a graph. SIAM J Comput. 16, 359~366
[138] de Pina J C. Application of shortest-path methods. Ph.D. Thesis, Universiteit van Amsterdam
[139] Konkar R, Cutkosky M. Incremental kinematics analysis of mechanisms. ASME Journal of Mechanical Design, 1995, 117(4): 589~596
[140] Adams J D, Whitney D E. Application of screw theory to constraint analysis of mechanical assemblies joined by features. ASME Journal of Mechanical Design, 2001, 123(1): 26~32
[141] Mullins S H, Anderson D C. A positioning algorithm for mechanical assemblies withclosed kinematic chains in three dimensions. In: Proceedings of the Second ACM Symposium on Solid Modeling and Applications. New York: ACM Press, 1993: 271~280
[142]吴永明.三维几何约束闭环的动态识别与满足.计算机辅助设计与图形学学报, 2000,12(8): 624~629
[143] Kim J, Kim K, Lee J Y, et al. Solving 3D geometric constraints for closed-loop assemblies. International Journal of Advanced Manufacturing Technology, 2004, 23(9-10): 755~761
[144]李明浩,黄正东.基于旋量理论的装配模型中零件瞬时运动分析.机械科学与技术, 2008, 27(10): 1169~1176
[145] Bae D C, Haug E J. A recursive formulation for constrained mechanical system dynamics, Part I-open loop systems, Mechanics Based Design of Structures and Machines, 1987, 15(3): 359~382
[146] Bae D C, Haug E J. A recursive formulation for constrained mechanical system dynamics, Part II-closed loop systems, Mechanics Based Design of Structures and Machines, 1987, 15(4): 481~506
[147] Zou H L, Ko A M. Computer-aided design using the method of cut-joint kinematic constraint. Computer-Aided Design, 1996, 28(10): 795~806
[148]曹惟庆.连杆机构的分析与综合.北京:科学出版社, 2002
[149]赵景山,冯之敬,褚福磊.机器人机构自由度分析理论.北京:科学出版社, 2009
[150]黄真,赵永生,赵铁石.高等空间机构学.北京:高等教育出版社, 2006
[151]熊有伦,尹周平,熊蔡华,等.机器人操作.武汉:湖北科学技术出版社, 2002
[152] Kavitha T, Liebchen Ch, Mehlhorn K, et al. Cycle bases in graphs characterization, algorithms, complexity, and applications. Computer Science Review, 2009,3(4):199~243
[153] Lamure H, Michelucci D. Qualitative study of geometric constraints. In Geometric Constraint Solving and Applications. Berlin: Springer; 1998: 234~258
[154] Foufou S, Michelucci D, Jurzak J. Numerical decomposition of geometric constraints. In: Proceedings of the Ninth ACM Symposium on Solid and Physical Modeling. New York: ACM Press, 2005: 143~151
[2] http://en.wikipedia.org/wiki/D-Cubed
[3] http://www.plm.automation.siemens.com/en_us/products/open/d-cubed/customers/index.shtml
[4] Oung J J, Sitharam M, Moro B. Frontier: fully enabling geometric constraints for feature based modeling and assembly. In Proceedings of the Sixth ACM Symposium on Solid Modeling and Applications, 2001
[5] Sitharam M. Frontier, an opensource 3d geometric constraint solver: architecture (Part I). In: http://www.cise.ufl.edu/~sitharam/partone.pdf, 2005
[6]向文.参数化特征造型系统的研究: [博士学位论文],武汉:华中理工大学, 1993
[7]陈立平.几何约束系统最大归约理论与应用研究: [博士学位论文],武汉:华中理工大学, 1995
[8]罗浩.基于约束的工程图形参数化设计系统的理论与实践: [博士学位论文],武汉:华中理工大学, 1996
[9]康友树.变量装配设计原理及方法研究: [博士学位论文],武汉:华中理工大学, 1996
[10]王波兴.几何约束系统若干关键技术的研究与实践: [博士学位论文],武汉:华中科技大学, 2001
[11]彭小波.二、三维几何约束统一求解器原理与方法研究: [博士学位论文],武汉:华中科技大学, 2002
[12]王彦伟.实体造型中的变量化技术研究: [博士学位论文],武汉:华中科技大学, 2004
[13]石志良.几何约束求解建模与求解方法研究: [博士学位论文],武汉:华中科技大学, 2006
[14]龚雄.陈述式几何约束系统的原理与方法研究: [博士学位论文],武汉:华中科技大学, 2007
[15] Lin V C, Gossard D. Variational geometry modification in computer aided design. In: Proceedings of the 8th Annual ACM SIGGRAPH Conference on Computer Graphics and Interactive Techniques, 1981, 15(3): 171~177
[16] Light R., Gossard D. Modification of geometric models through variational geometry. Computer-Aided Design, 1982, 14(4): 208~214
[17] Serrano D, Gossard D. Combining mathematical models with geometric models in CAE Systems. In: Proceedings of ASME Computer in Engineering Conference and Exhibit,Chicago, July, 1986
[18] Gossard D, Zuffante R P, Sakurai H. Representing dimensions, tolerances and features in MCAE Systems. IEEE Computer Graphics and Applications, 1988, 8(2): 51~59
[19] Serrano D. Constraint Management in Conceptual Design. Ph.D. Thesis. Massachusetts Institute of Technology, 1987
[20] Owen J C. Algebraic solution for geometry from dimensional constraints. In: Proceedings of the ACM Symposium on Solid Modeling Foundation, Austin, TX, 1991, 397~407
[21] Owen J C. Constraints on simple geometry in two and three dimensions. International Journal of Computational Geometry & Applications, 1996, 6, 421~434
[22] Bouma W, Fudos I, Hoffmann C M, et al. Geometric constraint solver. Computer-Aided Design, 1994, 27(6): 487~501
[23] Latham R S, Middleditch A E. Connectively analysis: a tool for processing geometric constraints. Computer-Aided Design, 1996(28): 917~928
[24]董金祥,葛建新,高屹,等.变参绘图系统中约束求解的新思路.计算机辅助设计与图形学学报, 1997, 9(6): 513~519
[25]陈立平,王波兴,彭小波,等.通用几何约束求解引擎关键技术研究.计算机学报, 2000, 23(5): 523~530
[26]陈立平,王波兴,彭小波,等.一种面向欠约束几何系统求解的二部匹配优化处理方法.计算机学报, 2000, 23(5): 523~530
[27]高小山,蒋鲲.几何约束求解研究综述.计算机辅助设计与图形学学报, 2004, 16(4): 385~396
[28] Podgorelec D, Salix B, Domiter V. Dealing with redundancy and inconsistency in constructive geometric constraint solving. Advances in Engineering Software, 2008, 39(9): 770~786
[29] Ait-Aoudia S, Jegou R, Michelucci D. Reduction of constraint systems. In: Proceedings of the Compugraphics, 1993, 83~92
[30] Li Y T, Hu S M, Sun J G. A constructive approach to solving 3D geometric constraint systems using dependence analysis. Computer-Aided Design, 2002, 34(2): 97~108
[31] Michelucci D, Foufou S. Detecting all dependences in systems of geometric constraints using the witness method. F. Botana and T. Recio (Eds.): ADG 2006, LNAI 4869, 2007: 98~112
[32] Haug E J.机械系统的计算机辅助运动学和动力学(第一卷基本方法).刘兴祥译,北京:高等教育出版社, 1996
[33]王波兴,陈立平,周济.传统绘图系统的几何约束驱动关键技术研究与实践.计算机研究与发展, 1998, 35(10): 935~940
[34]王波兴,陈立平,彭晓波,等.几何约束奇异性判定的残量扰动算法.华中科技大学学报, 2001, 29(5): 7~11
[35] Peng X B, Chen L P, Zhou F L, et al. Singularity analysis of geometric constraint system. Journal of Computer Science and Technology, 2002, 17(3): 314~323
[36]石志良,陈立平.快速判定几何约束奇异性的切面扰动法.计算机学报, 2006, 29(10): 1843~1849
[37] Gao X S, Chou S C. Solving geometric constraint systems I. a global propagation approach. Computer-Aided Design, 1998, 30(1):47-54. Solving geometric constraint systems II. a symbolic approach and decision of Rc-constructibility. Computer-Aided Design, 1998, 30(2):115~122
[38] Michelucci D, Foufou S. Geometric constraint solving: The witness configuration method. Computer-Aided Design, 2006, 38(4): 284~299
[39] Michelucci D, Foufou S. Interrogating witness for geometric constraint solving. In: Proceeding of SIAM/ACM Joint Conference on Geometric and Physical Modeling, 2009
[40] Duff I S, Reid J K. An implementation of Tanjan's algorithm for the blocking triangular form of a matrix. ACM Trans Math. Soft, 1978, 4(2): 137~147
[41] Duff I S, Reid J K. Direct Method for Sparse Matrices. Clarendon Press, UK, 1986
[42] Pothen A, Fan CJ. Computing the block triangular form of a sparse matrix. ACM Transactions on Mathematical Software, 1990, 16(4): 303~324
[43] Dulmage A L, Mendelsohn N S. Two algorithms for bipartite graphs. Journal of the Society for Industrial and Applied Mathematics, 1963, 11(1): 183~194
[44] K?nig D. Uber Graphen und ihre anwendung auf determinantentheorie und mengenlehre. Mathematische Annalen, 1916, 77: 453~465
[45] Hopcroft J E, Karp R M. An n5/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal of Computing, 1973, 2(4): 225~231
[46] Tarjan R E. Depth first search and linear graph algorithms. SIAM Journal of Computing, 1972, 1(2): 146~160
[47] Esko N, Eljas S S. On finding the strongly connected components in a directed graph. Information Processing Letters, 1994, 49 (1): 9~14
[48] Edmonds Jack. Paths, trees, and flowers. Canadian Journal of Mathematics. 1965, 17: 449~67
[49] Cunningham W H, Marsh A B. A primal algorithm for optimum matching. Mathematical Programming Studies, 1978, 8: 50~72
[50]彭小波,陈立平,周济.一种基于有向图的几何约束系统分解方法.计算机科学, 2002, 29(4): 41~44
[51]彭小波,陈立平,周济.几何约束有向图的规划分解方法.计算机工程, 2002, 03:56~59
[52] Gao X S, Lin Q, Zhang G F. A C-tree decomposition algorithm for 2D and 3D geometric constraint solving. Computer-Aided Design, 2006, 38(1): 1~13
[53] Joan-Arinyo R, Soto-Riera A, Vila-Marta S, et al. Revisiting decomposition analysis of geometric constraint graphs. Computer-Aided Design, 2004, 36(2): 123~140
[54] Zhang G F, Gao X S. Spatial Geometric Constraint Solving Based on k-connected Graph Decomposition. In: Proceedings of the 21st Annual ACM Symposium on Applied Computing, Dijon, France, 2006
[55] Fudos I, Hoffmann, C M. A graph-constructive approach to solving systems of geometric constraints. ACM Transactions on Graph, 1997, 16(2): 179~216
[56] Hoffmann C M, Joan-Arinyo R. Symbolic constraints in constructive geometric constraint solving. Journal of Symbolic Computation, 1997, 23(2-3): 287~299
[57] Lee J Y, Kim K. A 2-D geometric constraint solver using DOF-based graph reduction. Computer-Aided Design, 1998, 30(11): 883~896
[58] Podgorelec D. A new constructive approach to constraint-based geometric design. Computer-Aided Design, 2002, 34(11):769~785
[59] Gao X S, Jiang K, Zhu C C. Geometric constraint solving with conics and linkages. Computer-Aided Design, 2002, 34(6): 421~433
[60] Gao X S, Zhu C C. Geometric constraint solving with linkages. Journal of Software, 2000, 11(9): 1511~1518
[61] Jiang K, Gao X S. 3D geometric constraint solving with conicoid. Journal of Software, 2002, 13(4): 482~489
[62] Gao X S, Lei D L, Liao Q, et al. Generalized Stewart-Gough platforms and their direct kinematics. IEEE Transaction on Robotics, 2006,21(2): 141~151
[63] Zhang G F, Gao X S. Planar generalized Stewart-Gough platforms and their direct kinematics, ADG 2004, LNAI 3763, 198-211, Springer-Verlag, Berlin, 2006
[64] Gao X S, Hoffmann C M, Yang W. Solving spatial basic geometric constraint configurations with locus intersection. Computer-Aided Design, 2004, 36(2): 111~122
[65]高小山,黄磊东,蒋鲲.求解几何约束问题的几何变换法.中国科学(E辑), 2001, 31(2): 182~192
[66]高小山,张桂芳,杨伟强.几何约束求解与复杂连杆机构的模拟.计算机辅助设计与图形学学报, 2003, 15(5): 517~522
[67] Kramer G. Using degrees of freedom analysis to solve geometric constraint system. In: Proceedings of the First ACM Symposium on Solid Modeling Foundations and CAD/CAM Applications. New York: ACM Press, 1991: 371~378
[68] Kramer G. Solving Geometric Constraints System: A Case Study in Kinematics[M]. Cambridge, MA: MIT Press, 1992
[69] Anantha R, Kramer G, Crawford R H. Assembly modelling by geometric constraint satisfaction. Computer-Aided Design, 1996, 28(9): 707~722
[70] Hoffmann C M, Lomonosov A, Sitharam M. Finding solvable subsets of constraint graphs. In: LNCS, No. 1330; 1997: 163~197
[71] Hoffmann C M, Lomonosov A, Sitharam M. Decomposition plans for geometric constraint system, I. Performance measures for CAD. Journal of Symbolic Computation, 2001,31(4): 367~408
[72] Hoffmann C M, Lomonosov A, Sitharam M. Decomposition plans for geometric constraint system, II. New algorithms. Journal of Symbolic Computation, 2001, 31(4): 409~427
[73] Joan-Arinyo R, Soto-Riera A, Vila-Marta S, et al. Transforming an under-constrained geometric constraint problem into a well-constrained one. In: Proceedings of ACM Symposium on Solid Modeling and Applications, USA, Washington, Seattle, 2003, 33~44
[74] Zhang G F, Gao X S. Well-constrained completion and decomposition for under- constrained geometric constraint problems. International Journal of Computational Geometry and Applications, 2006, 16: 461~478
[75] Lee K Y, Kwon O H, Lee J Y, et al. A hybrid approach to geometric constraint solving with graph analysis and reduction. Advances in Engineering Software, 2003, 34(2): 103~113
[76] Laman G. On graphs and rigidity of plane skeletal structures. Journal of Engineering Mathematics, 1970, 4(4): 331~340
[77] Jermann C, Neveu B, Trombettoni G. A New Structural Rigidity for Geometric Constraint Systems. In: 5th International Workshop on Automated Deduction in Geometry (ADG 2002), Linz, Hagenberg, 87~106
[78] Jermann C, Neveu B, Trombettoni G. Algorithms for Identifying Rigid Subsystems in Geometric Constraint Systems. In: Proceedings of the 18th International joint conference on Artificial Intelligence, Acapulco, Mexico. 2003
[79] Meera Sitharam, Yong Zhou. A tractable, approximate, combinatorial 3D rigidity characterization. In Automated Deduction in Geometry, 2004
[80] Chen J L, Sitharam M, Streinu I. Nucleation-free 3D rigidity. In: Proceedings of the 21st Canadian Conference on Computational Geometry, Univ. British Columbia, Vancouver, Canada, 2009
[81] Haller K, Lee A, Sitharam M, et al. Body-and-cad geometric constraint system. In: Proceedings of 24th Annual ACM Symposium on Applied Computing, Technical Track on Geometric Constraints and Reasoning, Honolulu, HI, 2009
[82] Lee A. Geometric constraint systems with applications in CAD and Biology. Ph,D. Thesis, University of Massachusetts Amherst, 2008
[83] Lee A, Streinu I. Angular rigidity in 3D: Combinatorial characterization and algorithms. In: Proceedings of the 21st Canadian Conference on Computational Geometry, Univ. British Columbia, Vancouver, Canada, 2009
[84] Schulze B. Combinatorial and geometric rigidity with symmetry constraints. Ph.D. Thesis, York University, 2009
[85] Whiteley W. The Union of matroids and rigidity of frameworks. SIAM Journal of Discrete Math. 1988, 1(2): 237~255
[86] Whiteley W. Predicting the flexibility and rigidity of proteins: geometry, combinatorics,conjectures, and algorithm. In: Proceedings of the 21st Canadian Conference on Computational Geometry, Univ. British Columbia, Vancouver, Canada, 2009
[87] Connelly R, Whiteley W. Global rigidity: the effect of coning. Discrete & Computational Geometry, 2010, 43(4): 717~735
[88] Owen J C, Power S C. Infinite bar-joint frameworks, crystals and operator theory. In http:// www.maths.lancs.ac.uk/~power/
[89] Owen J C, Power S C. Frameworks, symmetry and rigidity. In http://www.maths.lancs. ac.uk/~power/
[90]孟祥旭,汪嘉业,刘慎权.基于有向超图的参数化表示模型及其实现.计算机学报, 1997, 20(11): 982~988
[91]蒋丹东,何援军,杨东等.基于点簇归约的几何约束求解器研究.高技术通讯, 2002, 12(6): 49~53
[92]李彦涛,胡事民,孙家广.一个几何约束系统分解的新算法.计算机辅助设计与图形学学报, 2000, 12(12): 926~930
[93]李彦涛,陈玉键,孙家广.混合式几何约束满足的研究.计算机学报, 2001, 24(4): 347~353
[94] Sutherland I E. Sketchpad: a man machine graphical communication system. Ph.D. Thesis, Massachusetts Institute of Technology, 1963
[95] Hillard R C, Braid I C. Analysis of dimensions and tolerance in Computer-Aided mechanical design. Computer-Aided Design, 1978, 10(3): 161~166
[96] Borning A. The programming of language aspects of Thinglab: a constraint oriented simulation laboratory. ACM Transaction on Programming Language and System, 1981, 3(4): 353~387
[97]蒋正新,施国梁.矩阵理论及其应用.北京航空航天出版社, 1988.
[98] Press W H, Teukolsky S A, Vetterling W T, et al. Numerical Recipes, The Art of Scientific Computing, Third Edition [M]. Cambridge University Press, 2007
[99] Ge J X, Chou S C, Gao X S. Geometric constraint satisfaction using optimization methods. Computer-Aided Design, 1999, 31(14): 867~879
[100]欧阳应秀,唐敏,董金祥,等.几何约束求解的BFGS-混沌混合算法.浙江大学学报(工学版), 2005, 39(9): 1334~1338
[101]王则柯,高安堂.同伦方法引论.重庆:重庆出版社, 1990
[102]廖世俊.同伦分析方法:一种新的求解非线性问题的近似解析方法.应用数学和力学, 1998, 19(10): 885~890
[103] Morgan A P. Solving Polynomial Systems using Continuation for Scientific and Engineering Problems. Englewood Cliffs, N.J.: Prentice-Hall, 1987
[104] Wampler C W, Morgan A P, Sommese A F. Numerical continuation methods for solving polynomial systems arising in kinematics, ASME Journal of Mechanical Design, 1990, 112(1): 59~68
[105] Lamure H, Michelucci D. Solving geometric constraints by homotopy. IEEE Transactions on Visualization and Computer Graphics, 1996, 2(1): 28~34
[106] Durand C. Symbolic and Numerical Techniques for Constraint Solving. Ph.D. Thesis, Purdue University, 1998
[107]彭小波,陈立平,周济.面向欠约束几何系统的一种同伦求解方法.中国图象图形学报, 2002. 7(9): 956~961
[108] Peng X B, Lee K W, Chen L P. A geometric constraint solver for 3-D assembly modeling. International Journal of Advanced Manufacturing Technology, 2006, 28(5/6): 561~570
[109]吴文俊.几何定理机器证明的基本原理.北京:科学出版社, 1984
[110] Wu W T. Basic principle of mechanical theorem proving in elementary geometries. Journal of Automated Reasoning, 1987, 2(3): 221~252
[111]刘木兰. Gr?bner基理论及其应用.北京:科学出版社, 2000
[112] Buchberger B. Algebraic methods for non-linear computational geometry. In Proceedings of the Fourth Annual ACM Symposium on Computational Geometry, Urbana-Champaign, IL. 1988
[113] Kondo K. PIGMOD: parametric and interactive geometric modeler for mechanical design. Computer -Aided Design, 1990, 22(10): 633~644
[114] Kondo K. Algebraic method for manipulation of dimensional relationships in geometric models. Computer-Aided Design, 1992, 24(3): 141~147
[115] Buchanan S A, Pennington D A. Constraint definition system: a computer-algebra based approach to solving geometric-constraint problems. Computer Aided Design, 1993, 25(12): 740~750
[116] Tomas F, Torras C. A group-theoretic approach to the computation of symbolic part relations. IEEE Transactions on Robotics and Automation, 1988, 4(6): 622~634
[117] Ruiz O E, Ferreira P M. Algebraic geometry and group theory in geometric constraint satisfaction. In: Proceedings of the International Symposium on Symbolic and Algebraic Computation. Oxford: ACM Press, 1994, 224~233
[118] Deepark K. Automatic geometry reasoning: Dixon resultant, Gr?bner basis, and characteristic set. Technical report, Institute for programming and logics department of computer science, State University of New York, 1995
[119]杨路,张景中,候晓荣.非线性代数方程组与定理机器证明.上海:上海科技教育出版社, 1996
[120] Kim D, Kim D S, Sugihara K. Apollonius tenth problem via radius adjustment and M?bius transformations. Computer-Aided Design, 2006, 38(1): 14~21
[121]乔雨,王波兴,向文.基于自由度分析的三维几何约束推理求解.计算机辅助设计与图形学学报, 2002, 14(6):557~561
[122]姜勇,王波兴,陈立平.三维几何约束求解的自由度归约算法.计算机辅助设计与图形学学报, 2003, 15(9): 1128~1133
[123] Kim J, Kim K, Chio K, et al. Solving 3D geometric constraints for assembly modeling. International Journal of Advanced Manufacture Technology, 2000, 16(11): 843~849
[124] Kumar Ashok V, Yu Lichao. Sequential constraint imposition for dimension-driven solid models. Computer-Aided Design, 2001, 33(6): 475~486
[125]王小刚,陈立平,赵建军,等.三维几何约束的球面几何求解.计算机辅助设计与图形学学报, 2005, 17(11): 2433~2440
[126]石志良,陈立平,王小刚.三维装配约束推理的球面几何和球面机构法.计算机辅助设计与图形学学报, 2006, 18(7): 942~947
[127]石志良,陈立平.装配位置约束建模及求解.计算机辅助设计与图形学学报, 2007, 19(5): 553~557
[128]洪嘉振.计算多体系统动力学.北京:高等教育出版社, 1999
[129] David A. Cox, John B. Little, Don O’Shea. Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra (Third Edition). Springer, 2007
[130] Li Y T, Hu S M, Sun J G. On the numerical redundancies of geometric constraint systems. In: Proceedings of the IEEE 9th Pacific Conference on Computer Graphics and Applications, Tokyo, Japan, 2001, 118~123
[131]石志良,陈立平.几何约束的简化迭代算法研究.计算机辅助设计与图形学学报, 2006, 18(6): 787~792
[132]石志良,陈立平.几何约束等价性及等价迭代研究.机械科学与技术, 2007, 9(26): 1207~1211
[133]夏鸿建,王波兴,陈立平.三维几何约束求解的变分方法[J].计算机辅助设计与图形学学报, 2006, 18(12): 1878~1883
[134]刘勇,雍俊海,王斌.一类闭环约束的装配约束问题求解.计算机辅助设计与图形学学报, 2008, 20(9): 1171~1175
[135]肖位枢.图论及其算法.北京:航空工业出版社, 1993
[136] Edoardo Amaldi. An improved algorithm for finding minimum cycle bases in undirected graphs, http://www.lamsade.dauphine.fr/~poc/Edmonds/Exposes/Amaldi.pdf
[137] Horton J. A polynomial-time algorithm to find the shortest cycle basis of a graph. SIAM J Comput. 16, 359~366
[138] de Pina J C. Application of shortest-path methods. Ph.D. Thesis, Universiteit van Amsterdam
[139] Konkar R, Cutkosky M. Incremental kinematics analysis of mechanisms. ASME Journal of Mechanical Design, 1995, 117(4): 589~596
[140] Adams J D, Whitney D E. Application of screw theory to constraint analysis of mechanical assemblies joined by features. ASME Journal of Mechanical Design, 2001, 123(1): 26~32
[141] Mullins S H, Anderson D C. A positioning algorithm for mechanical assemblies withclosed kinematic chains in three dimensions. In: Proceedings of the Second ACM Symposium on Solid Modeling and Applications. New York: ACM Press, 1993: 271~280
[142]吴永明.三维几何约束闭环的动态识别与满足.计算机辅助设计与图形学学报, 2000,12(8): 624~629
[143] Kim J, Kim K, Lee J Y, et al. Solving 3D geometric constraints for closed-loop assemblies. International Journal of Advanced Manufacturing Technology, 2004, 23(9-10): 755~761
[144]李明浩,黄正东.基于旋量理论的装配模型中零件瞬时运动分析.机械科学与技术, 2008, 27(10): 1169~1176
[145] Bae D C, Haug E J. A recursive formulation for constrained mechanical system dynamics, Part I-open loop systems, Mechanics Based Design of Structures and Machines, 1987, 15(3): 359~382
[146] Bae D C, Haug E J. A recursive formulation for constrained mechanical system dynamics, Part II-closed loop systems, Mechanics Based Design of Structures and Machines, 1987, 15(4): 481~506
[147] Zou H L, Ko A M. Computer-aided design using the method of cut-joint kinematic constraint. Computer-Aided Design, 1996, 28(10): 795~806
[148]曹惟庆.连杆机构的分析与综合.北京:科学出版社, 2002
[149]赵景山,冯之敬,褚福磊.机器人机构自由度分析理论.北京:科学出版社, 2009
[150]黄真,赵永生,赵铁石.高等空间机构学.北京:高等教育出版社, 2006
[151]熊有伦,尹周平,熊蔡华,等.机器人操作.武汉:湖北科学技术出版社, 2002
[152] Kavitha T, Liebchen Ch, Mehlhorn K, et al. Cycle bases in graphs characterization, algorithms, complexity, and applications. Computer Science Review, 2009,3(4):199~243
[153] Lamure H, Michelucci D. Qualitative study of geometric constraints. In Geometric Constraint Solving and Applications. Berlin: Springer; 1998: 234~258
[154] Foufou S, Michelucci D, Jurzak J. Numerical decomposition of geometric constraints. In: Proceedings of the Ninth ACM Symposium on Solid and Physical Modeling. New York: ACM Press, 2005: 143~151