ch6三維形體的表示課件

引言三維圖形在科學研究和工程技術(shù)中有著廣泛的應(yīng)用。在CAD中，需要對所設(shè)計的作品從不同的角度進行審視。計算機幾何造型就是用計算機系統(tǒng)來表示、控制、分析和輸出三維形體。所以幾何造型是計算機圖形學中一個十分重要的應(yīng)用領(lǐng)域，它是CAD/CAM和CIMS系統(tǒng)的核心技術(shù)，也是用來實現(xiàn)計算機輔助設(shè)計的基本手段。幾何造型的功能：形體輸入，即把形體從用戶格式轉(zhuǎn)換成計算機內(nèi)部格式；圖形數(shù)據(jù)的存儲和管理；圖形控制，如對形體進行平移、縮放、旋轉(zhuǎn)等幾何變換；圖形修改，如應(yīng)用集合運算、歐拉運算、有理B樣條操作及其交互手段實現(xiàn)對形體局部或整體修改；圖形分析，如形體的容差分析，物質(zhì)特性分析等；圖形顯示輸出，如消隱、光照、顏色的控制等；詢問形體的屬性及其有關(guān)參數(shù)引言三維圖形在科學研究和工程技術(shù)中有著廣泛的應(yīng)用。在CA1形體在計算機形體一般定義為六層拓撲結(jié)構(gòu)，首先介紹在三維空間中基本術(shù)語的定義。形體(object)外殼(shell)面(face)環(huán)(loop)邊(loop)頂點(vertex)曲線和直線方程點的幾何坐標形體在計算機形體一般定義為六層拓撲結(jié)構(gòu)，首先介紹在三維空2形體體

由封閉表面圍成的有效空間稱為體；一個形體Q是R3空間中非空、有界的封閉子集。其邊界（記為?Q）是有限個面的并集，而外殼是形體的最大邊界。一個單位立方體可定義為： {(x,y,z)∈R3|0≤x≤1,0≤y≤1,0≤z≤1}

其中一個表面可表示為：

{(1,y,z)∈R3|0≤y≤1,0≤z≤1} 必須注意：并沒有規(guī)定形體必須是一個連續(xù)的封閉集合，目的是用這樣的定義來擴大幾何造型的域，使得形體可以由不連續(xù)的體素，或是僅有某些相交的形體組成。xzy形體體

由封閉表面圍成的有效空間稱為體；一個形體Q是R33形體面

R3中非空、連續(xù)、共面且封閉的子集稱為面F，

其邊界(記為?F)是有限條線段的并集，

Pt表示含有F的唯一平面。

面是形體表面的一部分，且具有方向性.FPt形體面

R3中非空、連續(xù)、共面且封閉的子集稱為面F，

4形體環(huán)

由有序、有向邊組成的面的封閉邊界稱為環(huán)，環(huán)中任意邊都不能自交，相鄰兩條邊共享一個端點，環(huán)又分為內(nèi)環(huán)和外環(huán)。內(nèi)環(huán)是在已知面中的內(nèi)孔或凸臺面邊界的環(huán)，其邊按逆時針方向。外環(huán)是已知面的最大外邊界的環(huán)，其邊按順時針方向，按這種方式定義，在面上沿著邊的方向前進，面的內(nèi)部始終在走向的右側(cè)。形體環(huán)

由有序、有向邊組成的面的封閉邊界稱為環(huán)，環(huán)中任意5形體邊

形體內(nèi)兩個相鄰面的交界稱為邊，一條邊有且僅有兩個相鄰面。兩個端點確定一條邊，這兩個端點分別稱為該邊的起點和終點。假設(shè)Q是一個形體，E(Q)是形體邊的集合，則在?Q(形體的邊界)中E(Q)滿足下屬條件的所有線段的集合：邊e的兩個端點屬于V(Q)；邊e中沒有一個內(nèi)部點屬于V(Q)（所有頂點的集合）邊e上每個點，都有兩個不同的面，即存在兩個面fi，fi≤?Q使得邊e∈fi∩fj；形體Q的邊框線WF(Q)是由有序?qū)?V(Q),E(Q))所組成。v1v2ef1f2形體邊

形體內(nèi)兩個相鄰面的交界稱為邊，一條邊有且僅有兩個6形體點

邊的端點稱為點，點不能出現(xiàn)在邊的內(nèi)部，也不能孤立地位于物體內(nèi)、物體外或面內(nèi)，頂點又是?F(面邊界)中兩條不共線的線段的交點。v1v2ef1f2形體點

邊的端點稱為點，點不能出現(xiàn)在邊的內(nèi)部，也不能孤立7形體體素

具有有限個參數(shù)定義，且簡單

的連續(xù)封閉的形體稱為體素，

如長方體、圓柱體、圓錐、球、環(huán)等。半空間

集合{P|F(P)≤0}成為半空間，其中P為R3中的一點，F(xiàn)為一個平面，當F=0時，表示一個平面，這個平面的半空間可以由F(P)=ax+by+cz+d定義的平面加上在平面某一側(cè)的所有點組成。顯然一個長方體可以看成是6個平面半空間的交。幾何信息

用來表示形體的幾何性質(zhì)和度量關(guān)系稱為幾何信息。拓撲信息

用來表示形體之間的連接關(guān)系稱為拓撲信息。形體體素

具有有限個參數(shù)定義，且簡單

的連續(xù)封閉的形體稱8表示形體的兩種模型數(shù)據(jù)模型完全以數(shù)據(jù)描述例如用以8個頂點表示的立方體以中心點和半徑表示的球以數(shù)據(jù)文件的形式存在包括----特征表示、空間分割表示、推移表示、邊界表示、構(gòu)造實體幾何表示等進一步分為線框模型表面模型實體模型表示形體的兩種模型數(shù)據(jù)模型9線框模型線框模型：將形體表示成一組輪廓線的集合。一般地，畫出了形體的棱線與輪廓線就能唯一地表示出來。如圖，八個頂點可以定義一個長方體，但還不足以識別它，如果定義了棱線，則無論如何放置長方體都能唯一地表示了。對于多面體由于其輪廓線和棱線通常是一致的，所以多面體的線模型更便于識別，且簡單。e12v4v8s3e2e4e6e8e2e7e11e10e9e3e1v2v3v1v7v5v6s2s6s5s1s4線框模型線框模型：將形體表示成e12v4v8s3e2e4e610線框模型優(yōu)點：簡單、處理速度快缺點：1、對于非平面多面體，如圓柱、球等形體，其輪廓線隨觀察方向的改變而改變，無法用一組固定的輪廓線來表示它們。2、線框模型與形體之間不存在一一對應(yīng)關(guān)系：它僅僅通過給定的輪廓線約束所表示形體的邊界面，而在輪廓線之間的地方，形體的表面可以任意變化。3、沒有形體的表面信息，不適于真實感顯示，由此導(dǎo)致表示的形體可能產(chǎn)生二義性。線框模型優(yōu)點：簡單、處理速度快11表面模型表面模型將形體表示成一組表面的集合如果把線框模型中的棱線包圍的部分定義為面，所形成的模型便是表面模型。其數(shù)據(jù)結(jié)構(gòu)是在線模型的基礎(chǔ)上附加一些指針，有序地連接棱線。下圖中表面編號表示第幾個表面，表面特征表面是平面還是曲面。形體與其表面一一對應(yīng)，適合于真實感顯示4頂點個數(shù)1起始指針0表面特征5表面編接指針屬性頂點號14232341表面模型表面模型4頂點個數(shù)1起始指針0表面特征5表面編號1412表面模型缺點：不能有效的用來表示實體原因：1、表面模型中的所有面未必形成一個封閉的邊界2、各個面的側(cè)向沒有明確定義，即不知道實體位于面的哪一側(cè)表面模型缺點：13實體模型實體模型用來描述實體，主要用于CAD/CAM包含了描述一個實體所需的較多信息，如幾何信息、拓撲信息，可以支持多種運算，如歐拉運算等。實體模型實體模型14表示形體的兩種模型過程模型以一個過程和相應(yīng)的控制參數(shù)描述例如用一些控制參數(shù)和一個生成規(guī)則描述的植物以一個數(shù)據(jù)文件和一段代碼的形式存在包括----粒子系統(tǒng)、L系統(tǒng)、迭代函數(shù)系統(tǒng)等表示形體的兩種模型過程模型15表示形體的兩種模型模型分類表示形體的兩種模型模型分類16實體的定義抽象帶來的問題計算機中表示的物體是無效的不能夠客觀存在為什么要求客觀存在CAD/CAM的需求什么是客觀存在（有效）—實體的定義具有一定的形狀具有封閉的邊界（表面)內(nèi)部連通占據(jù)有限的空間經(jīng)過運算后，仍然是有效的物體實體的定義抽象帶來的問題17實體的定義將三維物體看做一個點集，它由內(nèi)點和邊界點共同組成。內(nèi)點：具有完全包含于該點集的充分小的鄰域邊界點：不具有內(nèi)點性質(zhì)的點集實體的定義將三維物體看做一個點集，它由內(nèi)點和邊界點共同組成。18實體的定義

