第十章实体造型中的基本算法及特征造型

1、第十章 实体造型中的基本算法及特征造型 10.1 概述10.2 半边数据结构 10.3 欧拉操作 10.4 基本体元的生成 10.5 实体的布尔操作 10.6 特征造型 10.1 概述计算机辅助设计的发展：1. 二维绘图软件的发展 2. 分离的详细设计软件的发展，并向CAM延伸 3. 全关联的并行设计软件的发展，并向初步设计阶段延伸 10.2 半边数据结构当实体以边界模型存储时，翼边结构较好地描述了点、边、面之间的拓扑关系，但它也存在着一些缺陷。因此，人们提出了一种更完善的数据结构半边数据结构，简称半边结构。 10.2.1 半边数据结构描述10.2.2 半边结构程序描述 10.2.3 半边数据

2、结构的具体算法 10.2.1 半边数据结构描述5种节点Solid、Face、Loop、HalfEdge和Vertex的描述： Solid 节点Solid构成一个半边结构引用的根节点。在任意时刻，会存在几个数据结构引用，为了存取其中的一个，需要指向其Solid节点的指针。通过指向3个双向链表的指针，Solid节点给出对该模型的面、边和顶点的访问。所有实体被链接到一个双向链表中，这个表通过指向该表的后继和前驱实体的指针来实现。 Face 节点Face对应用半边结构表示的多面体的一个小平面。将具有多个边界的小面也包括在数据结构中，这样每个小面与一个环表(Loops)相联系，而每个环表示该小面的一条多

3、边形边界曲线。由于所有小面都表示平面多边形，则一个环(Loop)可指定为“外部”边界，而其他则表示小面的“孔”。这可用两个指向Loop节点的指针实现。一个指向“外部”边界，而另一个指向该面的所有环(Loop)组成的双向链表的首环(Loop)。通常遵循一个约定，称带孔的环(hole loops)为内环(rings)。面由一个4个浮点数表示的向量表示其平面方程。为了实现一个实体所有小面的双向链表，每个小面包含了指向该表前趋面和后继面的指针。最后的小面有一个指向其他实体的指针。 Loop 节点Loop描述前面讨论的一个用于连接的边界。它具有一个指向其他面的指针，一个指向构成边界的半边(Half Ed

4、ge)之一的指针，和指向该面的后继Loop和前驱Loop的指针。 Half Edge 节点Half Edge表示一个Loop的一条线段。它由在Loop方向上一个指向其他Loop的指针和一个指向该线段起始顶点的指针组成。指向Half Edge前驱和后继的指针实现一个Loop的半边(Half Edge)的双向链表，这样，线段的最后顶点可用做后继半边(Half Edge)的起始顶点。 Vertex 节点Vertex包含一个由4个浮点数表示的向量，它以齐次坐标形式表示三维空间的一个点。该节点指向后继顶点和前驱顶点。 图10.1 半边数据结构节点间的层次关系 使用附加的节点类型Edge来记录信息 Edg

5、e 节点Edge使两个半边相互联系。直观地讲，它将一个全边的两半组合在一起。它由指向“左”半边和“右”半边的指针组成。边的双向链表通过指向后继边和前驱边的指针来实现。 Half Edge 每个半边包含一个指向其他边的附加指针。 Vertex 每个顶点包含一个附加指针来指向起源于它的某一个半边。为了表示顶点的标识，以某特殊点做角点的所有小面必须(通过环和半边)引用那个点对应的Vertex节点。 图10.2 半边的标识法 10.2.2 半边结构程序描述 ypedef float vector4;t y p e d e f f l o a t matrix44;typedef short Id;ty

