（机械设计及理论专业论文）二、三维几何约束统一求解器原理与方法研究.pdf

华中科技大学博士学位论文 摘要 ( 自从参数化技术被应用到实际工程设计中来以后，几何约束求解技术已经成为 c a d 系统开发的核心技术之一。几何约束求解引擎的开发涉及到建模、约束分解、约 束维护以及求解等几个方面的关键技术。， 奉文首先分析了二维草图设计、三维造型与 装配设计以及多刚体系统几何模型各自在几何上的特点及相互之间的共同点，提出了 几何元素和几何约束的统一表达方法，从而在几何约束建模的层次上构造了一种统一 的几何约束系统层次模型，在几何建模的层次上为统一几何约束系统和多刚体系统奠 定了基础。几何约束系统的最大分解问题是一个组合优化问题，要得到系统分解的最 优解在时间花费上是得不偿失的。因此，针对欠约束几何系统约束匹配的多样性，本 文提出了基于有向图复杂度分析的次优分解方法，包括剥离简化和匹配优化，该方法 具有多项式的时间复杂度，大大提高了分解效率，改善了分解品质；同时，针对闭环 约束问题讨论了回溯求解算法。本文深入分析了造成几何约束系统奇异的原因，提出 了几何约束冗余性符号判别方法以及数值一代数混合判定方法，数值一代数判别法缩 小了判定范围、提高了判别效率与稳定性，更重要的是，该方法既避免了大量的数值 判别，又能分别出冗余奇异与分支奇异；在约束冗余性判定的基础上，提出了动态的 几何约束分类容器管理，给出了全新的约束系统真理维护机制，并讨论了其在约束识 别中的应用。针对几何约束系统数值求解的过程中所遇到的若干问题，比如牛顿法的 收敛性问题，提出了针对欠约束系统的牛顿一同伦混合算法，兼顾了系统的求解能力 与求解效率；在此基础上，讨论了几何约束系统的多解问题。最后，在对几何约束求 解问题进行深入研究的基础上，将几何约束满足理论扩展到多剐体系统分析的应用中， 研究了基于几何约束的多刚体机械系统的矩阵组装与自动建模技术，初步探讨了几何 约束系统与多刚体系统的统一建模。【作为上述研究的成果与实践，本文运用面向对象 方法，设计实现了统一几何约束求解引擎c b a 及其扩展d c b a ，为构造全约束的c a d 系统提供了技术基础。、j 关键词：参数化设计，几何建模i 几何约束求解，约束分解，奇异性 华中科技大学博士学位论文 a b s t r a c t g e o m e t r i cc o n s t r a i n ts o l v i n gh a sb e c o m eak e r n e lt e c h n o l o g yo fc a d s y s t e m ss i n c e p a r a m e t r i z a t i o nt e c h n o l o g ) 7w a sa p p l i e dt op r a c t i c a le n g i n e e r i n gd e s i g n t h ed e v e l o p m e n t o fa g e o m e t r i c c o n s t r a i n ts o l v e ri n v o l v e ss o m e k e yt e c h n o l o g i e s s u c ha s m o d e l i n g d e c o m p o s i t i o n ，c o n s t r a i n t m a i n t e n a n c ea n d s o l v i n g f i r s t l y ，b ya n a l y z i n g c o l n n l o n g e o m e t r i cf e c i u r e so f 2 ds k e t c hd e s i g n ，3 ds o l i dm o d e l i n g ，a s s e m b l yd e s i g na n d g e o m e t r i c m o d e lo f m u l l i - b o d ys y s t e m ，t h et h e s i sp r e s e n t su n i t e de x p r e s s i o n so fg e o m e t r i ce l e m e n t s a n dc o n s u i n t ，c o n s t r u c t sau n i t e dh i b e r a r c h ys t r u c t u r ef o rg e o m e t r i cc o n s l t a i n t m o d e l i n g ， a n dt h u se s t a b l i s h e st h eb a s i so fu n i t e dg e o m e t r i c m o d e l i n gf o rg e o m e t r i cc o n s t r a i n ts y s t e m a n dm u l t i - b o d ys y s t e m t h em a x i m a ld e c o m p o s i t i o no fg e o m e t r i cc o n s w a i n ts y s t e mi sa c o m b i n a t i o no p t i m i z a t i o np r o b l e ma n d f u n d i n g t h em a x i m a l d e c o m p o s i t i o no f t h es y s t e mi s n o te f f i c i e r i t s o ，ah y p o - o p t i m i z e d d e c o m p o s i t i o n m e t h o di sa d v a n c e db a s e do nt h ea n a l y s i _ s o fc o m p l e x i t yo fd i r e c t e d g e o m e t r i c c o n s t r a i n t g r a p h ，e s p e c i a l l y f o rt h e d i v e r s i t y o f g e o m e t r i cc o n s t r a i n tm a t c h i n gi nu n d e r - c o n s t r a i n e ds y s t e m s t h em e t h o dp r o p o s e dh a sa c o m p l e x i t yo f p o l y n o m i a lt i m e ，a n da c c o r d i n g l yi m p r o v e st h ed e c o m p o s i t i o ne f f i c i e n c ya n d q u a l i t y a sas u p p l e m e n to f t h ed e c o m p o s i t i o nm e t h o d a n a c em e t h o di sa d v a n c e dt os o l v e l o o p s i ng e o m e t r i cc o n s t r a i n ts y s t e m s t h et h e s i st h e na n a l y z e s 也ec a u s e so f s i n g u l a r i t i e so f g e o m e t r i cc o n s w a i n ts y s t e ma n dp r e s e n t san u m e r i c a l a l g e b r a i cd i s c r i m i n a t i n gm e t h o d w h i c hu s e sn u m e r i c a lm e t h o dt or e d u c et h e d i s c r i m i n a t i n gr a n g ea n di m p r o v e t h ee f f i c i e n c y w h i l ea d o p t sa l g e b r a i cm e t h o d , n a m e l yg r 6 b n e rb a s e m e t h o d ，t oa d v a n c et h er o b u s t n e s so f s h a g u l a d t ya n a l y s i s t h em o s ta d v a n t a g eo f t h em e t h o di st h a ti tc a nd i s c r i m i n a t er e d u n d a n t s i n g u l a r i t yf r o me m b r a n c h m e n ts i n g u l a r i t yw h i l ea v o i d so v e r m u c hn u m e r i c a lc o m p u t a t i o n b a s e do nt h e s i n g u l a r i t ya n a l y s i s ，t h e t h e s i s p r o v i d e s a d y n a m i c c o n s t r a i n tt r u t h m a i n t e n a n c es c h e m e ，u s i n gas o - c a l l e dc o n s t r a i n tc o n t a i n e rt o d y n a m i c a l l ym a n a g et h e g e o m e t r i cc o n s t r a i n mi nt h es y s t e m f o rt h es t a b i l i t yp r o b l e m so fn u m e r i c a lc o m p u t a t i o n , e s p e c i a l l y i n3 da p p l i c a t i o n s ，a h y b r i dn e v c t o n - h o m o t o p y m e t h o di s p r o p o s e d f o r u n d e r - e o n _ c t m i n e ds y s t e m s i tm a k e su s eo fb o t ht h ef a s t n e s so f n e w t o n - r a p h s o n i t e r a t i o n m e t h o da n dt h es t a b i l i t yo f h o m o t o p y m e t h o da n dt h u si m p r o v e sb o t ht h ea b i l i t ya n dt h e 华中科技大学博士学位论文 e f f i c i e n c yo f t h es o l v e r f i n a l l y ，b ys t u d y i n gt h em a t r i xa s s e m b l ya n da u t o m a t i cm o d e l i n g t e c h n o l o g yo fg e o m e t r i cc o n s t r a i n tb a s e dm u l t i - b o d ym e c h a n i c a ls y s t e m s ，t h et h e s i sm a k e s ae l e m e n t a r y s t u d yo fu r d t e d g e o m e t r i cm o d e l i n go fg e o m e t r i cc o n s t r a i n ts y s t e ma n d m u l t i - b o d ys y s t e m ，e x t e n d i n g t h e t h e o r y o f g e o m e t r i c c o n s t r a i n ts a t i s f a c t i o nt ot h e a p p l i c a t i o n so fm u l t i - b o d ys y s t e ma n a l y s i s a st h ea c h i e v e m e n ta n di m p l e m e n t a t i o no ft h e r e s e a r c h e sa b o v e ：au n i t e d2 d 3 dg e o m e t r i cc o n s t r a i n ts o l v e rc b aa n di t se x t e n s i o nd c b a a l ed e v e l o p e du s m go om e t h o d ，w h i c h p r o v i d e si m p o r t a n tt e c h n o l o g yf o u n d a t i o nf o rt h e d e v e l o p m e n to f f u l l - c o n s w a i n tc a ds y s t e m k e y w c r d s ：p a r a m e t r i z a t i o n ，g e o m e t r i cm o d e l i n g ，g e o m e t r i cc o n s t r a i n ts o l v i n g c o n s t r a i n td e c o m p o s i t i o n ，s i n g u l a r i t y i i i 华中科技大学博士学位论文 1 1 课题的提出及其研究的意义 1 绪论 自从c a d ( c o m p u t e ra i d e dd e s i g n ) 的概念被提出以来，它已经迅速渗透到机械、 航天、纺织、电子等国民经济的各个领域，发挥了巨大的作用，产生了令人瞩目的经 济效益。在国内，国家科委于“九五”期间发起了“甩图板”运动，使得c a d 技术 在我国工程设计领域得到了极为广泛的应用，极大地提高了设计效率、缩短了设计周 期，使我国的设计水平有了一个质的飞跃。 尽管如此，由于设计活动是一个智能化程度很强的活动，传统的c a d 系统并不 能很好地适应这个特点。设计活动蕴含着一系列的不同特点的问题求解过程，设计问 题就其本质来说是一个约束满足问题【i 、2 3 , 4 , 5 , 6 1 ，即从系统的功能、结构、材料及工艺等 方面的设计要求，得到满足这些设计条件的设计对象。而传统的c a d 系统几乎都是 仅限于接受设计问题的解，而不是参与设计问题的求解过程，从而使得c a d 系统仅 仅局限于辅助几何造型和工程绘图；也就是说，传统c a d 系统在更多的意义上来讲 是c o m p u t e r a i d e dd r a w i n g ，而不是真正的c o m p u t e r a i d e dd e s i g n 。 当前c a d 技术正不断向标准化、集成化、智能化和网络化的方向发展。人们从 上个世纪八十年代开始研究新一代的c a d 系统。这其中以1 9 8 8 年p t c 推出的以约束 驱动为核心的特征参数化c a d 系统p r o e 为代表，利用人工智能领域的专家系统和约 束管理等方面的研究成果，使用户可以建立较为完善的产品模型，支持智能化的设计 过程，并能进行参数化设计和变量化设计。p m e 的成功使几乎所有的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 系统的关 键组件技术之一，研究并开发该技术有利于提高我国c a d c a m 自主技术占有率，促 进自主c a d 系统特别是三维通用c a d 系统的普及和应用。 1 2 基于约束的g a d 技术概述 约束满足问题存在明显的领域性和多样性1 7 ，8 】，因此，研究普遍的约束满足问题意 义不大。基于约束的c a d 技术主要是指在几何设计领域，结合几何设计的特点，发 掘针对几何约束系统的约束分解和管理的有效机制。 基于约束的c a d 概念始于1 9 6 3 年。其时，麻省理工学院的s u t h e r l a n di e 1 9 j 在其 s k e t c h p a d 系统的研究中提出了基于约束的设计的概念，将c a d 的概念定位于约束满 足问题。然而，直到1 9 8 8 年p r o e 出现，基于约束的c a d 技术的强大威力才为人们 感受到。基于约束的c a d 系统一改传统c a d 系统的简单的辅助绘图思维，将设计目 标用一组约束关系来描述，并用这些约束来表达产品模型的形状特征，利用约束来控 2 华中科技大学博士学位论文 制设计过程与结果，从而使得设计过程的反复修改成为可能。基于约束的参数化设计 技术为初始设计、产品模型的修改、系列零件族的生成、多方案比较提供了强大的手 段，在工程绘图、实体造型、装配设计、公差分析与综合、机构分析和优化设计等领 域发挥着越来越大的作用l l 。 参数化设计( p a r a m e t r i cd e s i g n ) 和变量化设计( v a r i a t i o n a ld e s i g n ) 是基于约束 的设计方法的两种主要形式【1 。二者在实现的方法上存在着本质的差异。在参数化 设计系统中，所有约束方程的建立和求解都依赖于约束创建的顺序，每个几何元素根 据先前己知的几何元素来确定，参数的求解采用顺序求解策略，由前向后依次进行， 求解过程不能逆向进行，也就是说，约束求解是过程式的。正因为如此，参数化设计 方法难以调整约束之间的依赖关系和求解顺序，无法处理循环约束，因而最适合于无 需在方案上做反复修改的设计。变量化设计系统则具有更好的灵活性与操作性。其约 束的指定过程是陈述式的，没有先后之分。它通常采用并行求解的策略，通过求解一 组约束方程组来确定产品的几何形位，设计过程的修改不受限制。同时，由于工程约 束和几何约束在本质上的一致性，使得变量化设计方法的应用范围大大增加。但是， 这种策略带来的问题是，随着求解方法的不同，求解效率也会大不一样。随着约束求 解技术的发展，过去那种单向的过程式的方法已经逐渐为陈述式方法所取代。在平时， 我们一般仍旧把基于约束的设计方法统称为参数化方法。 1 2 1 几何约束求解方法研究 到目前为止，针对几何约束满足问题的求解已经发展了许多方法，这些方法各有 特色和侧重点，从而所面向的问题也有不同。而许多求解器则结合采用了这其中的某 几种方法，以达到提高求解器的求解能力和普适性的目的。 1 、数值方法 数值方法将约束转化为一组非线性方程组，然后采用迭代法整体求解。h i l l y a r d r c 【l7 】将约束系统表示为一组状态变量和一组约束方程，通过求解该约束方程组，就可 以得到状态变量，实现了几何约束满足问题向非线性方程组求解的转换。m i t 的 g o s s a r dd 【1 3 - 2 4 研究小组发展和完善了这一理论，并将其称为变量几何法( v a r i a t i o n a l g e o m e t r y ) 。该方法把几何形状定义成一系列的特征点，约束则表示成以特征点的坐标 为变元的非线性代数方程组，通过数值迭代方法求解非线性方程组，从而确定出系统 中几何元素的特征点坐标。 ：数值左法生韭线性绉鏖友强组的塞醒通整爰厦生夔= 拉置疆盗岱蓬e 煎约垂直撂 ， 华中科技大学博士学位论文 组为f ( x ) e ( x ) ，f 朋( x ) 】7 = 0 ，其中x 为设计变量，则相应的牛顿拉普逊迭代 公式为： x 。= x 。一中。1 ( x 。) f ( x 。) 其中， 中( x ) = c 筘l雳i ( 魏l砒 器 。穗、 a l反一 为约束方程组f ( x ) 的雅可比矩阵。求解过程从系统初值x 。开始迭代，直到满足 | | 。一x 。i i 占或者| | 只l | s ，其中为s 为计算精度。 牛顿一拉普逊迭代法可能会收敛到局部最小点，而且当方程组的雅可比矩阵奇异 时，该方法就不能使用，因此，l i g h t r 【2 0 l 运用一个修正的d o o l i t t e 方法以找到雅可比 矩阵的逆。n e v i l l ed t 2 s ) $ 1 采用最小二乘法求解非线性方程组，其特点在于无论约束模 式是否有效，算法总能给出一个最- b - 乘意义上的近似解。当只有局部变量值发生变 化时，l i nv c 【l8 】采用一种矩阵分块算法找到受影响最小的子约束方程组，以缩小问 题的规模，提高计算效率。另外，w i t l d n k f 1 2 6 用一个能量函数来表示约束，再利用 能量梯度法搜索到一个局部最小值。k i nyt 【2 ”利用基于扩展b o l t z m a n n 机的人工神 经网络技术，求解几何约束系统的非线性最优化问题。t h r o n t o n a c 【2 8 】采用模拟退火 算法求解大型等式和不等式约束方程组。s u t h e r l a n di e 1 9 】的s k e t c h p a d 则是首次采用 松弛迭代法求解的约束系统，和牛顿一拉普逊迭代法相比，松弛法速度较慢，但比较 通用。其它一些系统如t h i n g l a b l 2 9 j 0 】和m a g r i t t e t 3 t 3 2 l 也采用了松弛法。 在国内，向文 1 4 1 运用图论把约束网络分解成一组可以顺序求解的方程或方程组， 大量的线性和二次方程可以用精确的解析法求解，从而减小了联立非线性方程组的规 模。葛建新【3 3 】采用优化方法求解几何约束系统，利用成熟的优化求解方法，将几何约 束满足问题转化为优化问题求解。 数值法的好处在于其具有普遍性，能适应各种约束类型和约束形式，建模方法和 求解思路非常清晰，能不加区分地处理几何约束与工程约束，同时还能处理约束闭环 问题。但是，数值法的缺点也是显而易见的，主要有以下几点： a 、当采用牛顿迭代法时，对系统的初值要求很高，要求系统的初值距离问题的解 4 华中科技大学博士学位论文 竺竺! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! o ! ! ! ! ! ! 蔓_ _ _ _ 蔓蔓i _ - - - - _ 一i i _ _ _ _ _ _ _ - 一 不远。就是说，如果以系统的当前状态作为初始状态的话，要想求解器能顺利求解， 那么要求在系统的初始状态，各约束几乎都已经得到了满足。这点在二维几何设计中 可能算不上一个很严重的缺点，但对于三维几何系统，往往系统的初始状态离解很远， 此时就不得不考虑初值对求解的影响了。 b 、非线性约束方程组的解的数目通常为指数级，而一般的数值法往往只能找到其 中的一个解。因此，对于那些满足约束条件但实际上并不合适的解，数值法无能为力。 c 、数值法在几何概念层次上丢失信息过多，不具备几何可解释性：不能体现几何 约束所具有的传播特性，人为地扩大了求解的范围与规模。 2 、基于规则的构造方法 基于规则的约束求解来源于这样一个事实：绝大多数工程图都可以用尺规加量角 器作图来完成。其基本思想是从现有的已知约束中尽可能多地派生出新的知识，从而 将约束图形转化成可构造的形式。它运用一定的规则来建立和执行几何系统的构造步 骤，几何元素按照一定的顺序被求解，从而按照同样的顺序被构造出来。 b r u d e r l i nb 【3 4 1 的系统正是采用的这样的方式。而a l d e f e l db 的几何推理研究则 被公认是基于规则的几何推理求解的代 表。其采用一个基于符号推理和操作的 专家系统，建立了一个规则体系，将几 何约束关系以一介谓词的形式放入知识 库，通过推理机对知识库进行规则匹配， 逐步构造出整个图形，推理过程如图1 1 所示。 图1 1a l d e f e l d 法示意图 几何系统中各几何元素之间的关系称为事实，被包含于事实库中。事实库中最初 的内容是系统所拥有的的初始约束。通过规则推理，不断有新的事实被推理出来，这 些新的事实不断被添加到事实库中。规则库收集所有的推理规则。推理机是控制部分， 其任务是按某些策略选择规则并应用于现有事实。推理史则记录所有成功的推理过程。 该几何推理方法最为关键的任务在于模式匹配，即检验每个原子表在事实库中是否有 所对应。每当得到一个新的约束以后，启动推理过程，循环使用所有的推理规则，直 至没有新的事实产生，推理停止。 约束处理分为两个阶段： l 。约束读厶险段；盎且值终泉篮迭谣厶系统：更薤要塞崖：扈麴燕理扭：童旦墨畜 华中科技大学博士学位论文 j i l l 新的事实产生或者删除，递归地更新事实库与推理史。 2 后处理阶段：推理史根据推理过程和规则名得到相应的处理过程，形成构造计 划：执行该构造计划，就可以构造出整个系统。 目本东京大学k i l t i r i ae 1 3 “0 】的研究小组也采用了基于规则的构造方法，其约束来 源有二：一为系统模型自动生成，二为用户交互定义。该方法和r o l l e rd 【4 1 l 都对系统 的多解情况作了考虑，但对约束的一致性检验考虑不周。 基于规则的构造方法普遍具有几何关系的表达很清晰，知识和处理分离，规则库 的扩充性好，而且完全避免了数值算法的不稳定性的优点。a l d e f e l d 法还能避免约束 顺序对构造图形的影响，而且还利用相似性判定考虑了多解问题。但是，这种方法的 缺点也是很明显的：系统庞大，繁重的计算搜索与规则匹配给系统带来了很大的负担， 速度慢、效率低，而且无法处理循环约束。 在基于规则求解方面作出过深入研究的另外个人就是s u n d eg 【4 羽，在其p i c m e 系统的研究中，点、线段、圆( 弧) 构成基本几何元索，将几何元素间的约束关系划 分为关系集，然后利用产生式推理机构造几何图形。继p i c m e 之后，s u n d eg t 4 3 1 针对 约束的创建过程，提出了薪的基于规则的约束管理和求解策略，着重考虑了约束的一 致性问题。这种方法允许在不断施加约束的过程中修正图形，直至图形得到完全定义。 同时还能对过约束进行检测。s u n d e 的研究最大的特点在于他引入了两种集合： 1 、c a 集：两线段之间生成角度约束时，生成c a 集： 2 、c d 集：两点之间生成距离约束时，生成c d 集。 利用产生式规则不断合并各个c a 、c d 集，从而最终构造整个图形。合并的规则 为：如果两个c d 集有一个共同点，且它们之间在该点的角度确定，则这两个c d 集 合并为一个c d 集；如果两个c a 集共一条线段，则这两个c a 集合并为一个c a 集。 而且，通过判断某个约束的几何元素是否已经存在于一个c a 集或者c d 集，很容易 就能判断该约束是否为过约束。 s u n d e 用c a 、c d 集的合并过程来记录约束传播的过程不失为一种新颖有效的思 路，大大减少了纯专家系统所需的事实和规则数目。但其约束表达能力显然不能满足 各种类型丰富的几何形体的需要。4 7 1 。 3 、基于图论的构造方法 这种方法实际上是图论在构造方法中的应用。从总体上来说，可以将这种方法分 6 华中科技大学博士学位论文 为两步：首先它把几何约束系统抽象为几何约束图，通过分析约束图来推导出图形的 构造步骤1 4 舡5 3 】；然后按照构造步骤顺序求解，得到系统的解。图论研究方法的共同特 点是直接对几何实体的自由度进行分析，逐步选择能够满足的约束，用解析方法计算 相应的几何变换矩阵来实现约束满足。系统的分析和求解过程基于图论算法，理论严 密，速度快，效率很高，但对系统中出现的闭环约束还是需要借助于数值方法才能解 决。 f i t z r a l d w 【5 4 】构造了一种x 向和y 向的尺寸树来表达水平和竖直方向的距离约束， 通过判断尺寸树中的回路来判断系统中出现的多余约束。t o d de 1 55 j 则发展了f i t z r a l d 的尺寸树的概念，用图来表达几何约束系统，其中顶点表示几何元素，弧表示几何元 素之间的约束关系，使求解器的求解能力大为提高。d e c h t e r r | 5 6 - 5 7 1 提出了二元约束网 络来表达简单的几何图形。 在商业几何约束求解器d c m 中，o w e nj c 口8 】拓展了尺寸树的思想，引入了循环 尺寸约束。他分析了约束图的三连通部分，对每个三连通域，用符号代数方法分别求 解。求解过程是递归的，亦即旦某个三连通域已知，它就会在图上被归约为一个顶 点，并在归约图上成为其它三连通域的成员。然后在割点处递归进行连通块分解，按 分解的逆序求解每个子块，并按照维持几何实体之间拓扑关系的原则来处理多解情况。 这个方法最为关键的点是它只能处理尺规可构造( r u l e ra n dc o m p a s sc o n s t r u c t i b l e ) 的图形，o w e nj c 1 5 8 】指出，这种方法能处理所有的尺规可构造的点构型。与o w e n 的方法类似，h o f f m a nc 5 9 , 6 0 利用自下而上的搜索机制，采用图缩并的代数方法开发 了基于约束的描述语言e r e p ，并能让用户交互地选择所需要的解。 k r a m e rq 6 1 , 6 2 以刚体运动学为背景提出了几何约束系统的无向图表示法，结合自 由度分析，给出了简洁的链路搜索和环路搜索算法，较好地解决了一般低阶连杆机构 的分解和求解问题，但这种方法无法解决高阶杆组机构的复合约束模式。k r a m e r 的研 究强调几何约束传播应具备良好的可解释性，他首次明确地指出：“几何约束满足问题 的核心是实现约束的最大分解”。而且，他认为不同应用领域的几何约束问题应具有同 样的内在机制，如装配设计，参数化造型，参数化绘图及机构仿真等。在k r a m e r 的 几何约束求解器( g e o m e t r i c c o n s t r a i n t e n g i n e ) 中，用无向图中的顶点表示几何实体，称 为“顶点”( g e o m ) ，或者一组内部顶点已经确定的几何实体集，称“宏顶点” ( m a c r o g e o m s ) 。顶点和弧的权值分别记录各自的自由度与约束度。k r a m e r 的这种定义 方式较好地将几何实体、实体间的约束以及约束的求解方法结合了起来，初步将面向 华中科技大学博士学位论文 对象的思想引入了几何约束求解领域。 勋哪e r 的约束求解思路大致为：( 1 ) 实施链式搜索和环路搜索，确定无向图上的 宏顶点。( 2 ) 从约束变动的宏顶点出发，不断地寻找其上一层宏，并识别其约束模式， 调用相应的计算方法，从而得到问题的解。 之所以l 洫m e r 的方法无法解决高阶杆组机构的复合约束模式，是因为鼬 a m e r 并 没有提出宏的完备搜索方法。他提出的链、环两种模式只是所有宏模式的子集，在几 何约束领域，这两种模式通常存在解析解。同样，因为没能找出完备的宏顶点集， i k h a m e r 的几何约束求解器并未实现约束系统的最大分解，而退变为先最大程度地以封 闭形式求解，然后再进行数值迭代求解。另外，i h 锄e r 没有将基于变量的分解上升到 基于j l f j 实体分解的高度，从而降低了求解方法的几何可解释性。 陈立平【7 】和罗浩【”】采用约束的无向图表达方法，以面向对象的分析方法探讨了几 何约束系统的构成及表达，研究了几何约束系统所固有的串、并、耦并存的约束传播 机制。针对几何约束系统的特点，结合自由度分析，提出了饱和几何约束集的概念， 并以此为基础，提出了以简单归约集为核心的归约概念体系，找出了几何约束系统最 大归约的必要条件：最大归约一定简单归约。图1 2 所示为一个完全归约的操作过程。 同时，提出了理想结构矩阵的概念和虚拟基的技术，利用归约操作，将分解从变量层 次e 升列几何实体层次，从而使几何约束分解具备了良好的几何可解释性。并引入了 最优归约集的概念和评判方法，解决了几何约束系统的最大归约问题。对于其提出的 两类消极约束，给出了相应的检验策略。基于最大归约理论，陈立平对平面连杆机械 系统进行了研究，其方法可识别不可分解的复合约束求解模式，能自动识别阿苏尔杆 组和巴拉诺夫构型，解决高阶机构的分解问题。 图1 2 完全归约操作过程 ：堑金搓! 竺丛三维绘图凶登墨：埕出工由玉自约鏖生盛丛且值五蠢蕴亟直曲绉鏖直 8 华中科技大学博士学位论文 向图的方法，为构造全参数化的绘图系统奠定了算法基础。j a e y e o l l e e 6 4 发展了基于 自由度分析的图归约求解方法，使之适合于r c n c ( r u l e r - a n d c o m p a s s n o n - c o n s t r u c t i b l e 、 二维几何约束问题的求解。 然而，上述研究工作都尚未对欠约束系统分解的多态性做深入分析。而实际的设 计过程是一个逐步求精的过程，也就是说设计过程的大部分都是在欠约束状态中度过 的，所以深入研究欠约束问题有一定的理论意义和重要的实用价值。 4 、约束传播法 约束传播法在早期的约束求解器中较为盛行。在这种方法中，约束首先被转化为 约束方程组：然后生成约束无向图，在这个约束无向图中，顶点表示方程、方程中的 变量和常量：图中的弧表示变量和常量出现在哪个方程中，即表现了变量和常量与约 束方程的关系。传播法求解的思路就是从常量开始，沿着弧顺序地求解方程，一直得 到整个系统的解。为此，发展起来了许多约束传播的方法1 6 5 , 6 6 1 。但是，约束传播法并 不能保证能得到系统原本存在的解，而且不能处理循环约束。 5 、基于构造过程的方法 基于构造过程的方法属于过程式的方法，实际上几何系统设计本身就具有过程式 的特点，因此，这种方法也一直是几何约束研究的一个方向。该方法在图形输入的过 程中借助设计和造型的命令自动捕捉设计者的意 3 4 , 6 7 , 6 8 , 6 9 , 7 0 , 7 1 ，记录用户在设计过程 中的每一步操作。其基本思想是设计、造型操作与几何约束之间有着对应的关系，因 而操作过程能够用来管理和维护几何元素之间约束关系的内部数据结构，设计的修改 可以通过修改操作过程的某一参数得到。 r o s s i g n a cj r 1 6 7 , 6 3 1 ，c h u n gj i 7 0 7 1 ，c u g i n iu m 1 3 1 均基于标准数据结构c s g 和 b r e p ，让设计者以交互方式确定体素的刚体运动参数，并记录其过程。e m m e r i c km j 【7 4 7 5 ，7 6 谰控制点来决定3 d 几何，并由此生成几何树，当控制点发生变化时，几何树 上相应的节点的位置参数会发生变化。k o n d o 7 7 7 8 】贝0 针对几何操作与几何约束的对应 关系，用有向无环图来表达几何元素和几何操作过程，其实质是对作图过程的记录， 此方法不易扩展至复杂的几何约束系统。 r o l l e r d 【4 “7 1 扩展了传统c a d 系统的数据结构，引入了固定、可变和柔性这三种 类型的几何实体；通过对命令语义的推理，自动建立起几何实体之间的约束关系；跟 踪辅助线的添加来捕捉构造原则，然后根据构造顺序生成构造计划：最后执行构造计 划，得到系统图形。 9 华中科技大学博士学位论文 高小山【7 9 8 1 1 等提出了几何自动作图的全局延拓法，在绘图操作中引入了两种新 的作图工具：二次曲线与连杆。引入二次曲线后，二维作图范围从原来尺规作图可以 解二次系列方程组扩大到解次数小于等于四的系列代数方程，由于3 次、4 次方程可 以象2 次方程一样可以用根号显示求解，因此具体方程的求解困难并耒增加。高小山 还证明了使用一般的连杆作图等价于一般的构造性几何图形，即可以两两引进几何体 的图形。引入连杆作图工具，用四连杆解决了o w e n - h o f f r a a n n 方法不能解决的关系图。 在此基础上，高小山给出了基于关系图的新算法，对于无约束闭环的问题，可以给出 一个线性的判定与解决方法，对于有约束闭环的问题，给出了一个二次算法。算法的 复杂度与o w e n h o f f m a n n 的算法复杂度相同，但解题范围有所扩大。高小山的算法试 图用尺规作图和四连杆的数学理论，结合符号计算法与基于优化的数值法，解决约束 系统中的约束闭环、冗余约束与矛盾约束这难点。 向文f 】4 j 提出了集特征、约束、几何造型于一体的产品参数化模型，该模型将几何 约束分为2 d 陈述式约束与3 d 基于构造过程的约束，并在实际应用中取得了很好的效 果。 基于构造过程的方法对于结构相同而尺寸不同的零件设计十分有效。但是由于其 必须严格遵循构造过程，所以对于那些设计要求不断变化的设计环境则不太适用，而 且难以利用传统c a d 系统生成的图形。另外，无法处理耦合程度高的约束闭环问题。 由于空间问题的复杂性，三维参数化方法难以实现陈述式的表达、规划和求解，因此 早期的商用c a d 多采用基于几何模型构造过程的方法。 6 、符号代数法 同数值法类似，符号代数法也是首先将几何约束系统转化为代数方程组。所不同 的是，符号法求解所采用的是符号代数方法，比如g r t i b n e r 基方法【8 2 1 和吴方法阻洲。 b u c h a n a ns a 8 5 1 描述了一个定义点、线、圆( 弧) 的二维几何约束定义系统c d s ， 应用g r s b n e r 基方法对隐式方程组进行简化和排序，使约束方程组变为非耦合和低耦 合的方程组，通过求解一元方程，然后回溯迭代来逐步求解整个约束方程组。c d s 还 能识别和处理过约束、欠约束和矛盾约束方程组。k o n d o 7 7 , 7 s l 应用b u c h b e r g e r 算法处 理增加和删除的约束，并导出一个多项式表示增加和删除约束之间的关系。 符号代数法被广泛应用于几何定理的机器证明，在几何约束方程组的求解中也有 运用。但是，一般来说符号法求解具有指数级别的时间花费，因此效率不高，不利于 系统的实时交互。 1 0 华中科技大学博士学位论文 1 2 2 目前几何约束满足技术的应用状况 目前世界上最为成功的商用几何约束求解器当属d c u b e d 公司的d c m 。位于英 国剑桥的d c u b e d 公司是一家专门从事约束求解系统软件开发的公司。d - c u b e d 于 1 9 9 0 年推出其二维约束求解核心模块2 dd c m s 6 1 ，于1 9 9 4 年，推出三维约束求解模 块3 dd c m l 8 7 1 。d c m 基于o w e nj c 【5 8 ，8 8 】的图构造方法，o w e n 直接参与了d c m 的 开发。目前，国际上许多知名的c a d 系统开发商在自己开发约束求解器失败后，都 转而采用d c m 作为其几何约束求解核心，比如：d a s s a u l ts y s t e m e s 、a u t o d e s k 、 s o l i d w o r k s ，另外还包括p t c ( p a r a m e t r i ct e c h n o l o g yc r o p ) 的p r o e 。 实际上，最早成功应用参