第7章幾何造型

2023/2/5計算機圖形學演示稿紀玉波制作(C)1第七章幾何造型(SolidGeometryModeling)

通過對點、線、面、體等圖形元素進行幾何變換和并、交、差等集合運算，在計算機內(nèi)表示、構(gòu)造三維形體的技術(shù)，即為幾何造型技術(shù)。它是計算機圖形學的一個重要組成部分，是CAD/CAM和各種計算機輔助制作技術(shù)的基礎(chǔ)。幾何造型包括曲面造形和實體造型等技術(shù)。曲面造形所涉及到的基礎(chǔ)內(nèi)容諸如自由曲線和曲面的表示我們已經(jīng)討論過。下面將介紹有關(guān)實體造型的基礎(chǔ)知識。2023/2/5計算機圖形學演示稿紀玉波制作(C)27.1形體在計算機內(nèi)的表示(SolidObjectRepresentations)

如何在計算機內(nèi)定義和表示由基本圖元的集合所決定的形體，是幾何造形中最基本的問題。7.1.1幾何元素的定義(Thedefinitionofgeometricelements)

在計算機內(nèi)通常用點、邊、面、環(huán)、體等作為基本幾何元素。1.點(vertice)

點是0維幾何元素，分端點、交點、切點等，如邊的端點。但在形體定義中，點不允許孤立地存在于實體內(nèi)部或外部，只能存在于實體邊界上。在自由曲線和曲面的描述中常用三種類型的點，即控制點、型值點、插值點。在計算機內(nèi)，點用其位置坐標表示。點是幾何造型中的最基本元素，用計算機存儲、管理、輸出形體的實質(zhì)就是對點集及其連接關(guān)系的處理。2023/2/5計算機圖形學演示稿紀玉波制作(C)32.邊(edge)

邊是1維幾何元素，由端點或曲線方程定義，如直線邊、二次曲線邊、三次樣條曲線邊等。曲線邊也可由一系列型值點或控制點表示。3.面(face)

面是2維幾何元素，是形體上一個有限、非零的區(qū)域，由數(shù)學方程定義。面具有方向性，一般用其外法線方向作為面的正向。它用一個外環(huán)和若干內(nèi)環(huán)界定其有效范圍，面可以無內(nèi)環(huán)，但必須有外環(huán)。在幾何造型中常分平面、二次面、雙三次參數(shù)曲面等形式。4.環(huán)(loop)

環(huán)是有序、有向邊組成的面上封閉邊界，環(huán)中各條邊不能自交，相鄰兩條邊共享一個端點。環(huán)有內(nèi)環(huán)與外環(huán)之分，確定面的最大外邊界的環(huán)稱為外環(huán)，每個面有且僅有一個外環(huán)。若面內(nèi)有空，則還有內(nèi)環(huán)。通常外環(huán)的邊按逆時針方向排序，而內(nèi)環(huán)的邊按順時針方向排序。這樣定義后，在面上沿一個環(huán)前進，其左側(cè)總是面內(nèi)，右側(cè)總是面外。2023/2/5計算機圖形學演示稿紀玉波制作(C)45.體(solid)

體是3維幾何元素，是由封閉表面圍成的維數(shù)一致的有效空間。為了保證幾何造型的可靠性和可加工性，要求形體上任意一點的足夠小的鄰域在拓撲上應(yīng)是一個等價的封閉圓，即圍繞該點的形體鄰域在二維空間中可構(gòu)成一個單連通域。把滿足這個定義的形體稱之為正則形體。形體的正則性限制任何面必須是形體表面的一部分，不能是懸面；每條邊有且只能有兩個鄰面，不能是懸邊；點至少和三條邊鄰接。圖1示出幾個非正則形體的例子。

有懸面有懸邊1條邊有4個鄰面圖12023/2/5計算機圖形學演示稿紀玉波制作(C)57.1.2三維形體表示的三種模型

(Threekindsofmodel3Dshaperepresentation)

