三維幾何造型

第一講三維幾何造型1第6講幾何造型6.1概述6.2基礎(chǔ)知識(shí)6.3常用的形體表示模型6.4三維形體的多邊形表示6.5過程模型6.6常見實(shí)體造型系統(tǒng)簡(jiǎn)介2每個(gè)粒子有一個(gè)生命周期，包括出生、成長(zhǎng)、滅亡等幾個(gè)階段，演化過程有一定的規(guī)則控制；邊界表示(B-Rep)模型在一個(gè)幾何造型系統(tǒng)中，往往是多種方法并存，互相補(bǔ)充。abaababaabaab(a)中的形體可以用(b)或(c)定義構(gòu)造實(shí)體幾何表示模型的幾何造型系統(tǒng)一般由兩部分組成：不適于真實(shí)感顯示（不能處理物體的側(cè)影輪廓線，也不能生成剖切圖、消隱圖、明暗色彩圖等）。形體常用的3種表示方法：能夠計(jì)算體積、面積、重量、動(dòng)量、轉(zhuǎn)矩等物理量；注意，凡是標(biāo)識(shí)為“Full”或“Empty”的立方體均為終端結(jié)點(diǎn)，而標(biāo)識(shí)為“Partial”的立方體為非終端結(jié)點(diǎn)。面的形狀可以是平面或曲面。粒子系統(tǒng)(ParticleSystem)表示簡(jiǎn)單、直觀，是生成三維形體的有效方法。構(gòu)造實(shí)體幾何(CSG)表示模型構(gòu)造實(shí)體幾何表示模型(CSG:ConstructiveSolidGeometry)6.1概述客觀世界中的物體都是三維的，真實(shí)地描述和顯示客觀世界中的三維物體是計(jì)算機(jī)圖形學(xué)研究的重要內(nèi)容。一個(gè)物體的計(jì)算機(jī)描述叫做模型，它能被計(jì)算機(jī)所懂得，并在一定的條件下（變換和投影）被轉(zhuǎn)換成相應(yīng)的圖形在屏幕顯示或在繪圖機(jī)上輸出；圖形是模型的一個(gè)具體可見像，是人們所看到的模型的表征。不能把兩者混為一談。在三維空間，描述的是幾何形體和幾何曲面，只有在平面上，它才是人們通常所稱的圖形。36.1概述計(jì)算機(jī)幾何造型就是用計(jì)算機(jī)系統(tǒng)來(lái)表示、控制、分析和輸出三維形體(描述物體的幾何信息和拓?fù)湫畔?。所以幾何造型是計(jì)算機(jī)圖形學(xué)中一個(gè)十分重要的研究領(lǐng)域。幾何造型系統(tǒng)的主要功能：形體輸入，即把形體從用戶格式轉(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ì)特性分析等；形體顯示輸出，如消隱、光照、顏色的控制等；詢問形體的屬性及其有關(guān)參數(shù)。46.1概述表示形體的兩種模型:數(shù)據(jù)模型：規(guī)則形體的建模方法；用歐式幾何描述。過程模型：不規(guī)則形體的建模方法；用分形幾何描述。形體表示數(shù)據(jù)模型過程模型線框模型表面模型實(shí)體模型56.1概述數(shù)據(jù)模型完全以數(shù)據(jù)描述。通常是歐式幾何所能描述的規(guī)則物體。例如：以頂點(diǎn)表示的立方體、以球心和半徑表示的球。按發(fā)展時(shí)間：線框模型、表面模型、實(shí)體模型；以數(shù)據(jù)文件的形式存在。(靜態(tài))本章主要介紹實(shí)體模型。66.1概述過程模型以一個(gè)過程和相應(yīng)的控制參數(shù)描述。通常描述不規(guī)則的自然景物。(基于分形幾何)例如：用一些控制參數(shù)和一個(gè)生成規(guī)則描述的植物。以一個(gè)數(shù)據(jù)文件和一段代碼的形式存在；（動(dòng)態(tài)）包括：隨機(jī)插值模型、迭代函數(shù)系統(tǒng)、L系統(tǒng)、粒子系統(tǒng)、動(dòng)力系統(tǒng)等。7第6講幾何造型6.1概述6.2基礎(chǔ)知識(shí)6.3常用的形體表示模型6.4過程模型6.5三維形體的多邊形表示6.6常見實(shí)體造型系統(tǒng)簡(jiǎn)介86.2基礎(chǔ)知識(shí)1.形體2.形體表示方法3.正則集合運(yùn)算4.歐拉運(yùn)算91.形體在計(jì)算機(jī)中，形體一般定義為六層拓?fù)浣Y(jié)構(gòu)，首先介紹在三維空間中基本術(shù)語(yǔ)的定義。形體(object)外殼(shell)面(face)環(huán)(loop)邊(edge)頂點(diǎn)(vertex)曲線或直線方程點(diǎn)的幾何坐標(biāo)101.形體體 由封閉表面圍成的有效空間稱為體；一個(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}必須注意：并沒有規(guī)定形體必須是一個(gè)連續(xù)的封閉集合，目的是用這樣的定義來(lái)擴(kuò)大幾何造型的域，使得形體可以由不連續(xù)的體素，或是僅有某些相交的形體組成。xzy111.形體面

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

