基于轨迹相交的三维顺序尺寸标注完备性检查

程亚龙，刘晓军，刘金锋

（东南大学 机械工程学院，江苏 南京 211189）

0 引言

尺寸标注的主要作用是精确描述零件的结构特征、形状特征和精度特征，其质量将直接影响产品生命周期各个阶段的顺利运行，因此尺寸的完备性检查也一直是计算机辅助设计（Computer Aided De-sign，CAD）／计算机辅助工艺规划（Computer Aided Poress Planning，CAPP）领域研究的重要问题［1］。几何模型上的几何基元在尺寸标注下不添加辅助元素就可以顺序确定其空间位姿，即固定该几何基元，这样的尺寸标注称为顺序标注，否则称为循环标注。顺序标注是尺寸完备性检查所要面对的首要问题，也是本文要解决的主要问题。

国内学者主要对二维工程图的尺寸完备性检测进行了研究，并取得了很多成果［2-5］，所采用的基本方法是将各视图尺寸标注坐标转换到空间投影模型，建立统一的空间尺寸标注，然后按照坐标方向建立邻接矩阵来判断尺寸的封闭性。这些方法能处理较为简单的二维工程图的尺寸完备性检测问题。当三维几何模型设计完成后，所有的几何基元都被完整约束，这与传统的几何约束求解问题极为相似。目前几何约束求解领域存在基于图论的方法［6］、基于规则的方法［7］、数学计算法［8］和符号计算法［9］等几种主要方法。实际应用中，上述几种方法的综合运用往往会取得更好的结果［10-11］。Gao等［12-13］利用几何约束生成几何基元的动态轨迹，通过轨迹的交点求出几何基元的确切解；Hoffman等［9，14］在约束关系图的基础上提出分解—组合的规划算法，将约束问题分解为可作子图的算法；Ait-Aoudia等［15］在Hoffman算法的基础上做了改进，提出S-DR 算法，弥补了分解—组合算法只利用结构信息而忽略数值信息的缺点。

三维尺寸标注所约束的几何基元远远多于几何约束求解所面对的几何基元，而多种几何基元的引入会增加检测系统的复杂度，因此有必要对几何基元进行简化分解。Clemént等［16］提出“与工艺和拓扑相关的表面”（Topologically and Technologically Related Surfaces，TTRS）的概念，该理论将零件的功能表面划分为7个基本类型，而为了更好地表达功能表面之间的关系，提出了最小几何基准要素（Minimum Geometric Datum Elements，MGDE）的概念，即一个功能表面的MGDE 实质上是参考点、参考线或参考面的最小几何，并能充分确定相应的功能表面约束不变。根据上述理论，通过点、直线和平面可以表示各种几何基元，因此尺寸标注完备性检查也主要以点、直线、平面为研究对象。

本文对三维顺序尺寸标注的完备性检查进行了研究，提出几何基元轨迹的概念，分析了各种约束下轨迹的生成规则，通过依赖性分析明确了几何约束的使用规则，并建立尺寸完备性状态与几何基元的约束状态、尺寸使用状态之间的映射关系。通过离散化分解实现了轨迹两两求交，并分析了求交规则。最后基于几何约束图依次判断得到几何基元的约束状态，进而得到了尺寸的完备性状态。

1 几何基元的轨迹

几何约束包括拓扑约束和度量约束两部分［17］，尺寸标注的完备性检查就是在拓扑约束已经确定的情况下，检查标注的尺寸是否有冗余或缺失，而该问题最终归结为几何基元的约束状态判断问题，可以借鉴几何约束求解方面已有的技术和方法。

本文考虑点（P）、直线（L）和平面（PL）三种类型的几何基元，以及距离、角度、平行、垂直和重叠五种基本约束类型，并用DIS（O1，O2）=d，ANG（O1，O2）=θ，PAR（O1，O2），PER（O1，O2）和SUP（O1，O2）分别表示上述约束，其中：O1和O2表示几何基元，d表示距离值，θ表示角度值。若不区分约束种类，则用CONS（O1，O2）表示O1和O2之间的一个约束。

假定一个几何约束CONS（O1，O2）中的一个几何基元O1被固定，则O2在该几何约束的限制下，在几何空间中任意移动所形成的与其共切、重叠、平行或垂直的几何形状即为轨迹，它可以是形象具体的几何基元，也可以是抽象的矢量方向。用LOCI（O2，CONS（O1，O2））表示O2在几何约束CONS（O1，O2）作用下形成的轨迹，其形成不仅与O1和O2的类型有关，也与几何约束的类型有关。