可以通過對一個三維空間形體進行近似的描述來表示和構(gòu)造相應(yīng)的三維圖形。在計算機中常用的是線框、表面和實體三種表示模型。1.線框模型(WireframeModel)

線框模型是最早用來表示形體的模型，并且至今仍在廣泛地應(yīng)用。線框模型由頂點表示幾何位置，相鄰頂點連接構(gòu)成棱邊表示幾何形狀特征。圖2是一個長方體的例子，8個頂點和12條棱邊表示出這一形體。圖22023/2/5計算機圖形學演示稿紀玉波制作(C)6

線框模型是表面模型和實體模型的基礎(chǔ)。它具有結(jié)構(gòu)簡單、易于理解、數(shù)據(jù)量少的特點，因此計算機處理速度快。但用線框模型表示形體不充分，無法進行剖切、消隱、明暗等圖形處理，也很難表示圓柱體、球體等曲面形體。2.表面模型(Surfacemodel)

表面模型是用有向棱邊圍成的部分來定義形體表面，由面的集合來定義形體。表面模型是在線框模型的基礎(chǔ)上，通過增加由哪些棱邊按何種順序連接等內(nèi)容定義出表面，從而可以滿足面面求交、線面消隱、明暗處理等應(yīng)用需要。這種模型通常用于構(gòu)造復(fù)雜的曲面形體。表面模型完整地定義了形體的邊界，但是形體的實心部分在邊界哪一側(cè)并不明確。2023/2/5計算機圖形學演示稿紀玉波制作(C)7圖3是在線框模型的基礎(chǔ)上增加各表面的信息。圖32023/2/5計算機圖形學演示稿紀玉波制作(C)83.實體模型(SolidModel)

如果要處理完整的三維形體，最終必須使用實體模型，實體模型明確定義了表面的哪一側(cè)存在實體。在表面模型的基礎(chǔ)上，使用表面的外法線矢量方向來指明實體存在的一側(cè)，例如規(guī)定正向指向體外。通常用有向棱邊隱含地表示表面的外法線矢量方向。在定義表面時，有向棱邊按右手法則取向，沿著閉合的棱邊所得的方向與表面外法線矢量方向一致。圖4是在表面模型的基礎(chǔ)上增加定義了表面外環(huán)的棱邊方向。用此方法還可檢查形體的拓撲一致性，拓樸合法的形體在相鄰兩個面的公共邊界上，棱邊的方向正好相反。圖42023/2/5計算機圖形學演示稿紀玉波制作(C)94.三種模型的數(shù)據(jù)結(jié)構(gòu)(Datastructureofthemodels)

線框模型的數(shù)據(jù)信息是頂點和棱邊，其數(shù)據(jù)結(jié)構(gòu)一般使用兩組數(shù)據(jù)，或稱兩表結(jié)構(gòu)。一張表表示頂點，一張表表示棱邊。以圖2為例，假定長方體的長是2，寬是1，高是1，則數(shù)據(jù)組織如表1和表2所示。表面模型是在線框模型的基礎(chǔ)上增加定義表面信息，所以其數(shù)據(jù)結(jié)構(gòu)也是在線框模型兩表結(jié)構(gòu)的基礎(chǔ)上增加一面表，如表3所示。2023/2/5計算機圖形學演示稿紀玉波制作(C)10

實體模型是在表面模型的基礎(chǔ)上增加定義了表面的哪一側(cè)存在實體,并且使用有向邊表示表面的外法線矢量方向。不同于表面模型的是，實體模型在定義表面時，需要按右手法則取向安排組成表面的邊順序。表3中邊的順序已經(jīng)符合這一要求，也可以作為實體模型的面表。三個表中除了所列的基本幾何數(shù)據(jù)外，還可以擴充增加屬性信息。比如邊表和面表中可以包括顏色屬性，面表中還可包括透明度、紋理特征等。對上述三表還可以進行數(shù)據(jù)的一致性和完整性檢驗，內(nèi)容諸如每個頂點至少是二條邊的端點；每條邊至少是一個面的組成部分；每個面的邊界都是封閉的；每個面至少有一條同其它面的公共邊等。2023/2/5計算機圖形學演示稿紀玉波制作(C)117.2實體模型的構(gòu)造(ConstructiveSolidGeometry)

