（机械设计及理论专业论文）三维几何约束求解方法研究与实践.pdf

华中科技大学硕士学位论文 = = = ；= # = = = = = = = = = = = # = = = = = 一= ： ； 摘要 三维几何约束求解在装配设计、几何造型和动力学分析等领域有着广泛的应用。本 文对三维凡何约束求解的壤论和方法迸行了研究，实现了基予自由发翔约分轿的解析求 瓣和约轰阉环阉题懿数篷求鳃。 本文系统地总结了国内外几何约束求解的研究成果，对三维几何约康求解技术进彳亍 了深入地研究。首先借饕刚体动力学理论建立了三维几何约束模型，并利用欧挝参数 实现了刚体的空阅形位表达，采用有向图表达三维j l 何约束潮络；其次，给掰了检测豹 寨闭环懿算法，采薄爨适藏传攒策臻实磷求瓣痔裂翘掰；最黪，塞殄辑基本尼露嚣素溺 的约束关系对剐体自国度状态影赡的基础上，提出了剐体自由度的归约算法- 以此求得 满足约柬后刚体的自由状态空间，并以刚体自由度状态空间分析为基础实现了对合理约 束的解析求解和约束一致性维护。从而，避免了数值方法中对初始值和迭代多长的依赖， 提高了求辩效率。一手订 努一方瑟，为了宠聂孵摄袋嬲誉能瓣决约轰阙烬阉题鲍缺点，本文偻鉴多体系统蛇 运动副表达建立了常见工程约束的数学模型和三维基本几何约束的分量表达，采用扩展 n e w t o n - - r a p h s o n 方法求解装配设计中出现的约束闭环问题。 ，本文采用“鼹大解析+ 最小数值”的求解策略，通过有机遮统一解祈求解和数值求 解又掇离了三维死簿约隶系统酌求解效率程逶羯缝。采掰瑟趣对象翡方法，宠成了逶蹋 约哀求烬g l 攀e 默的三维约束求瓣模块设诗，其研究成粜在鸯自主知识版权的天喻三缎 c a d 软件的装配设计模块中得到了实际应用。力一y 一一 关键键：三维见 可终京，鑫出发羟约，囊由发分攒，瓣提求鳃，数值方法 _ h 一“。一、。 华中科技大学硕士学位论文 a b s t r a c t 3 d g e o m e t r i cc o n s t r a i n ts o l v i n gi so fg r e a ts i g n i f i c a n c et oa s s e m b l ed e s i g n ，g e o m e t r i c m o d e l i n ga n dk i n e m a t i c sa n a l y s i sa n ds oo n t h i st h e s i ss t u d i e st h et h e o r ya n da p p r o a c ho f t h e3 dg e o m e t r i cc o n s t r a i n ts o l v i n gd e e p l y 3 dg e o m e t r i cc o n s t r a i n ts o l v i n gb a s e do nd o f r e d u c t i o na n dt h e s o l v i n g o f g e o m e t r i c c o n s t r a i n t l o o p su s i n g n u m e r i cm e t h o da r e i m p l e m e n t e d r e l a t e dr e s e a r c h e so ng e o m e t r i cc o n s t r a i n ts o l v i n ga r er e v i e w e d f i r s t l y ，b a s e do nt h e r i g i db o d yd y n a m i c st h e o r yt h e3 dg e o m e t r i cc o n s t r a i n ti sm o d e l e d ，a n dt h es h a p ea n d p o s i t i o no ft h eg e o m e t r i ce l e m e n t si sd e f i n e db ye u l e rp a r a m e t e r s a tt h es a m et i m e ，t h e g e o m e t r i cc o n s t r a i n t sn e t w o r ki se x p r e s s e db yd i r e c t e dg r a p h s e c o n d l y , t h ea l g o r i t h mo f d e t e c t i o no fc l o s e dl o o pc o n s t r a i n t si sg i v e na n dt h es o l v i n gc o n s e q u e n c ei sc o n s t r u c t e db y s e l f - a d a p t a t i o ns t r a t e g y f i n a l l y , t h eb a s i cm a t i n gc o n s t r a i n t se f f e c to n t h er i g i db o d y sd o f s t a t ei sd i s c u s s e d ，a n dt h ed o fr e d u c t i o na l g o r i t h mt h a tc a ne a s i l yg e tt h er i g i db o d y sf r e e s p a c ea f t e rs a t i s f y i n gt h ec o n s t r a i n t si sp r o p o s e d b a s e do na b o v ed i s c u s s i o n ，t h ea n a l 【y t i c a l s o l v i n go fr e a s o n a b l ec o n s t r a i n t sa n dt h ec o n s t r a i n tc o n s i s t e n c ym a i n t e n a n c ea r e r e a l i z e d t h ea n a l y t i cs o l v i n gm e t h o da v o i d st h ed e p e n d e n c eo fn u m e r i c a la p p r o a c ho ni n i t i a lv a l u e a n di t e r a t e ds t e p ，a n ds o l v e st h e3 d g e o m e t r i c c o n s t r a i n t sm o r e e f f i c i e n t l y o nt h eo t h e rh a n d ，t h ee n g i n e e r i n gc o n s t r a i n t sa r em o d e l e du s i n gt h e m u l t i b o d y s y s t e m s k i n e m a t i c s j o i n tr e p r e s e n t a t i o n t h e n t h ee l e m e n tf u n c t i o no ft h eb a s i c3 d g e o m e t r i cc o n s t r a i n t si sb u i l t t h ee x t e n d e dn e w t o n - r a p h s o nm e t h o di su s e dt o s o l v et h e g e o m e t r i cc o n s t r a i n tl o o p s n u m e r i c a lm e t h o di sa b l et os o l v et h eg e o m e t r i c c o n s t r a i n tl o o p s a n da v o i d st h ed e f e c t so ft h eg e o m e t r i ca n a l y z i n g t h es t r a t e g yf o rs o l v i n g3 dg e o m e t r i cc o n s t r a i n t si nt h ed i s s e r t a t i o ni ss u f f i c i e n t l y a n a l y z i n ga n d l e a s tv a r i a b l e s t h u s ；i ti m p r o v e st h es y s t e m se f f i c i e n c ya n da p p l i c a b i l i t y t h e 3 dg e o m e t r i cc o n s t r a i n t s s o l v i n ge n g i n ec b ai si m p l e m e n t e dt h r o u l g i lo b j e c t - o r i e n t e d a p p r o a c h t h er e s e a r c hi n t h i st h e s i sh a sb e e na p p l i e dt ot h ea s s e m b l yd e s i g ns y s t e mi n t i a l l y u3 dc a ds o t t w a r e k e y w o r d s ：3 d g e o m e t r i cc o n s t r a i n t s ，d o fr e d u c t i o n ，d o fa n a l y s i s ，a n a l y t i cs o l v i n g ，n u m e r i c i i 华中科技大学硕士学位论文 1 1 课题的提出 1 绪论 设计阶段蕴含着一系列的不同特点的问题求解活动，设计问题本质上是一个约束满 足问题c s p ( c 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 ) ，即给定功能、结构、材料及制造等 方面的约束描述，求得满足设计要求的设计对象的细节。在传统c a d 系统的设计环境中， 几乎所有的设计问题都是由人类设计者解出的，而系统只是接受问题的解。新代c a d 哲理来源于当代设计理论、方法和模型研究的最新成果，也来源于虚拟现实、面向对象 和因特网等信息领域众多前沿技术的迅猛发展。当前，新一代c a d 研究和开发正经历着 从设计系统到设计环境，从基于几何到基于模型的革命性转变之中。设计模型是几何模 型与设计信息( 特征和约束) 的结合，设计模型比几何模型包含了更多的智能化因素， 可以更好、更完整地沟通设计意图，同时，设计信息在设计模型中也能够得到充分表达。 在诸多设计约束中，几何约束最具有基础性，是表达其它设计约束的基础，是约束 管理和求解技术中必须优先解决的问题。因此，几何约束管理和求解技术已成为当前 c a d 领域的项关键单元技术，是新一代c a d 技术的制高点，其重要性已被广泛认识。 研究和掌握几何约束管理和求解技术是开发具有自主知识产权的新一代c a d 系统的关 键所在。 在c a d 软件中，三维几何约束求解是其核心技术之一。在装配设计、几何造型和动 力学分析等领域有着广泛的应用。本文以三维几何约束的解析求解和数值求解为研究重 点，采用欧拉参数描述刚体的空间位姿，在分析基本几何实体间的约束关系对刚体自由 度状态空间影响的基础上，提出了自由度归约算法，运用此算法实现三维几何约束的解 析求解，同时，针对三维几何约束求解中出现的闭环问题采用数值方法求解。 本文的研究工作来源于科技部“十五”科技攻关计划项目“产品设计c a d 软件”的 支持( 任务书编号2 0 0 1 b a 2 0 i a 0 2 ) 以及天喻三维c a d 软件装配模块的研制需要。 1 2 国内外相关研究综述 约束是设计模型中的设计参数之间的关系的表达【n 。在设计领域，设计约束贯穿于 设计的各个阶段和方面，然而要给定其统一的表达和描述决非易事。因此，约束管理和 求解的形垄是主宣垒壁盟：至查垄塞苎：垫垡垄盛工丝壅笪型塑鲞塑堡鲨：查鎏婴壅塑 _ - _ - - - _ _ _ _ _ _ _ _ _ _ - _ _ _ _ _ - _ _ _ _ _ - _ - - _ _ _ _ _ _ _ _ _ _ - _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ - - 一 华中科技大学硕士学位论文 = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = 一 ： 多样性。 1 2 1基于图论的方法 该方法把几何约束系统抽象为几何约束图，通过分析约束图推导出一系列构造过 程，再根据这些构造步骤来导出几何体。 t o d d 2 1 用图来表达约束系统，其中顶点代表元素。r e q u i c h a l 3 1 和f i t z r a l d 4 1 构造了 一种x 向和y 向的尺寸树，如果树中出现了图( 即出现了封闭回路) ，则表明出现了多 余的尺寸约束。该方法只能处理水平和垂直方向的距离尺寸，因此只适用于简单的工程 图形。o w e n s - 6 l 引入了循环尺寸约束，拓展了这一方法。他把几何约束系统表达为一个 图并分析了约束图的三连通部分，对每个三连通域用符号代数方法分别求解。求解过程 是递归的，亦即一旦某个三连通域已知，它就会在图上被归约为一个顶点，并在归约图 上成为其它三连通域的成员。然后在割点处递归进行连通块分解，用分解的逆序进行求 解每个子块，并通过维持几何实体之间的拓扑关系来处理多解情况。董金祥【7 l 提出以有 向图来表达几何约束系统，提出了种新的约束求解思路。 k r a m e r 弘1 0 】的研究强调几何约束传播应具备良好的可解释性，指出“几何约束满足 问题的核心是实现约束的最大分解”，虽然其研究内容侧重于刚体运动学，但提出某些 不同应用领域的几何约束问题应具有同样的内在机制，如装配设计、参数化造型、参数 化绘图及机构仿真。k r a m 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 r o 条件的几何实体集，并记为m a c r o 顶点。( 2 ) 从约束变动的宏m a c r o 出发，不断 地寻找上一层宏，并识别其约束模式，调用相应的计算方法，得到问题的解。 k r a m e r 并未提出宏的完备搜索方法，以平面连杆机构问题为例，链式搜索和环路 搜索仅能在约束图上找出链、环两种宏模式，见图1 1 。 图1 1 链、环模式 链、环两种模式只是所有宏模式的子集，在几何约束领域，这两种模式通常存在解 析解。因为没能找出完备的m a c r o g e o m 集，k r a m e r 的几何约束机最终并未实现约束系 统的最大分解，而退交为先最大程度地以封闭形式求解，然后再进行数值迭代的求解方 法址a m e t 五法在在西企回题。笛= 。他没直给出月纽约束系统显太盆鲤的判挹；第 2 华中科技大学硕士学位论文 = = = = ；= = ；= = = = = = = # = = = = = j = = = = = = = = 一= 二，他没有把基于变量的分解上升到基于几何实体分解的高度来解决几何约束系统的最 大分解问题。 陈立平。2 1 和罗浩1 1 3 基于对机构运动规律的深入分析和大规模稀疏矩阵分解的数 学成果的成功运用，提出几何约束系统最大归约理论，把从基于方程组的变量的分解上 升到了几何实体分解的层次，并给出了几何约束系统最大分解的判据，实现了几何约束 系统的最大分解。 图论研究方法的共同特点是直接对几何实体的自由度进行分析，逐步选择能够满足 的约束，用解析方法计算相应的几何变换矩阵，来实现约束满足。由于基于图论理论， 因而该方法理论严密，速度快，效率很高。但是，基于图论的方法都需要借助于数值方 法才能解决闭环约束问题。 1 2 2 数值求解方法 这是一种面向非线性方程组整体求解的代数方法，最早是由英国剑桥大学的 h i t l y a r d p 4 1 提出，m i t 的g o s s a r d 1 5 - 1 5 1 研究小组发展和完善了这一理论，称为变量几何 法( v a r i a t i o n a lg e o m e t r y ) 。该方法把几何形状定义成一系列的特征点，约束则表示 成以特征点坐标为变元的非线性代数方程组，通过数值迭代方法求解非线性方程组，从 而确定出几何细节。非线性方程组的求解通常基于n e w t o n - r a p h s o n i 迭代法，它是牛顿法 的一种改进。将非线性方程组表示成： f ( x ) = 0 ，其中：x = ( x ，) ，一，f = ( ) ，s m 对于初值x o ，第n + 1 次迭代的x ”1 值由以下迭代公式得到： 其中 令： 则有： j ”1 = x ”一【f ( j ”) 】_ l f ( j ”) f ( j n ) ：( 要( z 一) ) 。；。 c 历f 醢= x “一x n f f ( x ”) a x = 一，( j ”) 1 并：必+ x 一 我们于是得到：r z = f 华中科技大学硕士学位论文 = = = = = = = = = = = ；= = = = = = = = ；= 一- 其中， j = 窃7 l 毳l 西2 反l d a i 屠7 l 反2 臼7 l 赢 固 玩 为j a c o b i a n 矩阵。 x = 沁一，x z ， r ，表示各个变量的微小位移。 ，= - f r f 2 一n ，表示方程组的残差。 经过反复迭代，直至i 爿l s ，就得n t 方程组的解。约束集的有效性可以通过判 断j a c o b i a n 矩阵的秩来实现。 n e w t o n r a p h s o n 迭代法由于其二次收敛速度比较常用，但有可能收敛到局部最小 点，在约束求解中通常是把初始图形作为迭代的初始状态，以避免这种情况的出现。当 方程组的雅可比矩阵奇异时，n e w t o n - r a p b s o n 方法就不能使用。因此，l i g h t 1 9 1 运用一 个修正的d o o l i t t e 方法以找到雅可比矩阵的逆。w i t k i n 【2 0 l 用一个能量函数表示约束， 再利用能量梯度法搜索到一个局部最小值。n e v i l l e l 2 1 1 提出了采用最4 , - 乘法求解非线 性方程组的算法，其特点在于无论约束模式有效与否，总能给出一个最4 , - 乘意义上的 近似解。a n n a f 2 2 】采用模拟退火算法求解大型等式和不等式约束方程组。向文运用图 论把约束网络分解成一组可以顺序求解的方程或方程组，大量的线性和二次方程可以用 精确的解析法求解，从而减小了联立非线性方程组的规模。郭建新 2 4 j 将约束问题转化 为优化问题，改进的迭代公式变为：x “1 = x 4 一p ；以 4 - 九j j _ 。f f 伍4 ) ，通常采用计 算优化函数的梯度向量的零点来获得优化函数的极小点或b f g s 法求解【2 5 】 数值法的优点在于其具有普遍性，能适应各种约束类型和约束形式，建模方法和求 解思路非常清晰，能不加区分地处理几何约束与工程约束，同时还能处理约束闭环问题。 但是，数值法的缺点也是显而易见的，主要有以下几点： a 、当采用牛顿迭代法时，对系统的初值要求很高，要求系统的初值距离问题的解 不远。就是说，如果以系统的当前状态作为初始状态的话，要想求解器能顺利求解，那 么要求在系统的初始状态，各约束几乎都已经得到了满足。这点在二维几何设计中可能 不是一个很严重的缺点，但对于三维几何系统，往往系统的初始状态离解很远，此时就 不得不考虑初值对求解的影响。 b 。非线性约衷左程组曲鲤曲数目通堂浊指数级。顽= 般的数值法往往县能找到其 4 华中科技大学硕士学位论文 中的一个解。因此，对于那些满足约束条件但实际上并不合适的解，数值法无能为力。 c 、数值法在几何概念层次上丢失信息过多，不具备几何可解释性，而且不能体现 几何约束所具有的传播特性，人为地扩大了求解的范围与规模。 1 2 3 符号代数法 符号代数方法也称数学机械化方法，它是利用数学机械化方法来决定约束方程组有 效求解的顺序 2 6 - 2 7 1 。如应用g r s b n e r 基【2 8 1 和吴方法【2 9 3 0 1 将方程组求解出来。b u c h a n a n 描述了个定义点、线、圆和圆弧的几何约束定义系统c d s ，应用g r s b n e r 基方法对隐 式方程组进行简化和排序，使约束方程组变为非耦合和低耦合的方程组，通过求解单元 方程，然后回溯迭代来逐步求解整个约束方程组。c d s 还能识别和处理过约束、欠约束 和矛盾的方程组。 基于符号代数的方法为许多几何约束满足问题提供了完备的解决方法1 3 ”，在理论 上可以准确判定一个非线性联立方程组有无解、有否无穷多解以及在有有限多个解时可 求出全部解丽无增无漏，但在效率上有待进一步改进。 1 2 4 基于规则的几何推理方法 基于规则的几何推理方法运用规则来建立和执行构造步骤，又称为规则一构造式求 解方法。它基于这样一个事实，即在工程图中的绝大多数情况都可以通过直尺、圆规和 量角器绘出。约束通过构造的方式得到满足，这样对用户来说更显得自然而且适合于交 互式查错。 a l d e f e l d 【3 3 1 采用一个基于符号推理和操作的专家系统，建立了一个规则体系，将 几何形体的约束关系用一阶逻辑谓词描述，存入知识库中。系统从知识库中提取出有关 信息，通过推理机逐步推导出几何细节。推理示意图如下： 约柬 图1 2a l d e f e l d 法示意图 事实库包含某特定几何模型的知识，初始内容是给定的约束，通过规则推理出的事 实不断累加。规则库收集所有规则，通常仅有一个规则子集作用于某给定模型，但预先 华中科技大学硕士学位论文 = = = = 2 = = = = = = = = = = = = = = = = = = = = = 2 = = = = 一= ： 无法知道。推理机是控制部分，其任务是按某些策略选择规则并应用于现有事实。处理 的中心点在于模式匹配，即检验每个原子表在事实库中是否有所对应。推理的结论成为 新的事实。推理史记录了所有成功的规则应用。 基本思想是从现有的已知约束中派生出尽可能多的知识。因此每当一个新的约束 得到后，推理过程启动，所有规则循环使用，直至没有新的事实产生。约束处理分为 两个阶段： 1 几何约束一读入系统，并加入事实库，启动推理机，所有可派生的事实存入 系统。一旦某个约束被删除，推理回溯。 2 在后处理阶段，推理史输出重建步骤，把规则名翻译成相应的处理过程，形成 构造计划，一步步执行，从而构造出整个几何体。 s u z u k i 和k i m u r a l 3 4 - 3 6 1 等提出了一个面向对象的几何推理方法，它允许在用户构造 设计模型的同时，自动生成约束关系的谓词描述。同a l d e f e l d 法类似，也是通过推理机 对知识库进行规则匹配，逐步构造出整个图形。 葛建新等【3 7 l 提出一种利用自由度亏损方法依次导出几何元素的求解次序，基本思 想是几何元素的确定过程即该元素自由度下降的过程，当自由度下降为零时，该几何元 素也就完全确定下来，它还可以用来导出其它相关联的未知元素。因而，算法的整个过 程就是不停地搜索可用约束以减少该约束特定几何元素的自由度。高嘿明、彭群生等口引 将几何约束蕴含于图形数据结构，通过程序对尺寸约束进行快速几何推理，比建立专家 系统进行推理效率更高，实用性更强。黄长林、陆国栋等【3 9 - 4 0 采用一种基于变量流技术 的变量推理方法，在交互作图的过程中同步建立图形结构约束。它将约束封闭于几个图 形元素之间，因此约束具有局限性，便于修改和求解。 上述方法具有基于规则的方法的优点，诸如几何知识清晰的表示、知识和处理的分 离、规则库的扩充性，而且完全避免了数值算法的不稳定性。然而，系统庞大、速度慢、 无法处理循环约束等也是该方法的明显不足。 1 2 5 基于构造过程的方法 基于构造过程的方法在图形输入的过程中借助造型命令自动捕捉设计者的意图。这 种方法记录了用户在造型过程中的每一步操作，基本思想是造型操作与几何约束之间有 着对应的关系，造型过程能够用来管理和维护反应几何元素之间约束关系的内部数据结 构，设计的修改可以通过修改造型过程的某一参数得到。 r o l l e r 【4 l - 4 2 】扩展了传统c a d 系统的数据结构，以便更好地捕捉设计者的意图，其 主要作法包括： 6 华中科技大学硕士学位论文 = = = = = ；= = = = = = = = = = ；= = = = = = = = = 一 1 引入三种类型的几何实体：固定的、可变的和柔性的； 2 通过对命令语义的推理，自动建立几何约束关系； 3 跟踪构造几何体( 辅助线) 的使用，捕捉构造原则； 4 存储构造顺序； 5 生成由传统c a d 的命令组成的构造计划； 6 对于给定的某一组尺寸参数，执行构造计划。 高小山h 卜4 5 】等提出了几何自动作图的全局延拓法，在绘图操作中引入了两种新的 作图工具：二次曲线与连杆。引入二次曲线后，二维作图范围从原来尺规作图可以解二 次系列方程组扩大到解次数小于等于四的系列代数方程，由于3 次、4 次方程可以象2 次方程一样可以显示求解，因此具体方程的求解难度并未增加。高小山还证明了使用一 般的连杆作图等价于一般的构造性几何图形，即可以两两引进几何体的图形。引入连杆 作图工具，用四连杆解决了o w e n h o f f m a n n 方法不能解决的关系图。在此基础上，高小 山给出了基于关系图的新算法，对于无约束闭环的问题，可以给出一个线性的判定与解 决方法，对于有约束闭环的问题，给出了一个二次算法。算法的复杂度与o w e n h o f f m a n n 的算法复杂度相同，但解题范围有所扩大。高小山试图用尺规作图和四连杆的数学理论， 结合符号计算法与基于优化的数值法，解决约束系统中的约束闭环、冗余约束与矛盾约 束这一难点。 基于构造过程的方法，对于结构相同尺寸不同的零件设计是十分有效的。但是由于 必须严格遵循构造过程，对于那些设计要求不断变化的设计环境则不太适用，而且难以 利用传统c a d 系统生成的图形。另外，无法处理耦合度高的约束闭环的情形。由于空间 问题的复杂性，三维参数化方法难以实现陈述式的表达、规划和求解，因此早期的商用 c a d 多采用基于几何模型构造过程的方法。 1 2 6 几何约束管理和求解技术应用研究的最新进展 作为新一代c a d 系统的关键技术，美国p t c 公司于1 9 9 8 年推出参数化造型系统 p r o e n g i n e e r 后，基于约束的参数化特征造型成为c a d 公司应用技术研究的热点。 位于英国剑桥的d - - c u b e d 公司是一家专门从事约束求解系统软件开发的公司。 d - c u b e d 采用基于o w e n 的算法，在1 9 9 0 年就推出了二维约束求解核心模块2 dd c m l 6 j ， 并于1 9 9 4 年推出了三维约束求解模块3 0d c m 。在2 0 0 1 年1 1 月推出的a e m 【4 7 j ( a s s e m b l y e n g i n e e r i n g m a n a g e r ) 在实时冲突检测、三维约束的自动添加和删除、三维约束求解技 术、实时仿真等方面都有新的突破。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 o l i d w o r k s 等国际著名的c a d 公司所广泛采用。 华中科技大学硕士学位论文 1 3 本文工作及论文组织结构 本文研究是在基于有向图的三维几何约束模型上，以刚体上的点、线、面、圆柱面 等基本三维几何实体为研究对象，提出了剐体自由度的归约算法以求得满足约束后剐体 的自由度状态空间，以刚体自由度状态空间分析为基础实现对合理约束的解析求解和约 束一致性维护，这样可以实现在不破坏原有约束关系的前提下满足新的约束关系。实现 增量式地求解。同时，针对三维几何约束求解中出现的约束闭环问题，采用数值方法进 行求解。采用“最大解析+ 最小数值”的求解策略，实现了解析方法与数值方法的统一， 提高了三维几何约束求解系统的效率、稳定性以及适用范围。本文研究成果可应用于三 维参数化设计和装配设计领域，同时也可应用于对机构分析装配工艺规划和d f a 等多个 领域。 本文的组织结构如下： l ：简述课题的来源、意义，国内外相关研究工作以及本文的研究工作和论文结构； 2 ：运用面向对象的技术建立三维几何约束模型，采用有向图表达三维几何约束网 络，介绍了约束网络图的求解序列规划； 3 ：在自由度分析的基础上，提出了刚体的自由度归约算法，利用该算法实现了三 维几何约束的解析求解和冗余约束与矛盾约束的检测； 4 ：针对约束闭环问题，建立约束的分量方程表达并映射成代数约束方程组，采用 扩展n e w t o n - - r a p h s o n 方法进行数值迭代求解； 5 ：原型系统开发与应用实例； 6 ：全文总结与展望。 华中科技大学硕士学位论文 = = ；= = ；= = = = = = = = 2 = = = = ；= 一 2 1 概述 2 三维几何约束系统建模与求解概述 在三维几何约束系统中，三维几何约束模型的表达、几何实体空间位姿的表达以及 求解序列规划都是实现三维几何约束系统求解的基础。 2 2 三维几何约束系统的对象空间 面向对象建模的第一步是发现问题域中的基本对象，把具有共同特征的对象归结为 一类。对于三维几何约束系统。它的主要目的是提供三维几何约束的管理和求解功能。 因此，在三维几何约束系统中，为了管理和求解三维几何约束，引入三维几何约束模型 和约束求解器两个对象，三维几何约束模型中记录了三维几何实体以及它们之间的约束 关系，并且能够维护这些约束关系，包括添加、删除和修改等。三维几何约束求解器用 来求解这些几何约束关系，包括数值求解方法和解析求解方法。同时，三维几何实体是 三维几何约束的载体，三维几何约束是用来提供服务的对象，也是服务的结果，它们很 自然地是系统的基本对象。这四个对象构成了三维几何约束系统的基本对象空间，如图 2 1 所示。 图2 1 三维几何约束系统的基本对象空间 2 3 基于有向图的三维几何约束模型 装配体的配合联结信息是构成装配体的所有零部件的互相关联的信息，它包括三维 几何约束关系和拓扑联接关系。三维几何约束就是装配体各零部件的配合关系，它把零 部件约束在某个三维几何空间中，使这些零部件只能在此特定的三维空间中或固定或运 9 华中科技大学硕士学位论文 = = = = = = ；= = = = = = = = = = = = = = = = = = = = = = = = 一一 动。零部件之间的几何空间关系是种拓扑联结关系，它描述的是一个零件在另个零 件的内部、外部、上面、下面等的定性关系和它们之间的距离、角度等定量关系。这种 关系可以通过约束关系来描述，最终反映到零件的基本几何元素上。 几何约束系统的约束表达方式有很多种，如代数方程映射、图表达方法等。 从本质上来讲，约束就是方程。代数方程映射将一个几何约束系统映射为一个代数 方程组，通过代数方程组的求解来得到问题的解。因此，代数方程映射方式反映了约束 系统的本质。这种方法简单直观，但由于映射是单向的，映射得到的代数方程组不能反 映系统的几何意义，缺乏良好的几何可解释性。 图表达方法利用图结构中节点之间的关系来表达几何约束系统内的约束关系。由于 图中节点之间的关系是任意的，而且图论算法成熟高效，存储结构紧凑，特别是图方法 具有良好的几何可解释性，因而，在实际应用中得到了广泛的应用，其缺陷在于表达多 元约束较为麻烦。 图表达方法分为有向图表达方法与无向图表达方法。从本质上来说，约束是无方 向的，几何实体之间的约束关系是相互的，不存在谁约束谁的问题。但是，约束的传播 是有方向的，也就是说，某个顶点的几何条件发生改变时，它会沿着一定的路径影响该 路径上的顶点。显然，无向图不能体现这种特点。几何约束系统的规划和分解过程。从 根本上来讲就是约束传播的路径问题。因此，用有向图来表达几何约束系统更能够表达 约束系统规划和分解的实际过程，也更具有几何可解释性。同时，利用约束有向图可以 很方便地判断出几何约束的状态是完备的、还是欠约束的或者是过约束的。利用有向弧 的方向性，对某个约束的变化包括约束值的变化和约束的增删，可将其影响范围控 制在尽量小的局部范围，这样将几何约束系统的求解规模从整体降至局部，从而大大降 低了计算复杂度，提高了系统的求解效率。 因此，本文采用有向图来表达几何约束系统，称之为几何约束网络f e n ( g e o m e t r i c c o n s t r a i n tn e t w o r k ) f 4 8 】。 g c n = ( e ，r ，w ) 其中：e = ee 为几何实体) ； r = f ie 。，e j 之间存在几何约束，e t e ，e j e e ，i j ； w = ( w g ，w e ) ，w g 为实体顶点的权值，记录该顶点的自由度，w c 为约束关系弧的权值，记录该弧两端的实体之间的约束度。 图2 2 所示的是一个千斤顶装配图，其各个零部件之间的约束关系即几何约束网络 如图2 3 所示。 1 0 华中科技大学硕士学位论文 一一一一2 一一 图2 2 千斤顶装配图 图2 3 千斤顶j i a , , g 约束网络图 华中科技大学硕士学位论文 = = 2 ；= = 一= = 2 4 几何实体的欧拉参数表达 2 4 i 空i 司刚体的位置表达 从刚体动力学的知识知道，剐体的一般运动可以分解为刚体质心的平动和绕质 心的转动。在装配设计中，通过零件的旋转和平移使它满足装配约束关系。因此，刚体 的位置是三维几何约束求解的最终结果，刚体上的几何实体的形状和位置则相对于刚体 的位置而决定。 对于约束求解中的几何实体，由欧拉定理知，其方位可以通过固定于刚体上的局部 坐标d 夕_ 的原点位置和o ，f 相对于全局坐标系o x y z 的有限转动来表达，见图2 4 ， 这个有限转动可以由方向余弦矩阵彳确定。 图2 4 刚体及其局部坐标 因此，刚体上任意一点p 可以表达为： r 9 = r + a s 。9 ( 2 1 ) 这里表达有限转动的方向余弦矩阵为： a l l a 1 2 1 a = i 口2 l 口2 2 口2 3i l 口3 l 口3 2 口”j ( 2 2 ) 在三维几何约束系统的求解中，可以从三维几何模型得到齐次变换矩阵，包括方向 余弦矩阵a 和平移向量，。刚体的空间位置表示为它在几何约束模型中的局部坐标 l o c a l c o o r d i n a t e s ，其中，t r a n s l a t i o n 为从全局坐标原点到局 部坐标原点的平移矢量，r o t a t i o n 为局部坐标相对于全局坐标的旋转变换矩阵彳。 华中科技大学硕士学位论文 = = 2 = = = = = 2 = ； 2 4 2 欧拉参数的性质 在计算机图形学中，方向余弦矩阵是几何实体的旋转变换矩阵，对于几何约束系统 求解来说，相当直观方便，但方向余弦矩阵并没有确定描述空间刚体方位所需要的独立 参数。 根据欧拉定理5 0 1 ，空间刚体的方位可用刚体的局部坐标系o x t v z ，和绕某一单位向 量，的有限转动量0 描述，卵图2 5 。 图2 5 刚体的有限转动 考察全局坐标她弦中的单位向量( j ，工肋和局部坐标系o _ 掣中的单位向量( c 岛 之间通过u 的变换，得到它们的关系式： ，= ，c z c 。s 2 詈一，+ z “c u r i ，s ；n 2 罢+ z 石，s ；n 罢c 。s 詈 g = j ( 2 e o s 2 詈一1 ) + 2 “( “7 ，) s i n 2 詈+ 2 可s i n 詈c 。s 罢 一= t ( 2 c o s z 罢一，+ 2 “c ”7 七) s i n 2 詈+ z 嚣ts t n 兰c 。s 詈 氏叫0 8 i 卧心 e r e = e ；+ p ? + e ；+ e ；= 1 ( 2 3 ) ( 2 4 ) ( 2 5 ) 华中科技大学硕士学位论文 i2 k ：+ e 1 2 ) l 2 e p ：+ 岛) 2 g 。岛e 。e ：) a - - i2 0 ，p ：一p 。e ，) 2 t ：+ p ；) 一1 2 q ：e ，+ e o e t ) ( 2 6 ) 【2 “巳+ 印：) 2 也e ，- - e o e l ) 2 p ：+ e ；) 一1i 同理，也可以由方向余弦矩阵彳得到欧拉参数 石万玎 氏5 t p ；塑蛰二丝 虹剑 2 7 。 4 p o 厶：塑! 鱼! 。 4 e o 在几何约束系统的求解中，可以从几何模型得到表达几何实体局部坐标的齐次变换 矩阵，去除平移分量之后，得到该几何实体的方向余弦矩阵a ，由公式( 2 7 ) 可以得到 欧拉参数。 2 , 4 3 三维几何实体的欧拉参数表达 对于一个空间刚体，可以把它分解为多个基本几何实体。由于c a d 系统中的几何实 体采用b - r e p 表达，可以分解为几何实体的复合即刚体可以分解为点、线、面的基本表 达。对于二维几何约束系统，可以分解为点、直线、圆、圆弧、椭圆等几类基本几何实 体；对于三维几何约束系统，可以分解为点、直线、平面、柱面、球面等基本几何实体。 下面以图2 6 的平面为例来说明几何实体的欧拉参数表达。 图2 6 空间中的平面及其局部坐标系 华中科技大学硕士学位论文 采用面向对象表达的思想，平面可以用平面上的一点p 和单位法向量v 表达，对于 点p ，由式( 2 1 ) 得：r 9 = r + a s 。，其中a 9 是用欧拉参数表示的方向余弦矩阵。对于 法向量v ，v = a 矿，其中a ”是用欧拉参数表示的方向余弦矩阵。因此，所有基本几 何实体都可以表达为欧拉参数的方式，见表2 1 ： 表2 i 三维几何实体的欧拉参数表达 几何实体边界表示欧拉参数 点 p ( x ，y ，z ) r p = r + a p s 。9 直线 p 为定义点，v 为方向向量 一：r + a p s 9v = a v ， 平面 p 为定义点，y 为法向量 r p ：r + a p s 9v = a v p 为定义点 r p = r + a p s 9v = a v v 为方向向量 柱面 r 4 = r + a w 9 叫s v 1 = ，r 为半径 q 为柱面上任意一点 p 为球心点 r p ：r + a p s 9 球面 r 为半径 q 为球面上任意一点r 9 = r + a w 9 且h = r 采用欧拉参数表达几何实体的空间位姿，避免了采用其它广义坐标系在约束求解中 出现的奇点和非线性问题。 2 5 求解序列规划 g c s p 的解决通常包含求解序列规划和求解两个重要方面。规划的目的是导出一个 正确的求解步骤，以利于求解快速准确地进行，它是求解的基础。在实际问题中往往会 出现高阶的求解模式，求解步骤不再是简单的线性序列。因而，采用几何解析方法无法 满足要求。这时若采用非线性方程组整体求解，由于联立求解的方程组规模太大，使求 解的速度和稳定性大大下降。k r a m e r 的研究强调指出“几何约束满足问题的核心是实 现约束的最大分解”，即寻求一个良好的求解序列。因此，良好的求解序列对于提高系 统的处理能力、可靠性和效率都是至关重要的。 1 5 华中科技大学硕士学位论文 = = = ；= = = = = = = = 2 = = = = = = = = = = = = = = = = = 一一 几何约束系统的本质在于约束的传播，在几何层次上发掘其约束传播机制应当是几 何约束系统的关键。 几何约束传播的时序不外乎下列三种： 1 串行机制：问题b 以问题a 为先决条件，必须先求解a ，然后求解b ： 2 并行机制：问题a ， ，y ，彼此无关，求解的顺序互不影响； 3 耦合机制：问题a ， ，y ，互为依存，互为先决条件，需联立求解； 在几何约束系统的约束传播中存在上述三种机制，关键问题在于三种约束传播机制 如何协作规划，并且在几何约束的传播过程中，保证几何约束系统的一致性和无矛盾性。 在几何约束网络中，几何约束的传播表现为约束沿着有向图的弧进行传播。通过优化调 整改变约束传播的路径来获取求解序列。 2 5 1 约束传播的自由度条件 几何约束的传播首先是基于自由度的，即约束传播首先要满足几何实体的自由度条 件。也就是说，对于几何约束网络中的任何一个实体g ，它受到的约束度要小于或等于 它的自由度，即o o