第7章幾何造型

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

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

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

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

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

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

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

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

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

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

(Threekindsofmodel3Dshaperepresentation)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(正則交)、∪*

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

G={bG,iG}

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

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

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

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

SonG={Son(bG),Son(-bG)}2023/2/5計(jì)算機(jī)圖形學(xué)演示稿紀(jì)玉波制作(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為兩個(gè)正則形體，則正則集合運(yùn)算算子定義如下：

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

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

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

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

(Constructivesolidmodels)

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

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

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