其邊界(記為?F)是有限條線段的并集，Pt表示含有F的唯一平面。面是形體表面的一部分，且具有方向性.FPt121.形體環(huán) 由有序、有向邊組成的面的封閉邊界稱為環(huán)。環(huán)中任意邊都不能自交；相鄰兩條邊共享一個(gè)端點(diǎn)；環(huán)又分為內(nèi)環(huán)和外環(huán)。內(nèi)環(huán)是在已知面中的內(nèi)孔，其邊按逆時(shí)針方向。外環(huán)是已知面的最大外邊界的環(huán)，其邊按順時(shí)針方向，按這種方式定義，在面上沿著邊的方向前進(jìn)，面的內(nèi)部始終在走向的右側(cè)。131.形體邊 形體內(nèi)兩個(gè)相鄰面的交界稱為邊。一條邊有且僅有兩個(gè)相鄰面。兩個(gè)端點(diǎn)確定一條邊，這兩個(gè)端點(diǎn)分別稱為該邊的起點(diǎn)和終點(diǎn)。假設(shè)Q是一個(gè)形體，E(Q)是形體邊的集合，則在?Q中E(Q)為滿足下列條件的所有線段的集合：邊e的兩個(gè)端點(diǎn)屬于頂點(diǎn)V(Q)；邊e中沒有一個(gè)內(nèi)部點(diǎn)屬于頂點(diǎn)V(Q)邊e上每個(gè)點(diǎn)，都有兩個(gè)不同的面，即存在兩個(gè)面

fi，fJ∈

?Q，使得邊e∈fi∩fj；形體Q的邊框線WF(Q)是由有序?qū)?V(Q),E(Q))所組成。v1v2ef1f2141.形體頂點(diǎn) 邊的端點(diǎn)稱為頂點(diǎn)，頂點(diǎn)不能出現(xiàn)在邊的內(nèi)部，也不能孤立地位于物體內(nèi)、物體外或面內(nèi)，頂點(diǎn)又是?F中兩條不共線的線段的交點(diǎn)。假設(shè)Q是一個(gè)形體，V(Q)是所有頂點(diǎn)P的集合，Pf是含面f的唯一平面，則存在3個(gè)面f1,f2,f3∈?Q，一點(diǎn)P∈V(Q)，使得|P|=f1∩f2∩f3=Pf1∩Pf2∩Pf3。v1v2ef1f2151.形體幾何信息 用來(lái)表示形體的幾何性質(zhì)和度量關(guān)系稱為幾何信息。拓?fù)湫畔?用來(lái)表示形體之間的連接關(guān)系稱為拓?fù)湫畔ⅰ?66.2基礎(chǔ)知識(shí)1.形體2.形體表示方法3.正則集合運(yùn)算4.歐拉運(yùn)算172.形體表示方法形體常用的3種表示方法：

線框模型、表面模型和實(shí)體模型:線框模型早期模型。用頂點(diǎn)和棱邊來(lái)描述物體。一般地，畫出了形體的棱線(邊)與輪廓線就能唯一地表示出來(lái)。如上圖，八個(gè)頂點(diǎn)可以定義一個(gè)長(zhǎng)方體，但還不足以識(shí)別它，如果定義了棱線，則無(wú)論如何放置長(zhǎng)方體都能唯一地表示了。e12v4v8e2e4e6e8e2e7e11e10e9e3e1v2v3v1v7v5v618V1V2V3V4V5V6V7V8E8E10E1E2E3E4E5E6E7E9E11E12abcXZY下圖和表說(shuō)明了線框模型在計(jì)算機(jī)內(nèi)存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)原理。組成長(zhǎng)方體的頂點(diǎn)和邊

頂點(diǎn)表V1V2V3V4V5V6V7V8x坐標(biāo)aaaa0000y坐標(biāo)0bb00bb0z坐標(biāo)00cc00cc長(zhǎng)方體的頂點(diǎn)表

19邊號(hào)E1E2E3E4E5E6E7E8E9E10E11E12起點(diǎn)號(hào)V1V2V3V4V5V6V7V8V1V2V3V4終點(diǎn)號(hào)V2V3V4V1V6V7V8V5V5V6V7V8長(zhǎng)方體的邊表

V1V2V3V4V5V6V7V8E8E10E1E2E3E4E5E6E7E9E11E12abcXZY組成長(zhǎng)方體的頂點(diǎn)和邊

202.形體表示方法線框模型