A是一個點集，定義點集的正則運算如下：i：取內(nèi)點運算c:取閉包運算正則運算riA：A的全體內(nèi)點組成的集合，稱為A的內(nèi)部ciA為A的內(nèi)部的閉包的運算，是iA與其邊界點的并集。實體的定義19實體的定義正則點集稱為A的正則點集稱A為正則點集，如果它滿足問題：正則點集是實體？實體的定義正則點集20實體的定義-舉例說明陰影部分：物體的內(nèi)部區(qū)域黑色部分：邊界(a)圖取內(nèi)點->(b)圖求閉包->(c)圖正則運算：去除與物體維數(shù)不一致的懸掛部分或孤立部分。實體的定義-舉例說明陰影部分：物體的內(nèi)部區(qū)域21實體的定義實體的定義—可計算的條件正則點集表面是二維流形二維流形其上任意一點存在充分小的領(lǐng)域與圓盤同構(gòu)（存在連續(xù)的一一映射）實體的定義實體的定義—可計算的條件22正則集合運算為什么需要正則集合運算正則集合運算是構(gòu)造復(fù)雜物體的有效方法普通的集合運算會產(chǎn)生無效物體(b):A∩B(c):普通A∩B(d)：正則A∩B正則集合運算為什么需要正則集合運算23正則集合運算集合運算（并、交、差）是構(gòu)造形體的基本方法。正則形體經(jīng)過集合運算后，可能會產(chǎn)生懸邊、懸面等低于三維的形體。Requicha在引入正則形體概念的同時，還定義了正則集合運算的概念。正則集合運算保證集合運算的結(jié)果仍是一個正則形體，即丟棄懸邊、懸面等。正則集合運算集合運算（并、交、差）是構(gòu)造形體的基本方法。正則24正則集合運算正則集合運算的定義正則并正則交正則差正則集合運算正則集合運算的定義25

任一實體S可以用它的邊界bS和它的內(nèi)部iS來表示，即

S=bS∪iS

由實體的定義可知，bS是封閉的，它將整個三維空間分成了三個區(qū)域：S的內(nèi)部iS,S的邊界bS,S的外部eS。邊界bS與實體S是一一對應(yīng)的。確定了邊界，也就唯一確定了一個實體。因此，為了求實體A，B的正則集合運算結(jié)果Aop*B，只要求出其邊界b（Aop*B）即可。

正則集合運算任一實體S可以用它的邊界bS和它的內(nèi)部iS來表26正則集合運算考察A,B兩物體的交所形成拼合體的邊界，由于A,B為正則點集，它們均可表示為邊界點與體內(nèi)點的集合，即A=bA∪iA;B=bB∪iBA物體的邊界bA可按其位于B物體內(nèi)、B物體上、B物體外而分別表示為

bA=(bA∩iB)∪(bA∩bB)∪(bA∩eB)

同理，bB=(bB∩iA)∪(bB∩bA)∪(bB∩eA)

A正則集合運算考察A,B兩物體的交所形成拼合體的邊界，A27正則集合運算其中bA∩bB=bB∩bA是A與B的公共邊界，它可以分成兩部分：（bA∩bB）同側(cè)、(bA∩bB)異側(cè)(bA∩bB)同側(cè)由這樣一些邊界構(gòu)成：A、B位于邊界的同側(cè)(bA∩bB)異側(cè)由這樣一些邊界構(gòu)成：A、B位于邊界的異側(cè)正則集合運算其中bA∩bB=bB∩bA是A與B的28正則集合運算對于A∩*B，由交的定義可知：1）A、B兩物體的邊界位于對方內(nèi)部的部分，即bA∩iB和bB∩iA是b(A∩*B)的組成部分。2）A、B兩物體的邊界位于對方外部的部分，即bA∩eB和bB∩eA不是b(A∩*B)的組成部分。3）對于A、B的重合邊界有：(bA∩bB)同側(cè)屬于b(A∩*B);(bA∩bB)異側(cè)不屬于b(A∩*B)因此：b(A∩*B)=(bA∩iB)∪(bB∩iA)∪(bA∩bB)同側(cè)正則集合運算對于A∩*B，由交的定義可知：29正則集合運算同理：b(A∪*B)=(bA∩eB)∪(bB∩eA)∪(bA∩bB)同側(cè)b(A－*B)=(bA∩eB)∪(bB∩iA)∪(bA∩bB)異側(cè)正則集合運算同理：30一些非正則形體的實例一些非正則形體的實例一些非正則形體的實例一些非正則形體的實例31為了能夠處理非正則形體，產(chǎn)生了非正則造型技術(shù)。九十年代以來，基于約束的參數(shù)化、變量化造型和支持線框、曲面、實體統(tǒng)一表示的非正則形體造型技術(shù)已成為幾何造型技術(shù)的主流。為了能夠處理非正則形體，產(chǎn)生了非正則造型技術(shù)。32形體表示模型在實體模型的表示中，基本上可以分為分解表示、構(gòu)造表示和邊界表示三大類。1、分解表示將形體按某種規(guī)則分解為小的更易于描述的部分，每一小部分又可分為更小的部分，這種分解過程直至每一小部分都能夠直接描述為止。形體表示模型在實體模型的表示中，基本上可以分為分解表示、構(gòu)造33分解表示-空間位置枚舉表示形體空間細分為小的均勻的立方體單元。用三維數(shù)組C[I][J][K]表示物體，數(shù)組中的元素與單位小立方體一一對應(yīng)當C[I][J][K]=1時，表示對應(yīng)的小立方體被物體占據(jù)當C[I][J][K]=0時，表示對應(yīng)的小立方體沒有被物體占據(jù)分解表示-空間位置枚舉表示形體空間細分為小的均勻的立方體單元34分解表示-空間位置枚舉表示優(yōu)點簡單，可以表示任何物體容易實現(xiàn)物體間的交、并、差集合運算容易計算物體的整體性質(zhì)，如體積等缺點占用大量的存儲空間，如1024*1024*1024=1Gbits物體的邊界面沒有顯式的解析表達式，不適于圖形顯示對物體進行幾何變換困難，如非90度的旋轉(zhuǎn)變換是物體的非精確表示分解表示-空間位置枚舉表示優(yōu)點35分解表示-八叉樹表示八叉樹表示對空間位置枚舉表示的空間分割方法作了改進：均勻分割自適應(yīng)分割八叉樹建立過程八叉樹的根節(jié)點對應(yīng)整個物體空間如果它完全被物體占據(jù)，將該節(jié)點標記為F(Full)，算法結(jié)束；如果它內(nèi)部沒有物體，將該節(jié)點標記為E(Empty)，算法結(jié)束；如果它被物體部分占據(jù)，將該節(jié)點標記為P(Partial)，并將它分割成8個子立方體，對每一個子立方體進行同樣的處理分解表示-八叉樹表示八叉樹表示八叉樹的根節(jié)點對應(yīng)整個物體空間36分解表示-八叉樹表示8叉樹的表示應(yīng)用三維形體的分解，它對一個外接立方體的形體進行前后、左右、上下等部分8個小立方體，如果小立方體單元為滿或為空，表示該立方體完全在形體中或完全不在形體中，則其停止分解；對部分形體占有的小立方體需進一步分解為8個子立方體，直至所有小立方體單元要么全部滿，要么全部空，或已分解到規(guī)定的分解精度為止。236720131375具有子孫的節(jié)點(P)空節(jié)點(E)實節(jié)點(F)分解表示-八叉樹表示8叉樹的表示應(yīng)用三維形體的分解，它對一個37分解表示-八叉樹表示優(yōu)點可以表示任何物體，且形體表示的數(shù)據(jù)結(jié)構(gòu)簡單簡化了形體的集合運算。只需同時遍歷參加集合運算的兩形體相應(yīng)的八叉樹，無需進行復(fù)雜的求交運算。簡化了隱藏線（或面）的消除，因為在八叉樹表示中，形體上各元素已按空間位置排成了一定的順序。分析算法適合于并行處理。缺點沒有邊界信息，不適于圖形顯示對物體進行幾何變換困難是物體的非精確表示占用大量存儲。實際上，八叉樹表示是以存儲空間換取算法的效率分解表示-八叉樹表示優(yōu)點38分解表示-線性八叉樹表示線性八叉樹：用一可變長度的一維數(shù)組來存儲一棵八叉樹。數(shù)組中僅存儲八叉樹的性質(zhì)為FULL的終端結(jié)點。并用一個八進制數(shù)表示該結(jié)點在八叉樹中的位置。編碼方式為：Q1Q2…Qm,其中Q1表示該結(jié)點所屬的一級父結(jié)點的編號（0-7），以此類推。例右圖為：{1X,30X,31X,323X,33X}

3

2031