1.1 距离约束下的轨迹生成规则

在距离约束DIS（O1，O2）=d的情况下，当O1为点且固定时，无论O2的类型如何，O2的轨迹都是一个以O1为圆心、以d为半径的球面，反之亦然。轨迹生成规则为

式中：TYPE（O）表示几何基元O的类型，SP表示球面，如图1a所示。当P1固定时，P2在距离尺寸d的作用下形成了以P1为圆心、以d为半径的球面轨迹SP，P2可以是SP上的任意一点，如P3。同理，如图1b和图1c所示，含有直线和平面的距离约束的轨迹生成规则下：

式中CY表示圆柱面。

1.2 角度约束下的轨迹生成规则

与距离尺寸不同的是，角度尺寸只能约束几何基元的方向，不能约束其位置。以直线L1和L2间的角度约束ANG（L1，L2）=θ为例，假定L1固定，则L2为一个以L1为轴线、以L1上任意一点P为锥点的圆锥面上的一条母线。因为P点可以在L1上自由移动，所以L2可以是一个以L1为轴线并在L1上自由移动的圆锥面的母线。换言之，L2在角度约束下形成的轨迹是一个沿轴移动的圆锥面，它限制了L2的方向，本文将这种轨迹定义为线型圆锥，用COL表示，如图2a和图2b所示。图2c所示为面面角度θ，当PL1固定时，角度形成圆锥面CF，锥角为2（90°-θ），它可以在PL1上自由移动，而角度约束的另外一个平面与CF相切于任一母线，如PL2，PL3等。当CF移动时，PL2和PL3同步移动，它形成的轨迹是一个沿平面移动的圆锥面，定义为面型圆锥，用COP表示。

综上所述，无论直线还是平面，它们之间的角度尺寸生成轨迹的规则表示如下：

1.3 平行、垂直约束下的轨迹生成规则

平行和垂直属于特殊的角度约束，当两个几何基元之间的夹角为0°或180°时即为平行，90°时即为垂直。以直线L1和L2之间的平行约束PAR（L1，L2）为例，假定L1固定，则L2可以是平行于L1的任意一条直线，甚至与L1共线。换言之，平行约束限制了L2的方向平行于一个固定方向，但没有限制它的位置，因此该轨迹可以表示为平行方向，本文用PAD表示，如图3a和图3b所示。

经过分析，可以生成PAD轨迹的规则如下：

以直线L1和L2之间的垂直约束PER（L1，L2）为例，假定L1固定，则L2可以是与L1垂直的任意平面上的任意一条直线，即垂直约束限制了L2的方向垂直于一个固定方向，这个固定方向可以是平面的法向或者直线的方向。因此该轨迹可以表示为垂直方向，本文用PED表示，如图3c所示。可以生成PED轨迹的规则如下：

1.4 重叠约束下的轨迹生成规则

无论同类几何基元还是异类几何基元，在重叠约束的作用下，O1的轨迹就是O2，O2的轨迹就是O1，因此重叠约束下的轨迹生成规则可以统一表示为

2 尺寸完备性检查的轨迹相交法

2.1 尺寸完备性状态的映射

2.1.1 依赖性分析

Li等［18］认为几何基元之间由于约束的存在而互相依赖，这些互相依赖的几何基元必须一起求解。在尺寸完备性的检查过程中，当几何基元O1被固定后，几何约束CONS（O1，O2）就可以用来约束O2，O2通过该约束依赖于O1，该约束就被O2“使用”。一旦该几何约束被它的一个几何基元使用，它就不能用于约束另外一个几何基元。

2.1.2 尺寸的完备性状态

尺寸的完备性状态与几何模型上的几何基元的约束状态有紧密的联系，如果可以通过一种方法判断得到每个几何基元的约束状态（包括已固定和未固定两种）以及每个尺寸的使用状态（包括已使用和未使用两种），则通过以下映射关系就可以得到尺寸标注的完备性状态：

（1）若一个尺寸标注的两个几何基元O1和O2均已被固定而该尺寸未使用，则其为冗余尺寸。