6、pedef struct solid Solid;typedef struct face Face;typedef struct loop Loop;typedef struct halfedge HalfEdge;typedef struct vertex Vertex;typedef struct edge Edge;typedef union nodes Node;struct solidId Solidno; /*solid identifier*/Face *sfaces; /*pointer to list faces*/Edge *sedges; /*pointer to lis

7、t of vertices*/Vertex *sverts; /*pointer to list of solid*/Solid *nexts; /*pointer to next solid*/Solid *prevs; /*pointer to previous solid*/;struct faceId faceno; /*face identifier*/Solid *fsolid; /*back pointer to solid*/Loop *flout; /*pointer to outer loop*/Loop *floops; /*pointer to list of loop

8、s*/vector feq; /*face equation*/Face *nextf; /*pointer to next face*/Face *prevf; /*pointer to previous face*/;struct loopHalfEdge *lege; /*pointer to ring of halfedges*/Face *lface; /*back pointer to face*/Loop *nextl; /*pointer to next loop*/Loop *prevl; /*pointer to previous face*/;struct edgeHal

9、fEdge *he1; /*pointer to right halfedge*/HalfEdge *he2; /*pointer to left halfedge*/Edge *nexte; /*pointer to next edge*/Edge *preve; /*pointer to previous edge*/;struct halfedgeEdge *edg; /*pointer to parent edge*/Vertex *vex; /*pointer to starting vertex*/Loop *wloop; /*back pointer to loop*/HalfE

10、dge *nxt; /*pointer to next halfedge*/HalfEdge *prv; /*pointer to previous halfedge*/;struct vertexId vertexno; /*vertex identifier*/HalfEdge *vedge; /*pointer to a halfedge*/vector vcoord; /*vertex coordinates*/Vertex *nextv; /*pointer to next vertex*/Vertex *prevv; /*pointer to previous vertex*/;u

11、nion nodesSolid s;Face f;Loop l;HalfEdge h;Vertex v;Edge e;/*return values and misc constants*/#define ERROR 1# define SUCCESS 2#define PI 3.141592653289793 /*node type parameters for memory allocation routines*/# define SOLID 0# define FACE 1# define LOOP 2# define HALFEDGE 3#define EDGE 4#define V

12、ERTEX 5 层次化存取 2. 边上的存取 3. 半边结构中数据的增删算法 10.2.3 半边数据结构具体算法10.2.3.1 10.2.3.1 层次化存取层次化存取 许多例程只需要简单地扫描整个数据结构，并在每个节点处执行某种计算即可。 通过层次结构，每个顶点能够通过检查其半边指针的方法一次性列出。若指针为空，或等于父半边，则列出该顶点，否则不再列出。同样地，每条边也能够通过检查其半边指针的方法一次性列出。作为沿已有路线存取顶点的可选择方法，半边数据结构提供了对顶点和边的一条直接存取路径。 10.2.3.2 10.2.3.2 边上的存取边上的存取 重要的，有用的宏定义： #define m

13、ate(he) (he= =he-edg-he1)?he-edg-he2:he-edg-he1) 10.2.3.3 10.2.3.3 半边结构中数据的增删算法半边结构中数据的增删算法 （1） 增加结点new例程 unsigned nodesize =sizeof(Solid), sizeof(Face), sizeof(Loop), sizeof(HalfEdge), sizeof(Edge), sizeof(Vertex), 0;（2）链表例程（3）半边例程 HalfEdge *addhe(e,v,where,sign)Edge *e;Vertex *v;HalfEdge *where;in

14、t sign;HalfEdge *he;if(where-edg=NULL)he=where;elsehe=(HalfEdge*)new(HALFEDGE,NULL);where-prv-nxt=he;he-prv=where-prv;where-prv=he;he-nxt=where;he-edg=e;he-vtx=v;he-wloop=where-wloop;if(sign=PLUS)e-he1=he;elsee-he2=he;return(he);HalfEdge *delhe(he);HalfEdge *he;if(he-edg=NULL) del(HALFEDGE,he,NULL);