75具有子孫的節(jié)點(P)空節(jié)點(E)實節(jié)點(F)分解表示-線性八叉樹表示線性八叉樹：用一可變長度的一維數(shù)組來39分解表示-單元分解表示單元分解表示對空間位置枚舉表示的空間分割方法作了改進：單一體素多種體素三種空間分割方法的比較空間位置枚舉表示----同樣大小立方體粘合在一起表示物體八叉樹表示----不同大小的立方體粘合在一起表示物體單元分解表示----多種體素粘合在一起表示物體分解表示-單元分解表示單元分解表示40分解表示-單元分解表示優(yōu)點表示簡單容易實現(xiàn)幾何變換基本體素可以按需選擇，表示范圍較廣可以精確表示物體缺點物體的表示不唯一物體的有效性難以保證分解表示-單元分解表示優(yōu)點41構(gòu)造表示掃描表示構(gòu)造實體幾何表示（CSG）特征表示構(gòu)造表示掃描表示42構(gòu)造表示-推移表示將物體A沿著軌跡P推移得到物體B，稱B為sweep體平移sweep----將一個二維區(qū)域沿著一個矢量方向推移構(gòu)造表示-推移表示將物體A沿著軌跡P推移得到物體B，稱B為s43構(gòu)造表示-推移表示旋轉(zhuǎn)sweep----將一個二維區(qū)域繞旋轉(zhuǎn)軸旋轉(zhuǎn)一周構(gòu)造表示-推移表示旋轉(zhuǎn)sweep----將一個二維區(qū)域繞旋轉(zhuǎn)44 三維形體也能在空間通過掃 描變換生成新的形體：如左 圖，一個圓柱體按指定方向 在長方體上運動生成新的形 體，這個過程猶如長方體與 運動者的圓柱體不斷的作差 運算操作。

有時經(jīng)過掃描變換所生成的形體可能會出現(xiàn)維數(shù)不一致問題。構(gòu)造表示-推移表示掃描線方向U 三維形體也能在空間通過掃 描變換生成新的形45構(gòu)造表示-推移表示廣義sweep任意物體沿著任意軌跡推移推移過程中物體可以變形構(gòu)造表示-推移表示廣義sweep46構(gòu)造表示-推移表示優(yōu)點表示簡單、直觀適合做圖形輸入手段缺點作幾何變換困難對幾何運算不封閉用掃描變換產(chǎn)生的形體可能出現(xiàn)維數(shù)不一致的問題。掃描方法不能直接獲取形體的邊界信息，表示形體的覆蓋域非常有限。構(gòu)造表示-推移表示優(yōu)點47構(gòu)造表示-構(gòu)造實體幾何表示(CSG).通過對體素定義運算而得到新的形體的一種表示方法。體素可以是立方體、圓柱、圓錐等，也可以是半空間，其運算為變換或正則集合運算并、交、差。CSG表示可以看成是一棵有序的二叉樹。其終端節(jié)點或是體素、或是形體變換參數(shù)。非終端結(jié)點或是正則的集合運算，或是變換（平移和/或旋轉(zhuǎn)）操作，這種運算或變換只對其緊接著的子結(jié)點（子形體）起作用。構(gòu)造表示-構(gòu)造實體幾何表示(CSG).通過對體素定義運算而得48構(gòu)造表示-構(gòu)造實體幾何表示(CSG)構(gòu)造表示-構(gòu)造實體幾何表示(CSG)49構(gòu)造表示-構(gòu)造實體幾何表示(CSG)CSG樹是無二義性的，但不是唯一的.CSG表示的優(yōu)點：數(shù)據(jù)結(jié)構(gòu)比較簡單，數(shù)據(jù)量比較小，內(nèi)部數(shù)據(jù)的管理比較容易；物體的有效性自動得到保證；CSG方法表示的形體的形狀，比較容易修改。構(gòu)造表示-構(gòu)造實體幾何表示(CSG)CSG樹是無二義性的，但50構(gòu)造表示-構(gòu)造實體幾何表示(CSG)CSG表示的缺點：對形體的表示受體素的種類和對體素操作的種類的限制，也就是說，CSG方法表示形體的覆蓋域有較大的局限性。對形體的局部操作不易實現(xiàn)，例如，不能對基本體素的交線倒圓角；由于形體的邊界幾何元素（點、邊、面）是隱含地表示在CSG中，故顯示與繪制CSG表示的形體需要較長的時間。表示不唯一

構(gòu)造表示-構(gòu)造實體幾何表示(CSG)CSG表示的缺點：51構(gòu)造表示-特征表示用一組特征參數(shù)表示一組類似的物體特征包括形狀特征、材料特征等適用于工業(yè)上標準件的表示構(gòu)造表示-特征表示用一組特征參數(shù)表示一組類似的物體52構(gòu)造表示-特征表示從應(yīng)用層來定義形體，因而可以較好的表達設(shè)計者的意圖。從功能上可分為形狀、精度、材料和技術(shù)特征。特征是面向應(yīng)用、面向用戶的。特征模型的表示仍然要通過傳統(tǒng)的幾何造型系統(tǒng)來實現(xiàn)。不同的應(yīng)用領(lǐng)域，具有不同的應(yīng)用特征。在幾何造型系統(tǒng)中，根據(jù)特征的參數(shù)我們并不能直接得到特征的幾何元素信息，而在對特征及在特征之間進行操作時需要這些信息。特征方法表示形體的覆蓋域受限于特征的種類。構(gòu)造表示-特征表示從應(yīng)用層來定義形體，因而可以較好的表達設(shè)計53構(gòu)造表示的特點構(gòu)造表示的特點：構(gòu)造表示通常具有不便于直接獲取形體幾何元素的信息、覆蓋域有限等缺點，但是，便于用戶輸入形體，在CAD/CAM系統(tǒng)中，通常作為輔助表示方法。構(gòu)造表示的特點構(gòu)造表示的特點：54邊界表示邊界表示（BR表示或BRep表示）按照體－面－環(huán)－邊－點的層次，詳細記錄了構(gòu)成形體的所有幾何元素的幾何信息及其相互連接的拓撲關(guān)系。邊界表示的一個重要特點是在該表示法中，描述形體的信息包括幾何信息（Geometry）和拓撲信息（Topology）兩個方面。拓撲信息描述形體上的頂點、邊、面的連接關(guān)系，拓撲信息形成物體邊界表示的“骨架”。形體的幾何信息猶如附著在“骨架”上的肌肉。邊界表示邊界表示（BR表示或BRep表示）55邊界表示邊界模型表達形體的基本拓撲實體包括：1.頂點2.邊。邊有方向，它由起始頂點和終止頂點來界定。邊的形狀（Curve）由邊的幾何信息來表示，可以是直線或曲線，曲線邊可用一系列控制點或型值點來描述，也可用顯式、隱式或參數(shù)方程來描述。邊界表示邊界模型表達形體的基本拓撲實體包括：56邊界表示3.環(huán)。環(huán)（Loop）是有序、有向邊（Edge）組成的封閉邊界。環(huán)有方向、內(nèi)外之分，外環(huán)邊通常按逆時針方向排序，內(nèi)環(huán)邊通常按順時針方向排序。4.面。面（Face）由一個外環(huán)和若干個內(nèi)環(huán)（可以沒有內(nèi)環(huán)）來表示，內(nèi)環(huán)完全在外環(huán)之內(nèi)。若一個面的外法矢向外，稱為正向面；反之，稱為反向面。邊界表示3.環(huán)。環(huán)（Loop）是有序、有向邊（Edge）組57邊界表示面的形狀可以是平面或曲面。平面可用平面方程來描述，曲面可用控制多邊形或型值點來描述，也可用曲面方程（隱式、顯式或參數(shù)形式）來描述。對于參數(shù)曲面，通常在其二維參數(shù)域上定義環(huán)，這樣就可由一些二維的有向邊來表示環(huán)，集合運算中對面的分割也可在二維參數(shù)域上進行。5.體。體（Body）是面的并集。邊界表示面的形狀可以是平面或曲面。平面可用平面方程來描述，曲58邊界表示邊界表示模型是一種采用描述形體表面的方法來描述的幾何表示模型。一個形體一般可以通過其邊界拆成一些有界的“面”或“小片”的子集來表示，而每一個面又可以通過其邊界的邊和頂點來表示。若面的表示無二義性，則其邊界表示模型也無二義性，但通常不一定只有唯一的表示。邊界表示邊界表示模型是一種采用描述形體表面的方法來描述的幾何59邊界表示的數(shù)據(jù)結(jié)構(gòu)邊界表示法的數(shù)據(jù)結(jié)構(gòu)有四種方法：以面為基礎(chǔ)、以頂點為基礎(chǔ)、以邊為基礎(chǔ)和翼邊結(jié)構(gòu)；以面為基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu) 以面為基礎(chǔ)，按照體、面、頂點坐標的樹結(jié)構(gòu)層次組織元素數(shù)據(jù)；如面頂點坐標F1(X1Y1Z1,X2Y2Z2,X3Y3Z3,X4Y4Z4)F2(X1Y1Z1,X2Y2Z2,X6Y6Z6,X5Y5Z5)

…

……..

其中頂點按照外觀順時針順序；邊界表示的數(shù)據(jù)結(jié)構(gòu)邊界表示法的數(shù)據(jù)結(jié)構(gòu)有四種方法：以面為基礎(chǔ)60邊界表示的數(shù)據(jù)結(jié)構(gòu)2．以頂點為基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu) 以頂點/坐標和面/頂點序列兩張關(guān)系表表示，如：頂點坐標面頂點序列V1X1Y1Z1F1V1V2V3V4…………………..3.以邊為基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu) 以邊/頂點，頂點/坐標，面/邊三張關(guān)系表表示；邊界表示的數(shù)據(jù)結(jié)構(gòu)2．以頂點為基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)61邊界表示模型四棱椎邊界表示的例子如右，由4個面組成，且這種表示可以看作是含有體、面、邊、頂點為節(jié)點的有向圖四棱椎邊界表示也可以基于邊界的三角形分解，即把形體的邊界拆成一些互不重疊的三角形。v1v2v3v4v5v2v3v4v5e1e2e3f1v1四棱柱面節(jié)點邊節(jié)點頂點坐標f1f2f3….e1e2e3e4….v1v2v3….(x1,y1,z1) 組合