（2）若一个尺寸标注的两个几何基元O1和O2均已被固定，且该尺寸已使用，则其为必需尺寸。

（3）若一个尺寸标注的两个几何基元O1和O2至少有一个未固定且该尺寸未使用，则无法判断其是否冗余或必需，为待定尺寸。

（4）若几何基元未固定，则表明该几何基元缺少尺寸标注。

通过上述映射关系，可以将尺寸标注的完备性检查问题转换为几何基元的约束状态的判断问题，在几何基元的约束状态判断过程中会同时得到尺寸的使用状态。

2.2 轨迹相交分析

2.2.1 轨迹相交的离散化处理

几何模型上的每个几何基元会同时受到多个几何约束的作用，每个几何约束会形成该几何基元的一个轨迹，则在几何基元被完整约束的情况下，所有的轨迹求交就一定会得到该几何基元，当这些约束的其他几何基元固定时，该几何基元也被固定。

在分析轨迹相交规则之前，先定义INTER（Lc1，Lc2，…，Lcn）来表示轨迹Lc1，Lc2，…，Lcn之间的交集。前面的分析得到了几何约束作用下各种几何基元所能形成的轨迹，一个几何基元O在多个几何约束｛CONS（O，Oi）｜i=1，2，…，n｝作用下，会形成多个轨迹｛Lci=LOCI（O，CONS（O，Oi））｜i=1，2，…，n｝，这些轨迹的交集表示为In=INTER（O，Lc1，Lc2，…，Lcn），当In与O的类型相同时，即TYPE（In）=TYPE（O）时，就表示几何对象O被固定。因为轨迹的数量和种类不同，同时求交不好处理，所以对求交过程进行离散化处理，采用分步两两求交的方法，只需确定任意两种轨迹之间的求交规则，就可以解决所有的轨迹求交问题。

2.2.2 轨迹相交规则

每一次轨迹求交相当于生成了几何基元的一个新的轨迹，其生成也遵循轨迹的生成原则，即新的交集是几何基元在多个约束作用下任意移动所形成的共同相切（或重叠）的最大几何体，其类型与轨迹和几何对象的类型有关。如图4所示，若点P的两个轨迹为直线L1和L2，则在L1和L2不重叠的情况下，它们的交集既要与L1重叠、也要与L2重叠，它只能是L1和L2的交点，因此L1和L2的交集存在且必然是一个点，这个点就是点P。若平面PL的两个轨迹为直线L1和L2，则在L1和L2不重叠的情况下，它们的交集即要穿过L1又要穿过L2，它只能是过L1和L2的平面，因此L1和L2的交集对PL而言就必然是一个平面。

各种几何约束可以形成9种轨迹，它们两两相交会形成新类型的轨迹，包括圆锥面（CF）和非直线（NL）。通过分析，这11种轨迹两两相交，会在几何空间中形成相交、相切、重合等多种位置关系，每种位置关系对应不同的交集，最终针对点、直线和平面形成了21，44，42种合理可行的相交规则。

2.3 基于约束图的几何基元约束状态判断

几何约束系统可以表示为几何约束图。几何基元用圆圈表示，粗线圈表示几何基元已固定，细线圈表示未固定。虚线表示几何约束已被使用，箭头指向使用该约束的几何基元，实线表示未使用的几何约束。以图5为例，图5a所示为含有完整尺寸标注的零件三维模型，图5b所示即为图5a中零件的几何约束图。

一个完整约束的零件其几何基元之间的相对位置关系是确定的，作为一个刚体，它可以在几何空间自由运动，因此在零件设计和加工时还需要指定三个定位基准。在图5 中：指定PL1为第一基准，默认为固定；指定PL2为第二基准，因为它与PL1垂直，所以PL2也固定；指定PL6为第三基准，它分别与PL1，PL2垂直，则PL6也固定。同时设置其相关的几何约束线为虚线，并添加箭头，如图6a所示。由于PL1已固定，存在距离尺寸DIS（PL1，PL5）=38，则PL5的轨迹为平面，PL5被固定，如图6b所示。从箭头方向可知，PL5依赖于PL1。同理，由于PL2已固定，由距离尺寸DIS（PL2，PL4）可知，PL4也被固定。如图6c所示，L与PL6之间的距离约束形成轨迹为平面，与PL5之间的重叠约束形成轨迹也为平面，对L而言，这两个平面并不共面，因此它们的交集为其交线，即L被固定。如图6d 所示，PL3与PL1的角度尺寸形成轨迹为面型圆锥COP，而PL3与L的重叠约束形成轨迹为直线，当PL3与一个移动的锥面相切且要穿过一条直线时，它们的轨迹相交是一个平面，因此PL3被固定。综上，图5a所示零件的所有几何基元均被固定，根据前述的尺寸完备性状态的映射关系可知，所有尺寸均为必需尺寸，既无冗余也无缺失。