15、 return(he);else if(he-nxt=he) he-edg=NULL; return he;else he-prv-nxt=he-nxt; he-nxt-prv=he-prv; del(HALFEDGE,he,NULL); return(he-prv);10.3 欧拉操作已知多面体的欧拉不变性定理，即对于一个顶点数为v、面数为f、边数为e的多面体，恒有如下性质：ve+f = 2 （欧拉公式）为了适应在数据结构中对各数据项的操作，在欧拉公式中引入另外3个参数：s：实体的个数。h：实体所含孔的个数。r：实体中面所含孔(内环)的个数。于是，欧拉公式扩展为 ve+f=2(sh)+r (

16、扩展的欧拉公式)如图10.3(a)中，v=8、e=12、f=6、s=1、h=0，满足扩展的欧拉公式。图10.3(b)中，v=14、e=21、f=9、s=1、h=1、r=2，也满足扩展的欧拉公式。 图10.3 两个实体 10.3.1 基本欧拉操作 符号说明：M(make)：增加K(kill)：删除V(vertex)：顶点E(edge)：边F(face)：面S(solid)：实体H(hole)：孔R(ring)：环基本欧拉操作一般包括如下5对：MVFS； Mev；Mef； Mekr； Kfmrh；KVFS； KEV； KEF； KEMR； MFKRH； MVFS MVFS生成一个solid，它只包

17、含一个顶点和一个面，没有环和边。这个面包在顶点的外面。MVFS是用于创建一个实体的初操作。KVFS 删去一个顶点，一个面和一个体，它是MVFS的逆操作。 MEV MEV在指定的s上增加一个新的顶点v和一条新边e，新边以v为顶点，指向s中的一个指定的已有顶点。KEV 删去s中的一个已有顶点和边，是MEV的逆操作。 MEF MEV 在指定的s中的一个面face上增加一条新边e，e将face分划出一个新的面f， f与face通过e相邻。KEF删去s中的一条边和一个面，是MEF的逆操作。 4.MEKR MEKR在s中一个指定面的外环与内环之相应顶点间增加一条新边e，从而使两个环合成一个外环。KEMR

18、删去s中面所含的一条边，生成一个新的内环，是MEKR的逆操作。 5. KFMRH KFMRH将两个面f1，f2变成一个面。其方法是将f2的外环变成f1的内环，结果是f2消去，f1出现一个内孔。KFMRH用于将两个面粘合成一个面，或将面的内环打穿，形成体的孔。MFKRH 删去一个内环和一个孔，从而创建一个面，是KFMRH的逆操作。 10.3.1.2 低级欧拉算子 1、 LMEVlmev为低级顶点分裂算子(vertex-spliting operator)2、 LMEFlmef，低级面分裂算子(face-spliting operator)。和lmev相似，如果he1!=he2，则lmef将用一条

19、从he1-vtx到he2-vtx的新边把he1和he2的环分为两个环。半边he1仍处于老环中，而he2被移到新环上，该环变成了一个新面的外边界。对于he1= =he2的特殊情况，就建立只带有一条边的环形面。3、 LKEMRlkemr，分裂一个环为两部分的低级算子。首先为一个新环的节点分配存储单元，然后，对将要删除边的相应的两个半边h1和h2进行操作，将它们保留在两个不同的部分中，其中与h2对应的部分变成新环。这种处理方式的优点是可以直接应用例程delhe删除h1和h2，且排除了“空”环等各种特殊情况。 10.3.1.3 高级级欧拉算子 高级欧拉算子的实现是基于其相应的低级欧拉算子和一些辅助例程

20、，这些辅助例程用来对半边数据结构进行搜索，查找所有需要的指针。高级欧拉操作总是分为两步实现： 1. 通过搜索，找出相应低级欧拉操作所需的半边结点参数。 2. 调用低级欧拉操作实现功能 例程getsolid用标识符sn从存有所有实体的表中对实体进行定位，若成功则返回一个指向该实体的指针，否则返回一个空指针。 Solid *getsolid(sn)Id sn;Solid *s;for(s=firsts;s!=NULL;s=s-nexts)if(s-solidno=sn)return(s);else return(NULL);fface用标识符fn对实体S的小面f定位，并返回一个指向小面f的指针。F

21、ace *fface(s,fn)Solid *s;Id fn;Face *f;for(f=s-sfaces;f!=NULL;f=f-nextf)if(f-faceno=fn)return(f);else return(NULL);HalfEdge *fhe(f,vn1,vn2)Face *f;Id vn1,vn2;Loop *l;HalfEdge *h;for(l=f-floops;l!=NULL;l=l-nextl)h=l-ledg;doif(h-vtx-vertexno=vn1&h-nxt-vtx-vertexno=vn2)return(h);while(h=h-nxt)!=l-l