結(jié)構(gòu) 坐標

信息….邊界表示模型v1v2v3v4v5v2v3v4v5e1e2e362邊界表示的數(shù)據(jù)結(jié)構(gòu)-翼邊數(shù)據(jù)結(jié)構(gòu)翼邊數(shù)據(jù)結(jié)構(gòu)：在1972年，由美國斯坦福大學Baumgart作為多面體的表示模式提出。它用指針記錄了每一邊的兩個鄰面（即左外環(huán)和右外環(huán)）、兩個頂點、兩側(cè)各自相鄰的兩個鄰邊（即左上邊、左下邊、右上邊和右下邊），用這一數(shù)據(jù)結(jié)構(gòu)表示多面體模型是完備的，但它不能表示帶有精確曲面邊界的實體。邊界表示的數(shù)據(jù)結(jié)構(gòu)-翼邊數(shù)據(jù)結(jié)構(gòu)翼邊數(shù)據(jù)結(jié)構(gòu)：在1972年，63邊界表示的數(shù)據(jù)結(jié)構(gòu)-翼邊數(shù)據(jù)結(jié)構(gòu)翼邊結(jié)構(gòu)由四種結(jié)點Solid,Face,edge和Vertex組成的，各結(jié)點描述如下：

Solid構(gòu)成引用的根節(jié)點。在任意時刻，會存在幾個數(shù)據(jù)結(jié)構(gòu)引用；為了存取其中的任何一個，需要指向其Solid節(jié)點的指針。通過指向三個雙向鏈表的指針，Solid節(jié)點給出對該模型的面、邊和頂點的訪問。所有實體被鏈接到一個雙向鏈表中，這個表通過指向該表的后繼和前趨實體的指針來實現(xiàn)的。具體包括：

邊界表示的數(shù)據(jù)結(jié)構(gòu)-翼邊數(shù)據(jù)結(jié)構(gòu)翼邊結(jié)構(gòu)由四種結(jié)點Solid64邊界表示的數(shù)據(jù)結(jié)構(gòu)-翼邊數(shù)據(jù)結(jié)構(gòu)SolidID;

指向face的鏈表指針；指向edge的鏈表指針；指向vertex的鏈表指針；

邊界表示的數(shù)據(jù)結(jié)構(gòu)-翼邊數(shù)據(jù)結(jié)構(gòu)SolidID;65邊界表示的數(shù)據(jù)結(jié)構(gòu)-翼邊數(shù)據(jù)結(jié)構(gòu)Face表示多面體的一個小平面,包括：

FaceID；

指向face的鏈表首元素的指針；指向face的下一元素的指針；

邊界表示的數(shù)據(jù)結(jié)構(gòu)-翼邊數(shù)據(jù)結(jié)構(gòu)Face表示多面體的一個66邊界表示的數(shù)據(jù)結(jié)構(gòu)-翼邊數(shù)據(jù)結(jié)構(gòu)Edge由Edge節(jié)點構(gòu)成，是整個數(shù)據(jù)結(jié)構(gòu)的核心，每個Edge結(jié)點代表一條邊，包括：

EdgeID; Edge的起始頂點指針；

Edge的終止頂點指針；

Edge的右鄰面的指針；

Edge的左鄰面的指針；

Edge的右方向向前鄰邊指針；

Edge的右方向向后鄰邊指針；

Edge的左方向向前鄰邊指針；

Edge的左方向向后鄰邊指針；

邊界表示的數(shù)據(jù)結(jié)構(gòu)-翼邊數(shù)據(jù)結(jié)構(gòu)Edge由Edge節(jié)點構(gòu)67邊界表示的數(shù)據(jù)結(jié)構(gòu)-翼邊數(shù)據(jù)結(jié)構(gòu)Vertex由vertex節(jié)點構(gòu)成，包括：

VertexID;

頂點坐標(x,y,z);

指向與該vertex相連的第一條邊指針； 指向下一個Vertex結(jié)點指針；