對(duì)于多面體由于其輪廓線和棱線通常是一致的，所以多面體的線模型更便于識(shí)別，且簡(jiǎn)單。 對(duì)于圓柱體或球體之類的形體，只畫出棱線而不畫出輪廓線是不能完整地表示出這個(gè)形體的。下圖是圓柱體的多種表示方法：e12v4v8e2e4e6e8e5e7e11e10e9e3e1v2v3v1v7v5v6212.形體表示方法線框模型的優(yōu)缺點(diǎn):簡(jiǎn)單，處理速度快，所占的存貯空間較少；對(duì)于非平面多面體，如圓柱、球等形體，其輪廓線隨觀察方向的改變而改變，無(wú)法用一組固定的輪廓線來(lái)表示它們。線框模型與形體之間不存在一一對(duì)應(yīng)關(guān)系：它僅僅通過給定的輪廓線約束所表示形體的邊界面，而在輪廓線之間的地方，形體的表面可以任意變化。沒有包含全部的信息，定義的形體存在多義性；不能計(jì)算面積、體積等物理量；不適于真實(shí)感顯示（不能處理物體的側(cè)影輪廓線，也不能生成剖切圖、消隱圖、明暗色彩圖等）。其應(yīng)用范圍很有限。22線框圖的二義性232.形體表示方法表面模型將形體表示成一組表面的集合。如果把線框模型中的棱線及輪廓線包圍的部分定義為面，所形成的模型便是表面模型。其數(shù)據(jù)結(jié)構(gòu)是在線模型的基礎(chǔ)上附加一些指針，有序地連接棱線。下圖中表面編號(hào)表示第幾個(gè)表面，表面特征是平面還是曲面。4頂點(diǎn)個(gè)數(shù)1起始指針0表面特征5表面編號(hào)014043032021連接指針屬性頂點(diǎn)形體表示方法比線框模型立體感強(qiáng)；形體與其表面一一對(duì)應(yīng)，表達(dá)了物體的表面形狀，消除了多義性；能夠計(jì)算面積；適合于真實(shí)感顯示；存在的問題不能有效的用來(lái)表示實(shí)體；表面模型中的所有面未必形成一個(gè)封閉的邊界；各個(gè)面的側(cè)向沒有明確定義，即不知道實(shí)體位于面的哪一側(cè)。在面模型上打孔，內(nèi)部為“空洞”252.形體表示方法實(shí)體模型 形體為封閉表面圍成的有效空間；可以簡(jiǎn)單理解為“實(shí)心”。 在表面模型的基礎(chǔ)上增加：一個(gè)封閉的邊界；實(shí)體在表面某一側(cè)的定義方法。能夠計(jì)算體積、面積、重量、動(dòng)量、轉(zhuǎn)矩等物理量；可以賦予材料特性；模擬物理的運(yùn)動(dòng)，受力變形等。262.形體表示方法實(shí)體模型 以下是實(shí)體在表面某一側(cè)的4種定義方法：方法1：除了定義一個(gè)表面外，還已知實(shí)體存在于表面一側(cè)的一點(diǎn)P；方法2：以箭頭指向?qū)嶓w存在一側(cè)的方法；方法3：定義表面邊界線為有向邊界，并設(shè)右螺旋前進(jìn)的方向?yàn)閷?shí)體存在的一側(cè)；方法4：將形體分割成幾個(gè)區(qū)域，

由于每一條邊界線兩側(cè)的箭頭方

向相反，則表明表面一側(cè)存在實(shí)體。P276.2基礎(chǔ)知識(shí)1.形體2.形體表示方法3.歐拉運(yùn)算286.2基礎(chǔ)知識(shí)1.形體2.形體表示方法3.歐拉運(yùn)算294.歐拉運(yùn)算歐拉公式：

V-E+F=2 （V為頂點(diǎn)數(shù)，E為棱線數(shù)，F(xiàn)為面數(shù)）凡是滿足歐拉公式的形體均稱為歐拉形體。歐拉公式是必要條件。V=4,E=6,F=4 v2v1v3v4v4v1v5v8v6v3v2v7V=8,E=12,F=6V=10,E=15,F=7304.歐拉運(yùn)算擴(kuò)展的歐拉公式：V-E+F-H=2(B-P)

其中，H為面上的孔穴數(shù)，P為貫穿多面體的孔穴數(shù)，B為形體非連通部分總數(shù)。V=16,E=24,F=11,

H=1,B=1,P=0V=10,E=15,F=7,

H=2,B=1,P=1