22、edg);return(NULL);根据得到的小面f，例程fhe从vn1和vn2中搜索一个半边。同样，如果查找不到，则返回NULL。 利用这些扫描例程，高级欧拉算子的实现是非常直观的。例如，下面程序中的算子mev，在搜索到所需的指针后，简单地调用相应的低级算子lmev来完成其操作。 10.4 基本体元的生成 10.4.1移动掠扫算法 10.4.2 长方体产生的算法 10.4.3 圆柱生成算法 10.4.4以曲线为基的旋转掠扫算法 10.4.1移动掠扫算法 移动掠扫算法使用一个基本平面FACE，并指定一个移动方向（dx,dy,dz）。其中dx,dy,dz分别表示移动距离的三上分量，通过欧拉操作，

23、自动生成一个多面体的半边数据结构 (a) (b) (c) (d) (e) (f) 图10.4 在程序10.1执行过程中，数据结构的逐步生成的示意图 void sweep(fac, dx, dy, dz)Face * fac;Float dx, dy, dz; Loop * l;HalfEdge*first, *scan;Vertex * v; lgetmaxnames(fac-fsolid);l = fac-floops;while(l)first = l-ledg; / * a * /scan = first-nxt;v =scan-vtx;lmev(scan, scan, +maxv,v-

24、vcoord0+dx,v-vcoord1+dy,v-vcoord2+dz); / * b * / 程序10.1移动掠扫算法while(scam ! = first) v = scan-nxt-vtx;lmev(scan-nxt, scan-nxt, +maxv,v-vcoord0+dx,v-vcoord1+dy,v-vcoord2+dz); / * c * /lmef(scan-prv, scan-nxt-nxt, +maxf); / * d * /scan = mate(scan-nxt)-nxt; / * e * /lmef(scan-prv, scan-nxt, +maxf);l = l

25、-nextl; / * end of sweep * /10.4.2 长方体产生的算法长方体产生的算法如程序10.2所示。函数block生成一个名为sn，长、宽、高分别为dx,dy,dz的直角六面体。block 的算法思想是：首先生成一个四边形的面，编号为2。然后将这个面按照0，0，dz的方向调用sweep程序进行移动掠扫，即生成一个长方体的数据结构。 Solid *block(sn, dx, dy, dz)Id sn;Float dx, dy, dz;Solid * s; s = mvfs(sn, l, l, 0.0, 0.0, 0.0);smev(sn, l, l, 2, dx, 0.0,

26、 0.0);smev(sn, l,2, 3, dx, dy, 0.0);smev(sn, l, 3, 4, 0.0, dy, 0.0); smef(sn, l, l, 4, 2);sweep(fface(s, 2), 0.0, 0.0, dz);return(s); 程序10.2 长方体生成算法 程序10.2中所用的专用欧拉操作smev的参数意义如下：smev(s, fl, vl, v4, x, y, z)smev专用于fl = f2的情况，此时f2不必再给出，并且区分v2和v3也就没有了意义。各参数的意义如图10.5所示。 v1 f1 = f2v1v4(x, y, z)smev图10.5 s