邊界表示的數(shù)據(jù)結(jié)構(gòu)-翼邊數(shù)據(jù)結(jié)構(gòu)Vertex由verte68邊界表示的數(shù)據(jù)結(jié)構(gòu)-半邊數(shù)據(jù)結(jié)構(gòu)半邊數(shù)據(jù)結(jié)構(gòu)，是在80年代提出的，作為一種多面體的表示方法。在構(gòu)成多面體的三要素（頂點、邊、面）中，半邊數(shù)據(jù)結(jié)構(gòu)以邊為核心。一條邊表示成拓撲意義上方向相反的兩條“半邊”，所以稱為半邊數(shù)據(jù)結(jié)構(gòu)。其中各節(jié)點的數(shù)據(jù)結(jié)構(gòu)及含義如下：邊界表示的數(shù)據(jù)結(jié)構(gòu)-半邊數(shù)據(jù)結(jié)構(gòu)半邊數(shù)據(jù)結(jié)構(gòu)，是在80年代提69邊界表示的數(shù)據(jù)結(jié)構(gòu)-半邊數(shù)據(jù)結(jié)構(gòu)typedeffloatvector[4];typedefshortID;typedefstructsolidSolid;typedefstructfaceFace;typedefstructloopLoop;typedefstructedgeEdge;typedefstructhalfedgeHalfEdge;typedefstructvertexVertex;邊界表示的數(shù)據(jù)結(jié)構(gòu)-半邊數(shù)據(jù)結(jié)構(gòu)typedeffloat70邊界表示的數(shù)據(jù)結(jié)構(gòu)-半邊數(shù)據(jù)結(jié)構(gòu)多面體structsolid{IDsolidno;//多面體序號

Face*sfaces;//指向多面體的面；

Edge*sedges;//指向多面體的邊；

Vertex*sverts;//指向多面體的頂點

Solid*nexts;//指向后一個多面體

Solid*prevs;//指向前一個多面體

}；邊界表示的數(shù)據(jù)結(jié)構(gòu)-半邊數(shù)據(jù)結(jié)構(gòu)多面體71邊界表示的數(shù)據(jù)結(jié)構(gòu)-半邊數(shù)據(jù)結(jié)構(gòu)面Structface{IDfaceno;//面序號

Solid*fsolid;//指向該面所屬的多面體

Loop*floops;//指向構(gòu)成該面的環(huán)

Vectorfeq;//平面方程

Face*prevf;//指向前一個面；

Face*nextf;//指向后一個面；}；邊界表示的數(shù)據(jù)結(jié)構(gòu)-半邊數(shù)據(jù)結(jié)構(gòu)面Structface72邊界表示的數(shù)據(jù)結(jié)構(gòu)-半邊數(shù)據(jù)結(jié)構(gòu)環(huán)structloop{HalfEdge*ledge;//指向構(gòu)成環(huán)的半邊

Face*lface;//指向該環(huán)所屬的面

Loop*prevl;//指向前一個環(huán)

Loop*nextl;//指向后一個環(huán)}

邊界表示的數(shù)據(jù)結(jié)構(gòu)-半邊數(shù)據(jù)結(jié)構(gòu)環(huán)structloop73邊界表示的數(shù)據(jù)結(jié)構(gòu)-半邊數(shù)據(jù)結(jié)構(gòu)邊structedge{IDedgeno;//邊的序號

HalfEdge*he1;//指向左半邊

HalfEdge*he2;//指向右半邊

Edge*preve;//指向前一條邊

Edge*nexte;//指向后一條邊}邊界表示的數(shù)據(jù)結(jié)構(gòu)-半邊數(shù)據(jù)結(jié)構(gòu)邊structedge74邊界表示的數(shù)據(jù)結(jié)構(gòu)-半邊數(shù)據(jù)結(jié)構(gòu)半邊structhalfedge{Edge*edge;//指向半邊的父邊

Vertex*vtx;//指向半邊的起始頂點

Loop*wloop;//指向半邊所屬的環(huán)

HalEdge*prv;//指向前一條半邊

HalfEdge*nxt;//指向后一條半邊}邊界表示的數(shù)據(jù)結(jié)構(gòu)-半邊數(shù)據(jù)結(jié)構(gòu)半邊structhalf75邊界表示的數(shù)據(jù)結(jié)構(gòu)-半邊數(shù)據(jù)結(jié)構(gòu)頂點structvertex{IDvertexno;//頂點序號

HalfEdge*vedge;//指向以該頂點為起點的半邊

Vectorvcoord;//頂點坐標

Vertex*nextv;//指向前一個頂點

Vertex*prevv;//指向后一個頂點}邊界表示的數(shù)據(jù)結(jié)構(gòu)-半邊數(shù)據(jù)結(jié)構(gòu)頂點structvert76歐拉運算和正則集合運算在邊界表示法中，可以定義一系列運算來構(gòu)造或修改三維實體，常用的這類運算有：歐拉運算正則集合運算歐拉運算和正則集合運算在邊界表示法中，可以定義一系列運算來構(gòu)77歐拉運算歐拉運算是三維物體邊界表示數(shù)據(jù)結(jié)構(gòu)的生成操作。運用歐拉運算，可以正確、有效構(gòu)建三維物體邊界表示中的所有拓撲元素和拓撲關(guān)系。該運算之所以稱為歐拉運算，是因為每一種運算所構(gòu)建的拓撲元素和拓撲關(guān)系均要滿足歐拉公式。歐拉運算歐拉運算是三維物體邊界表示數(shù)據(jù)結(jié)構(gòu)的生成操作。運用歐78歐拉運算歐拉公式V：頂點數(shù)E：棱線數(shù)F：面數(shù)凡是滿足歐拉公式的形體均稱為歐拉形體歐拉公式是簡單多面體的必要條件。附加條件：每邊連接兩個頂點每條邊只被兩個面共享等來保證有效性至少要有三條邊交于一個頂點。V-e+f=2歐拉運算歐拉公式V-e+f=279歐拉運算廣義歐拉公式（P204）V-e+f-r=2(s-h)V：頂點數(shù)，E：棱線數(shù)，F(xiàn)：面數(shù)r:多面體表面上孔的個數(shù)s:相互分離的多面體數(shù)h:貫穿多面體的孔洞個數(shù)歐拉運算廣義歐拉公式（P204）V-e+f-r=2(s-h)80歐拉運算若將廣義歐拉公式中的v,e,f,h,r,s分別看作獨立的坐標變量，則上式在六維空間中定義了一張平面（平面是五維的），該平面通過原點。由于各坐標變量的取值只能是非負的整數(shù)，所以上式實際上對應(yīng)了一張五維平面上的網(wǎng)格，每個多面體都對應(yīng)一個網(wǎng)格點。但并不是每個網(wǎng)格都對應(yīng)一個有效的多面體（只是必要條件）。如果要構(gòu)造的多面體對應(yīng)的網(wǎng)格點的坐標是（v,e,f,h,r,s），那么構(gòu)造該實體的過程就是從原點開始沿網(wǎng)格一步一步向這個坐標點前進的過程。由于網(wǎng)格上的每點都滿足歐拉公式，最后的多面體也必然滿足它。V-e+f-r=2(s-h)歐拉運算若將廣義歐拉公式V-e+f-r=2(s-h)81歐拉運算前進的“走法”是多種多樣的，因為只有五個自由變量，所以只需五種基本走法就可以了。要求：每一步至多只能使某一坐標變量增（減）一個單位。每一步行走都有明顯的幾何意義。歐拉運算是對形體進行增加，刪除點、邊、面而生成的一個新的歐拉形的處理。最基本的五種歐拉運算是：增加一條邊和一個頂點；增加一個面和一條邊；增加一條邊,一個面和一個頂點；增加一條邊和一個頂點；增加一條邊,且刪除一個孔穴。歐拉運算前進的“走法”是多種多樣的，因為只有五個自由變量，所82歐拉運算相應(yīng)的五種補運算是：刪除一條邊和一個頂點；刪除一個面和一條頂點；刪除一個體,一個面和一個頂點；刪除一個孔洞和一個體；刪除一條邊,且增加一個孔穴；任何一種歐拉形體(或歐拉運算)都可以用最基本的歐拉運算的現(xiàn)行組合來表示。用最基本的歐拉運算操作生成的形體必定是一個歐拉形體。歐拉運算相應(yīng)的五種補運算是：83正則集合運算通過對邊界表示的物體做正則集合運算可以構(gòu)造新的邊界表示的物體。對具有平面邊界、曲面邊界的物體進行集合運算的算法有很多，算法的大致步驟如下：(1)預(yù)檢查兩物體是否相交第一步：計算兩個待求交物體的包圍盒，若兩包圍盒不相交，則兩物體不相交，正則集合運算結(jié)束，否則進行下一層。第二步：計算兩物體每一個表面片的包圍盒，當某個面片的包圍盒與另一物體的包圍盒相交時，將該面片與另一物體的所有表面片一一求交，否則該面片與另一物體的所有表面片都無交。同樣，只有在用邊界盒法無法判斷時才進行求交計算，從而避免許多不必要的復(fù)雜的求交計算。

正則集合運算通過對邊界表示的物體做正則集合運算可以構(gòu)造新的邊84正則集合運算(2)計算兩物體各表面之間的交線。由于物體表面均為有界表面，因此物體表面之間的交線是有界的直線或曲線。計算兩物體表面之間的交線的一般步驟如下

a.基于兩相交表面的方程，建立交線的方程，確定出初始交線。初始交線可能為無界。

b.分別確定初始交線位于兩相交表面內(nèi)部的部分。

c.計算位于兩相交表面內(nèi)部的兩相交區(qū)段的重疊部分，即為兩相交表面之間的真正交線。正則集合運算(2)計算兩物體各表面之間的交線。85(3)對物體的表面進行分類兩物體之間的交線將它們的表面分割成兩部分，其中一部分落在拼合體的表面上，形成新的邊界，另一部分位于拼合體內(nèi)或拼合體外，應(yīng)在集合運算最后一步予以刪除。(4)建立結(jié)果物體的邊界表示。正則集合運算(3)對物體的表面進行分類正則集合運算86邊界表示Brep表示覆蓋域大，原則上能表示所有的形體，而且易于支持形體的特征表示等，Brep表示已成為當前CAD/CAM系統(tǒng)的主要表示方法。Brep表示的優(yōu)點是：表示形體的點、邊、面等幾何元素是顯式表示的，使得繪制Brep表示的形體的速度較快，而且比較容易確定幾何元素間的連接關(guān)系；容易支持對物體的各種局部操作，比如進行倒角。便于在數(shù)據(jù)結(jié)構(gòu)上附加各種非幾何信息，如精度、表面粗糙度等。邊界表示Brep表示覆蓋域大，原則上能表示所有的形體，而且易87邊界表示Brep表示的缺點是：數(shù)據(jù)結(jié)構(gòu)復(fù)雜，需要大量的存儲空間，維護內(nèi)部數(shù)據(jù)結(jié)構(gòu)的程序比較復(fù)雜；Brep表示不一定對應(yīng)一個有效形體，通常運用歐拉操作來保證Brep表示形體的有效性、正則性等。邊界表示Brep表示的缺點是：88各種表示方法的比較精確性：能否精確的表示實體。特征表示-能夠精確表示一個實體。構(gòu)造實體幾何表示-依賴于它所采用的基本體素，如果基本體素足夠豐富，則能精確描述較大范圍內(nèi)的實體。邊界表示-如果以多面體表示實體，則僅是一種近似表示；若允許曲面邊界，則可以精確表示實體。推移表示-與邊界表示類似?？臻g分割表示-近似表示一個實體。各種表示方法的比較精確性：能否精確的表示實體。89各種表示方法的比較表示域：指一種表示法所能表示的實體的范圍。表示域越大，表示能力越強。特征表示法、推移表示法：表示能力有限空間分割表示法：可以表示任何實體。邊界表示法：理論上說，可以表示所有實體。但若將邊界表示法中的邊界限制在某個范圍之內(nèi)（如平面多邊形），則表示能力降低。實體構(gòu)造表示法：依賴其基本體素的范圍。各種表示方法的比較表示域：指一種表示法所能表示的實體的范圍。90各種表示方法的比較唯一性：實體的表示形式唯一。只有空間位置枚舉方法和八叉樹具有唯一性。各種表示方法的比較唯一性：實體的表示形式唯一。91各種表示方法的比較封閉性：若其表示域內(nèi)的實體經(jīng)過某種運算（如正則集合運算，幾何變換）后，結(jié)果實體仍然落在表示域之內(nèi)。特征表示：實體之間不能進行集合運算。簡單推移表示，單元分解表示：不封閉?？臻g位置枚舉表示，八叉樹表示，CSG樹表示封閉。邊界表示雖然對正則集合運算不封閉，但可以附加約束條件避免。各種表示方法的比較封閉性：若其表示域內(nèi)的實體經(jīng)過某種運算（如92各種表示方法的比較有效性：通常，邊界表示（包括推移表示）物體的有效性難以檢驗。特征表示的物體有效性自動得到保證。其它表示方法的有效性驗證也比較簡單。各種表示方法的比較有效性：93各種表示方法的比較簡潔性：空間分割表示：占用空間大特征表示、推移表示、CSG樹表示較簡潔。邊界表示介于其間。各種表示方法的比較簡潔性：94各種表示方法的比較輸入：特征表示、推移表示、CSG樹表示和單元分解表示都是面向用戶的，只需輸入少量參數(shù)，即可生成所需實體。空間位置枚舉和八叉樹表示很難由用戶直接建立，一般都由其它表示形式轉(zhuǎn)化過來。若采用邊界表示作為輸入手段，則一方面用戶能方便的控制實體的形狀，另一方面，需輸入大量數(shù)據(jù)，且數(shù)據(jù)一致性很難保證。各種表示方法的比較輸入：95各種表示方法的比較輸出：實體造型的輸出包括圖形、計算機輔助制造系統(tǒng)進行數(shù)控加工所需的數(shù)據(jù)以及實體的性質(zhì)（重量、體積等）。圖形顯示和數(shù)控加工主要要求實體的邊界信息，所以邊界表示較好。若需實體性質(zhì)等方面的計算，則空間分割表示、CSG樹表示更好。各種表示方法的比較輸出：96模型的考慮模型的考慮

必須考慮以下一些問題：根據(jù)形體邊界給定的信息，是否能自動的獲取形體的幾何特征？如何確定對形體操作數(shù)據(jù)的有效性？形體的表示模型是否唯一？不同的表示模型是否可以轉(zhuǎn)換？是否最佳表示模型？對于幾何造型系統(tǒng)來說，按照不同的目的可以采用不同的最佳表示模型。模型的考慮模型的考慮

必須考慮以下一些問題：97不規(guī)則形體的建模方法迭代函數(shù)系統(tǒng)基于文法的模型粒子系統(tǒng)動力系統(tǒng)不規(guī)則形體的建模方法迭代函數(shù)系統(tǒng)98L系統(tǒng)由生物學家Lindenmayer創(chuàng)立基本思想：用文法表示植物的拓撲結(jié)構(gòu)通過圖形學方法生成逼真的畫面DOL系統(tǒng)（確定的上下文無關(guān)的L系統(tǒng)）定義為三元組<V,w,P>，其中

V----表示字母集合

V*----表示V上所有單詞的集合

w----是一個非空單詞，稱為公理

P----產(chǎn)生式集合 ，使得 如果沒有明顯的產(chǎn)生式，則令L系統(tǒng)由生物學家Lindenmayer創(chuàng)立99L系統(tǒng)例子----Koch雪花曲線V：{F,+,-}w：FP：F->F-F++F-F幾何解釋F：向前畫一條線+：右轉(zhuǎn)-：左轉(zhuǎn)

L系統(tǒng)例子----Koch雪花曲線100L系統(tǒng)BracketedL系統(tǒng)增加如下兩個字符[：壓棧]：出棧例子----植物w：FP：F->F[+F]F[-F]FL系統(tǒng)BracketedL系統(tǒng)101L系統(tǒng)L系統(tǒng)102引言三維圖形在科學研究和工程技術(shù)中有著廣泛的應(yīng)用。在CAD中，需要對所設(shè)計的作品從不同的角度進行審視。計算機幾何造型就是用計算機系統(tǒng)來表示、控制、分析和輸出三維形體。所以幾何造型是計算機圖形學中一個十分重要的應(yīng)用領(lǐng)域，它是CAD/CAM和CIMS系統(tǒng)的核心技術(shù)，也是用來實現(xiàn)計算機輔助設(shè)計的基本手段。幾何造型的功能：形體輸入，即把形體從用戶格式轉(zhuǎn)換成計算機內(nèi)部格式；圖形數(shù)據(jù)的存儲和管理；圖形控制，如對形體進行平移、縮放、旋轉(zhuǎn)等幾何變換；圖形修改，如應(yīng)用集合運算、歐拉運算、有理B樣條操作及其交互手段實現(xiàn)對形體局部或整體修改；圖形分析，如形體的容差分析，物質(zhì)特性分析等；圖形顯示輸出，如消隱、光照、顏色的控制等；詢問形體的屬性及其有關(guān)參數(shù)引言三維圖形在科學研究和工程技術(shù)中有著廣泛的應(yīng)用。在CA103形體在計算機形體一般定義為六層拓撲結(jié)構(gòu)，首先介紹在三維空間中基本術(shù)語的定義。形體(object)外殼(shell)面(face)環(huán)(loop)邊(loop)頂點(vertex)曲線和直線方程點的幾何坐標形體在計算機形體一般定義為六層拓撲結(jié)構(gòu)，首先介紹在三維空104形體體

由封閉表面圍成的有效空間稱為體；一個形體Q是R3空間中非空、有界的封閉子集。其邊界（記為?Q）是有限個面的并集，而外殼是形體的最大邊界。一個單位立方體可定義為： {(x,y,z)∈R3|0≤x≤1,0≤y≤1,0≤z≤1}

其中一個表面可表示為：

{(1,y,z)∈R3|0≤y≤1,0≤z≤1} 必須注意：并沒有規(guī)定形體必須是一個連續(xù)的封閉集合，目的是用這樣的定義來擴大幾何造型的域，使得形體可以由不連續(xù)的體素，或是僅有某些相交的形體組成。xzy形體體

由封閉表面圍成的有效空間稱為體；一個形體Q是R3105形體面

R3中非空、連續(xù)、共面且封閉的子集稱為面F，

其邊界(記為?F)是有限條線段的并集，

Pt表示含有F的唯一平面。

面是形體表面的一部分，且具有方向性.FPt形體面

R3中非空、連續(xù)、共面且封閉的子集稱為面F，

106形體環(huán)

由有序、有向邊組成的面的封閉邊界稱為環(huán)，環(huán)中任意邊都不能自交，相鄰兩條邊共享一個端點，環(huán)又分為內(nèi)環(huán)和外環(huán)。內(nèi)環(huán)是在已知面中的內(nèi)孔或凸臺面邊界的環(huán)，其邊按逆時針方向。外環(huán)是已知面的最大外邊界的環(huán)，其邊按順時針方向，按這種方式定義，在面上沿著邊的方向前進，面的內(nèi)部始終在走向的右側(cè)。形體環(huán)

由有序、有向邊組成的面的封閉邊界稱為環(huán)，環(huán)中任意107形體邊

形體內(nèi)兩個相鄰面的交界稱為邊，一條邊有且僅有兩個相鄰面。兩個端點確定一條邊，這兩個端點分別稱為該邊的起點和終點。假設(shè)Q是一個形體，E(Q)是形體邊的集合，則在?Q(形體的邊界)中E(Q)滿足下屬條件的所有線段的集合：邊e的兩個端點屬于V(Q)；邊e中沒有一個內(nèi)部點屬于V(Q)（所有頂點的集合）邊e上每個點，都有兩個不同的面，即存在兩個面fi，fi≤?Q使得邊e∈fi∩fj；形體Q的邊框線WF(Q)是由有序?qū)?V(Q),E(Q))所組成。v1v2ef1f2形體邊