(圓柱孔上取兩點(diǎn)）V=12,E=18,F=8,

H=2,B=1,P=1

(圓柱孔上取四點(diǎn)）31第6講幾何造型6.1概述6.2基礎(chǔ)知識(shí)6.3常用的形體表示模型6.4三維形體的多邊形表示6.5過程模型6.6常見實(shí)體造型系統(tǒng)簡(jiǎn)介326.3常用的形體表示模型1.模型的考慮2.掃描變換(Sweep)表示模型3.構(gòu)造實(shí)體幾何(CSG)表示模型4.邊界表示(B-Rep)模型5.空間分割模型331.模型的考慮必須考慮以下一些問題：根據(jù)形體邊界給定的信息，是否能自動(dòng)的獲取形體的幾何特征？如何確定對(duì)形體操作數(shù)據(jù)的有效性？形體的表示模型是否唯一？不同的表示模型是否可以轉(zhuǎn)換？是否最佳表示模型？34邊界表示(B-Rep)模型擴(kuò)展的歐拉公式：V-E+F-H=2(B-P)3常用的形體表示模型由于物體的八叉樹表示就是由它內(nèi)部含有的大大小小的立方體（稱為體元）組成，因此對(duì)物體執(zhí)行并、交、差運(yùn)算時(shí)，只需同時(shí)遍歷參加集合運(yùn)算的兩物體相應(yīng)的八叉樹，就可以獲得拼合體的八叉樹，而無(wú)需進(jìn)行復(fù)雜的求交運(yùn)算。此時(shí)可將每一小立方體標(biāo)識(shí)為“Full”。注意，凡是標(biāo)識(shí)為“Full”或“Empty”的立方體均為終端結(jié)點(diǎn)，而標(biāo)識(shí)為“Partial”的立方體為非終端結(jié)點(diǎn)。自然界中很多的物體具有特征長(zhǎng)度，如人有高度、山有海拔等等?？梢栽谝粋€(gè)三角形的三邊上，隨機(jī)各取一點(diǎn)，沿垂直方向隨機(jī)偏移一段距離得到新的三個(gè)點(diǎn)，再連接成四個(gè)三角形，如此繼續(xù)，即可形成皺褶的山峰。字符串a(chǎn)，b，改寫規(guī)則a→ab;b→a生成規(guī)則：取一等邊三角形，連接各邊中點(diǎn)將原三角形分成四個(gè)小三角形，然后舍棄位于中間的一個(gè)小三角形，將剩下的其余三個(gè)小三角形按同樣方法繼續(xù)分割，并舍棄位于中間的那個(gè)三角形，如圖所示。如果把線框模型中的棱線及輪廓線包圍的部分定義為面，所形成的模型便是表面模型。分形（Fractal）這個(gè)詞，是由美籍法國(guó)數(shù)學(xué)家曼德爾布羅特（）自己創(chuàng)造出來(lái)的，此詞來(lái)源于拉丁文fractus，意為不規(guī)則、支離破碎。4三維形體的多邊形表示掃描變換(Sweep)表示模型方法1：除了定義一個(gè)表面外，還已知實(shí)體存在于表面一側(cè)的一點(diǎn)P；1.模型的考慮在實(shí)體模型的表示中，基本上可以分為分解表示、構(gòu)造表示和邊界表示三大類。目前常用的形體表示模型有：掃描變換表示模型(Sweep)構(gòu)造實(shí)體幾何表示模型(CSG:ConstructiveSolidGeometry)邊界表示模型(B-rep：BoundaryRepresentations)空間分割模型對(duì)于幾何造型系統(tǒng)來(lái)說(shuō)，按照不同的目的可以采用不同的最佳表示模型。后面將介紹四種模型。356.3常用的形體表示模型1.模型的考慮2.掃描變換(Sweep)表示模型3.構(gòu)造實(shí)體幾何(CSG)表示模型4.邊界表示(B-Rep)模型5.空間分割模型362.Sweep表示模型掃描變換表示模型的基本思想非常簡(jiǎn)單：“物體”+“運(yùn)動(dòng)的軌跡”。掃描變換表示模型是基于一個(gè)基體

(一般是一個(gè)封閉的平面輪廓或一個(gè)形體)沿指定路徑運(yùn)動(dòng)而掃掠生成的新形體。也稱“推移表示”。如：圖形A沿Z軸做掃描變換出來(lái)的三維形體。zyxA平移掃描法372.Sweep表示模型常用的掃描方式有：平移掃描法：基體沿直線進(jìn)行掃描；（拉伸體）旋轉(zhuǎn)掃描法：基體繞某一軸線旋轉(zhuǎn)一定角度；（旋轉(zhuǎn)體）廣義掃描法：掃描路徑是曲線，掃描過程中基體還可以發(fā)生變化；旋轉(zhuǎn)掃描法廣義掃描法382.Sweep表示模型圖形A繞B軸作旋轉(zhuǎn)掃描的形體：因此，三維形體S可以表示為由一個(gè)二維圖形A和一根軸B組成，即三維形體的表示可簡(jiǎn)化為二維圖形的表示。BAzyxA平移掃描法旋轉(zhuǎn)掃描法392.Sweep表示模型三維形體也能在空間通過掃描變換生成新的形體。 如左圖，一個(gè)圓柱體按指定方向在長(zhǎng)方體上運(yùn)動(dòng)生成新的形體，這個(gè)過程猶如長(zhǎng)方體與運(yùn)動(dòng)者的圓柱體不斷的作差運(yùn)算操作。U掃描線方向有時(shí)經(jīng)過掃描變換所生成的形體可能會(huì)出現(xiàn)維數(shù)不一致問題。402.Sweep表示模型優(yōu)點(diǎn)：表示簡(jiǎn)單、直觀，是生成三維形體的有效方法。適合做圖形輸入手段；可用來(lái)生成一些體素。配合仿射變換可生成復(fù)雜的形體；缺點(diǎn)：用掃描變換產(chǎn)生的形體可能出現(xiàn)維數(shù)不一致的問題(非正則物體－無(wú)效物體)；掃描方法不能直接獲取形體的邊界信息；表示形體的覆蓋域(類型)非常有限；作幾何變換困難；412.Sweep表示模型426.3常用的形體表示模型1.模型的考慮2.掃描變換(Sweep)表示模型3.構(gòu)造實(shí)體幾何(CSG)表示模型4.邊界表示(B-Rep)模型5.空間分割模型433.CSG表示模型構(gòu)造實(shí)體幾何表示模型對(duì)于復(fù)雜的形體都可以通過正則集合運(yùn)算或幾何變換操作用簡(jiǎn)單形體（體素）組合來(lái)表示。并交球－柱差體素：球和柱柱－球443.CSG表示模型由于體素表示的有效性決定了構(gòu)造實(shí)體幾何表示的有效性，所以在幾何造型中必須細(xì)致定義各種體素。在幾何造型系統(tǒng)中常用的體素如圖，每個(gè)體素都用簡(jiǎn)單參數(shù)變量表示，這里的參數(shù)包含體素的大小、形狀、位置和方向。HHHHHHHRRRRRrRdWWWWWLLLLL453.CSG表示模型體素的構(gòu)造：參數(shù)定義的簡(jiǎn)單形體，如球體，柱體，立方體等；掃描變換生成的形體；體素的表示也可以用曲面或平面半空間的交運(yùn)算來(lái)表示。463.CSG表示模型一般地，用構(gòu)造實(shí)體幾何表示模型構(gòu)造形體的方法無(wú)二義性，但不是唯一的，通常采用最簡(jiǎn)單的構(gòu)造方法。(a)中的形體可以用(b)或(c)定義(b)A-*B (a)(c)AU*B473.CSG表示模型構(gòu)造實(shí)體幾何表示模型的構(gòu)造方法可以看作一棵有序的二叉樹，稱為CSG樹。其中葉節(jié)點(diǎn)可以是體素，也可以是形體運(yùn)動(dòng)的變換參數(shù)，非葉節(jié)點(diǎn)可以是正則集合運(yùn)算操作，也可以是形體的幾何變換（平移、旋轉(zhuǎn)或縮放）操作，所有操作只對(duì)其子樹（子形體）起作用。對(duì)一棵CSG樹按深度優(yōu)先遍歷，依次執(zhí)行指定的操作，結(jié)果便得到所表示的形體。CSG樹的形式定義為：

<CSG樹>::=<體素葉子> |<CSG樹><正則集合運(yùn)算><CSG樹> |<CSG樹><幾何變換><變換參數(shù)>483.CSG表示模型例如：體素π1、π2和平移變換Δx作為3個(gè)葉節(jié)點(diǎn)，π1-π2和π2(Δx)的操作結(jié)果作為兩個(gè)中間節(jié)點(diǎn)(非葉節(jié)點(diǎn))，最終的形體(π1-π2)-π2(Δx)作為根節(jié)點(diǎn)。493.CSG表示模型構(gòu)造實(shí)體幾何表示模型的幾何造型系統(tǒng)一般由兩部分組成：一部分是描述通過集合運(yùn)算和幾何變換操作連接體素所生成子形體的CSG樹的數(shù)據(jù)結(jié)構(gòu)；另一部分是描述相應(yīng)體素的大小、形狀、位置和方向等幾何參數(shù)。通過以上給定的構(gòu)造實(shí)體幾何表示模型可以計(jì)算出其形體的邊界表示。其計(jì)算過程如下：對(duì)單個(gè)形體，計(jì)算其表面在何處被截?cái)?，哪些邊或頂點(diǎn)被產(chǎn)生或刪除？對(duì)兩個(gè)相交形體，計(jì)算由于其相交而產(chǎn)生的新邊：計(jì)算兩相交形體的相交線段；按幾何元素分類，確定相交線段的哪一部分真正屬于新形體的邊（有效邊）。503.CSG表示模型CSG表示的優(yōu)點(diǎn)：數(shù)據(jù)結(jié)構(gòu)比較簡(jiǎn)單，數(shù)據(jù)量比較小，內(nèi)部數(shù)據(jù)的管理比較容易；CSG表示可方便地轉(zhuǎn)換成邊界（B-Rep）表示；CSG方法表示的形體的形狀，比較容易修改。CSG表示的缺點(diǎn)：是一種體表示方法，顯示/繪制時(shí)需進(jìn)行轉(zhuǎn)換；對(duì)形體的表示受體素的種類和對(duì)體素操作的種類的限制，也就是說(shuō)，CSG方法表示形體的覆蓋域有較大的局限性。對(duì)形體的局部操作不易實(shí)現(xiàn)。例如：彎曲表面，對(duì)交線倒圓角；所以在使用CSG表示模型的系統(tǒng)中需要結(jié)合其他表示模型或算法來(lái)解決有關(guān)問題。516.3常用的形體表示模型1.模型的考慮2.掃描變換(Sweep)表示模型3.構(gòu)造實(shí)體幾何(CSG)表示模型4.邊界表示(B-Rep)模型5.空間分割模型52構(gòu)造實(shí)體幾何(CSG)表示模型由有序、有向邊組成的面的封閉邊界稱為環(huán)。5三維形體的多邊形表示邊界表示(B-Rep)模型掃描變換(Sweep)表示模型必須考慮以下一些問題：CSG表示與B-Rep表示曾為兩大主流方法。邊界表示模型(B-rep：BoundaryRepresentations)表面模型中的所有面未必形成一個(gè)封閉的邊界；環(huán)中任意邊都不能自交；并沿垂直連線方向隨機(jī)偏移一個(gè)距離，再將偏移后的點(diǎn)與該線段兩端點(diǎn)分別連成兩個(gè)新線段。在一個(gè)幾何造型系統(tǒng)中，往往是多種方法并存，互相補(bǔ)充。邊界表示(B-Rep)模型正確的答案令人吃驚：是不確定的，其長(zhǎng)度依賴于測(cè)量單位的長(zhǎng)度。用來(lái)表示形體的幾何性質(zhì)和度量關(guān)系稱為幾何信息。4.邊界表示(B-Rep)模型CSG表示與B-Rep表示曾為兩大主流方法。80’，ACMSolidmodeling、歐洲CSG會(huì)議當(dāng)前B-Rep表示一統(tǒng)天下。在一個(gè)幾何造型系統(tǒng)中，往往是多種方法并存，互相補(bǔ)充。534.邊界表示模型邊界表示模型是一種采用幾何和拓?fù)湫畔?lái)描述的表示模型。一個(gè)形體一般可以通過其邊界拆成一些有界的“面”或“小片”的子集來(lái)表示，而每一個(gè)面又可以通過其邊界的邊和頂點(diǎn)來(lái)表示。若面的表示無(wú)二義性，則其邊界表示模型也無(wú)二義性，但通常不一定只有唯一的表示。四棱椎邊界表示的例子如右，由4個(gè)面組成，且這種表示可以看作是含有體、面、邊、頂點(diǎn)為節(jié)點(diǎn)的有向圖四棱椎邊界表示也可以基于邊界的三角形分解，即把形體的邊界拆成一些互不重疊的三角形。v1v2v3v4v5v2v3v4v5e1e2e3f1v1四棱柱面節(jié)點(diǎn)邊節(jié)點(diǎn)頂點(diǎn)坐標(biāo)f1f2f3….e1e2e3e4….v1v2v3….(x1,y1,z1) 組合