27、mev的功能 10.4.3圆柱生成算法 圆柱生成算法如程序10.3所示。函数cy1自动生成一个名为sn，高为h，底圆半径为rad，并以一个n边多边形逼近的圆柱。函数返回一根指向该圆柱的指针。其算法思想是：首先调用circle函数，生成一个半径为rad的正n边多边形。然后用sweep子程序掠扫 z = h方向而得到圆柱的数据结构。 Solid * cylinder(sn, rad, ht, nfac)Id sn;float rad, ht;int nfac;Solid * s; s = circle(sn, 0.0, 0.0, rad, 0.0, nfac);sweep(fface(s, l),

28、 0.0, 0.0, ht);return(s);程序10.3 圆柱生成算法 程序10.4示出函数circle的算法。这个函数自动生成一个名为sn，圆心位置在x = cx，y = cy, z = h, 半径为rad 的正n边形所逼近的圆的指针。其算法思想是：调用arc子程序，生成一个半径为rad的正n边形的n-1条边所逼近的圆弧。然后用smef操作生成最后一条边和一个逼近圆的正n边形数据结构。 Solid *circle(sn, cx, cy, rad, h, n)Id sn;float cx, cy, rad, h;int n;Solid * s, * mvfs( ); s = mvfs(s

29、n, l, l, cx, + rad, cy, h);arc(sn, l, l, cx, cy, rad, h, 0.0, (n-l) * 360.0 / n), n-l);smef(sn, l, n, l, 2);return(s);/ * end of circle * /程序10.4 圆生成算法 程序10.5示出子程序arc的算法。这个子程序以实体s所含的面f上的点v为起点，以cx, cy, h为圆心，rad为半径，生成一个以n条边折线所逼近的圆弧。圆弧的范围从角度phil起到phi2止，并定x轴角度为0，转角以逆时针方向为正。圆弧所在的平面与z轴垂直。其算法思想是；依次算出折线的n个顶

30、点的坐标值(x, y)，并用欧拉操作smev将它们连成一条弧并构成相应的数据结构。其中常数PI为圆周率。 void arc(s, f, v, cx, cy, rad, h, phil, phi2, n)Id s, f, v;floar cx, cy, rad, h, phi1, phi2;int n;float x, y, angle, inc;double sin( ), cos( );Id prev;int i; angle = phil * PI /180.0;inc = (phi2 phi1) * PI / (180.0 * n);prev = v;lgetmaxnames(s);fo

