（机械设计及理论专业论文）几何约束系统若干关键技术的研究与实践.pdf

华中科技大学博士学位论文 摘要 ( 设计问题本质上是一个约束满足问题，即给定功能、结构、材料和制造等诸 多方面的设计约束描述，求得满足设计约束的设计对象的细节。神：i 者多设计约束 巾，几何约束是表达其它约束的基础，是约束管理和求解研究中必须优先解决的 问题。本文围绕几何约束系统的若干关键技术，进行了深入的理沦研究和系统实 践。j7 7 。本文从约束满足问题开始，简要地概述了几何约束系统的基本概念，也探讨 了几何约束的概念和分类。针对几何约束系统中的求解机制，提出了几何推理与 数值迭代相结合的求解策略。同时针对约束求解当【| i 现的于f i 问题，提f | 了于 征维护的具体准则。 本文利用面向对象的系统建模方法和统一建模语高，建立了儿何约束系统的 对象模型。本文提口j 了基于有向图的约束网络模型，利用约束网络模型，得到了 几何约束系统的最大分解。本文提出了用欧拉参数描述几何实体的形位，将几何 约束转换为欧拉参数的统表达，解决了二二维与三维的几何约束统一模型问题， 为二二、三维几何约束求解提供了统一机理。 本文根据几何约束系统中串行、并行和耦合，f ：存的约束传播机制，从彳i 同层 次来研究几何约束传播的本质特征。l 在儿何约束的方程和变量层次上，提u5 了基 1 二稀疏矩阵三角块分和二分图匹配的约束传播分析方法。在儿何约束的关系层次 l ：，提出了基于儿何约束网络的约束传播分析方法，并在此基础卜，7 提 了几何 约束传播矩阵的概念，利用约束传播矩阵，提出了检测几何约束闭环的算法。同 州针对约束传播的多样性问题，提出了解决约束传播多样性的自适应传播策略和 算法。 j、 i 奇异性问题是几何约束求解引擎工程化、实用化的关键问题本复把奇异性 总结为饱和奇异、分支奇异和冗余奇异j 种类型。本文揭示了欠约束情况下的伪 冗余现象，提出了甄别分支奇异与冗余奇异的有效方法一约束残量扰动算法。 本文用面向对象分析方法，设计了几何约束系统的类体系，提出了与c a d 平 台的集成框架结构，开发了一个二、三维通用几何约束求解引擎。本文用：i 维参 数化设计、平面机构仿真和三维装配设计实 多1 j 验* 1 ：了本文研究的先进一e i ：和实川，阼。 关键词：计算机辅助设计，几何约束系统，系统建模，约束传播，奇异性 华中科技大学博士学位论文 ! ! ! ! ! ! 竺! ! ! ! ! ! ! ! ! ! 竺苎! ! ! ! ! ! ! ! 竺! ! ! 苎； a b s t r a c t p r o d u c td e s i g ni sac o n s t r a i n ts a t i s f a c t i o np r o b l e m ，t h a ti s ，t oa c q u i r et h ed e s i g n d e t a i l s 、v h e np r o v i d e dw i t ht h ed e s i g nc o n s t r a i n t sd e s c “p t i o n sf o rf u n c t i o n s ，s t r u c t u r e s ， m a t e r i a l sa n dm a n u f a c t u r i n g a m o n ga l lt h e s ed e s i g nc o n s t r a i n t s ，g e o m e t r i cc o n s t r a i n t i st h eb a s eo f o t h e r s ，a n dt h ep r o b 】e mt h a tm u s tb es o 】v e dn r s t l y t h e r e f o r e ，i nt h i st h e s i s w ed or e s e a r c ha 1 1 dp r a c t i c eo ns o m ek e yi s s u e so f t h eg e o m e t r i cc o n s t r a i n ts y s t e m s t a r t e dw i t ht h ec o n s t r a i n ts a t i s f a c t i o np r o b l e m ，t h i st h e s i sb r i e n yi n t r o d u c e st h e f u n d a m e n t a l so ft h e g e o m e t r i c c o n s t r a i n t s y s t e m ， a sw e l la st h e c o n c e p t a n d c l a s s m c a t i o no f g e o m e t r i cc o n s t m i n t s f u r t h e r m o r e ，t h es t r a t e g yo fg e o m e t r i cr e a s o n i n g a n dan u m e r i ci t e r a t i o nm e t h o da r ep r o p o s e df o rs o l v i n gg e o m e t “cc o n s t r a i n ts y s t e m t om e e tt h ed e m a n d so fc o n s t r a i n tc h i r a l i ty t h em a i n t e n a n c en i l e so fc h i r a l i t ya r ea l s o p r o p o s e d s e c o n d l y ag e o m e t r i cc o n s t r a i ms y s t e mm o d e li sc o n s t m c t e di nt h i st h e s i sw i t ht h e o b j e c t o r i e n t e dm o d e j i n gm e l h o da n dt h eu n i n e dm o d e j i n gj a n g u a g e f o rm o d e 】i n gt h e c o n s t r a i n tr e l a t i o n ，t h ed i g r a p h _ b a s eg e o m e t r i cc o n s t r a i n tn e t w o r ki sp r o p o s e d ，a n dw e g e tt h em a x i m u md i s s o l v eo ft h eg e o m e t r i cc o n s t r a i n ts y s t e mw i t hg e o m e t r i cc o n s t r a i n t n e t w o r k e u l e rp a r a m e t e r s ，w h i c hi sf r o md y n a m i c s ，i su t i l i z e dh e r et or e p r e s e n tt h e g e o m e t r i ce n t i t i e sa n dc o n s t r a i n t s ，a n dt ou n i f yt h er e p r e s e n t a “0 1 1 so fl w od i m e n s i o n a j a n dt h r e ed i m e n s i o n a lg e o m e t r i cc o n s t r a i n t si nt h i sw a y ，w eg e tt h eu n i f i e dm o d e lo f t h et w o d i m e n s i o n a la n dt h r e e d i m e n s i o n a lg e o m e t r i cc o n s t r a i n t ，w h i c hm e a n sw eg e t t 1 1 es a m em e c h a n i s mf o rt w o - d i m e n s i o n a ia n dt h r e e d i n l e n s i o n a lg e o m e t “cc o n s t r a i l l t s o l v i n g t h i r d l y a c c o r d i n g t ot h e s e r i a l ，p a r a l l e l a n d c o u p l i n g c o n s t r a i n t p r o p a g a t i o n m e c h a n i s m s ，w ed or e s e a r c ho nt h ei n t e r n a if e a t u r e so fg e o m e t r 主cc o n s t r a i n tp r o p a g a t i o n 0 nt h e l a y e r o fc o n s t r a i n t e q u a t i o n s a n dv a r i a b l e s ，b a s e do nt h e s p a r s em a t r i x d e c o m p o s i t i o na n db i p a m t eg r 印hm a t c h ，ag e o m e t r i cc o n s t r a i n ta n a l y s i sm e t h o di s p r o p o s e d 0 nt h ej a y e ro fc o n s t r 籼n tr e l a “o n s ，b a s e do ng e o m e 打j cc o n s l m i n tn e t w o r k ， a n o t h e rg e o m e t r i cc o n s t r a i n ta n a l y s i sm e t h o di s p r o p o s e d ，a sw e l l a st h eg e o m e t “c c o n s t r a i n t p r o p a g a t i o nm a t r i x w i t ht h i sm a t r i x ，ag e o m e t r i cc o n s t r a i n tl o o p sc h e c k a l g o “t h mi sp r o p o s e d f o rs o l v i n gt h ec o n s t r a i n tp r o p a g a t i o np r o b l e m ，t h es t r a t e g ya n d a j g o r i t h mo f a d a p t i v ep r o p a g a t i o na r ep r o p o s e d k n o w i n gt h a tt h ec o n s t r a i n ts i n g u l a r i t y i st h ek e yp r o b l e mo ft h eg e o m e t r i cc o n s t r a i n ts o l v e r ，w ed or e s e a r c ho nt h i s ，a n d c l a s s i f y c o n s t r a i n t s i n g u l a r i t y i n t ot h es a t u r a t i o n s i n g u i a r i t y ， t h e e m b r a n c h m e n t s i n g u i a r i t ya n dt h er e d u n d a n ts i n g u l a r i t y w i t ha na n a l y s i so ft h ep s e u d o - s i n g u l a r i t y p f o b l e m ，ar e m a i n sd i s t u r ba l g o “t h mi sp m p o s e df o rd e t e r l l l j n i n gf h ep r o b l e m f i n a l l y ，u s i n gt h eo b j e c t - o r i e n t e da n a l y s i sm e t h o d ，w ec o n s t r u c tt h ec l a s ss y s t e mo f g e o m e t r i cc o n s t r a i n ts y s t e m ，p r o p o s ea ni n t e g r a t e d f r a m e w o r kf o ro p e nc a d s y s t e m ， a n d d e v e l o p a g e o m e t r i c c o n s t r a i n ts o l v e lt h e s o l v e rh a sb e e n a p p l i e d i n t w o d i m e n s i o n p a r a m e t r i cd e s i g n ，p l a n a r n l a c l l i n es i m l l l a t i o na n dt h r e e 。d i m e l l s i o n a s s e m b l ys y s t e m i tv e r i n e st h ea d v a n t a g eo f t h e t h e s i sr e s e a r c l l k e yw o r d s ：c o m p u t e 卜a i d e dd e s i g n ，g e o m e t r i c c o n s t r a m ts y s t e m ，s y s t e m1 1 1 0 d e l i l l 昏 p r o p a g a t i o no fc o n s t r a i n t ，s i n g u l a r i t y i i i 华中科技大学博士学位论文 1 1 课题的提出 1绪论 对一个国家来说，制造业的水平反映了一个国家的总体工业水平。对一个制 造企业来说，设计水平的高低是一个企业兴衰成败的关键因素之一。如果“昨天 的竞争是价格的竞争，今天的竞争是质量的竞争，”那么“明天的竞争就是设计 的竞争。”科研开发力量和高新技术的应用是支撑企业设计的强有力后盾。计算 机辅助设计和计算机辅助制造( c o m p u t e r a i d e d d e s i g n c o m p u t e r a i d e d m a l l u f a c t u r e ，c a d c a m ) 技术是直接支持设计的高新技术，它也越来越成为一项 基础技术。1 9 8 9 年，美国评出近2 5 年间当代十项最杰出的工程技术成就，其中第 四项就是c a d c a m 技术。c a d 技术之所以这么重要，是因为它推动了几乎一 切工程领域的设计革命。 从人工智能的角度来看，4 ，5 1 ，设计问题本质上是一个约束满足问题( c o n s t r a i n t s a t i s f a c t i o np r o b l e m ) ，即给定功能、结构、材料和制造等诸多方面的要求描述，也 就是设计约束，求得满足设计约束的设计对象的细节。设计问题同时也是一个循 环反复、不断渐进的过程，在设计周期中，从概念设计到详细设计，设计模型被 反复修改，但是设计约束贯穿始终，它要求在设计的各个阶段得到满足，并在设 计过程中保证设计约束的一致性。 传统的c a d 系统是一种基于几何模型而向上模拟、适应设计需求的辅助工具， 但这一工具始终未能满足极为智能的设计活动的需要。没有几何约束管理和求解 技术支撑的传统c a d 系统，其设计模型只记录了产品的形位坐标信息，没有记录 约束信息，亦即只保存了设计的最后结果，而将贸穿始终的设计约束信息丢弃， 这样的c a d 系统显然无法满足现代制造企业对设计的需求。在企业的实际生产中， 许多新产品的研究和丌发是基于原有设计基础上的修改完善，在这种情况下，只 需要对原设计的某些局部进行修改。但是，在传统c a d 系统中，即使一个很小的 设计修改，也往往会导致对以前大量设计努力的放弃，由于设计约束信息的丢失， 设计的局部改动常常会引起整个模型的删除和重画，不仅效率低，而且难以保证 设计约束的一致性。 新一代c a d 哲理来源于当代设计理论、方法和模型研究的最新成果，也来源 华中科技大学博士学位论文 丁二虚拟现实、面向对象和因特网等信息领域众多前沿技术的迅猛发展。当前，新 代c a d 研究和开发币经历着从设计系统到设计环境，从基于几何到基于模型 的革命性转变之中。设计模型是几何模型与设计信息( 特征和约束) 的结合，设 计模型比几何模型包含了更多的智能化因素，可以更好、更完整地沟通设计意图， 同时，设计信息在设计模型中也能够得到最充分的表达。 在诸多设计约束中，几何约束最具有基础性，是表达其它设计约束的基础， 是约束管理和求解技术中必须优先解决的问题。因此，几何约束管理和求解技术 已成为当前c a d 领域的一项关键单元技术，是新一代c a d 技术的制高点，其重 要性已被广泛认识。研究和掌握几何约束管理和求解技术，是开发具有自主知识 产权的新一代c a d 系统的关键所在。基于以上认识，本文将几何约束系统关键技 术的研究作为博士论文的主要内容。 本文的研究工作得到国家高技术研究发展计划( 8 6 3 5 1 1 9 8 4 2 0 0 3 ) 和国家“九 五”c a d ，c a m 攻关计划的支持。 1 2 国内外相关研究综述 j e 尽管s u m e r l a n d 在其具有里程碑意义的s k e t c h p a d 【6 1 石开究中已经将计算机辅助 设计系统的概念定位于约束满足问题，但是传统的c a d 系统没有约束管理和求解 的支持，它更多地表现为电子图板，缺乏良好的支持设计的能力，难以被广大的 丁程设计人员所接受。同时，约束满足问题一直是人工智能领域研究和应用的重 要课题，约束满足是问题描述而不是过程实现，在设计领域，设计约束贯穿于设 计的各个阶段和方面，然而要给定其统一的表达和捕述并非易事。因此，约束管 理和求解是丰富多样的，不存在定式，这也形成了约束管理和求解理论、方法研 究的多样性。 1 2 1 变量几何方法 这是一种面向非线性方程组整体求解的代数方法，h i i l y a r d 【7 l 提出了约束的非 线性方程组表达，约束系统可以表达为状态变量z = l j = 1 ，2 ，n ) ，和组 约束方程f = 石i = l ，2 ，m ) ，其中m = n 。即约束系统可以表示为： f ( x ) = o 其中：x = ( 船) ，s m ， f = ( 力，s m 华中科技大学博士学位论文 由m i t 的g o s s a r d - 1 0 ，1 1 ，1 2 ，13 ，1 4 1 研究小组发展和完善了这一理论，称为变量几 何法( v 打i a t i o n a lg e o m e t r y ) 。该方法把几何形状定义成一系列的特征点，约束则 表示成以特征点坐标为变元的非线性代数方程组，通过数值迭代方法求解非线性 方程组，从而确定出几何细节。 非线性方程组的求解通常基于n e 叭o n r a p h s o n 迭代法。对于式( 1 1 ) 的方程组， 由初值f ，第n + 1 次迭代的x ”1 值由以下迭代公式得到： x ”= x ”_ 【f ( x ”) 】。f ( x ”) 其中，f ( x ”) ：( 拿( 一) ) “；。， c 况 令；x = x “t x “ 则有： i f ( x ”) = 一f ( x ”) l x ”1 = 硝+ x ” 我们于是得到： j 醯= 其中，= 卵i f 袅t 牙p 2 知 勰， a l c 万i c 毳2 c 矿l 表。 蕊。 西c 卅 为雅可比矩阵。 = 而，x 2 ，缸。) 7 ，表示各个变量的微小位移 厂= 一e ，一最，一只 ，表示方程组的残差。 ( 1 2 ) ( 1 3 ) 经过反复迭代，直至i x i ，就得到了方程组的解。约束集的有效性可以通 过判断雅可比矩阵的秩来实现。 s u t h e r l a i l d 【6 1 的s k e t c h p a d 系统首次采用松弛迭代法求解约束方程组，松弛法虽 然速度慢，但比较通用。其它一些系统如t h i n 9 1 a b 1 6 】和m a g r i t t e 1 8 1 也采用了松 华中科技大学博士学位论文 弛法。求解约束方程组时，n e 似o n r a p h s o n 迭代法比较常用，它比松弛法速度快， 但有可能收敛到局部最小点，在约束求解中通常是把初始图形作为迭代的初始状 念，以避免这种情况的出现。当方程组的雅可比矩阵奇异时，n e 叭o n - r a p h s o n 方 法就不能使用。因此，l i g h t 运用一个修正的d o o l i t t e 方法以找到雅可比矩阵的 逆。n e v i l l e 提出了采用最小二乘法求解非线性方程组的算法，其特点在于无论 约束模式有效与否，总能给出一个最小二乘意义上的近似解。当只有局部变量值 改变时，l i n 【8 】采用一种矩阵分块算法找到受影响最小的子约束方程组，以缩小问 题规模，提高计算效率。另外，w i t k i n 用一个能量函数表示约束，再利用能量梯 度法搜索到一个局部最小值。k i n 利用基于扩展b o l t z m a n n 机的人工神经网络技 术，求解几何约束的非线性最优化问题。a n n a 【2 2 l 采用模拟退火算法求解大型等式 和不等式约束方程组。向文【2 3 l 运用图论把约束网络分解成一组可以顺序求解的方 程或方程组，大量的线性和二次方程可以用精确的解析法求解，从而减小了联立 非线性方程组的规模。 在变量几何方法提出的初期，方而，由于数值方法求解稳定性差，迭代初 值与步长的选取也会影响算法的成败，方程组整体求解的规模和速度难以得到有 效的控制，以及需要对雅可比矩阵进行求逆运算，因此，只能求解完备约束问题， 不能求解欠约束问题，这样使得变量几何方法很难应用于实际的c a d 系统中。另 一方面，从使用的角度，用户很难以一组方程式刻画几何元素之间的约束关系。 而且当出现不一一致的情况或非预期的结果时，从约束方程组得不到准确的反馈。 变量几何方法的主要优点在于能适应很大范围的约束类型，对所有的约束类 型有统一的模型，而且循环约束情形可以通过约束方程组的联立求解得到处理， 也可以和工程约束联立求解。 1 2 2 符号代数方法 符号代数方法也称为数学机械化方法，它是利用数学机械化方法来决定约束 方程组有效求解的顺序但4 ，2 引。如应用g r 曲n e r 基【2 6 j 和吴方法【2 7 2 8 j 将方程组求解出 来。b u c h a i l a l l 【2 9 】描述了一个定义点、线、圆和圆弧的二维几何约束定义系统c d s ， 应用g r 6 b n e r 基方法对隐式方程组进行简化和排序，使约束方程组变为非耦合和低 耦合的方程组，通过求解单元方程，然后回溯迭代柬逐步求解整个约束方程组。 c d s 还能识别和处理过约束、欠约束和矛盾的方程组。k o n d o f 3 0 3 1j 应用b u c h b e r 2 e r 算法处理增加和删除的约束，并导出一个多项式表示增加和删除约束之问的关系。 符号代数法在几何定理的机器证明中得到广泛应用，虽然也可求解约束方程 华中科技大学博士学位论文 组，但在效率上有待进一步改进。 1 2 3 基于规则的几何推理方法 基于规则的几何推理方法运用规则来建立和执行构造步骤，又称为规则一构 造式求解方法。它基于这样一个事实，即在二维工程图中的绝大多数图形都可以 通过直尺、圆规和量角器绘出。约束通过构造的方式得到满足，这样对用户来说 更显得自然而且适合于交互式操作。 a l d e f c l d f 3 2 1 采用一个基于符号推理和操作的专家系统，建立了一个规则体系， 将几何形体的约束关系用一阶逻辑谓词描述，存入知识库中。系统从知识库中提 取出有关信息，通过推理机逐步推导出几何细节。推理示意图如下： 约束 图1 1a l d e f e l d 方法 事实库包含某特定几何模型的知识，初始内容是给定的约束，通过规则推理 出的事实不断累加。规则库收集所有规则，通常仅有一个规则子集作用于某给定 模型，但预先无法知道。推理机是控制部分，其任务是按某些策略选择规则并应 用于现有事实。处理的中心点在于模式匹配，即检验每个原子表在事实库中是否 有所对应。推理的结论成为新的事实，推理史记录了所有成功的规则应用。 其基本方法是从现有的已知约束中派生出尽可能多的知识。因此每当一个新 的约束得到后，推理过程启动，所有规则循环使用，直至没有新的事实产生。约 束处理分为两个阶段： 1 几何约束读入系统阶段，并加入事实库，启动推理机，所有可派生的事实 存入系统。一旦某个约束被删除，推理史回溯。 2 在后处理阶段，推理史输出重建步骤，把规则名翻译成相应的处理过程， 形成构造计划，一步步执行，从而构造出整个几何体。 s u z u k i 和k i m u r a 【3 3 3 4 3 5 ，3 6 ，3 7 ，3 8 1 等提出了一个面向对象的几何推理方法，它允许 在用户构造设计模型的同时，自动生成约束关系的谓词描述，该方法建立了一个 规则体系，将几何形体的约束关系用一阶逻辑谓词描述，存入知识库中。系统从 华中科技大学博士学位论文 知识库中提取出有关信息，同a l d e f e l d 法类似，也是通过推理机对知识库进行规 则匹配，通过推理机推导出几何细节，逐步构造出整个图形。 上述方法具有基于规则的方法的优点，诸如几何知识清晰的表示，知识和处 理的分离，规则库的扩充性好，而且完全避免了数值算法的不稳定性。然而，系 统庞大、速度慢、无法处理循环约束等也是该方法的明显不足。 针对上述缺点，s u n d e l 3 9 | 的方法允许在不断施加约束的过程中修证图形，直至 图形得到完全定义。他引入了两种数据类型： 1 c a s e t ：相互之间含有角度约束的线段的集合 2 c d s e t ：相互之间含有距离约束的点的集合 产生式规则作用于这些集合，并把它们组合为更大的集合。例如以下规则： 1 如果两个c d s e t 含有一个共同的点，并且它们之问的角度在该点被约束， 则这两个c d s e t 被合并为一个c d s e t 。 2 如果两个c a s e t 含有一个共同的线段，则它们被合并为一个c a s e t 。 这种方法大大减少了纯专家系统所需的事实和规则数目，能很快地引导推理 向正确的方向进行。缺点是不容易加入新的实体类型和约束类型，难以解决复杂 的图形。 葛建新等1 4 0 】提出种自由度亏损方法依次导出几何元素的求解次序。基本方 法是几何元素的确定过程亦即该元素自i j | 度下降的过程，当自由度下降为零时， 该几何元素也就完全确定下来了，它还可以用来导出其它相关联的未知元素。高 曙明1 4 1 1 将几何约束蕴含于图形数据结构，通过程序对尺寸约束进行快速几何推理， 比建立专家系统进行推理效率更高，实用性更强。 1 2 4 基于图论的方法 这种方法把几何约束系统抽象为几何约束图，通过分析约束图推导出一系列 构造过程，再根据这些构造步骤来导出几何体心4 3 4 4 ，4 5 ，4 6 ，4 7 1 。 d e c h t e r 1 8 1 提出了二元约束网络表达，但二元约束不足以完善地表达约束系 统中广泛存在的多元关系。t o d d 【4 8 j 用图来表达约束系统，其中顶点代表元素。 r e q u i c h a 和f i t z r a “5 0 l 构造了种x 向和y 向的尺寸树，如果树中出现了图( 即 出现了封闭回路) ，则表明出现了多余的尺寸约束。该方法只能处理水平和垂直方 向的距离尺寸，因此只适用于简单的工程图形。0 w e n j 5 1 5 2 1 引入了循环尺寸约束， 拓展了这一方法。他将二维几何约束系统表达为个图，并分析了约束图的三连 华中科技大学博士学位论文 通部分。对每个三连通域，用符号代数方法分别求解。求解过程是递归的，亦即 一一h 某个三连通域已知，它就会在图上被归约为一个顶点，并在归约图上成为其 它三连通域的成员。然后在割点处递归进行连通块分解，用分解的逆序进行求解 每个子块，并通过维持几何实体之间的拓扑关系来处理多解情况。h o f r m a l l n 忙。”j 和l e e 【5 5 5 6 ，5 7 】采用的是基于图缩并的代数方法，他们丌发了一个可编辑的高层次的 基于约束的描述语言e r e p ，并能让用户交互式地选择所需要的解。h o f r m a i l n 法 与o w e n 法类似，只是o w e n 法是自上而下确定图的三连通域，而h o m n a i l l l 法则 自下而上搜索几何元素簇( c l u s t e r ) 。董会祥1 5 8 】提出以有向图来表达几何约束系统， 提出了一种新的约束求解思路。 鼬锄e r 【5 9 ，6 0 川的研究强调几何约束传播应具备良好的可解释性，指出“几何约 束满足问题的核心是实现约束的最大分解”，虽然其研究内容侧重于刚体运动学， 但提出某些不同应用领域的几何约束问题应具有同样的内在机制，如装配设计， 参数化造型，参数化绘图及机构仿真。 k r 锄e r 的几何约束机( g e o m e t r i cc o n s t r a i n te n g i n e ) 将几何约束系统抽象为无 向图，图顶点为几何实体称为g e o m ，或一组可独立确定相对形位的几何实体集， 称m a c r o g e o m s ，顶点的自由度及顶点之间的约束度以权值的形式分别记录在顶点 和弧上。约束求解过程大致分为两步：( 1 ) 由链式搜索和环路搜索在图上找出符合 m a c m 条件的几何实体集，并记为m a c r o 顶点。( 2 ) 从约束变动的宏m a c r o 出发， h ：断地寻找上一层宏，并识别其约束模式，调用相应的计算方法，得到问题的解。 l ( r 锄e r 并未提出宏的完备搜索方法，以平面连杼机构问题为例，链式搜索和 环路搜索仅能在约束图上找出链、环两利- 宏模式，见1 2 。 _ 3 u2 3o 3o _ 旬 图1 2 链、环模式 链、环两种模式只是所有宏模式的子集，在几何约束领域，这两种模式通常 存在解析解。因为没能找出完备的m a c r o g e o m 集，k r a m e r 的几何约束机最终并未 实现约束系统的最大分解，而退变为先最大程度地以封闭形式求解，然后再进行 数值迭代的求解方法。 但是l ( r a m e r 方法存在两个问题，第一，他没有给出几何约束系统最大分解的 华中科技大学博士学位论文 判据；第二，他没有把基于变量的分解上升到基于几何实体分解的高度来解决几 何约束系统的最大分解问题。 陈立平呲6 3 1 和罗浩【叫基于对机构运动规律的深入分析和大规模稀疏矩阵分解 【6 5 6 6 ，6 7 1 的数学成果的成功运用，提出几何约束系统最大归约理论，把从基于方程组 的变量的分解上升到了几何实体分解的层次，并给出了几何约束系统最大分解的 判据，实现了几何约束系统的最大分解。 最大归约理论的核心是简单归约集，把复杂的几何约束系统分解为简单归约 集的组合，将几何约束图g c g ( g e o m e t r y c o n s t m i n tg r 印h ) 表达为最大归约树的 形式。揭示了几何约束系统内部的串行、并行和耦合并存的约束求解机制。以简 单归约集的耦合度来反映几何约束系统的复杂度，以此作为几何最大分解的判掘。 图论研究方法的共同特点是直接对几何实体的自由度进行分析，逐步选择能 够满足的约束，用解析方法计算相应的几何变换矩阵，来实现约束满足。由于基 于图论算法，因而理论严密，速度快，效率很高。但是，这些方法都需要借助于 数值方法才能解决闭环约束问题。 1 2 5 基于构造过程的方法 基于构造过程的方法在图形输入的过程中借助造型命令自动捕捉设计者的意 图唧，6 9 ，7 0 ，7 ，7 2 ，埘。这种方法记录了用户在造型过程中的每一步操作；基本思想是造 型操作与几何约束之间有着对应的关系，造型过程能够用来管理和维护反应几何 元素之间约束关系的内部数据结构，设计的修改可以通过修改造型过程的某一参 数得到。 r o l l e r l 7 4 7 5 ，7 6 7 7 - 7 8 l 扩展了传统c a d 系统的数据结构，以便更好地捕捉设计者的 意图，其主要作法包括： 1 引入三种类型的几何实体：固定的、可变的和柔性的； 2 通过对命令语义的推理，自动建立几何约束关系； 3 跟踪构造几何体( 辅助线) 的使用，捕捉构造原则； 4 存储构造顺序； 5 生成由传统c a d 的命令组成的构造计划； 6 对于给定的某一组尺寸参数，执行构造计划。 s o j a n o 9 l 给出了一个内部的模型定义语言，它能对预定义模型进行参数化建 模，不仅支持二维和三维，而且能实现拓扑结构的修改。 华中科技大学博士学位论文 高小山【8 0 8 1 ，8 2 】等提出了几何自动作图的全局延拓法，在绘图操作中引入了两种 新的作图工具：二次曲线与连杆。引入二次曲线后，二维作图范围从原来尺规作 ， 图可以解二次系列方程组扩大到解次数小于等于四的系列代数方程，由于3 次、4 次方程可以象2 次方程一样可以用根号显示求解，因此具体方程的求解困难并未 。 增加。高小山还证明了使用一般的连杆作图等价于一般的构造性几何图形，即可 以两两引进几何体的图形。引入连杆作图工具，用四连杆解决了0 w e n h o m l l a n n 方法不能解决的关系图。在此基础上，高小山给出了基于关系图的新算法，对于 无约束闭环的问题，可以给出一个线性的判定与解决方法，对于有约束闭环的问 题，给出了一个二次算法。算法的复杂度与o w e n h o 胁a 1 1 n 的算法复杂度相同， 但解题范围有所扩大。高小山的算法试图用尺规作图和四连杆的数学理论，结合 符号计算法与基于优化的数值法，解决约束系统中的约束闭环、冗余约束与矛盾 约束这一难点。 基于构造过程的方法，对于结构相同尺寸不同的零件设计是十分有效的。但 是由于必须严格遵循构造过程，对于那些设计要求不断变化的设计环境则不太适 用，而且难以利用传统c a d 系统生成的图形。另外，无法处理耦合程度高的约束 闭环的情形。由于空间问题的复杂性，三维参数化方法难以实现陈述式的表达、 规划和求解，因此早期的商用c a d 多采用基于几何模型构造过程的方法。 1 2 6 编程求解方法 编程求解方法的基本过程是通过分析模型的特点，确定各尺寸之间的的数学 关系，给定输入参数，然后确定其它参数的值，并用高级语言在c a d 软件中实现 1 8 3 8 4 ，8 5 8 6 ，8 7 ，8 8 8 9 ，9 m 。当前多数的商业c a d 系统都提供了此项功能。例如s o l i d w o r k s 、 s o l i d e d g e 等c a d 系统就提供了v i s u a lb a s i c 编程语言。编程求解方法的优点是可 以表达过程性的约束，对于结构相同而尺寸不同的零件设计是十分有效的。缺点 是只能用于拓扑关系确定的样板设计模型，如果对于拓扑关系变化的模型就不适 用了。 1 2 7 几何约束管理和求解技术应用研究的最新进展 作为新一代c a d 系统的关键技术，美国p t c 公司于一九八八年推出参数化 造型系统p r o e n g i n e e r 后，基于约束的参数化特征造型成为c a d 公司应用技术研 究的热点。几何约束的管理和求解技术的开发应用得到了国际上各知名c a d 厂 商的极大重视，纷纷投入到它的丌发研究中，但由于几何约束问题的难度，多数 c a d 厂商的开发以失败而告终，最终不得不购买其它公司的技术，如微机c a d 华中科技大学博士学位论文 产品s o l i d w o r k s 、s 0 1 i d e d g e 等系统。这样，虽然厂商缩短了开发时间，但可能为 c a d 技术进一步的研发带来了障碍。但是，也有一些公司的应用研究获得了很大 的成功。 i d e a sm a s t e rs e r i e s5 【9 6 ，9 7 1 使用了新一代c a d 的约束求解技术，即变量几何 扩展技术，简称v g x ( i a t i o n a lg e o m e t r ye x t e n d ) 技术，s d r c 称之为“最引人注 目的c a d 技术革命”。v g x 是用于三维零件设计和修改时的最直观的交互技术， 允许用户利用强有力的几何造型和完全的设计意图进行零件设计。v g x 将直接几 何描述和历史树描述这两种目前最好的造型技术创造性的结合起来，这意味着用 户只需在一个主模型中，就可以动态捕捉设计、分析和制造的意图并连贯地进行 操作。此外，i d e a s 将v g x 技术应用于设计和装配，并从装配模型自动导出 机构动力学模型，进行动力学仿真。此外，v g x 技术极大地改进了交互操作的直 观性，从而更加易于使用，富有效率。 位于英国剑桥的d c u b e d 公司，是一家专门从事约束求解系统软件丌发的公 司。d c u b e d 基于在o w e n 5 2 】的算法，在1 9 9 0 年就推出了二维约束求解核心模 块2 dd c m 【9 8 】，并于1 9 9 4 年，推出了三维约束求解模块3 dd c m 【吲。经过十年的 研究丌发，d c u b e d 公司的二、三维约束求解模块现在已经为d a s s a u l ts y s t e m e s ， a u t o d e s k ，s 0 1 i d w o r k s 等国际著名的c a d 公司所广泛采用。 1 3 本文的研究工作和创新点 几何约束的研究源于参数化设计应用的需求。二维参数化设计在实现方法上， 走过了从基于过程机制的编程方法、构造方法、推理方法到更具智能特征的基于 陈述式约束描述的求解方法的发展历程。对于三维参数化应用，如参数化特征造 型、装配仿真等，可以发现许多二维应用早期的技术特征，如基于过程的构造方 法( 三维特征造型的特征历史树) 及几何推理方法( 丌环模式的装配) ，但是三维 参数化应用完全可以借鉴二维几何约束系统中与过程无关的管理和求解理论、方 法，来改造三维应用中不够灵活的操作技术。 作为二维参数化研究的变量几何方法，由于需要求解非线性方程组，在早期 常被认为具有非线性数值不稳定的缺陷。但是，经过多年不懈的研究和实践，已 很难发现原来的不稳定现象。其主要原因在于，不稳定特性并非源于基于约束表 达的模型本身，而源于模型的数值求解方法，通过改进求解方法可完全避免不稳 定现象。 华中科技大学博士学位论文 本文以图论、多体系统分析、大规模稀疏矩阵理论、非线性方程组求解和面 向对象建模理论等为基础，围绕几何约束系统的关键技术，进行了深入的理论研 究和系统开发实践。本文的研究工作集中体现在以下几个方面： l 在几何约束系统建模的研究中，应用面向对象建模方法，以有向图为基础， 日欧拉参数的几何约束分量表达方法，建立几何约束系统模型。 2 在约束传播机理研究中，在几何约束的方程与变量层次，研究几何约束系 统的分解，在约束层次上，用几何约束网络来用几何约束矩阵描述约束的传播机 制。针对几何约束系统约束传播的多样性，在约束的分量表达方法的基础上，提 出了基于有向图的二分图匹配的自适应约束传播策略，实现了欠约束强连通分量 的优化分解，实现了几何约束系统的最大分解。 3 针对几何约束系统冗余约束的判定问题，结合欠约束系统约束求解规划的 多样性，对几何约束系统的奇异性进行了深入研究，提出了奇异性分类，并给出 相应的判定策略：提出并分析了欠约束情况下影响约束求解的伪冗余现象，在欠 约束几何系统优化分解的基础上，进一步提出了可准确判别冗余约束并可自适应 地规避伪冗余现象的约束求解规划算法；提出了残量扰动方法，快速准确的判定 约束的冗余性。 4 在本文研究成果的基础上，运用面向对象方法设计实现了几何约束求解引 擎，提出了几何约束求解引擎与c a d 无缝集成框架结构，并应用于二维参数化设 计，三维草图设计，三维装配设计中。 1 4 本文的组织结构 本文围绕几何约束系统管理和求解研究中的关键技术进行了深入的研究，以 此为中心，对几何约束系统中的研究成果展开系统的阐述，本文的组织结构如图 1 3 所示。 一一 1 l 华中科技大学博士学位论文 1 奄 绪论 l 几何约磊统概述l l lli 4 章 i5 蕈j l 几几何约束系统建模i 几何约束传播机理研究 i 几何约束的奇异性分析i f l l 6 章 原型系统开发与j 衄用实例 7 奄 全文总结与展望 图1 3 本文的组织结构 l 章：系统全面地分析了研究的背景和课题的来源，论述了国内外相关研究的 概况，并简述了本文的研究工作。 2 章：