形體內(nèi)兩個相鄰面的交界稱為邊，一條邊有且僅有兩個108形體點

邊的端點稱為點，點不能出現(xiàn)在邊的內(nèi)部，也不能孤立地位于物體內(nèi)、物體外或面內(nèi)，頂點又是?F(面邊界)中兩條不共線的線段的交點。v1v2ef1f2形體點

邊的端點稱為點，點不能出現(xiàn)在邊的內(nèi)部，也不能孤立109形體體素

具有有限個參數(shù)定義，且簡單

的連續(xù)封閉的形體稱為體素，

如長方體、圓柱體、圓錐、球、環(huán)等。半空間

集合{P|F(P)≤0}成為半空間，其中P為R3中的一點，F(xiàn)為一個平面，當F=0時，表示一個平面，這個平面的半空間可以由F(P)=ax+by+cz+d定義的平面加上在平面某一側(cè)的所有點組成。顯然一個長方體可以看成是6個平面半空間的交。幾何信息

用來表示形體的幾何性質(zhì)和度量關(guān)系稱為幾何信息。拓撲信息

用來表示形體之間的連接關(guān)系稱為拓撲信息。形體體素

具有有限個參數(shù)定義，且簡單

的連續(xù)封閉的形體稱110表示形體的兩種模型數(shù)據(jù)模型完全以數(shù)據(jù)描述例如用以8個頂點表示的立方體以中心點和半徑表示的球以數(shù)據(jù)文件的形式存在包括----特征表示、空間分割表示、推移表示、邊界表示、構(gòu)造實體幾何表示等進一步分為線框模型表面模型實體模型表示形體的兩種模型數(shù)據(jù)模型111線框模型線框模型：將形體表示成一組輪廓線的集合。一般地，畫出了形體的棱線與輪廓線就能唯一地表示出來。如圖，八個頂點可以定義一個長方體，但還不足以識別它，如果定義了棱線，則無論如何放置長方體都能唯一地表示了。對于多面體由于其輪廓線和棱線通常是一致的，所以多面體的線模型更便于識別，且簡單。e12v4v8s3e2e4e6e8e2e7e11e10e9e3e1v2v3v1v7v5v6s2s6s5s1s4線框模型線框模型：將形體表示成e12v4v8s3e2e4e6112線框模型優(yōu)點：簡單、處理速度快缺點：1、對于非平面多面體，如圓柱、球等形體，其輪廓線隨觀察方向的改變而改變，無法用一組固定的輪廓線來表示它們。2、線框模型與形體之間不存在一一對應(yīng)關(guān)系：它僅僅通過給定的輪廓線約束所表示形體的邊界面，而在輪廓線之間的地方，形體的表面可以任意變化。3、沒有形體的表面信息，不適于真實感顯示，由此導(dǎo)致表示的形體可能產(chǎn)生二義性。線框模型優(yōu)點：簡單、處理速度快113表面模型表面模型將形體表示成一組表面的集合如果把線框模型中的棱線包圍的部分定義為面，所形成的模型便是表面模型。其數(shù)據(jù)結(jié)構(gòu)是在線模型的基礎(chǔ)上附加一些指針，有序地連接棱線。下圖中表面編號表示第幾個表面，表面特征表面是平面還是曲面。形體與其表面一一對應(yīng)，適合于真實感顯示4頂點個數(shù)1起始指針0表面特征5表面編接指針屬性頂點號14232341表面模型表面模型4頂點個數(shù)1起始指針0表面特征5表面編號14114表面模型缺點：不能有效的用來表示實體原因：1、表面模型中的所有面未必形成一個封閉的邊界2、各個面的側(cè)向沒有明確定義，即不知道實體位于面的哪一側(cè)表面模型缺點：115實體模型實體模型用來描述實體，主要用于CAD/CAM包含了描述一個實體所需的較多信息，如幾何信息、拓撲信息，可以支持多種運算，如歐拉運算等。實體模型實體模型116表示形體的兩種模型過程模型以一個過程和相應(yīng)的控制參數(shù)描述例如用一些控制參數(shù)和一個生成規(guī)則描述的植物以一個數(shù)據(jù)文件和一段代碼的形式存在包括----粒子系統(tǒng)、L系統(tǒng)、迭代函數(shù)系統(tǒng)等表示形體的兩種模型過程模型117表示形體的兩種模型模型分類表示形體的兩種模型模型分類118實體的定義抽象帶來的問題計算機中表示的物體是無效的不能夠客觀存在為什么要求客觀存在CAD/CAM的需求什么是客觀存在（有效）—實體的定義具有一定的形狀具有封閉的邊界（表面)內(nèi)部連通占據(jù)有限的空間經(jīng)過運算后，仍然是有效的物體實體的定義抽象帶來的問題119實體的定義將三維物體看做一個點集，它由內(nèi)點和邊界點共同組成。內(nèi)點：具有完全包含于該點集的充分小的鄰域邊界點：不具有內(nèi)點性質(zhì)的點集實體的定義將三維物體看做一個點集，它由內(nèi)點和邊界點共同組成。120實體的定義