31、r(i = 0; isfaces-floops-ledg;while(first-edg ! = first-nxt-edg) first = first-nxt;last = first-nxt;while(last-edg! = last-nxt-edg) last = last-nxt;cfirst = first; / * a * /matident(m);matrotate(m, (-2.0 * PI / nfaces), 0.0, 0.0);while(-nfaces) vecmult(v, cfirst-nxt-vtx-vcoord, m); lmev(cfirst-nxt, c

32、first-nxt,+maxv, v0, v1, v2); scan = cfirst-nxt; / * b * / while(scan ! = last-nxt) vecmult(v, scan-prv-vtx-vcoord, m);lmev(scan-prv, scan-nxt, +maxf);scan = mate(scan-nxt-nxt); / * d * / last = scan; cfirst = mate(cfirst-nxt-nxt); / * e * / / * f * /tailf = lmef(cfirst-nxt, mate(first),+maxf);while

33、(cfirst ! = scan) lmef(cfirst, cfirst-nxt-nxt-nxt, +maxf); cfirst = mate(cfirst-prv)-prv; / * g * /程序 10.6 以曲线为基的旋转操作算法 cfirstscanfirstcfirstlastlastscanscancfirstscanlastcfirsttailfscanlastcfirstfirst(a) (b) (c) (d) (e) (f) (g) 图10.6 rsweep程序的执行过程图示 10.5 实体的布尔操作 10.5.1 引言 10.5.2 在Brep模型上的布尔集合操作 10.

34、5.3 边界分类 10.5.4 步骤 10.5.5 顶点邻域分类 10.5.6 空边的连接 10.5.7 结果的产生 10.5.8 提高拼合运算可靠性措施 10.5.1引言 实体的布尔运算是任何实体造型系统必不可少的组成部分，它完成实体间的并、交、差等布尔操作。许多算法中，布尔操作都提供一种方法来描述对应用对象的物理处理过程。 10.5.2 在Brep模型上的布尔集合操作 布尔集合操作包括3个操作，即交、并、差，它们分别记做、。通常，布尔集合操作的概念如图10.7所示 图10.7 A、B的布尔集合运算 对两个形状A、B进行布尔集合操作，可分两步进行： 将A和B沿相交线割剪成碎片。这个分裂操作称

35、为split。以图10.7所示的两个圆为例，split(A,B)x,y,z。 选择碎片，加以粘贴。这个粘合操作记为。以图10.7所示的两圆为例，粘合的规则是 zABxBAzyxBAyBA,首先定义如下记号。b(s)表示实体的边界。例如A的边界记为b(A)。A in B表示b(A)在B中的部分(图10.8(a)。A out B表示b(A)在B之外的部分。(A in B)1表示一个与A in B所含的所有面相同，但朝向相反的面的集合。A on B+表示b(A)中与b(B)相重合，并且法线方向相同的部分(图10.8(b)。 A on B表示b(A)中与b(B)相重合，并且法线方向与b(B)相反的部分

36、(图10.8(c)。 图10.8 边界的割剪 对于B-rep的布尔集合操作，仍分两步进行，描述如下： split(A,B)A out B,A in B,(A in B)1,A on B+,A on B,B out A,B in A,(B in A)1,B on A，其中B on A+与A on B+相同，故不列入内。 粘合规则(表示粘合操作) ABA in BB in AA on B+ ABA out BB out AA on B+ ABA out B(B in A)1A on B 上述粘合规则在实际使用中可以简化，即视操作的不同，将on用in或out代替。替代规则如下。 在AB中将A on

37、B+代之以A in B。 在AB中将A on B+代之以A out B。 在AB中将A on B代之以A out B。 因此，有简化的粘合规则如下。 ABA in BB in A ABA out BB out A ABA out B(B in A)1图10.9 A和B(B-rep)按交线割剪后的碎片 10.5.3 边界分类 “分裂”算法把整个问题划分为一系列的局部顶点邻域分类问题，且按照保证结果正确性的规则处理每个顶点邻域。这里的布尔运算算法及分类程序将同样使用这种方法。“分裂”算法把一个实体S按照分裂平面SP分裂成两个集合(Above,Below)。对集合运算来说，需要一个以多面体B为参考多

38、面体将多面体A分裂的更广义的方法。 给定两个实体A和B，将把A相对于B分裂或把B相对于A分裂所产生的4个实体A in B、A out B、B in A和B out A统称为A和B的“边界分类”。从A到B的边界分类可以容易地计算出它们的全部布尔组合，如第1组方程式所示。 为了生成重新分类规则，可以考虑A与B的8种(8-way)边界分类。它是在原来的4种(4-way)边界分类的分量中(A in B、A out B、B in A、B out A)增加分量 A on B+、A on B、 B on A+、B on A。由8种分类的分量可知，一个集合运算的结果能按第2组方程式计算。 具有这种性质的一组重

39、新分类规则纵向对应如下： Op A on B+ A on B B on A+ B on A A out B A in B B in A B in A A in B A out B B out A B out A/ A in B A out B B out A B out A10.5.4 步骤 将集合运算问题化成一系列的顶点邻域分类问题。这一问题能够概括如下： 确定所有A的边eA和B的边eB恰好彼此相交的边对，即这些边对在两者的内点处相交。再在它们的交点处子划分这两条边，即用两条边和位于交点上的一个新顶点来取代每一条边。 确定所有通过B的一个顶点A的边。再在交点处子划分所有这样的边。 对B的边和

40、A的顶点对称地做步骤2。 确定A的顶点VA与B的顶点VB的所有重合的顶点对，并保存它们供以后使用(当然，最后的集合至少包括步骤1到步骤3中所加的所有顶点)。 确定所有与B的一个小面fB恰好相交的A的边eA，即在fB的一个内点相交。再在交点处子划分所有这样的边。 对B的边和A的小面对称地做步骤5。 确定位于B的一个小面fB内的A的所有顶点VA，并保存(VA,fB)对，供后面处理用(这个集合将包括步骤5中所加的所有顶点)。 确定位于A的一个小面fA内的B的所有顶点VB，并保存(VB,fA)对，供后面处理用(这个集合将包括步骤6中所加的所有顶点)。 为了具体实现步骤18，有必要进一步假设A、B的所有

41、面均是最大的，即所有相邻的共面小面都已被组合，且所有出现在单个小面内的不必要的边已经去掉。在此前提条件下，搜索相交几何元素的工作可以组织成一个实体的所有边与另一个实体的小面之间的比较过程，反之亦然。并为每条边e、每个小面f作如下的情况分析： 边e的顶点均在面f的同侧，则e与f不相交。 边e的顶点在面f的异侧，则e恰好与f相交，此时可以算出交点，并通过“顶点在面内”例程对面f分类。这样就可以按照交点是否在面内、是否在面的一条边上、是否在一个顶点上或是否没有与面相交来作第二级的情况分析。 某边e的一个或两个顶点位于面f上，与情况2类似，可以用“顶点在面内”例程进行分类。除了顶点之外，边e与面f共面

42、的情况可以忽略，因为e与f的边之间的所有相交情况都在边e与(非共面的)f的邻面进行比较时得以确定。边面比较问题中，先算出所查询的边e的两端点到平面f的有符号距离。如果这两个距离异号，则该边必与平面f相交，此时计算出交点P(x,y,z)。其次，检查点P是否在面f内。如果点P与f相交，则将e在交点P处建立一个新顶点V进行子划分。如果P恰好落在f内，则(V,f)插入到共面的顶点一面对的集合中。如果P位于f的一条边e上，则将e进行子划分，并将新的顶点对插入到重合的顶点的集合中。最后，如果P位于f的一个顶点V上，则将顶点对(V,V)插入。如果被查询边的两个顶点的某一个到平面f的距离(近似地)等于零，则一

43、个共面的顶点就被定位。 10.5.5 顶点邻域分类经过上述操作，集合运算问题被简化为两类顶点邻域分类问题。 顶点面分类。一个实体的一个顶点位于另一个实体的一个小面上的处理。 顶点顶点分类。A与B的重合顶点对的处理。这些问题的解决与“分裂”算法极相似，它们都是通过一个邻域分类程序来解决的。该程序插入适当的空边，以使顶点邻域分裂成各个其他多面体之内或之外的子循环。顶点小面的实质与“分裂”算法相同。不同之处如下： 用小面的平面来取代分裂平面SP，且用“in”和“out”标志来取代“above”和“below”标志。 “on”扇区按新方程进行重新分类。 除了分裂顶点邻域外，对交点的一个引用也必须存放在

44、小面中，以便相交的多边形能通过该点画出。如果插入作为内环的空边到相交的小面中来标记求交的情况，连接空边的算法就能正确地工作，如图10.10所示。图10.10 顶点面分类 顶点顶点分类程序构成该算法的核心，它将两个顶点邻域(同重合的基顶点)进行比较，确定它们的求交情况，并插入适当的空边以便正确地产生相交的多边形。通过考虑两个邻域的扇区对，并检查它们的相交情况来完成对相交扇区的搜索。首先，算法计算出两个邻域的某些数据片，对“宽”扇区(其边界向量夹角大于180)进行子划分。其次，比较两个预先处理的扇区。如果两个扇区确实相交，则计算每个扇区相对于其他扇区的边界顶点分类(in,on,out)。扇区的相交

45、检查如图10.11所示 图10.11 扇区相交检查 图10.12 在扇区内检查 一个例子一个例子 图10.13 “on”扇区重新分类 当扇区相交检查完成之后，在数组sectors中有如下信息： A B A的方位代码 B的方位代码 相交位 A1 B1 IN-OUT OUT-ON 1 A1 B2 ON-ON ON-ON 1 A2 B2 ON-IN IN-OUT 1如果想计算集合并，由方程的规则知A1应该重新分类成位于B外，B2重新分类成位于A内。因此，数组sectors信息应读成：A B A的方位代码 B的方位代码 相交位 A1 B1 IN-OUT OUT-ON 1 A1 B2 OUT-OUT I

46、N-IN 0 A2 B2 ON-IN IN-OUT 1但这也可使用户对相邻扇区的信息重新分类。例如，如图10.13中所示，A2如果处理成与B2相交，它的方位代码(side code)应该读成OUT-IN。这样得到如下结果：A B A的方位代码 B的方位代码 相交位 A1 B1 IN-OUT OUT-IN 1 A1 B2 OUT-OUT IN-IN 0 A2 B2 OUT-IN IN-OUT 1 图10.14 “on”边重新分类 图10.15 简单“on”边 图10.16 双“on”边 图10.13的例子的最终结果。A B A的方位代码 B的方位代码 相交位 A1 B1 IN-OUT OUT-I

47、N 1 A1 B2 OUT-OUT IN-IN 0 A2 B2 OUT-IN IN-OUT 1 图10.17 插入空边 惟一需要处理的另一种情况就是，一个扇区有几个相交的情况。如果有，则必须确定如下排列之一将被定位。 A B A的方位代码 B的方位代码 相交位 A1 B1 IN-OUT OUT-IN 1 A1 B2 OUT-IN IN-OUT 1 A2 B1 OUT-IN IN-OUT 1在这些情况下，正确的做法是将一个“悬挂”(struct)空边分别插入到扇区A1或B1中。 10.5.6 空边的连接 现在讨论由前面的步骤产生的空边的组合，目的是生成相交的多边形。这与分裂算法的连接问题类似，不

48、同之处在于这里的相交多边形通常不是平面图形。不能期望同样的算法对集合运算也适用。然而可以进一步开发集合运算的特性。空边总是成对产生的，一个在实体A内，另一个在实体B内。当然，相交多边形应在每个实体中以同样的方式构造出来，即以对应空边的相同顺序来构造。利用这个性质，产生了一种基于集合运行的空边组合算法。该算法每次仅考虑两个对应的空边，且仅当它们能够连接到一个开口端时，才认为它们是“可以连接的”。当前的开口端保存两个数。如果这些边不能被连接，它们就被加到开口端的集合中。显然，数组的更新是以保持一致的方式实现的。 10.5.7结果的产生 布尔运算算法的最后阶段是由实际应用方程来产生最终结果。将每个空

49、间划分成两个相交的小面。基于空边的一致方位，新的小面被认为是属于A、B边界分类的“in”部分(A in B,B in A)，而其余的小面则属于“out”部分。算法把所希望的部分送入结果实体中。然后，重新构造结果的边和顶点表。最后，将相交的小面组合，而它们的边和顶点进行合并。集合差运算实现起来稍困难一些，因为“in”部分的方位必须首先颠倒一下。这是通过建立一个临时实体A in B，且颠倒其方位来实现的。这些工作做完之后，合并(merge)将作出正确的处理。可以看到，在最终结果中不需要的A与B的部分将保留在原来的实体中。这意味着本算法可以推广以便同时计算出AB、AB、AB或BA。 10.5.8 提

50、高拼合运算可靠性措施 计算机浮点运算中的尾数圆整误差对实体拼合运算的可靠性产生极大障碍。下面说明在on/on集合分类中引入平面厚度并利用顶点与边、面相互间的on/on约束关系进行推理的方法。 )()()()(111iiinijijinijijinijijiczbyaxdyyxxcxxzzbzzyya 式中j=i+1，当i=n时j=1。 计算多边形每个顶点Vi(i=1,2,n)到平面f的距离di。di=axi+byi+czi+d由于各种误差的影响，并非所有的d=0。取其中绝对值最大的一个di乘以2，叫做多边形P的厚度tP。|)(|max21iniPdt图10.18 on/on关系的验证 图10.

51、19 on/on关系的相容性调整步骤10.6.1 特征的定义 10.6.2 特征的分类 10.6.3 特征的形式化描述 10.6.4 特征造型系统实现模式 10.6.5 特征表示 10.6.6 特征与约束 10.6.7 特征的依赖描述 10.6 特征造型10.6.1 特征的定义 特征的一般性定义：“一个具有意义的区域。”“用于论证设计、工程和制造的任何实体。”“特征是一个产品模型的相关元素集，它必须遵从其识别与分类规则，被认为是一个独立实体，并且在一个产品的生命周期中具有一定的功能意义。”“特征是有关几何拓扑与功能基元的高层组合，以便于产品的设计、分析与制造。”“特征是包括材料类型、功能以真实描述信息的零件特性。”“特征是在设计、加工、装配等过程中定义推理所需的关于零件形状和其他属性的信息集合。” 尽管目