1、第八講 實(shí)體幾何造型,計(jì)算機(jī)圖形學(xué),一.概述 客觀世界中的物體都是三維的，真實(shí)地描述和顯示客觀世界中的三維物體是計(jì)算機(jī)圖形學(xué)研究的重要內(nèi)容。 一個(gè)物體的計(jì)算機(jī)描述叫做模型，它能被計(jì)算機(jī)讀懂，并在一定的條件下（變換和投影）被轉(zhuǎn)換成相應(yīng)的圖形在屏幕顯示或在繪圖機(jī)上輸出； 圖形是模型的一個(gè)具體可見像,幾何造型就是用計(jì)算機(jī)系統(tǒng)來(lái)表示、控制、分析和輸出三維形體。 表示形體的兩種模型: 數(shù)據(jù)模型：規(guī)則形體的建模方法； 用歐式幾何描述。 過(guò)程模型：不規(guī)則形體的建模方法； 用分形幾何描述。,1.數(shù)據(jù)模型 完全以數(shù)據(jù)描述。通常是歐式幾何所能描述的規(guī) 則物體。 按發(fā)展時(shí)間：線框模型、表面模型、實(shí)體模型； 以數(shù)據(jù)文

2、件的形式存在。(靜態(tài)),2.過(guò)程模型 以一個(gè)過(guò)程和相應(yīng)的控制參數(shù)描述。通常描述不規(guī)則的自然景物。(基于分形幾何） 以一個(gè)數(shù)據(jù)文件和一段代碼的形式存在；（動(dòng)態(tài)） 包括：隨機(jī)插值模型、迭代函數(shù)系統(tǒng)、 L系統(tǒng)、粒子系統(tǒng)、動(dòng)力系統(tǒng)等。,二. 形體的定義與運(yùn)算 形體一般定義為六層拓?fù)浣Y(jié)構(gòu)，首先介紹在三維空間中基本術(shù)語(yǔ)的定義。,形體（object）,由封閉表面圍成的有效空間稱為體； 一個(gè)體Q是R3空間中非空、有界的封閉子集。 其邊界（記為Q）是有限個(gè)面的并集，而外殼是形體的最大邊界。 例如：一個(gè)單位立方體可定義(x,y,z)R3|0 x1,0y1,0z1其中一個(gè)表面可表示為：(1,y,z)R3|0y1,0

3、z1,面 R3中非空、連續(xù)、共面且封閉的子集稱為面F，其邊界(記為F)是有限條線段的并集，Pt表示含有F的唯一平面。 面是形體表面的一部分，且具有方向性.,環(huán) 由有序、有向邊組成的面的封閉邊界稱為環(huán)。 環(huán)中任意邊都不能自交； 相鄰兩條邊共享一個(gè)端點(diǎn)； 環(huán)又分為內(nèi)環(huán)和外環(huán)。內(nèi)環(huán)邊按順時(shí)針?lè)较颉Ｍ猸h(huán)是確定面的最大外邊界，其邊按逆時(shí)針?lè)较颍催@種方式定義，在面上沿著邊的方向前進(jìn)，面的內(nèi)部始終在走向的左側(cè)。,邊 形體內(nèi)兩個(gè)相鄰面的交界稱為邊。一條邊有且僅有兩個(gè)相鄰面。 兩個(gè)端點(diǎn)確定一條邊，這兩個(gè)端點(diǎn)分別稱為該邊的起點(diǎn)和終點(diǎn)。,面1,面2,頂點(diǎn) 邊的端點(diǎn)稱為頂點(diǎn)，頂點(diǎn)不能出現(xiàn)在邊的內(nèi)部，也不能孤立地位于

4、物體內(nèi)、物體外或面內(nèi)。 上述定義中我們知道幾何元素中有兩種重要信息 幾何信息，用以表示幾何元素性質(zhì)和度量關(guān)系，如位置、大小、方向等； 拓?fù)湫畔?，用以表示幾何元素之間的連接關(guān)系。,形 體 頂點(diǎn)、棱邊、表面之間的拓?fù)潢P(guān)系,形體的性質(zhì)： 具有一定的形狀，不變形（剛性） 實(shí)體的各個(gè)部分均是三維的（維數(shù)的一致性） 占據(jù)空間有限（有限性） 經(jīng)過(guò)幾何變換和集合變換之后，仍然是有效地實(shí)體（封閉性） 實(shí)體的邊界可以區(qū)分出實(shí)體的內(nèi)部和外部。（邊界的確定性）。 滿足以上性質(zhì)的物體稱為有效物體或正則形體,帶有懸面的形體,帶有懸邊的形體,一條邊有兩個(gè)以上的鄰面,非有效的物體！ 非正則物體！,歐拉公式 檢驗(yàn)實(shí)體有效性的必