2.4 完备性检查算法流程

前述详细分析了基于轨迹相交法的三维尺寸完备性检查的各个基本环节，下面列出算法的完整流程：

步骤1 建立零件的几何约束图，初始化所有的几何基元的约束状态和几何约束的使用状态。

步骤2 依次指定零件的三个基准面，第一基准为默认固定。第二基准与第一基准之间的角度已知时，第二基准也固定。第三基准与第一、第二基准之间的角度已知时，第三基准固定。

步骤3 从基准开始，依次选择与已固定的几何基元有共同尺寸约束的未固定的几何基元作为待判断对象，提取与其相关的、未使用的、且对应的几何基元已固定的所有几何约束，生成各个约束的轨迹，并按照轨迹相交规则，以两两求交的方式判断其轨迹相交类型，若类型与待判断的几何基元类型相同，则表明该几何约束被固定，在几何约束图上修改该几何基元和相关约束的状态；若不相同，则取新的轨迹继续求交，循环判断。若相关的几何约束全部使用仍然不能固定该几何基元，则选择下一个几何基元为判断对象。

步骤4 若本次循环没有新几何基元被固定，则转步骤5；否则重复执行步骤3。

步骤5 所有几何基元的约束状态判断完毕，根据尺寸完备性状态与几何基元约束状态、尺寸使用状态的映射关系，从最终的几何约束图上依次判断得到每个尺寸的完备性状态，包括冗余尺寸、必需尺寸和待定尺寸，并列出细圆圈表示的缺少尺寸标注的几何基元。

假设几何基元数目为n，频度最高的步骤3 最多执行n（n+1）／2次，算法的最大复杂度为O（n2）。

3 示例

建立图7左侧所示的三维实体模型，并标注部分尺寸，其中包括冗余尺寸和缺失尺寸，在右侧标记涉及的几何基元，以PL，L和P开头的分别表示平面、直线和点。首先建立几何约束图，其次指定PL1，PL2和PL3为三个基准面，然后依照算法循环对每个几何基元的约束状态进行判定，判断流程如图8所示，边的箭头反映了几何基元的约束状态的判断顺序。由图8可知，实线且两节点用粗线圈表示的尺寸为冗余尺寸，共6 个，包括DIS（PL1，PL11）=30，DIS（PL6，L4）=15，DIS（PL3，L2）=72.68，DIS（PL21，PL15）=30，DIS（PL6，PL11）=30，DIS（PL12，L2）=30.68，剩余尺寸均为必需尺寸。用细线圈表示的节点为缺少尺寸标注的节点，包括平面PL19和PL16，其他平面均被完全固定。算法检查的结果与实际情况相符，表明了算法的有效性和可靠性。

4 结束语

本文对三维顺序尺寸标注的完备性检查进行了研究，将尺寸完备性的检查问题转换为几何基元约束状态的判断问题。提出轨迹的概念，并分析了几何约束下轨迹的生成规则。通过离散化操作，将轨迹同时求交分解为轨迹两两相交，并建立了各种轨迹的两两相交规则。利用约束图，循环判断每个几何基元的约束状态，按照尺寸完备性状态与几何基元约束状态、尺寸使用状态的映射关系，判断得到冗余尺寸、必需尺寸、待定尺寸和缺少尺寸标注的几何基元。最后以一个实例演示算法的运行过程，验证了算法的有效性。

本文提出的基于轨迹相交的顺序尺寸标注的完备性检查方法是一个基本框架，目前只对基本的几何基元和几何约束进行了处理，今后将以此为基础，引入包括圆柱面、圆锥面和球面等的复杂几何基元，以及相切、对称等复杂几何约束，并考虑循环标注问题，进一步研究更加通用的三维尺寸完备性检查方法。