A是一個點集，定義點集的正則運算如下：i：取內(nèi)點運算c:取閉包運算正則運算riA：A的全體內(nèi)點組成的集合，稱為A的內(nèi)部ciA為A的內(nèi)部的閉包的運算，是iA與其邊界點的并集。實體的定義121實體的定義正則點集稱為A的正則點集稱A為正則點集，如果它滿足問題：正則點集是實體？實體的定義正則點集122實體的定義-舉例說明陰影部分：物體的內(nèi)部區(qū)域黑色部分：邊界(a)圖取內(nèi)點->(b)圖求閉包->(c)圖正則運算：去除與物體維數(shù)不一致的懸掛部分或孤立部分。實體的定義-舉例說明陰影部分：物體的內(nèi)部區(qū)域123實體的定義實體的定義—可計算的條件正則點集表面是二維流形二維流形其上任意一點存在充分小的領(lǐng)域與圓盤同構(gòu)（存在連續(xù)的一一映射）實體的定義實體的定義—可計算的條件124正則集合運算為什么需要正則集合運算正則集合運算是構(gòu)造復(fù)雜物體的有效方法普通的集合運算會產(chǎn)生無效物體(b):A∩B(c):普通A∩B(d)：正則A∩B正則集合運算為什么需要正則集合運算125正則集合運算集合運算（并、交、差）是構(gòu)造形體的基本方法。正則形體經(jīng)過集合運算后，可能會產(chǎn)生懸邊、懸面等低于三維的形體。Requicha在引入正則形體概念的同時，還定義了正則集合運算的概念。正則集合運算保證集合運算的結(jié)果仍是一個正則形體，即丟棄懸邊、懸面等。正則集合運算集合運算（并、交、差）是構(gòu)造形體的基本方法。正則126正則集合運算正則集合運算的定義正則并正則交正則差正則集合運算正則集合運算的定義127

任一實體S可以用它的邊界bS和它的內(nèi)部iS來表示，即

S=bS∪iS

由實體的定義可知，bS是封閉的，它將整個三維空間分成了三個區(qū)域：S的內(nèi)部iS,S的邊界bS,S的外部eS。邊界bS與實體S是一一對應(yīng)的。確定了邊界，也就唯一確定了一個實體。因此，為了求實體A，B的正則集合運算結(jié)果Aop*B，只要求出其邊界b（Aop*B）即可。

正則集合運算任一實體S可以用它的邊界bS和它的內(nèi)部iS來表128正則集合運算考察A,B兩物體的交所形成拼合體的邊界，由于A,B為正則點集，它們均可表示為邊界點與體內(nèi)點的集合，即A=bA∪iA;B=bB∪iBA物體的邊界bA可按其位于B物體內(nèi)、B物體上、B物體外而分別表示為

bA=(bA∩iB)∪(bA∩bB)∪(bA∩eB)

同理，bB=(bB∩iA)∪(bB∩bA)∪(bB∩eA)

A正則集合運算考察A,B兩物體的交所形成拼合體的邊界，A129正則集合運算其中bA∩bB=bB∩bA是A與B的公共邊界，它可以分成兩部分：（bA∩bB）同側(cè)、(bA∩bB)異側(cè)(bA∩bB)同側(cè)由這樣一些邊界構(gòu)成：A、B位于邊界的同側(cè)(bA∩bB)異側(cè)由這樣一些邊界構(gòu)成：A、B位于邊界的異側(cè)正則集合運算其中bA∩bB=bB∩bA是A與B的130正則集合運算對于A∩*B，由交的定義可知：1）A、B兩物體的邊界位于對方內(nèi)部的部分，即bA∩iB和bB∩iA是b(A∩*B)的組成部分。2）A、B兩物體的邊界位于對方外部的部分，即bA∩eB和bB∩eA不是b(A∩*B)的組成部分。3）對于A、B的重合邊界有：(bA∩bB)同側(cè)屬于b(A∩*B);(bA∩bB)異側(cè)不屬于b(A∩*B)因此：b(A∩*B)=(bA∩iB)∪(bB∩iA)∪(bA∩bB)同側(cè)正則集合運算對于A∩*B，由交的定義可知：131正則集合運算同理：b(A∪*B)=(bA∩eB)∪(bB∩eA)∪(bA∩bB)同側(cè)b(A－*B)=(bA∩eB)∪(bB∩iA)∪(bA∩bB)異側(cè)正則集合運算同理：132一些非正則形體的實例一些非正則形體的實例一些非正則形體的實例一些非正則形體的實例133為了能夠處理非正則形體，產(chǎn)生了非正則造型技術(shù)。九十年代以來，基于約束的參數(shù)化、變量化造型和支持線框、曲面、實體統(tǒng)一表示的非正則形體造型技術(shù)已成為幾何造型技術(shù)的主流。為了能夠處理非正則形體，產(chǎn)生了非正則造型技術(shù)。134形體表示模型在實體模型的表示中，基本上可以分為分解表示、構(gòu)造表示和邊界表示三大類。1、分解表示將形體按某種規(guī)則分解為小的更易于描述的部分，每一小部分又可分為更小的部分，這種分解過程直至每一小部分都能夠直接描述為止。形體表示模型在實體模型的表示中，基本上可以分為分解表示、構(gòu)造135分解表示-空間位置枚舉表示形體空間細分為小的均勻的立方體單元。用三維數(shù)組C[I][J][K]表示物體，數(shù)組中的元素與單位小立方體一一對應(yīng)當C[I][J][K]=1時，表示對應(yīng)的小立方體被物體占據(jù)當C[I][J][K]=0時，表示對應(yīng)的小立方體沒有被物體占據(jù)分解表示-空間位置枚舉表示形體空間細分為小的均勻的立方體單元136分解表示-空間位置枚舉表示優(yōu)點簡單，可以表示任何物體容易實現(xiàn)物體間的交、并、差集合運算容易計算物體的整體性質(zhì)，如體積等缺點占用大量的存儲空間，如1024*1024*1024=1Gbits物體的邊界面沒有顯式的解析表達式，不適于圖形顯示對物體進行幾何變換困難，如非90度的旋轉(zhuǎn)變換是物體的非精確表示分解表示-空間位置枚舉表示優(yōu)點137分解表示-八叉樹表示八叉樹表示對空間位置枚舉表示的空間分割方法作了改進：均勻分割自適應(yīng)分割八叉樹建立過程八叉樹的根節(jié)點對應(yīng)整個物體空間如果它完全被物體占據(jù)，將該節(jié)點標記為F(Full)，算法結(jié)束；如果它內(nèi)部沒有物體，將該節(jié)點標記為E(Empty)，算法結(jié)束；如果它被物體部分占據(jù)，將該節(jié)點標記為P(Partial)，并將它分割成8個子立方體，對每一個子立方體進行同樣的處理分解表示-八叉樹表示八叉樹表示八叉樹的根節(jié)點對應(yīng)整個物體空間138分解表示-八叉樹表示8叉樹的表示應(yīng)用三維形體的分解，它對一個外接立方體的形體進行前后、左右、上下等部分8個小立方體，如果小立方體單元為滿或為空，表示該立方體完全在形體中或完全不在形體中，則其停止分解；對部分形體占有的小立方體需進一步分解為8個子立方體，直至所有小立方體單元要么全部滿，要么全部空，或已分解到規(guī)定的分解精度為止。236720131375具有子孫的節(jié)點(P)空節(jié)點(E)實節(jié)點(F)分解表示-八叉樹表示8叉樹的表示應(yīng)用三維形體的分解，它對一個139分解表示-八叉樹表示優(yōu)點可以表示任何物體，且形體表示的數(shù)據(jù)結(jié)構(gòu)簡單簡化了形體的集合運算。只需同時遍歷參加集合運算的兩形體相應(yīng)的八叉樹，無需進行復(fù)雜的求交運算。簡化了隱藏線（或面）的消除，因為在八叉樹表示中，形體上各元素已按空間位置排成了一定的順序。分析算法適合于并行處理。缺點沒有邊界信息，不適于圖形顯示對物體進行幾何變換困難是物體的非精確表示占用大量存儲。實際上，八叉樹表示是以存儲空間換取算法的效率分解表示-八叉樹表示優(yōu)點140分解表示-線性八叉樹表示線性八叉樹：用一可變長度的一維數(shù)組來存儲一棵八叉樹。數(shù)組中僅存儲八叉樹的性質(zhì)為FULL的終端結(jié)點。并用一個八進制數(shù)表示該結(jié)點在八叉樹中的位置。編碼方式為：Q1Q2…Qm,其中Q1表示該結(jié)點所屬的一級父結(jié)點的編號（0-7），以此類推。例右圖為：{1X,30X,31X,323X,33X}