5、要條件 V-E+F=2（V為頂點(diǎn)數(shù)，E為棱線數(shù)，F(xiàn)為面數(shù)）,歐拉運(yùn)算時(shí)，必須要保證歐拉公式和下述條件成立，才能夠保證形體的拓?fù)溆行浴?面單連通，沒(méi)有孔，且被單條邊環(huán)圍??； 實(shí)體的補(bǔ)集是單連通，沒(méi)有洞穿過(guò)它； 邊完全與兩個(gè)面鄰接，且每端以一個(gè)頂點(diǎn)結(jié)束； 頂點(diǎn)至少是三條邊的匯合點(diǎn)。,廣義歐拉公式 V- E+F - R=2(S-H) 其中，R為面上的孔穴數(shù)，H為貫穿多面體的孔穴數(shù)，S為形體非連通部分總數(shù)。,實(shí)體的正則集合運(yùn)算 有效實(shí)體具有封閉性：一個(gè)有效實(shí)體經(jīng)過(guò)一系列 集合運(yùn)算之后仍然是有效實(shí)體。 普通的集合運(yùn)算不能滿足此要求。,正則集合運(yùn)算保證集合運(yùn)算的結(jié)果仍是一個(gè)正則形體，即丟棄懸邊、懸面等。

6、,對(duì)共同邊的取舍： 邊的走向相反則無(wú)效,三. 形體（實(shí)體）的表示 形體常用的3種表示方法： 線框模型、表面模型 、實(shí)體模型 1.線框模型 早期模型。用頂點(diǎn)和棱邊來(lái)描述物體。 一般地，畫出了形體的棱線(邊)與輪廓線就能唯一地表示出來(lái)。,數(shù)據(jù)結(jié)構(gòu) 存儲(chǔ)頂點(diǎn)列表和邊列表,長(zhǎng)方體的頂點(diǎn)表,長(zhǎng)方體的邊表,對(duì)于多面體由于其輪廓線和棱線通常是一致的，所以多面體的線模型更便于識(shí)別，且簡(jiǎn)單。對(duì)于圓柱體或球體之類的形體，只畫出棱線而不畫出輪廓線是不能完整地表示出這個(gè)形體的。,線框模型的優(yōu)缺點(diǎn): 簡(jiǎn)單，處理速度快，所占的存貯空間較少； 對(duì)于非平面多面體，如圓柱、球等形體，其輪廓線隨觀察方向的改變而改變，無(wú)法用一組固

7、定的輪廓線來(lái)表示它們。線框模型與形體之間不存在一一對(duì)應(yīng)關(guān)系，定義的形體存在多義性。 難以計(jì)算面積、體積、物體重心等物理量,線框圖的二義性： 不同的模型顯示成線框圖的結(jié)果一樣,2. 表面模型 形體表示成一組表面的集合。 把線框模型中的棱線及輪廓線包圍的部分定義為面，所形成的模型便是表面模型。 數(shù)據(jù)結(jié)構(gòu)是在線模型的基礎(chǔ)上附加一些指針，有序地連接棱線。,多邊形網(wǎng)格模型,例如：如下圖的三角形網(wǎng)格構(gòu)成的曲面，用數(shù)組來(lái)存儲(chǔ)它的信息,v0,v1,v2,v3,v4,v6,v7,v8,v5,Vertex 0：x0,y0,z0 1：x1,y1,z1 2：x2,y2,z2 3：x3,y3,z3 4：x4,y4,z4

8、 5：x5,y5,z5 6：x6,y6,z6 7：x7,y7,z7 8：x8,y8,z8,Triangle 0：0,1,3 1：1,4,3 2：1,2,4 3：2,4,1 4：2,5,4 5：3,4,6 6：4,7,6 7：5,8,7,表面模型的優(yōu)點(diǎn)： 比線框模型立體感強(qiáng)； 形體與其表面一一對(duì)應(yīng)，表達(dá)了物體的表面形狀，消除了多義性； 易于計(jì)算面積 表面模型存在的問(wèn)題： 表面模型中的所有面未必形成一個(gè)封閉的邊界； 各個(gè)面的側(cè)向沒(méi)有明確定義，即不知道實(shí)體位于面的哪一側(cè)。,在面模型上打孔，內(nèi)部為“空洞”,3.實(shí)體模型 形體為封閉表面圍成的有效空間。 在表面模型的基礎(chǔ)上增加： 一個(gè)封閉的邊界； 實(shí)體在