前面介紹的表示形體的線框、表面和實體模型是一種廣義的概念，并不反映形體在計算機內(nèi)部所用的具體表示方式。為適應(yīng)不同的形體情況和應(yīng)用要求，已發(fā)展了多種具體的實體造型方法。目前常用有掃描表示法、邊界表示法、構(gòu)造實體幾何法和八叉樹表示法等。7.2.1掃描表示法(SweepsRepresentations)

掃描表示法是一個得到較廣泛應(yīng)用的表示三維物體的方法。它的基本原理十分簡單，即空間中的一個點，一條線或一個面沿著某一路徑移動時，所形成的軌跡將產(chǎn)生一個一維的、二維的或三維的圖形。用掃描法表示或形成一個形體需要定義作掃描運動的曲線或曲面，以及掃描運動的路徑。在三維形體的表示中，應(yīng)用得最多的是平移掃描法和旋轉(zhuǎn)掃描法兩種。2023/2/5計算機圖形學演示稿紀玉波制作(C)12

平移掃描法是所定義的掃描體沿著直線路徑作移動而形成掃描軌跡。如圖5中是一個平移掃描例子，掃描體是一個圓，掃描路徑是一條直線，掃描后得到一個圓柱體。圖52023/2/5計算機圖形學演示稿紀玉波制作(C)13

旋轉(zhuǎn)掃描法是所定義的掃描體繞某一軸線旋轉(zhuǎn)某一角度形成掃描軌跡。如圖6中是一條曲線繞垂直軸線旋轉(zhuǎn)后得到的三維形體。旋轉(zhuǎn)掃描法構(gòu)成物體的都是軸對稱的物體。圖62023/2/5計算機圖形學演示稿紀玉波制作(C)14

一般地,可以沿任何路徑來作掃描移動。對旋轉(zhuǎn)掃描可以沿從0到的角范圍內(nèi)的路徑移動。對非圓形路徑，可以給定描述路徑的曲線函數(shù)和沿路徑移動的距離。另外可以沿掃描路徑變化曲線或曲面的形狀和大小及相對于掃描路徑的方向。在掃描表示法中，只需定義二維平面及曲線，三維空間的實體和曲面就可分別由二維平面及曲線通過掃描來實現(xiàn)。這對于許多領(lǐng)域的實體造型是很方便的，因此，掃描表示法在許多造型系統(tǒng)得到應(yīng)用。2023/2/5計算機圖形學演示稿紀玉波制作(C)157.2.2邊界表示法(BoundaryRepresentations)

一個形體可以用面、環(huán)、邊、點來定義其位置和形狀,這些面、環(huán)、邊、點構(gòu)成形體的邊界。如圖2中，長方體由六個面圍成，對應(yīng)有六個環(huán)，每個環(huán)由四條邊組成，每條邊又由兩個端點定義。一個形體的邊界將該形體劃分為形體中的點和形體外的點，它也是形體與周圍環(huán)境之間的分界面。很顯然，只要完整地定義了形體的邊界，那么該形體就被唯一定義了。

邊界表示法（BoundaryRepresentation，B-Rep）就是以物體邊界為基礎(chǔ)定義和描述幾何形體的方法。所描述的物體由有限個面構(gòu)成，每個面可以由有限條邊圍成的有限個封閉區(qū)域定義。用邊界表示法描述實體，要求其表面必須滿足一定條件，如連通、有界、可定向、不自交和閉合連接等。2023/2/5計算機圖形學演示稿紀玉波制作(C)16

