一种基于图分解的几何约束求解方法

为了提高几何约束求解的效率和鲁棒性 ,对基于图的构造方法进行了改进 ,即加入虚约束进行扩展和过约束问题的一致性判定 ,提出了一种基于图分解的方法 ,用此方法可以处理包括完全约束、过约束和欠约束等多种情况的约束求解问题 ,另外 ,在该方法中还通过引入分解树将约束求解的范围由整体下降到局部 ,使大部分求解过程能够采用几何求解实现 ,提高了求解和后续修改的效率 ,通过实验数据测试证明 ,该方法对于大型约束求解问题可以达到实时处理的效果 ,具有较强的实用性

A Constraint Solving Approach Based on Graph Decomposition

To improve the efficiency and robustness of constraint solving algorithm, the paper presents a graph-constructive approach. In constructive phase, the algorithm can classify well-constrained, over constrained and under constrained configurations. By adaptively adding virtual constraints, the algorithm can handle all the above configurations, and can overcome the ill-condition constraint which occurs frequently in practice. Decomposition trees are used to reduce the scale of constraint solving problem, decompose it from global scope into many local sub-problems. By avoid solving large-scale equations, the algorithm can separately calculate the sub-problems geometrically with great improvement in efficiency and robustness. It also improves the efficiency for successive modification on constraints or geometric elements. Comparing to conventional algebra algorithms, symbolic algorithms, and rule-based algorithms, the algorithm is more practical and can be used in real-time constraint solving environment. It has been implemented in VC on Windows/NT platform, and been used as geometric constraint solving kernel of a feature based parametric modeling system GS-CAD, which is a commercial CAD system developed by Zhejiang University.