三维实体造型技术-第一部分-3.doc

第 6 节 参数化设计前面谈到的造型技术在具体应用于一个产品模型后，形成了固定的模型数据,当需要改变产品模型的某一数据时，只有删除该模型，再重新进行模型的造型设计。这对于同类产品不同型号的产品设计造成了极大的不便。因而在目前流行的 CAD 系统中又创造应用了参数化设计技术，可以对已有产品模型的数据进行修改，以形成新的产品模型，从而加快产品设计的速度。在新产品的研制过程中，约70%80% 的成本耗费于设计阶段，因此，如何开发、研究先进的设计方法和工具以提高产品设计的效率是至关重要的。设计是创造性的活动，需经多次循环而逐步求精。无论是全新设计或是局部更新设计，设计师总是在设计要求等条件的限制下，自设计开始的概念设计阶段，便开始将其设计活动勾画在图纸之上。从概念到具体的结构设计，设计师的几乎所有创作活动都蕴含于产品图纸(含电子图档)的演变与衍生之中。虽然图形的生成与演变在设计活动中占有基础性的地位，但并非设计活动的基本特征和本质表现。人工智能学研究认为：设计问题是约束满足问题(CSP：constraint satisfaction problem), 即给定功能、结构、材料及制造等方面的约束描述，求得设计对象的细节。由此而生的参数化设计就是：用几何约束、工程方程与关系来说明产品模型的形状特征，从而达到设计一簇在形状或功能上具有相似性的设计方案。目前能处理的几何约束类型基本上是组成产品形体的几何实体公称尺寸关系和尺寸之间的工程关系。参数化设计的关键是：几何约束关系的提取和表达、几何约束的求解以及参数化几何模型的构造。目前，二维参数化设计技术已发展得较为成熟，在参数化绘图方面已得到了广泛应用。而三维参数化造型能处理的问题还比较简单，能处理的类型主要是轴线、平面和轴对称面；能处理的约束类型还很有限，如：(1) 两个或多个平面间的垂直距离；(2) 两个或多个轴线间的垂直距离；(3) 两个或多个平面间的角度；(4) 轴和平面间的垂直距离；(5) 两个或多个轴线间的角度；(6) 轴和平面间的角度；(7) 轴对称面的半径等。在参数化设计中，几何约束关系的表示形式主要有：(1) 由算术运算符、逻辑比较运算符和标准数学函数组成的等式或不等式关系。它们可以在参数化造型系统的命令窗口中直接以命令行形式输入。(2) 曲线关系。直接把物理实验曲线或其他特性曲线用于几何造型。(3) 关系文件。它是许多关系命令行语句和特定语句的集合。多种几何约束关系，包括联立方程组可以写成一种特定格式的文件(即用户编程), 输入到计算机中，成批驱动几何设计。例如，确定一个立方体的长、宽、高的约束条件可以是：立方体的底面积等于 100, 底面周长等于 50 。(4) 面向人工智能的知识表达方式。这种方式将组成几何形体的约束关系、几何与拓扑结构用一阶逻辑谓词的形式描述，并写人知识库中。知识表达的方式：一方面是以符号化形式表达各种类型的数据，求取符号解；另一方面是加上基于约束的几何推理，求取数值解，从而可在更高程度上实现机械产品的智能设计。本节在简述参数化设计相关概念的基础上，介绍参数化设计的约束推理/求解算法。最后给出一种典型的参数化设计的应用实例。 一基于约束的参数化设计概述基于约束的 CAD 系统并不是传统 CAD 系统的简单扩展，而是以一种全新的思维和方式来进行产品的创新和修改设计。它用约束来表达产品模型的形状特征，定义一组参数以控制设计结果，从而能够通过调整参数来修改设计、模型，并能方便地创建一系列在形状或功能上相似的设计方案。 在设计过程中，参数化草图输入大大提高了图形输入和几何造型的效率；产品模型的修改通过尺寸驱动或参数驱动实现。给定几组参数值便可实现系列零件或部件的自动生成，约束的修改使对设计目标依赖关系的描述成为可能。基于约束的参数化变量化设计技术为初始设计、产品模型的修改、系列零件族的生成、多方案比较等提供了强有力的手段，在工程绘图、实体造型、装配、公差分析与综合、机构仿真、优化设计、数控加工(NC) 等领域发挥着越来越大的作用。1参数化设计与变量化设计参数化设计：是指在构造产品模型时，模型结构在保持模型拓扑关系不变的前提下，可随尺寸参数或工程参数的具体数值变化而自动改变，形成新的产品模型。图 6-1 为一个实体模型的视图。用参数化设计系统构造此实体模型时，系统将定义各尺寸为参数变量名 X、Y、U、V、D 等，当设计者改变参数变量 U、V、D 分别为 150mm、200mm、160mm 时，则实体模型将从如图 a）的结构变为图 b）的结构，但当 U 的数值大于 X+D/2 时，将使实体中的孔不在实体内部，则从逻辑上是不可能的。因而在改变尺寸变量值时，应满足一定的条件。a) b)图 6-1 参数化设计的示意图从上面的实例可以看出，参数化设计是使用约束来实现设计与修改产品的一种方法。约束可以理解为若干个对象之间的相互关系，即限制一个或多个对象满足一定的关系、条件。比如上面例子中孔不能存在于实体之外即为一个约束。基于约束的设计方法最主要的特点就是：能够处理用户对几何体施加的一系列约束，而用户无需关心这些约束是如何被满足的。参数化设计 (parametric design)和变量化设计（variation design） 是基于约束的设计方法中的两种主要形式。它们都能解决设计时所必须考虑的几何图形约束和工程约束等问题，具有在几何图形尺寸变动时自动更新图形的能力和尺寸驱动 (dimension driven)功能。无论参数化设计系统还是变量化设计系统，工程师都可以用几何约束(如平行、垂直等)和工程约束(通常以工程方程式来表达，如模型的性质、重量、载荷、可靠性、结构等)来设定产品设计上的要求。这些系统不仅是在初始的几何图形中要能满足工程约束的设计要求，而且在图形参数变更时也要能保持整体工程关系不变。这样，工程师就不用再去考虑如何更新设计几何造型以符合设计上要求的几何图形约束和工程约束关系，使 CAD 系统能真正捕捉到设计者对产品的设计意图。参数化设计系统和变量化设计系统二者表面上看起来很相似，但它们技术上的差别主要体现在：约束方程的定义和求解方式上。参数化设计系统：所有约束方程的建立和求解依赖于创建它们的顺序，每个几何元素根据先前已知的几何元素定位。程序设计者要预设一些几何约束，供设计工程师在建立几何图形时使用。系统调用这些预设约束的组合，以确定各几何元素的相关位置；参数求解采用顺序求解策略，后面的元素求解依赖于生成它的几何元素。求解过程不能逆向进行，即求解是过程式的；参数化方法注重于几何图形元素的邻域，对设计模型的整体修改比较困难，难以调整约束依赖关系和求解顺序，无法处理特性约束，因此最适用于已完全特性化的设计问题（即无需在设计方案上作重大改变）, 如具有明确层次依赖关系的装配体设计、系列标准件库的创建等。变量化设计系统：针对设计对象的操作具有更好的灵活性和自由度，约束的指定是陈述式的，即约束的指定没有先后顺序之分，约束依赖关系可以根据设计者意图随意更改；它通常采用并行求解的策略，通过同时求解一组约束方程来确定产品的形状和尺寸；另外，几何约束和工程约束可以联立整体求解，因而功能更为强大；但是也应该看到，大型约束方程组整体求解的效率和稳定性显然不如参数化设计方法。形象地说，陈述式的变量化设计系统告诉计算机做什么，过程式的参数化设计系统告诉计算机怎么做。它们具有各自的适用范围，用户可以根据自己特定的设计要求进行取舍。当前基于约束的设计方法研究趋向于将二者有机地结合起来，相互借鉴，优势互补，以发挥更大的效益。一般地，如无特殊说明，我们把基于约束的设计方法简称为参数化设计。2常用的参数化设计方法（1）数值约束求解方法这是一种面向非线性方程组整体求解的代数方法，最早由英国剑桥大学的 Hillyard 提出。美国 MIT 的 Gossard 研究小组发展和完善了这一理论，称为变量几何法。该方法将几何形状定义成一系列的特征点，将约束表示成以特征点坐标为变元的非线性代数方程组，通过数值迭代方法求解非线性方程组，从而确定几何细节。非线性方程组的求解通常基于 Newton-Raphson 迭代法。非线性方程组表示为：, 其中: , 对于初值 XO, 第 n+1 次迭代的 Xn+1 值由以下迭代公式得到: 其中： 令： 则有: 于是得到：其中，为 Jacobian 矩阵 表示各个变量的微小位移。,表示方程组的残差。经过反复迭代，直至 ,就得到了方程组的解。约束集的有效性可以通过判断 Jacobian 矩阵的秩来实现。数值求解的主要优点在于：能适应较大范围的约束类型，特性约束可以通过约束方程组的联立求解得到处理；但它难以避免数值方法求解稳定性差的问题，方程组整体求解的规模和速度较难得到有效的控制，迭代初值与步长的选取也会影响算法的成败。从用户的角度看，很难以一组方程式刻画几何元素之间的约束关系，而且，当出现不一致的情况或非预期的结果时，也得不到准确的反馈。（2）基于规则的几何推理方法基于规则的几何推理方法运用规则来建立和执行构造步骤，又称为规则构造式求解方法。它基于这样一个事实：即在工程图中的绝大多数配置都可以通过直尺、圆规和量角器绘出，约束通过构造的方式得到满足。这样对用户来说更显得自然而且适合于交互式查错。 Aldefeld 采用一个基于符号推理和操作的专家系统，建立一个规则体系，将几何形体的约束关系用一阶逻辑谓词描述，存人知识库中。系统从知识库中提取出有关信息，通过推理机逐步推导出几何细节。推理示意图如图 62 所示。图 62 基于规则的几何推理知识库包含某特定几何模型的知识，初始内容是给定的约束，通过规则推理出的事实不断累加。规则库收集相关规则，通常仅有一个规则子集作用于某给定模型，但预先无法知道。推理机是控制部分，其任务是按某些策略选择规则并应用于现有事实。处理的中心点在于模式匹配，即检验每个原子表在知识库中是否有所对应。推理的结论成为新的事实，推理机记录了所有成功的规则应用。几何推理是要从现有的已知约束中派生出尽可能多的知识。因此每当一个新的约束得到后，推理过程启动。所有规则循环使用，直至没有新的事实产生。约束处理分为两个阶段：1) 将几何约束一一读入系统，并加入知识库，启动推理机；将所有可派生的知识存入系统，一旦某个约束被删除，推理机回溯。2) 在后处理阶段，推理机输出重建步骤，把规则名翻译成相应的处理过程，形成构造计划，一步步执行，从而构造出整个几何体。（3）基于图论的约束求解方法这种方法将一般几何约束系统表示成图 (graph)的形式，通过分析约束图推导出一系列构造过程，再根据这些构造步骤来导出整个几何体。这种方式又称为图构造式求解方法。由于推理过程基于图论算法，因而理论严密，速度快，效率高。Fitzrald 构造了一种 x 向和 y 向尺寸树，如果树中出现了图(即出现了封闭回路), 则表明出现了多余的尺寸约束。该方法只能处理水平和垂直方向的距离尺寸，只适用于简单的工程图形。将尺寸树的概念一般化，用图来表达几何约束系统，其中：顶点代表几何元素，边代表几何元素之间的约束关系；再引人了循环尺寸约束，可拓展这一方法，分析约束图的三连通部分，对每个三连通域分别求解。求解过程是递归的，亦即一旦某个三连通域已知，它就会在图上被归约为一个顶点，并在归约图上成为其他三连通域的成员。若将几何约束系统抽象为无向图，顶点为几何实体称为 geom , 一组可独立确定相对形位的几何实体集称为 macrogeoms，顶点的自由度及顶点之间的约束度以权值的形式分别记录在顶点和弧上。约束机的求解过程大致分为两步：1) 由链式搜索和环路搜索在图上找出符合 macro 条件的几何实体集，并记为 macro 顶点。 2) 从约束变动的 macro 出发，不断地寻找上一层 macro, 并识别其约束模式，调用相应的计算方法，得到问题的解。(4)符号代数求解法这种方法将约束集转化为一个代数方程组，利用符号代数法求解该方程组。该方法虽然能求解一般的非线性代数方程组，但在运行时间和效率上有待进一步改进。 （5）基于构造过程的方法基于构造过程的方法在图形输入的过程中借助造型命令自动捕捉设计者的意图。这种方法记录了用户在造型过程中的每一步操作，基本思想是：造型操作与几何约束之间有着对应的关系。造型过程能够用来管理和维护反映几何元素之间约束关系的内部数据结构，设计的修改可以通过修改造型过程的某一参数得到。Roller 扩展了传统 CAD 系统的数据结构，以便更好地捕捉设计者的意图，其主要做法包括：1) 引入三种类型的几何实体：固定的、可变的和柔性的；2) 通过对命令语义的推理，自动建立几何约束关系；3) 跟踪构造几何体（辅助线）、面的使用，捕捉构造意图；4) 存储构造顺序；5) 生成由传统 CAD 的命令组成的构造计划；6) 对于给定的某一组尺寸参数，执行构造方案。基于构造过程的方法，对于结构相同尺寸不同的零件设计是十分有效的；但是由于必须严格遵循构造过程，对于那些设计要求不断变化的设计环境则不太适用，而且难以利用传统 CAD 系统生成的图形，另外，也无法处理耦合程度高的循环约束情形。由于空间问题的复杂性,3D 参数化方法难以实现陈述式的表达、规划和求解，因而也多采用基于几何模型构造过程的方法。二约束推理求解算法基于约束的产品描述方法就是：将产品的功能、特性、形状等属性通过约束的形式表示出来，然后采用某种算法使这些约束能同时得到满足，并在设计的整个过程中得到一致的维护。一个基于约束的产品设计过程，实际上就是一个约束指定和约束满足的过程，它们不断循环求精，直至所有设计要求得到满足。约束是特定元素之间必须满足的一组关系。约束满足问题可以通过一个有限集以及作用在这个有限集上的一组关系来定义。在一个约束系统 M =(E,C) 中，对于一个有限的元素集 E= ei |i =1, ，n ，存在一组关系 C= cj |j=1, ,m , 其中要求所有 ei 满足cj(e1, ,ej )。CSP 的主要任务就是：考察是否存在对于每一个 ei E, 都可使得每一个 cj C 得到满足。如果存在这样的 ei 的解，则能够把它找出来。这个解又称作 M 的一个实例，它是任何满足 C 的元素集合，获取 M 的实例是通过对 C 中变量的赋值实现的。1约束的表示与分类对于一般的参数化 CAD 系统，其中的约束分为几何约束和工程约束。工程约束是指：几何约束系统中几何元素之间固有的约束关系，它反映了产品在工程语义上的设计要求，一般以几何设计参数为变元的约束方程式的形式提供。例如：活塞的直径往往是由该活塞必须传递的功率来决定的，可以定义如下工程约束：d=f(P), 其中 d 为活塞直径，P 为活塞传递功率，因此根据传递功率可确定活塞的几何参数。工程约束的引人使得设计者可以直接关注设计的功能要求，从而为主设计提供了强有力的支持。本节主要讨论几何约束的分类和描述。几何约束：包含两种类型：结构约束和尺寸约束。结构约束：是指几何元素之间的拓扑结构关系，描述了几何元素的空间相对位置和连接方式，其属性值在参数化设计过程中保持不变。它在工程图中往往是隐含的，并不明确给出，如平行、垂直、相切等。尺寸约束：是通过图上的尺寸标注表示的约束，例如距离、角度等。工程图中的尺寸标注是几何体的一个直接和自然的描述，从而提供了修改几何形体的合适方式。尺寸驱动的目的:就是根据尺寸标注值的变化修改图形，并保持图形变化前后的拓扑结构关系不变。结构约束和尺寸约束可以统一为一种表示方式，用以下形式表示：C = ( T , 01 , 02 , V )其中: C表示约束；T表示约束类型；O1 , 02 分别表示约束对象；V表示约束值，数据类型可以是整型或实型。整型：代表结构约束，体现了对某种几何拓扑结构关系的肯定，是一种属性关系，不含数量关系；实型：代表尺寸约束，有数量上的关系。约束值也可能有正负号，以体现约束的方向。如图 63 所示，直线具有方向性,L1 相对于 L2 的角度约束值为,是因为从 Ll 的正向逆时针旋转到 L2 的正向测量的角度值为；L2 相对于 L1 的角度约束值为-，是因为从 L2 的正向顺时针旋转到 Ll 的正向测量的角度值为。图 63 约束的方向性带符号的约束体现了几何元素之间相互约束的方向性。它对几何体拓扑结构进行了更明确的限定，从而有效地限制了多解情况的发生。以平行约束为例，见图 64 给定两直线平行的约束，并不意味着两直线的夹角一定是 0。夹角为 0意味着两直线同向；两直线也可能反向，这时两直线夹角为180。因此可以用符号区分两种不同的平行约束，对几何图形作进一步的限定。图 64 平行约束（1） 结构约束l) 平行 (parallel )约束 (PAR , L1 , L2 , +1 )： 两直线平行且方向相同。 (PAR , L1 , L2 , -1 )： 两直线平行且方向相反。2) 垂直 (perpendicular) 约束 (PER , Ll , L2 , +1 )：两直线垂直 ,L1 逆时针旋转 90与 L2 重合 ( 见 65(a) 。 (PER , LI , L2 , -1 ): 两直线垂直 ,L1 顺时针旋转 90与 L2 重合 ( 见图 65(b )。图 65 垂直约束3) 两圆相切约束 (TAN_CC , C1 , C2 , +1 ): 两圆外切 ( 见图 66(a) 。 (TAN_CC , C1 , C2 , -l )：两圆内切 ( 见图 66(b) 。图 66 两圆相切约束4) 线圆相切约束 (TAN_LC , L , C , +l )： 线圆相切，圆心在直线的正半平面 (见图 67(a)。 (TAN_LC , L , C , -l )： 线圆相切，圆心在直线的负半平面 (见图 67(b) 。 图67 线圆相切约束5) 点在直线上(ON_L , P , L , +1 )： 点 P 在直线 L 上 ( 见图 68 )。 图 68 点在直线上6) 点在圆上(ON_C , P , C , +1 )：点 P 在圆 C 上 ( 见图 69)。图 69 点在圆上（2）尺寸约束1) 点与点的距离约束(D_PP , P1 , P2 , d )： 点 P1 到 P2 的距离是 d( 见图 610) 。 图 610 点与点的距离约束2) 点到线的距离约束 (D_PL , P , L , d )： 点 P 到直线 L 的距离是 d, 点 P 在直线 L 的正半平面（见图 611（a）。 (D_PL , P , L , -d )： 点 P 到直线 L 的距离是 d, 点 P 在直线 L 的负半平面 ( 见图 611（b）)。图 611 点到线的距离约束3) 平行线之间的距离约束（如图） (D_LL , L1 , L2 , d )：直线 L1 与 L2 的距离是 d, L1 与 L2 同向 ( 见图 611(a) )。 (D_LL , L1 , L2 , -d )： 直线 L1 与 L2 的距离是 d, Ll 与 L2 异向 ( 见图 611(b) )。 图 612 平行线之间的距离约束4) 两直线的角度约束(ANG , Ll , L2 , )： 直线 L1 到直线 L2 的角度是 （见图 612） 。图 613 两直线的角度约束5) 半径和直径约束约束对象的内部属性约束均是一元约束，其约束满足过程比较简单，只需对几何元素进行固有参变量的赋值（见图 613）。图 614 半径和直径约束（3）几何实体的自由度自由度指几何实体固有的独立运动 (自由) 变量的数目，记为 DOF(e)(degree of freedom), 其中 e 代表某一特定几何实体。对于二维平面上的点和直线，它们的自由变量数目是 2, 故其自由度也是 2 。对于平面上的圆，方程 (x-xo)2 + (y-yo)2 = r2 包含了 3 个自由变量，因而其自由度为 3 。对于二维平面上的刚体，它具有两个平移自由度和一个转动自由度，故刚体自由度为 3, 记为 DOR (degree of rigid)。而对于三维空间上的刚体, DOR=6 。(4) 约束的约束度由某个约束引起的相关几何实体自由度的减少量称为该约束的约束度，记为 DOC(c), 其中 c 代表约束类型。约束实质上表现为一组约束方程，约束的引入会限制几何体的运动，从而导致了相关几何实体的自由度的减少。几何约束的约束度 DOC 一般均为 1 。少数约束 DOC 超过 1 的约束类型可以分解成几个 DOC 为 1 的基本约束类型，这样便于进行约束的管理和维护。例如两直线共线约束，其 DOC=2, 可以将它转化成两条直线平行和距离为 0 的两个基本约束，其约束度均为 1 。几何约束系统中的常见约束均为二元约束，因而该模型中几何元素及其相互之间的约束关系可以规范地以几何约束图 (GCG：geometric constraint graph) 的结构来表达。在 GCG=(V,E) 中顶点集合 V 代表基本几何元素，边集合 E 代表几何元素之间的几何约束。初始建立的图是无向图，因为顶点的地位和作用等同，邻接点之间还没建立起依赖关系。如图 6-15 所示的平面图形，经转化后形成 GCG 。它清晰地表明了几何约束系统内部几何元素及其相互约束关系。图 6-15 平面图形及其 GCGGCG 中的顶点：记录了几何元素的类型、自由度 DOF 和其他相关参数信息；边：记录了几何约束的类型、约束度 DOC 和其他信息。边的权值的定义取决于特定问题解决的需要。例如几何约束的约束度 DOC 、约束值和约束优先权等都可以被认为是 GCG 边的权，因而 GCG 是一个几何约束网络。在图 6-15中, GCG 含有 10顶点，即 10几何元素；17 条边，即 17 个约束，形成的约束集描述如下： ( ANG , L1 , L3 , d3 ) ( PER , L1 , L4 , +1/-1 )( ON_L , P1 , L1 , +1/-1 )( ON_L , P2 , L1 , +1/-1 )（PER , L1 , L2 , +1/-1 ）( ON_L , P1 , L4 , +1/-1 )（D_PP , Pl , P5 , d2 ） （D_PP , Pl , P2 , d1 ）( ON_L , P2 , L2 , +1/-1 )( ON_L , P3 , L2 , +1/-1 )( ON_C , P3 , C , +1/-1 )( TAN_LC , L2 , C , +1/-1 )( ON_C , P4 , C , +1/-1 )( TAN_LC , L3 , L1 , +1/-1 )( ON_L , P4 , L3 , +1/-1 )( ON_L , P5 , L3 , +1/-1 )( ON_L , P5 , L4 , +1/-1 ) GCG 作为一种图，继承了图的一般概念和性质。从直观上看，一个被标注尺寸的草图，如果在非退化的情况下存在有限个的解，那么就认为是约束完备的；如果存在无穷多个解，就是约束不足的；如果没有一个解存在，那就是约束过载的。在这里，非退化的情况指：尺寸值是合理的，能够在结构上生成图形。例如，标注了三条边长的三角形，它的约束是合理的和完备的；如果某一边的长度大于其余两边之和，则该三角形无法正确生成。这就是出现了退化的情况。下面简要介绍几何约束系统中的几个常用概念及性质。(l) 约束过载 (over-constrainted)： 一个几何约束系统在结构上是约束过载的，如果其 GCG 中存在的子图含有 n 个顶点和多于 2n-3 条边。约束过载的系统又称过约束系统。(2) 约束不足 (under-constrainted) : 一个几何约束系统在结构上是约束不足的，如果它在结构上不是约束过载并且约束的数目严格小于 2n-3 。约束不足的系统又称欠约束系统。(3) 约束完备 (well-constrainted): 一个几何约束系统在结构上是约束完备的，如果它不是约束过载的并且其约束数目等于 2n-3 。约束完备的系统又称完备约束系统，对外表现为一个刚体。完备 GCG 一定是边稀疏的、连通的。过约束图形一般不能接受，但不排除工程图中允许多余但不矛盾的尺寸标注，以帮助阅读者看懂图形，理解设计者的意图；欠约束系统是广泛存在而且可以接受的，事实上在概念设计中，系统的初始状态必须是欠约束的。在设计不断深化和细化的过程中，可持续对欠约束系统施加约束，使之一步步走向完备的约束系统。一个支持概念设计的约束求解系统必须能够处理欠约束的情形。2几何约束系统的约束建模几何约束图 GCG 的建立可以通过三种方式实现：第一种：是在作图过程中记录下该操作对应产生的约束。在制图过程完成后，GCG 也就建立起来了。此种方法在制图的过程中很自然地实现了 GCG 的建立，因此能准确地记录下图形所蕴含的约束，捕捉设计者的意图；但该方法必须针对全新的设计对象，对于已有图形则无能为力。第二种：是按己画好的草图手工指定约束。该方法能处理已有图形，由用户指定所需约束。但约束指定过程过于烦琐，对于复杂的设计图形显然工作量太大。第三种：是自动识别原有图形隐含的约束。此方法能自动地为已有图形建立相应的约束模型 GCG, 避免了前两种办法的不足，但实现的难度比较大，现有的算法还不够成熟。因为大量无用和冗余的约束往往被系统识别出来，给后继的推理、排序和求解算法带来了很大负担，而且很容易导致过约束或异常结果。因此，该方法多用于规模较小的图，例如为平移、旋转等三维造型操作提供二维截面图形。在工程图中，隐含约束是普遍存在的，例如水平、垂直、平行、相切等结构约束并没有在图上标志出来。隐含约束的确定有一定的规则，或者说是工程常识，工程设计人员容易理解，我们利用计算机进行识别也要遵循这些规则。以下是常见的几种隐含约束识别规则，按识别的优先级顺序排列：(l) 近似水平的直线严格水平，近似铅垂的直线严格铅垂；(2) 近似相切的直线、圆和弧严格相切；(3) 近似同心的圆或弧严格同心；(4) 近似共线的两直线严格共线；（5）近似平行的两直线严格平行；(6) 近似垂直的两直线严格垂直；(7) 近似的多个圆和弧半径被认为相等；(8) 图形元素之间相互连接。这里有一个问题，究竟近似到什么程度才能被认为相等呢? 为此引人两个阈值的概念：如图 616 所示。距离阈值 d：如果两个点的距离在距离阈值d 之内，则认为这两个点是同一个点；同样，如果点到直线的距离小于d, 那么就可以认为点在直线上。角度阈值 ：规定了两条直线夹角的限定值，是角度类约束的识别依据。例如，如果两条直线的夹角小于可以认为两条直线平行。两种阈值的大小可以根据草图的形状和准确程度由用户设定。(a) 草图 (b) 约束识别后规整的图图 616 距离阈值和角度阈值的概念约束。每当一个几何元素被系统作为一个顶点插入到 GCG 时，都要与 GCG 中已存在的几何元素按照上述规则进行比较，以生成相应的边。尺寸约束的识别可以根据尺寸标注的控制点以及标注方向，搜索相应的控制图素，建立尺寸标注与对应几何元素的约束关系。在实际应用中，隐含约束的识别并不是在约束求解之前就全部完成的，否则会产生大量不必要的约束，严重影响推理效率。因此，往往是在推理过程中，由于约束不足而使推理过程无法继续进行时，才启动隐含约束识别模块，按约束优先级有针对性地识别某些隐含约束。3几何约束的推理算法在 GCG 中，每个约束对应于图的一条边，每个几何元素对应于图的一个顶点。从图的某一顶点出发，把所有与它关联的边变为以该顶点为弧尾的出弧，从而增加了相应邻接顶点的入度(或减少其自由度)。如果某顶点的入度达到了其自由度数，则变为已知且被输出。其非弧的边成为以该顶点为弧尾的出弧，用来减少与之邻接的顶点的自由度。通过广度优先搜索，逐步递归地由已知元素推理出未知元素，直到图中所有顶点的自由度约束均减为 0。这时无向图变为有向图，顶点输出的顺序就是拓扑排序的结果。（1） 推理步骤1) 预处理阶段：将所有含自反边的顶点的自由度 DOF(v) 减去自反边的约束度 DOC（e），同时在图中删掉自反边。自反边代表了一类一元约束，如半径、水平、垂直等约束。2) 固定一点作为基点，其自由度 DOF(v)=0, 它成为已知元素，是推理搜索的起点。3) 从基点出发，递归调用 SEARCH 过程，直至所有顶点的自由度约束均减为 0。SEARCH 算法过程说明如下：输入： 已知元素的顶点v 。输出： 表头结点己排好序的有向图。步骤l： 取已知元素 v 的表头结点，从第一个表头结点开始，将其插入到已排好序的已知元素表头结点的最后。步骤2： 遍历与 U 关联的所有边；对于当前边 e, 取与边 e 关联的 v 的邻接顶点 v；如果 DOF(v)0, 则 v 为已知元素，继续做步骤 2；否则 DOF(v)DOF(v)DOC(e)标记边成为从 v 指向 v的有向弧；如果 DOF(v)0, 将 v 压入临时堆找 s 。步骤3: 如果临时堆栈 s 为空，返回。否则从临时堆栈 s 中弹出顶点vv ，令 v = vv ，转步骤 1 。 算法最终输出己排好序的顶点序列。以上算法需进一步细化，才能保证其实用性。（2）启发式搜索策略由约束识别建立的 GCG 可能会包含大量冗余或矛盾的约束，并不是所有的约束都能用于推理，而且不同约束对推理过程所起的作用也不同。为此，通常遵照一般的工程常识为每个约束类型规定相应的优先权值。例如尺寸约束的优先权比结构约束的优先权要大，因为尺寸约束是显式的，而结构约束是隐式的。如果多个约束同时可用，则按照优先顺序触发，亦即搜索时优先搜索权值较大的边，从而能较快地引导搜索向正确的方向进行。（3）缺省推理 (default reasoning) 技术当用优先权较高的约束推理失败 (仍有自由度不为 0 的顶点) 时，依次采用系统内部 优先权较低的待用约束，分步进行推理。（4）冗余约束剔除几何推理的过程并不是完全由自由度驱动的，还要对矛盾的约束进行判别，与已用约束 ( 已标记为弧 ) 矛盾的约束不能用来减少顶点自由度，这样才能建立正确的求解方式。例如，若有一个点 P, 它在已知直线 L1 上，则该约束所代表的边已被标记为弧；假设又存在已知直线 L2, 使得点 P 在直线 L2 上，于是点 P 可以通过两直线求交进行求解。但是如果 L1 平行于 L2( 意味着这两条直线共线 ), 则点 P 不能求解，因此点 P 在直线 L2 上的约束不能使用。它是识别的冗余约束，虽未造成矛盾，但影响求解，也应该剔除。（5）局部参数变动处理对于已排好序的 GCG, 当用户只需要修改少数几个参数值时，没有必要从头至尾生成整个图形。为了提高效率，在某个局部参数变动时，只需重新计算受到该参数直接或间接影响的元素，亦即仅受到该参数变动影响的局部图形元素。下面给出在某一约束值变化时，找到仅受其影响的一组元素集合的算法步骤：步骤 1：找到该约束代表的弧，取出弧头元素阶。步骤 2：对于所有vi的后继元素vj，递归地向上回溯搜索其直接前驱元素。如果找到了vi，则标记 vj 为受参数变动影响的元素，送入待求元素队列。步骤 3：待求元素依次出队列，进行求解。（6）约束一致性检查1) 欠约束差别GCG 的拓扑排序结束后，依次遍历有向图的逆邻接表的表头结点。如果还存在自由度大于 0 的顶点，则系统必为欠约束，表明图中尺寸标注不足。这些自由度大于 0 的顶点没有受到尺寸的控制，系统会显示出这些约束不足的顶点。2) 过约束差别即使图中所有顶点的自由度均变为 0, 还有可能出现过约束，这就必须考察未用到的多余边(冗余约束) 。如果该边所代表的约束是由尺寸标注引起的，那么它是多余的尺寸标注，亦即产生了过约束。在上述排序算法中，每输出一个已知元素之前，必须检查它是否含有未用的边，这些未用边的约束很有可能是多余的。如果存在多余约束，系统会提示用户删除它。用户也可以忽略该约束，算法会继续执行下去，多余约束将会被自动忽略而不使其得到满足。4几何约束的求解计算推理结束后，几何元素的求解顺序就完全确定下来了。计算时只需依序遍历有向图的邻接表的表头结点，将入弧记录的约束信息转化为约束方程，从而计算出各顶点几何元素的参数值。图 617 显示了排序后的依次求解过程，可见它等同于一种尺规作图的方法,只需要进行几何解析交切运算，因此该算法比较准确高效。(a) 求解顺序 1 5 (b) 求解顺序 1 5 2（c）求解顺序 1 5 2 8 (d) 求解顺序 1 5 2 8 4 (e) 求解顺序 1 5 2 8 4 3 （f） 求解顺序 1 5 2 8 4 3 7 6图 617 排序后的求解过程求解方法依据入弧的类型和数目确定。由于约束类型的多样性和复杂性，求解时必须考虑到所有约束可能的排列组合，每一种求解方法对应于一段计算程序。实际求解之前，系统已将其他约束类型转化成距离和角度类约束，因此基于表 61 即可确定点和直线参数的约束组合。未注半径的圆，其自由度是 3, 需要同时有 3 个约束才能确定，即对它的求解需要 3 个方程联立求解。与未注半径的困相关的约束实际上只有两种：线圆相切约束和两圆相切约束 (如果把点视为半径为 0 的圆，那么可把点在圆上的约束转化为两圆相切约束), 因此未注半径的圆的求解方法可有如表 62 所示的四种组合。对于一个完备约束系统。通常可以存在有限个不同的解，但是用户一般只能接受其中的一个。因此，多解的取舍问题是 GCSP 中一个十分重要的问题。事实上，对于一个完备的几何约束系统来说，解的数目一般会达到几何元素数目的指数级。表 61 点和直线的求解方法和对应的约束组合几何元素约束组合求解方法点D_PP + D_PP ( 点点距离 + 点点距离 )D_PP + D_PL ( 点点距离 + 点线距离 )求与两已知点有一定距离的点求与一个已知点有一定距离且与一条已知直线有一定距离的点直线D_PL + D_PL ( 点线距离 + 点线距离 )D_PL + D_PL ( 点线距离 + 点线距离 )D_PL + ANG ( 点线距离 + 线线角度 )求与两已知直线有一定距离的点求与两巳知点有一定距离的直线求与一个已知点有一定距离且与一条己知直线有一定角度的直线表 62 未注半径的圆的求解方法约束组合求解方法TAN_CC + TAN_CC + TAN_CCTAN_CC + TAN_CC + TAN_LCTAN_CC + TAN_LC + TAN_LCTAN_LC + TAN_LC + TAN_LC求与三个已知圆相切的圆求与两个已知圆和一条已知直线相切的圆求与一个已知圆和两条己知直线相切的圆与三条已知直线相切的圆首先看一个简单的例子，如图 618 所示。图 618(a) 的三角形是一个完备约束系统，图 618的解是一致的，但显然不是用户所需要的。针对多解问题，各种约束求解系统可能采取不同的方法。（1）数值迭代方法基于数值迭代的约束求解器的基本策略是收敛到与初始图形最近的解，这种策略直观且通过迭代方式很容易实现。然而由于解的数目呈指数式上升，约束方程组的数值迭代 t往往呈现出病态，因此常常会收敛到鞍点而非所期盼的最小点。用户通常被迫将草图画得尽量准确，以使几何元素的数值接近所期望的解。同样的道理，尺寸值的变化也要尽量的小。另外，由尺寸值带来的变化并不一定是可逆的。例如把图中某一尺寸值由 40 改为 30, 再由 30 改回 40, 得到的结果并不一定还是原来的图，因此系统不得不小心地保留每一步 变化的设计历史。 (a) 约束完备的三角形 (b) 一个一致的解图 618 三角形的多解情况（2）通用规则判定方法这种思想的中心点在于根据某些特定的性质确定多解的取舍。这通常要依赖于特定的应用，例如可以选择封闭的、凸的和非自交的图形。该方法存在两个主要问题：(1) 通用规则的施加可能并不符合用户的要求，特别是在用户渐进式地构造草图时。因此在构造图形的某些阶段，不允许图形是自交的。(2) 甚至在非常严格的情况下，这类问题的求解在计算上也是很困难的。例如，考察一个多边形截面的顶点构成的点集。对于某些特定应用可能会要求草图的结果应该是一个简单多边形，即非自交的多边形。另外，也可以指定一个点集连接的环路方向构造这个多边形。这个附加要求使该问题成为一个 NP 完全问题。（3）通过过约束方法指定正确解这是一种很自然的方法，工程师在图中经常使用。图 619 给出了一个运用这种方法得到唯一解的典型实例。假设图中的三条平行线没有方向，如果我们仅仅指定了两个距离约束 dl 和 d2，则会得到两个不同的解。由于直线不含方向，因此除了第一个距离约束外，对于其他每个距离约束都有两个不同解的选择。一般地，对于 n 条平行直线和 n-1 个 距离约束的完备系统存在 2n-2 个解。如果在本例中加入第三个距离 d3，就能得到唯一解。虽然这种方法看起来很有效，但是即使把问题限制在一个很简单的条件下，也无法找到一个有效算法得到的问题的解。将上述例子一般化，得到问题的描述：给定 n 条平行线和它们之间的 n 个平行距离，是否存在满足要求的解？可以证明这个问题是一个 NP 完全问题，因为它可以转化成一个整数划分问题：给定一个 n 个正整数的集合 A, 是否存在 A 的一个划分，把这 n 个整数分成两个不相交的集 Al 和 A2, 使得 A1 中整数的和等于 A2 中整数的和? (a) 两个距离约束得到两个可能解 (b) 三个距离约束得到唯一解图 619 用距离约束三条平行线三、 参数化 CAD 系统基于上述的算法，在传统 CAD 系统的基础上，构造一个参数化 CAD 系统 (PCAD)对实际应用是十分重要的。由清华大学 CAD 中心开发的 PCAD 系统的基本流程是：对于用户输入的原始草图,通过草图识别方法建立起图形的 GCG 表达，这是一个无向图的邻接表结构。根据几何推理算法对原始 GCG 进行有向化处理，拓扑排序后生成顶点输出序列，亦即几何元素的求解顺序，它存储在有向图的逆邻接表的表头结点链中。顺序遍历该链，通过几何解析交切求解计算和多解判定，确定出每个结点所包含的几何元素的参数值，最终得到符合几何约束的精确图形。此流程图如图 620 所示。1参数化 CAD 系统的流程和基本功能（1） PCAD 系统的主要功能图 620 系统的流程框圈1) 草图设计在初始设计阶段，工程师可以将注意力集中在设计上，利用鼠标在屏幕上以草图的形式随手勾画出设计图形，表达设计思想。在给出必要的尺寸标注之后 ,PCAD 将根据草图形状和尺寸大小把规整的图形绘制出来。2) 修改设计在修改设计时只需将原有图形调出，修改某些尺寸标注的值，运行 PCAD 后就可以迅速得到新的设计图。在 PCAD 的支持下，设计师可以通过不断调整尺寸参数值产生不同的设计方案。3) 支持工程设计约束PCAD 允许定义一组设计变量，通过表达式为尺寸标注赋值，这样根据几个关键参数就可以定义一个很复杂的图形。4）相似零件图的生成只需要定义一张原型图并提供图中设计变量的数据 ,PCAD 系统就能自动生成一系列结构相同而尺寸不同的相似零件族，这使创建标准件和常用件库的工作变得十分容易。 事实上，我们已利用该系统创建了全套国家标准零件库。针对工程实际需要 ,PCAD 系统还增加了中心线处理、阵列处理、剖面线处理和三视图处理等实用功能。对于中等复杂的零件图，其处理速度和准确性均能满足工程设计的实际要求。（2）PCAD 系统的功能命令1) PPCREATE 命令自动识别草图约束，建立参数化模型，并按照识别的约束规整图形。2）PPUPDATE 命令根据图中的所有结构约束和尺寸标注值，更新全图。3）PPDIM 命令是尺寸标注命令，能够进行点到点的距离、点到线的距离、线到线的距离、角度、直径和半径的标注。4）PPCHGDIM 命令修改尺寸标注值，并按照新的尺寸值更新图形。5) PPDELDIM 命令删除尺寸标注，并报告当前所需的尺寸和约束数目。6）PPDSPDIM 命令显示尺寸标注状态，可以是数值、变量或方程的形式。7）PPADDCON 命令对图形施加指定约束，约束类型包括水平、铅垂、平行、垂直、相切、投影、共线、共点和固定点等。8) PPSHOWC