結(jié)構(gòu) 坐標(biāo)

信息….544.邊界表示(B-Rep)模型邊界模型的基本拓?fù)鋵?shí)體包括：1.頂點(diǎn)2.邊 邊有方向，它由起始頂點(diǎn)和終止頂點(diǎn)來(lái)界定。邊的形狀（Curve）由邊的幾何信息來(lái)表示，可以是直線或曲線，曲線邊可用一系列控制點(diǎn)或型值點(diǎn)來(lái)描述，也可用顯式、隱式或參數(shù)方程來(lái)描述。3.環(huán) 環(huán)（Loop）是有序、有向邊（Edge）組成的封閉邊界。環(huán)有方向，有內(nèi)、外環(huán)之分。554.邊界表示模型邊界模型表達(dá)形體的基本拓?fù)鋵?shí)體包括(參考8.2.1)：4.面 面（Face）由一個(gè)外環(huán)和若干個(gè)內(nèi)環(huán)（可以沒有內(nèi)環(huán)）來(lái)表示，內(nèi)環(huán)完全在外環(huán)之內(nèi)。 面具有方向。面的形狀可以是平面或曲面。平面可用平面方程來(lái)描述，曲面可用控制多邊形或型值點(diǎn)來(lái)描述，也可用曲面方程（隱式、顯式或參數(shù)形式）來(lái)描述。對(duì)于參數(shù)曲面，通常在其二維參數(shù)域上定義環(huán)，這樣就可由一些二維的有向邊來(lái)表示環(huán)，集合運(yùn)算中對(duì)面的分割也可在二維參數(shù)域上進(jìn)行。5.體 體（Body）是面的并集。564.邊界表示(B-Rep)模型用邊界模型表示形體的方法有多種：如把面組成CSG表示模型中的體素，再組合體素生成更復(fù)雜形體；或直接將表面的組合及其相交來(lái)生成復(fù)雜形體；利用歐拉運(yùn)算；B-Rep模型的數(shù)據(jù)結(jié)構(gòu)中比較著名的有：翼邊數(shù)據(jù)結(jié)構(gòu)；1972年，由斯坦福大學(xué)Baumgart作為多面體的表示模式提出。用這一數(shù)據(jù)結(jié)構(gòu)表示多面體模型是完備的，但它不能表示帶有精確曲面邊界的實(shí)體。輻射邊數(shù)據(jù)結(jié)構(gòu)；1986年，Weiler提出了輻射邊（RadialEdge）數(shù)據(jù)結(jié)構(gòu)。可表示非正則形體，及曲線邊、曲面等。數(shù)據(jù)結(jié)構(gòu)根據(jù)造型系統(tǒng)的需求設(shè)計(jì)。574.邊界表示(B-Rep)模型優(yōu)點(diǎn)：表示能力強(qiáng)；精確表示物體；幾何變換容易；適于顯示處理；缺點(diǎn)：表示復(fù)雜；有效性難以保證；(采用多邊形近似時(shí))集合運(yùn)算復(fù)雜；58空間分割表示模型

