第7章幾何造型

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

通過對點(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ǔ)知識。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ì)就是對點(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)

可以通過對一個(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ò)充增加屬性信息。比如邊表和面表中可以包括顏色屬性，面表中還可包括透明度、紋理特征等。對上述三表還可以進(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)成物體的都是軸對稱的物體。圖62023/2/5計(jì)算機(jī)圖形學(xué)演示稿紀(jì)玉波制作(C)14

一般地,可以沿任何路徑來作掃描移動(dòng)。對旋轉(zhuǎn)掃描可以沿從0到的角范圍內(nèi)的路徑移動(dòng)。對非圓形路徑，可以給定描述路徑的曲線函數(shù)和沿路徑移動(dòng)的距離。另外可以沿掃描路徑變化曲線或曲面的形狀和大小及相對于掃描路徑的方向。在掃描表示法中，只需定義二維平面及曲線，三維空間的實(shí)體和曲面就可分別由二維平面及曲線通過掃描來實(shí)現(xiàn)。這對于許多領(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è)面圍成，對應(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)是否便于對實(shí)體進(jìn)行面、邊、點(diǎn)的存放、查找或修改，是一個(gè)十分關(guān)鍵的問題。邊界表示詳細(xì)記錄了構(gòu)成形體所有的幾何信息和拓?fù)湫畔ⅰ缀涡畔⒚枋鲂误w的大小、尺寸、位置、形狀等，而拓?fù)湫畔t描述形體的表面、棱邊、頂點(diǎn)等相互間的連接關(guān)系，二者構(gòu)成一個(gè)有機(jī)的整體，共同形成對形體的完整的描述。有了幾何信息和拓?fù)湫畔?，可以直接對?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)，對實(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)算，但對兩個(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)后取反向作為新形體的有向邊界。對于二維的情況，其形體的邊界由直線段或曲線構(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í)體。在這一方法中，常用的體素有長方體、圓柱體、圓錐體、圓臺體、環(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)造過程中，