9、表面某一側(cè)的定義方法。 能夠計(jì)算體積、面積、重量、動(dòng)量、轉(zhuǎn)矩等物理量； 可以賦予材料特性；模擬物理的運(yùn)動(dòng)，受力變形等。,在實(shí)體模型的表示中，基本上可以分為 邊界表示 分解表示 構(gòu)造表示 掃描表示,（1）實(shí)體的邊界表示 邊界表示BRep 記錄形體所有的幾何信息和拓?fù)湫畔?在邊界表示法中，邊界表示按照體面環(huán)邊點(diǎn)的層次，詳細(xì)記錄了構(gòu)成形體的所有幾何元素的幾何信息及其相互連接的拓?fù)潢P(guān)系。,比較著名的邊界表示的數(shù)據(jù)結(jié)構(gòu)有半邊數(shù)據(jù)結(jié)構(gòu)、翼邊數(shù)據(jù)結(jié)構(gòu)、輻射邊數(shù)據(jù)結(jié)構(gòu)等。 翼邊數(shù)據(jù)結(jié)構(gòu)基于邊表示的數(shù)據(jù)結(jié)構(gòu),用指針記錄了每一邊的兩個(gè)鄰面（即左外環(huán)和右外環(huán)）、兩個(gè)頂點(diǎn)、兩側(cè)各自相鄰的兩個(gè)鄰邊（即左上邊、左下邊、右

10、上邊和右下邊）,Brep表示優(yōu)缺點(diǎn)是： 優(yōu)點(diǎn) 容易確定幾何元素間的連接關(guān)系； 缺點(diǎn)： 數(shù)據(jù)結(jié)構(gòu)復(fù)雜，需要大量的存儲(chǔ)空間，維護(hù)內(nèi)部數(shù)據(jù)結(jié)構(gòu)的程序比較復(fù)雜； Brep表示不一定對(duì)應(yīng)一個(gè)有效形體，通常運(yùn)用歐拉操作來(lái)保證Brep表示形體的有效性、正則性等。,（2）實(shí)體的分解表示 八叉樹的表示 首先對(duì)形體定義一個(gè)外接立方體，再把它分解成八個(gè)子立方體，并對(duì)立方體依次編號(hào)為0，1，2，7。 如果子立方體單元已經(jīng)一致，即為滿（該立方體充滿形體）或?yàn)榭眨](méi)有形體在其中），則該子立方體可停止分解； 否則，需要對(duì)該立方體作進(jìn)一步分解，再一分為八個(gè)子立方體。在八叉樹中，非葉結(jié)點(diǎn)的每個(gè)結(jié)點(diǎn)都有八個(gè)分支。,八叉樹的根節(jié)點(diǎn)

11、對(duì)應(yīng)整個(gè)物體空間 如果它完全被物體占據(jù)，將該節(jié)點(diǎn)標(biāo)記為F(Full)， 如果它內(nèi)部沒(méi)有物體，將該節(jié)點(diǎn)標(biāo)記為E(Empty) 如果它被物體部分占據(jù)，將該節(jié)點(diǎn)標(biāo)記為P(Partial)，并將它分割成8個(gè)子立方體，對(duì)每一個(gè)子立方體進(jìn)行同樣的處理,優(yōu)缺點(diǎn) 優(yōu)點(diǎn) 可以表示任何物體,數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)單 容易實(shí)現(xiàn)物體間的集合運(yùn)算 容易計(jì)算物體的整體性質(zhì)，如體積等 缺點(diǎn) 是物體的非精確表示 沒(méi)有邊界信息，不適于圖形顯示 對(duì)物體進(jìn)行幾何變換困難,（3）實(shí)體的構(gòu)造表示,并,交,差,體素： 球和柱,構(gòu)造實(shí)體幾何表示模型對(duì)于復(fù)雜的形體都可以通過(guò)正則集合運(yùn)算或幾何變換操作用簡(jiǎn)單形體（體素）組合來(lái)表示。,在幾何造型系統(tǒng)中常用的體素如圖，每個(gè)體素都用簡(jiǎn)單參數(shù)變量表示，這里的參數(shù)包含體素的大小、形狀、位置和方向。,一般地，用構(gòu)造實(shí)體幾何表示模型構(gòu)造形體的方法無(wú)二義性，但不是唯一的，通常采用最簡(jiǎn)單的構(gòu)造方法。,構(gòu)造實(shí)體幾何表示模型的構(gòu)造方法可以看作一棵有序的二叉樹，稱為CSG樹。非葉節(jié)點(diǎn)可以是正則集合運(yùn)算操作，也可以是形體的幾何變換（平移、旋轉(zhuǎn)或縮放）操作，所有操作只對(duì)其子樹（子形體）起作用。,（4）實(shí)體的掃描表示 基于一個(gè)基體，沿著某一路徑運(yùn)動(dòng)而產(chǎn)生形體。 “物體” + “運(yùn)動(dòng)的軌跡”,常用的掃描方式有： 平移掃描法：基體沿直