物體的八叉樹表示是一種層次數(shù)據(jù)結(jié)構(gòu)，是對(duì)二維空間中四叉樹編碼方法的擴(kuò)展。四叉樹將二維區(qū)域分成四等分而得，八叉樹是將三維區(qū)域分成八等分而得。

首先在空間中定義一個(gè)能夠包含所表示物體的立方體。立方體的三條棱邊分別與x,y,z軸平行，邊長(zhǎng)為2n。若立方體內(nèi)空間完全由所表示的物體所占據(jù)，則物體可用這個(gè)立方體予以表示，否則將立方體在x,y,z軸三個(gè)方向都分成二等分，整個(gè)立方體共等分為八個(gè)小塊，每塊仍為一個(gè)小立方體，其邊長(zhǎng)為原來(lái)立方體邊長(zhǎng)的1/2。將這八個(gè)小立方體依序編號(hào)為0，1，2，…，7，如圖所示。

八叉樹的結(jié)點(diǎn)編碼59若某一小立方體的體內(nèi)空間全部被所表示的物體占據(jù)，則將此立方體標(biāo)識(shí)為“Full”；若它與所表示物體無(wú)交，則該立方體被標(biāo)識(shí)為“Empty”；否則將它標(biāo)識(shí)為“Partial”，并繼續(xù)分割下去。依此方式，物體在計(jì)算機(jī)內(nèi)可表示為一棵八叉樹。注意，凡是標(biāo)識(shí)為“Full”或“Empty”的立方體均為終端結(jié)點(diǎn)，而標(biāo)識(shí)為“Partial”的立方體為非終端結(jié)點(diǎn)。最后，當(dāng)分割生成的每一小立方體的邊長(zhǎng)為單位長(zhǎng)時(shí)，分割即告終止。此時(shí)可將每一小立方體標(biāo)識(shí)為“Full”。60物體之間的集合運(yùn)算在八叉樹表示中具有十分簡(jiǎn)單的形式。由定義可知，兩物體的并就是這兩個(gè)物體一共占有的空間，而物體之間的交即它們共同占據(jù)的空間。由于物體的八叉樹表示就是由它內(nèi)部含有的大大小小的立方體（稱為體元）組成，因此對(duì)物體執(zhí)行并、交、差運(yùn)算時(shí)，只需同時(shí)遍歷參加集合運(yùn)算的兩物體相應(yīng)的八叉樹，就可以獲得拼合體的八叉樹，而無(wú)需進(jìn)行復(fù)雜的求交運(yùn)算。

