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 特征的定義 特征的一般性定義：“一個具有意義的區域。”“用于論證設計、工程和制造的任何實體。”“特征是一個產品模型的相關元素集，它必須遵從其識別與分類規則，被認為是一個獨立實體，并且在一個產品的生命周期中具有一定的功能意義。”“特征是有關幾何拓撲與功能基元的高層組合，以便于產品的設計、分析與制造。”“特征是包括材料類型、功能以真實描述信息的零件特性。”“特征是在設計、加工、裝配等過程中定義推理所需的關于零件形狀和其他屬性的信息集合。” 盡管目