3

2031

75具有子孫的節(jié)點(P)空節(jié)點(E)實節(jié)點(F)分解表示-線性八叉樹表示線性八叉樹：用一可變長度的一維數(shù)組來141分解表示-單元分解表示單元分解表示對空間位置枚舉表示的空間分割方法作了改進：單一體素多種體素三種空間分割方法的比較空間位置枚舉表示----同樣大小立方體粘合在一起表示物體八叉樹表示----不同大小的立方體粘合在一起表示物體單元分解表示----多種體素粘合在一起表示物體分解表示-單元分解表示單元分解表示142分解表示-單元分解表示優(yōu)點表示簡單容易實現(xiàn)幾何變換基本體素可以按需選擇，表示范圍較廣可以精確表示物體缺點物體的表示不唯一物體的有效性難以保證分解表示-單元分解表示優(yōu)點143構(gòu)造表示掃描表示構(gòu)造實體幾何表示（CSG）特征表示構(gòu)造表示掃描表示144構(gòu)造表示-推移表示將物體A沿著軌跡P推移得到物體B，稱B為sweep體平移sweep----將一個二維區(qū)域沿著一個矢量方向推移構(gòu)造表示-推移表示將物體A沿著軌跡P推移得到物體B，稱B為s145構(gòu)造表示-推移表示旋轉(zhuǎn)sweep----將一個二維區(qū)域繞旋轉(zhuǎn)軸旋轉(zhuǎn)一周構(gòu)造表示-推移表示旋轉(zhuǎn)sweep----將一個二維區(qū)域繞旋轉(zhuǎn)146 三維形體也能在空間通過掃 描變換生成新的形體：如左 圖，一個圓柱體按指定方向 在長方體上運動生成新的形 體，這個過程猶如長方體與 運動者的圓柱體不斷的作差 運算操作。

有時經(jīng)過掃描變換所生成的形體可能會出現(xiàn)維數(shù)不一致問題。構(gòu)造表示-推移表示掃描線方向U 三維形體也能在空間通過掃 描變換生成新的形147構(gòu)造表示-推移表示廣義sweep任意物體沿著任意軌跡推移推移過程中物體可以變形構(gòu)造表示-推移表示廣義sweep148構(gòu)造表示-推移表示優(yōu)點表示簡單、直觀適合做圖形輸入手段缺點作幾何變換困難對幾何運算不封閉用掃描變換產(chǎn)生的形體可能出現(xiàn)維數(shù)不一致的問題。掃描方法不能直接獲取形體的邊界信息，表示形體的覆蓋域非常有限。構(gòu)造表示-推移表示優(yōu)點149構(gòu)造表示-構(gòu)造實體幾何表示(CSG).通過對體素定義運算而得到新的形體的一種表示方法。體素可以是立方體、圓柱、圓錐等，也可以是半空間，其運算為變換或正則集合運算并、交、差。CSG表示可以看成是一棵有序的二叉樹。其終端節(jié)點或是體素、或是形體變換參數(shù)。非終端結(jié)點或是正則的集合運算，或是變換（平移和/或旋轉(zhuǎn)）操作，這種運算或變換只對其緊接著的子結(jié)點（子形體）起作用。構(gòu)造表示-構(gòu)造實體幾何表示(CSG).通過對體素定義運算而得150構(gòu)造表示-構(gòu)造實體幾何表示(CSG)構(gòu)造表示-構(gòu)造實體幾何表示(CSG)151構(gòu)造表示-構(gòu)造實體幾何表示(CSG)CSG樹是無二義性的，但不是唯一的.CSG表示的優(yōu)點：數(shù)據(jù)結(jié)構(gòu)比較簡單，數(shù)據(jù)量比較小，內(nèi)部數(shù)據(jù)的管理比較容易；物體的有效性自動得到保證；CSG方法表示的形體的形狀，比較容易修改。構(gòu)造表示-構(gòu)造實體幾何表示(CSG)CSG樹是無二義性的，但152構(gòu)造表示-構(gòu)造實體幾何表示(CSG)CSG表示的缺點：對形體的表示受體素的種類和對體素操作的種類的限制，也就是說，CSG方法表示形體的覆蓋域有較大的局限性。對形體的局部操作不易實現(xiàn)，例如，不能對基本體素的交線倒圓角；由于形體的邊界幾何元素（點、邊、面）是隱含地表示在CSG中，故顯示與繪制CSG表示的形體需要較長的時間。表示不唯一

構(gòu)造表示-構(gòu)造實體幾何表示(CSG)CSG表示的缺點：153構(gòu)造表示-特征表示用一組特征參數(shù)表示一組類似的物體特征包括形狀特征、材料特征等適用于工業(yè)上標準件的表示構(gòu)造表示-特征表示用一組特征參數(shù)表示一組類似的物體154構(gòu)造表示-特征表示從應(yīng)用層來定義形體，因而可以較好的表達設(shè)計者的意圖。從功能上可分為形狀、精度、材料和技術(shù)特征。特征是面向應(yīng)用、面向用戶的。特征模型的表示仍然要通過傳統(tǒng)的幾何造型系統(tǒng)來實現(xiàn)。不同的應(yīng)用領(lǐng)域，具有不同的應(yīng)用特征。在幾何造型系統(tǒng)中，根據(jù)特征的參數(shù)我們并不能直接得到特征的幾何元素信息，而在對特征及在特征之間進行操作時需要這些信息。特征方法表示形體的覆蓋域受限于特征的種類。構(gòu)造表示-特征表示從應(yīng)用層來定義形體，因而可以較好的表達設(shè)計155構(gòu)造表示的特點構(gòu)造表示的特點：構(gòu)造表示通常具有不便于直接獲取形體幾何元素的信息、覆蓋域有限等缺點，但是，便于用戶輸入形體，在CAD/CAM系統(tǒng)中，通常作為輔助表示方法。構(gòu)造表示的特點構(gòu)造表示的特點：156邊界表示邊界表示（BR表示或BRep表示）按照體－面－環(huán)－邊－點的層次，詳細記錄了構(gòu)成形體的所有幾何元素的幾何信息及其相互連接的拓撲關(guān)系。邊界表示的一個重要特點是在該表示法中，描述形體的信息包括幾何信息（Geometry）和拓撲信息（Topology）兩個方面。拓撲信息描述形體上的頂點、邊、面的連接關(guān)系，拓撲信息形成物體邊界表示的“骨架”。形體的幾何信息猶如附著在“骨架”上的肌肉。邊界表示邊界表示（BR表示或BRep表示）157邊界表示邊界模型表達形體的基本拓撲實體包括：1.頂點2.邊。邊有方向，它由起始頂點和終止頂點來界定。邊的形狀（Curve）由邊的幾何信息來表示，可以是直線或曲線，曲線邊可用一系列控制點或型值點來描述，也可用顯式、隱式或參數(shù)方程來描述。邊界表示邊界模型表達形體的基本拓撲實體包括：158邊界表示3.環(huán)。環(huán)（Loop）是有序、有向邊（Edge）組成的封閉邊界。環(huán)有方向、內(nèi)外之分，外環(huán)邊通常按逆時針方向排序，內(nèi)環(huán)邊通常按順時針方向排序。4.面。面（Face）由一個外環(huán)和若干個內(nèi)環(huán)（可以沒有內(nèi)環(huán)）來表示，內(nèi)環(huán)完全在外環(huán)之內(nèi)。若一個面的外法矢向外，稱為正向面；反之，稱為反向面。邊界表示3.環(huán)。環(huán)（Loop）是有序、有向邊（