616.3常用的形體表示模型1.模型的考慮2.構(gòu)造實(shí)體幾何(CSG)表示模型3.掃描變換(Sweep)表示模型4.邊界表示(B-Rep)模型62第6講幾何造型6.1概述6.2基礎(chǔ)知識(shí)6.3常用的形體表示模型6.4三維形體的多邊形表示6.5過程模型6.6常見實(shí)體造型系統(tǒng)簡(jiǎn)介636.4三維形體的多邊形表示造型的應(yīng)用？CAD/CAM中，需要精確的表示。實(shí)體模型。游戲、動(dòng)畫等顯示或繪制環(huán)境中，只需要可接受的視覺效果。往往采用多邊形網(wǎng)格來(lái)近似表示物體。多邊形表示的精度由多邊形網(wǎng)格的數(shù)量決定。646.4三維形體的多邊形表示多邊形網(wǎng)格實(shí)際上就是物體表面(faces)的近似多邊形的集合。為什么要采用多邊形網(wǎng)格來(lái)表示形體？結(jié)構(gòu)簡(jiǎn)單，可表示任意形體。雖然不精確，但足以滿足視覺的需要。在光照處理、紋理映射等算法中易于處理多邊形(計(jì)算屬性簡(jiǎn)單，如法向量等)，便于硬件實(shí)現(xiàn)。65第6講幾何造型6.1概述6.2基礎(chǔ)知識(shí)6.3常用的形體表示模型6.4三維形體的多邊形表示6.5過程模型6.6常見實(shí)體造型系統(tǒng)簡(jiǎn)介666.5過程模型1.分形幾何2.隨機(jī)插值模型3.迭代函數(shù)系統(tǒng)4.基于文法的模型：L系統(tǒng)5.粒子系統(tǒng)6.動(dòng)力系統(tǒng)671.分形幾何真實(shí)的世界卻并不規(guī)則。閃電不是直線，海岸線不是弧線，云團(tuán)不是球體，山巒也不是錐體。自然界的許多對(duì)象是如此不規(guī)則和支離破碎，以致歐氏幾何學(xué)不能真實(shí)有效地再現(xiàn)大自然。為了再現(xiàn)真實(shí)世界，必須選擇新的工具，分形幾何學(xué)應(yīng)運(yùn)而生。分形幾何是以非規(guī)則物體為研究對(duì)象的幾何學(xué)。由于閃電、海岸線、云團(tuán)、山巒、海浪、野草、森林、火光等非規(guī)則物體在自然界里比比皆是，因此分形幾何學(xué)又被稱為描述大自然的幾何學(xué)。681.分形幾何分形（Fractal）這個(gè)詞，是由美籍法國(guó)數(shù)學(xué)家曼德爾布羅特（）自己創(chuàng)造出來(lái)的，此詞來(lái)源于拉丁文fractus，意為不規(guī)則、支離破碎。1967年曼德爾布羅特在《科學(xué)》雜志上發(fā)表了劃時(shí)代的論文《英國(guó)海岸線有多長(zhǎng)？統(tǒng)計(jì)自相似與分?jǐn)?shù)維》，成為其分形思想萌芽的重要標(biāo)志。1973年，在法蘭西學(xué)院講學(xué)期間，曼德爾布羅特提出了分形幾何學(xué)的整體思想，并認(rèn)為分?jǐn)?shù)維是個(gè)可用于研究許多物理現(xiàn)象的有力工具。1982年曼德爾布羅特出版了《大自然的分形幾何學(xué)》，引起了學(xué)術(shù)界的廣泛重視，曼德爾布羅特也因此一舉成名。1985年獲得Barnard獎(jiǎng)?wù)拢ㄎ锢韺W(xué)，每五年一次）691.分形幾何67年，Mandelbrot提出“英國(guó)的海岸線有多長(zhǎng)？”正確的答案令人吃驚：是不確定的，其長(zhǎng)度依賴于測(cè)量單位的長(zhǎng)度。701.分形幾何分形物體的基本特征：1.自相似性