［1］JI Yangjian，ZHANG Shuyou，TAN Jianrong.Completeness testing of dimensioning in multi-views based on space coordinate transformation［J］.Journal of Computer-Aided Design and Computer Graphics，2001，13（6）：561-565（in Chinese）.［纪 杨建，张树有，谭建荣.基于空间坐标转换模型的多视图尺寸完备性检查［J］.计算机辅助设计与图形学学报，2001，13（6）：561-565.］

［2］CHENG Bin，WANG Yongping.Study on completeness testing of multi-view dimension based on merger of directed graph［J］.Journal of Xi'an University of Architecture &Technology：Natural Science Edition，2004，36（2）：246-249（in Chinese）.［成 彬，王永平.图归并的多视图尺寸完备性判别方法研究［J］.西安建 筑科技 大学学 报：自然科学版，2004，36（2）：246-249.］

［3］TAN Zhen.Study on completenees testing of dimensioning in 2Ddrawing［D］.Shenyang：Northeastern University，2008（in Chinese）.［谭 祯.二维工程图尺寸完备性检查的研究［D］.沈阳：东北大学，2008.］

［4］YANG Bo.Dimension maturity check-up and automatic calculation to engineering drawing based on restriction theory and CR graph［D］.Xiangtan：Xiangtan University，2005（in Chinese）.［杨 勃.基于约束原理和CR 图的工程图尺寸信息完备性检验和自动计算［D］.湘潭：湘潭大学，2005.］

［5］ZHANG Shuyou，ZHUO Yong.The research on logical coordinate-based redundancy of dimensions in multi-views［J］.Journal of Engineering Graphics，1997，18（4）：66-70（in Chinese）.［张树有，卓 勇.基于逻辑坐标的多视图尺寸冗余性判别［J］.工程图学学报，1997，18（4）：66-70.］

［6］HOFFMANN C M，SITHARAM M，YUAN B.Making constraint solvers more usable：overconstraint problem［J］.Computer-Aided Design，2004，36（4）：377-399.

［7］JOAN-ARINYO R，SOTO-RIERA A.Combining constructive and equational geometric constraint-solving techniques［J］.Acm Transactions on Graphics，1999，18（1）：35-55.

［8］AIT-AOUDIA S，MANA I.Numerical solving of geometric constraints by bisection：a distributed approach［J］.Interna-tional Journal of Computing &Information Sciences，2004，2（2）：66-73.

［9］HOFFMAN C M，LOMONOSOV A，SITHARAM M.Decomposition plans for geometric constraint problems，partⅡ：new algorithms［J］.Journal of Symbolic Computation，2001，31（4）：409-427.

［10］VAN DER MEIDEN H A，BRONSVOORT W F.A non-rigid cluster rewriting approach to solve systems of 3Dgeometric constraints［J］.Computer-Aided Design，2010，42（1）：36-49.

［11］HIDALGO M，JOAN-ARINYO R.Computing parameter ranges in constructive geometric constraint solving：Implementation and correctness proof［J］.Computer-Aided Design，2012，44（7）：709-720.

［12］GAO X S，HOFFMANN C M，YANG W Q.Solving spatial basic geometric constraint configurations with locus intersection［J］.Computer-Aided Design，2004，36（2）：111-122.

［13］GAO X S，JIANG K，ZHU C C.Geometric constraint solving with conics and linkages［J］.Computer-Aided Design，2002，34（6）：421-433.

［14］HOFFMAN C M，LOMONOSOV A，SITHARAM M.Decomposition plans for geometric constraint systems，partⅠ：performance measures for CAD［J］.Journal of Symbolic Computation，2001，31（4）：367-408.

［15］AIT-AOUDIA S，FOUFOU S.A 2D geometric constraint solver using agraph reduction method［J］.Advances in Engineering Software，2010，41（10／11）：1187-1194.

［16］DESROCHERS A，CL MENT A.A dimensioning and tolerancing assistance model for CAD／CAM systems［J］.The International Journal of Advanced Manufacturing Technology，1994，9（6）：352-361.

［17］MARTINEZ M L，FELEZ J.A constraint solver to define correctly dimensioned and overdimensioned parts［J］.Computer-Aided Design，2005，37（13）：1353-1369.

［18］LI Y T，HU S M，SUN J G.A constructive approach to solving 3-D geometric constraint systems using dependence analysis［J］.Computer-Aided Design，2002，34（2）：97-108.