第6章 實(shí)體幾何造型基礎(chǔ)

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

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

其中一個(gè)表面可表示為：

{(1,y,z)∈R3|0≤y≤1,0≤z≤1} xzy6形體面

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

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

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

面是形體表面的一部分，且具有方向性。FPt7形體環(huán)

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

形體內(nèi)兩個(gè)相鄰面的交線稱為邊，一條邊有且僅有兩個(gè)相鄰面。兩個(gè)端點(diǎn)確定一條邊，這兩個(gè)端點(diǎn)分別稱為該邊的起點(diǎn)和終點(diǎn)。v1v2ef1f29形體點(diǎn)

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

具有有限個(gè)參數(shù)定義，且簡(jiǎn)單

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

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

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

用來(lái)表示形體的幾何性質(zhì)和度量關(guān)系稱為幾何信息。拓?fù)湫畔?/p>

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

A是一個(gè)點(diǎn)集，定義點(diǎn)集的正則運(yùn)算如下：i：取內(nèi)點(diǎn)運(yùn)算c:取閉包運(yùn)算正則運(yùn)算riA：A的全體內(nèi)點(diǎn)組成的集合，稱為A的內(nèi)部ciA為A的內(nèi)部的閉包的運(yùn)算，是iA與其邊界點(diǎn)的并集。23實(shí)體的定義正則點(diǎn)集稱為A的正則點(diǎn)集稱A為正則點(diǎn)集，如果它滿足24實(shí)體的定義-舉例說(shuō)明陰影部分：物體的內(nèi)部區(qū)域黑色部分：邊界(a)圖取內(nèi)點(diǎn)->(b)圖求閉包->(c)圖正則運(yùn)算：去除與物體維數(shù)不一致的懸掛部分或孤立部分。25正則集合運(yùn)算為什么需要正則集合運(yùn)算正則集合運(yùn)算是構(gòu)造復(fù)雜物體的有效方法普通的集合運(yùn)算會(huì)產(chǎn)生無(wú)效物體(b):A∩B(c):普通A∩B(d)：正則A∩B26正則集合運(yùn)算集合運(yùn)算（并、交、差）是構(gòu)造形體的基本方法。正則形體經(jīng)過(guò)集合運(yùn)算后，可能會(huì)產(chǎn)生懸邊、懸面等低于三維的形體。Requicha在引入正則形體概念的同時(shí)，還定義了正則集合運(yùn)算的概念。正則集合運(yùn)算保證集合運(yùn)算的結(jié)果仍是一個(gè)正則形體，即丟棄懸邊、懸面等。27正則集合運(yùn)算正則集合運(yùn)算的定義正則并正則交正則差28

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

正則集合運(yùn)算29正則集合運(yùn)算考察A,B兩物體的交所形成拼合體的邊界，由于A,B為正則點(diǎn)集，它們均可表示為邊界點(diǎn)與體內(nèi)點(diǎn)的集合，即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)

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

三維形體也能在空間通過(guò)掃 描變換生成新的形體：如左 圖，一個(gè)圓柱體按指定方向 在長(zhǎng)方體上運(yùn)動(dòng)生成新的形 體，這個(gè)過(guò)程猶如長(zhǎng)方體與 運(yùn)動(dòng)者的圓柱體不斷的作差 運(yùn)算操作。

有時(shí)經(jīng)過(guò)掃描變換所生成的形體可能會(huì)出現(xiàn)維數(shù)不一致問(wèn)題。構(gòu)造表示-推移表示掃描線方向U48構(gòu)造表示-推移表示廣義sweep任意物體沿著任意軌跡推移推移過(guò)程中物體可以變形49構(gòu)造表示-推移表示優(yōu)點(diǎn)表示簡(jiǎn)單、直觀適合做圖形輸入手段缺點(diǎn)作幾何變換困難對(duì)幾何運(yùn)算不封閉用掃描變換產(chǎn)生的形體可能出現(xiàn)維數(shù)不一致的問(wèn)題。掃描方法不能直接獲取形體的邊界信息，表示形體的覆蓋域非常有限。50構(gòu)造表示-構(gòu)造實(shí)體幾何表示(CSG).通過(guò)對(duì)體素定義運(yùn)算而得到新的形體的一種表示方法。體素可以是立方體、圓柱、圓