三维几何约束系统的逼近最优分解理论与并行求解方法

The objective of this research is to develop mathematical foundations and algorithmic infastructures for achieving geometrically close-to-optimal decomposition and parallel solution of 3D geometric constraint systems that can be under-constrained, well-constrained or over-constrained. the research contents mainly include: 1)The recursive decomposition and parallel solution of 3D geometric constraint systems with closed-loops which can not be decomposed by all existing methods. 2)The closed-to-optimal decomposition method of 3D geometric.Constraint system based on equivalent transformation and its parallel processing.3)The online incremental solving mechanism and dynamic dragging solving strategy of 3D geometric constraint systems for real-time interative design.The characteristic of this research is to make good use of geometric domain knownledge to optimize the decomposition and solution of 3D geometric constraint systems, so that most 3D geometric constraint systems which can not be decomposed and have to be solved by numerical method, will be solved by analytical method in parallel.Successful completion of this project will provide theoretical foundations and key algorithms for developing a high-performance 3D geometric constraint solver. The research results would be also beneficial for the development of 3D variational direct modeling technology, integration of assembly design and kinematic analysis for mechanical product, parallel mechanism design and analysis technology, and other related research fields.

项目主要目标是建立能自然处理欠约束、完整约束和过约束的三维几何约束系统的逼近最优分解理论与并行求解方法，主要研究内容包括：1)不可结构分解的三维几何约束闭环系统的并行分解与求解方法；2)基于等价变换的三维几何约束系统的逼近最优分解方法及其并行化；3)面向实时交互设计的三维几何约束系统在线增量求解机制与动态拖动求解策略。项目主要特色是突破现有方法依赖于几何约束系统结构信息的局限，通过挖掘几何领域知识来优化几何约束系统的分解，可实现被认为难以分解的、通常采用数值方法求解的三维几何约束系统的并行、解析求解。研究成果将为研制高性能三维几何约束求解器提供新的理论方法，也有利于促进三维变量化直接建模技术、机械产品装配设计与运动学分析的集成、并联机构设计与分析等相关研究领域的发展。

三维几何约束求解技术是现代CAD领域的核心技术，其难点是如何实现三维几何约束系统的最优分解以及分解后子系统的高效求解。本项目围绕三维几何约束系统的最优分解和并行求解问题开展深入研究并取得重要研究进展，主要包括：1）研究串联运动链的结构约束及其等价几何约束表达，提出了基于串联运动链结构约束等价替换的三维几何约束闭环系统分解方法，实现原本被认为不可分解的三维几何约束闭环系统的优化分解，且能将大量常见的三维几何约束闭环系统分解为一系列的两个刚体之间的几何约束系统，以至于可采用几何推理方法求解此前必须采用数值迭代求解的几何约束闭环系统；2）基于三维几何约束的等价替换、串联运动链的等价替换，提出了融合几何约束图结构优化、串联运动链替换分离和几何约束图结构分解的三维几何约束系统逼近最优分解方法，在不检测并剔除冗余约束的情形下就能自然处理过约束、完整约束和欠约束的几何约束系统，并达成或逼近几何意义上的最优分解；3）通过挖掘三位几何约束问题的内在并行特征，提出了三维几何约束系统的并行分解与求解方法，能够利用多核CPU的计算能力提升约束求解的效率；4）通过引入混合约束图抽象表示三维几何约束系统，建立了三维几何约束系统的在线增量求解机制，可尽可能实现交互设计中动态变化的三维几何约束系统的最小求解；5）通过分析现有雅可比矩阵方法及其变型、约束残量扰动方法和基于偶图最大匹配的方法的优势和不足，提出了兼顾效率和正确性的三维几何约束系统的冗余约束判定方法；6）提出了一种由三维装配几何约束模型自动生成运动学模型的方法，解决了现有方法从同一机械产品的多个等价装配几何约束模型生成不同运动学模型的问题。基于上述研究成果，本项目建立了三维几何约束系统逼近最优分解理论与高效求解方法，并开发了三维几何约束求解器，有力推动了三维几何约束求解技术、装配设计与运动学分析集成技术等的发展。