由于邊界是以面、邊、點為基礎(chǔ)的，所采用的數(shù)據(jù)結(jié)構(gòu)是否便于對實體進行面、邊、點的存放、查找或修改，是一個十分關(guān)鍵的問題。邊界表示詳細記錄了構(gòu)成形體所有的幾何信息和拓撲信息。幾何信息描述形體的大小、尺寸、位置、形狀等，而拓撲信息則描述形體的表面、棱邊、頂點等相互間的連接關(guān)系，二者構(gòu)成一個有機的整體，共同形成對形體的完整的描述。有了幾何信息和拓撲信息，可以直接對構(gòu)成形體的各個面、邊、頂點的參數(shù)進行存取，有利于以面、邊、點為基礎(chǔ)的各種幾何運算和操作。邊界表示法中最為典型的數(shù)據(jù)結(jié)構(gòu)是翼邊結(jié)構(gòu)。2023/2/5計算機圖形學演示稿紀玉波制作(C)17

在以表面、棱邊、頂點組成形體的三要素中，翼邊結(jié)構(gòu)以邊為核心來組織數(shù)據(jù),如圖7所示。圖72023/2/5計算機圖形學演示稿紀玉波制作(C)18

與一條邊相連的有這條邊的上下兩個頂點，左右兩個鄰面以及上下左右四條鄰邊。棱邊的數(shù)據(jù)結(jié)構(gòu)中包含有2個頂點指針，分別指向該邊的起點和終點，每一個頂點也有一個指針，反過來指向以該頂點為端點的邊。棱邊被看作一個從起點指向終點的有向線段，如果形體是多面體，其棱邊為直線段，由它的起點和終點唯一確定。當形體為曲面體時，其棱邊可能為一曲線段，這時必須增添一項指針來指向所在曲線邊的數(shù)據(jù)。此外，在翼邊結(jié)構(gòu)中還設(shè)有兩個環(huán)指針，分別指向棱邊所鄰接的兩個表面上的環(huán)。由這種邊環(huán)關(guān)系就能確定棱邊與相鄰面之間的拓撲關(guān)系，為了能從棱邊出發(fā)搜索到所在的任一閉環(huán)上的其它棱邊，數(shù)據(jù)結(jié)構(gòu)中又增設(shè)四個指向邊的指針，它們分別是左上邊、左下邊、右上邊、右下邊。如右下邊表示該棱邊在右面環(huán)中沿逆時針方向所連接的下一條棱邊，而左上邊則為棱邊在左面環(huán)中沿逆時針方向所連接的下一條邊等。每一個面也有一個指針，反過來指向它的一條邊。通過這種翼邊結(jié)構(gòu)，可以方便地查找各元素之間的連接關(guān)系。2023/2/5計算機圖形學演示稿紀玉波制作(C)19

邊界表示法的優(yōu)點是，表示形體的點、邊、面等幾何元素是顯式表示的，比較容易確定幾何元素間的連接關(guān)系。有關(guān)形體的操作運算可以直接用面、邊、頂點的數(shù)據(jù)來實現(xiàn)，使得繪制形體的速度較快。邊界表示法的缺點是數(shù)據(jù)結(jié)構(gòu)復(fù)雜，需要大量的存儲空間，修改形體的操作比較難以實現(xiàn)，對實體的整體描述能力弱。7.2.3構(gòu)造實體幾何法(CSG)

構(gòu)造實體幾何法(ConstructiveSolidGeometry，CSG)，是在實體的表示、構(gòu)造中得到廣泛應(yīng)用的一種方法。它的基本思想是將簡單幾何形體（體素）通過正則集合運算組合成所需要的復(fù)雜實體。因此，這種方法稱為構(gòu)造實體幾何法。2023/2/5計算機圖形學演示稿紀玉波制作(C)201.正則集合運算(Regularizedsetoperation)

構(gòu)造實體幾何法中采用的集合運算包括并、交、差運算，但對兩個有效實體進行普通的集合運算產(chǎn)生的結(jié)果并不一定是有效實體，即可能產(chǎn)生懸邊、懸面等。如圖8(a)所示,設(shè)二維平面上有物體A及B，將它們?nèi)鐖D8(b)所示的位置作交運算。如果以通常的集合運算規(guī)則求，則得到圖8(c)中的結(jié)果，它有一條懸邊，不具有維數(shù)的一致性，所以不符合正則形體的條件，不是有效的二維形體。圖8(d)中的結(jié)果才是一個有效的二維形體。2023/2/5計算機圖形學演示稿紀玉波制作(C)21