指局部與整體相似的性質(zhì)。一座座山峰和整體山脈，河流中一個(gè)個(gè)支流和整體河川，茂密的樹木上的一條條樹杈和整體樹木等，均具有自相似性。如圖所示的是蕨類植物葉子上的細(xì)葉和整體葉子的相似性。71分形物體的基本特征：2.無(wú)標(biāo)度性

標(biāo)度是計(jì)量單位的刻度。比如長(zhǎng)度的標(biāo)度是米；重量的標(biāo)度是公斤；面積的標(biāo)度是平方米等。對(duì)歐氏幾何學(xué)內(nèi)的不同形體，可以選擇不同的標(biāo)度去度量。例如，直線是多長(zhǎng)，面積是多大，體積是多少。自然界中很多的物體具有特征長(zhǎng)度，如人有高度、山有海拔等等。1.分形幾何721.分形幾何分形的定義。一般認(rèn)為，滿足下列條件的圖形稱為分形集：分形集具有任意尺度下的比例細(xì)節(jié)，或者說(shuō)具有無(wú)窮的精細(xì)結(jié)構(gòu)；分形集是不規(guī)則的，以致于不能用傳統(tǒng)的幾何語(yǔ)言來(lái)描述。分形集通常具有某種自相似性，或許是近似的或許是統(tǒng)計(jì)意義下的自相似。分形集在某種方式下定義的“分?jǐn)?shù)維”一般大于它的拓?fù)渚S數(shù)。分形集的定義常常是非常簡(jiǎn)單的，或許是遞歸的。732.隨機(jī)插值模型1982年由AlainFournier，DonFussell和LorenCarpenter提出：能有效地模擬海岸線和山等自然景象，不是事先決定各種圖素和尺度，而是用一個(gè)隨機(jī)過程的采樣路徑作為構(gòu)造模型的手段。構(gòu)造二維海岸線的模型可以選擇控制大致形狀的若干初始點(diǎn)。再在相鄰兩點(diǎn)構(gòu)成的線段上取其中點(diǎn)。并沿垂直連線方向隨機(jī)偏移一個(gè)距離，再將偏移后的點(diǎn)與該線段兩端點(diǎn)分別連成兩個(gè)新線段。這樣下去可得到一條曲折的有無(wú)窮細(xì)節(jié)回歸的海岸線，其曲折程度由隨機(jī)偏移量控制，它也決定了分?jǐn)?shù)維的大小。742.隨機(jī)插值模型在三維情況下可通過類似過程構(gòu)造山的模型，一般通過多邊形（簡(jiǎn)單的如三角形）細(xì)分的方法?？梢栽谝粋€(gè)三角形的三邊上，隨機(jī)各取一點(diǎn)，沿垂直方向隨機(jī)偏移一段距離得到新的三個(gè)點(diǎn)，再連接成四個(gè)三角形，如此繼續(xù)，即可形成皺褶的山峰。山的褶皺程度由分?jǐn)?shù)維控制。753.迭代函數(shù)系統(tǒng)IteratedFunctionSystem（簡(jiǎn)稱IFS）在SIGGRAPH’85國(guó)際會(huì)議上，Demko，Barnsley等人作過IFS的專題報(bào)告。應(yīng)用自然景物的模擬圖像壓縮

763.迭代函數(shù)系統(tǒng)謝爾賓斯基墊片 生成規(guī)則：取一等邊三角形，連接各邊中點(diǎn)將原三角形分成四個(gè)小三角形，然后舍棄位于中間的一個(gè)小三角形，將剩下的其余三個(gè)小三角形按同樣方法繼續(xù)分割，并舍棄位于中間的那個(gè)三角形，如圖所示。如此不斷地分割與舍棄，就能得到中間有大