為此，把能夠產(chǎn)生正則形體的集合運算稱為正則集合運算。其相應(yīng)的正則集合算子以∩*

(正則交)、∪*

(正則并)、-*(正則差)表示。首先，正則形體的表面具有連通性、有界性、非自相交性、可定向性和閉合性。三維正則形體可以用它的邊界面及內(nèi)部來表示，即：

G={bG,iG}

式中，G為正則形體，bG為G的邊界面，iG為G的內(nèi)部。在三維空間中，給定一個實體G后，空間點集就被分為三個子集，一是該實體的內(nèi)部點集，二是該實體邊界上的點集，三是該實體之外的點集。若給定一個實體G及一個有界面S，那么S也可能被G分割為三部分，即位于G內(nèi)的面，位于G外的面以及位于G的邊界上的面。以C(S,G)表示這三種關(guān)系，P代表空間的點，則有：

C(S,G)={SinG,SoutG,SonG}2023/2/5計算機圖形學演示稿紀玉波制作(C)22其中

SinG={P|PS,PiG}SoutG={P|PS,PG}SonG={P|PS,PbG}

由于實體G的邊界面是可定向的，有界面S也是可定向的，比如按右手法則取法線方向。以-S表示有界面S的反向面，即-S和S是同一個有界面，只是有界面-S上任何一點的法向均和有界面S上該點的法向相反。也就是說，如有界面S在P點的法向為NP(S)，那么，有界面-S在P點的法向就是-NP(S)。同樣-bG表示G邊界面的反向。于是可以進一步分為兩種情況：有界面S在G邊界面上同為正向的點的集合和一個為正向一個為反向的點的集合，即：

SonG={Son(bG),Son(-bG)}2023/2/5計算機圖形學演示稿紀玉波制作(C)23其中

Son(bG)={P|PS,PbG,Np(s)=Np(bG)}Son(-bG)={P|PS,PbG,Np(s)=-Np(bG)}因此，C(S,G)可以修改為：

C(S,G)={SinG,SoutG,Son(bG),Son(-bG)}

由于正則形體可以由它的邊界來表示，得到了它的邊界，也就定義了該形體。設(shè)A和B為兩個正則形體，則正則集合運算算子定義如下：

b(A∪*B)={bAoutB,BoutA,bAonbB}

b(A∩*B)={bAinB,BinA,bAonbB}

b(A-*B)={bAoutB,-(bBinA),bAon(-bB)}2023/2/5計算機圖形學演示稿紀玉波制作(C)24

可以證明，通過上面定義的正則集合算子運算后得到的新形體仍為正則形體，運算的結(jié)果定義出新形體的邊界。最后一式中-(bBinA)表示得到點集(bBinA)后取反向作為新形體的有向邊界。對于二維的情況，其形體的邊界由直線段或曲線構(gòu)成。運算是指兩邊界線走向相同的部分，bAon(-bB)是指兩邊界線走向相反的部分。仍然用圖8的例子來說明正則集合算子運算，其結(jié)果如圖9表示。圖中實線表示運算后所生成的新形體邊界。圖92023/2/5計算機圖形學演示稿紀玉波制作(C)252實體模型的構(gòu)造

(Constructivesolidmodels)

構(gòu)造實體幾何法利用上面所述的正則集合運算，將簡單幾何形體(體素)組合成所需要的復(fù)雜實體。在這一方法中，常用的體素有長方體、圓柱體、圓錐體、圓臺體、環(huán)、球和封閉樣條曲面等?；倔w素本身可用建模算法、掃描方法或樣條方法構(gòu)造形成。圖10表示了用構(gòu)造實體幾何法形成新的實體的例子。在圖中，兩個不同的長方形作并操作后再同一個圓柱體作差操作，得到圖中的實體。

2023/2/5計算機圖形學演示稿紀玉波制作(C)26

在實體構(gòu)造過程中，