1、形體表示模型n在實(shí)體模型的表示中，基本上可以分為分解表示、構(gòu)造表示和邊界表示三大類。n1、分解表示將形體按某種規(guī)則分解為小的更易于描述的部分，每一小部分又可分為更小的部分，這種分解過程直至每一小部分都能夠直接描述為止。分解表示-空間位置枚舉表示n形體空間細(xì)分為小的均勻的立方體單元。n用三維數(shù)組CIJK表示物體，數(shù)組中的元素與單位小立方體一一對(duì)應(yīng)n當(dāng)CIJK = 1時(shí)，表示對(duì)應(yīng)的小立方體被物體占據(jù)n當(dāng)CIJK = 0時(shí)，表示對(duì)應(yīng)的小立方體沒有被物體占據(jù)分解表示-空間位置枚舉表示n優(yōu)點(diǎn)n簡(jiǎn)單，可以表示任何物體n容易實(shí)現(xiàn)物體間的交、并、差集合運(yùn)算n容易計(jì)算物體的整體性質(zhì)，如體積等n缺點(diǎn)n占用大量的存

2、儲(chǔ)空間，如1024*1024*1024 = 1G bitsn物體的邊界面沒有顯式的解析表達(dá)式，不適于圖形顯示n對(duì)物體進(jìn)行幾何變換困難，如非90度的旋轉(zhuǎn)變換n是物體的非精確表示分解表示-八叉樹表示n八叉樹表示n對(duì)空間位置枚舉表示的空間分割方法作了改進(jìn)：均勻分割 自適應(yīng)分割n八叉樹建立過程八叉樹的根節(jié)點(diǎn)對(duì)應(yīng)整個(gè)物體空間八叉樹的根節(jié)點(diǎn)對(duì)應(yīng)整個(gè)物體空間如果它完全被物體占據(jù)，將該節(jié)點(diǎn)標(biāo)記為如果它完全被物體占據(jù)，將該節(jié)點(diǎn)標(biāo)記為F(Full)，算法結(jié)束；算法結(jié)束；如果它內(nèi)部沒有物體，將該節(jié)點(diǎn)標(biāo)記為如果它內(nèi)部沒有物體，將該節(jié)點(diǎn)標(biāo)記為E(Empty)，算法結(jié)束；算法結(jié)束；如果它被物體部分占據(jù)，將該節(jié)點(diǎn)標(biāo)記為如果

3、它被物體部分占據(jù)，將該節(jié)點(diǎn)標(biāo)記為P(Partial)，并將它分割成并將它分割成8個(gè)子立方體，對(duì)每一個(gè)子立方體進(jìn)行個(gè)子立方體，對(duì)每一個(gè)子立方體進(jìn)行同樣的處理同樣的處理分解表示-八叉樹表示n8叉樹的表示應(yīng)用三維形體的分解，它對(duì)一個(gè)外接立方體的形體進(jìn)行前后、左右、上下等部分8個(gè)小立方體，如果小立方體單元為滿或?yàn)榭?，表示該立方體完全在形體中或完全不在形體中，則其停止分解；對(duì)部分形體占有的小立方體需進(jìn)一步分解為8個(gè)子立方體，直至所有小立方體單元要么全部滿，要么全部空，或已分解到規(guī)定的分解精度為止。236720131375具有子孫的節(jié)點(diǎn)具有子孫的節(jié)點(diǎn)( (P)P)空節(jié)點(diǎn)空節(jié)點(diǎn)( (E)E)實(shí)節(jié)點(diǎn)實(shí)節(jié)點(diǎn)(

4、(F)F)分解表示-八叉樹表示n優(yōu)點(diǎn)n可以表示任何物體，且形體表示的數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)單n簡(jiǎn)化了形體的集合運(yùn)算。只需同時(shí)遍歷參加集合運(yùn)算的兩形體相應(yīng)的八叉樹，無需進(jìn)行復(fù)雜的求交運(yùn)算。n簡(jiǎn)化了隱藏線（或面）的消除，因?yàn)樵诎瞬鏄浔硎局?，形體上各元素已按空間位置排成了一定的順序。n分析算法適合于并行處理。n缺點(diǎn)n沒有邊界信息，不適于圖形顯示n對(duì)物體進(jìn)行幾何變換困難n是物體的非精確表示n占用大量存儲(chǔ)。實(shí)際上，八叉樹表示是以存儲(chǔ)空間換取算法的效率分解表示-線性八叉樹表示線性八叉樹：用一可變長(zhǎng)度的一維數(shù)組來存儲(chǔ)一棵八叉樹。數(shù)組中僅存儲(chǔ)八叉樹的性質(zhì)為FULL的終端結(jié)點(diǎn)。并用一個(gè)八進(jìn)制數(shù)表示該結(jié)點(diǎn)在八叉樹中的位置。編

5、碼方式為：Q1Q2Qm,其中Q1表示該結(jié)點(diǎn)所屬的一級(jí)父結(jié)點(diǎn)的編號(hào)（0-7），以此類推。例右圖為：1X,30X,31X,323X,33X236720131375具有子孫的節(jié)點(diǎn)具有子孫的節(jié)點(diǎn)( (P)P)空節(jié)點(diǎn)空節(jié)點(diǎn)( (E)E)實(shí)節(jié)點(diǎn)實(shí)節(jié)點(diǎn)( (F)F)分解表示-單元分解表示n單元分解表示n對(duì)空間位置枚舉表示的空間分割方法作了改進(jìn)：?jiǎn)我惑w素 多種體素n三種空間分割方法的比較n空間位置枚舉表示-同樣大小立方體粘合在一起表示物體n八叉樹表示-不同大小的立方體粘合在一起表示物體n單元分解表示-多種體素粘合在一起表示物體分解表示-單元分解表示n優(yōu)點(diǎn)n表示簡(jiǎn)單n容易實(shí)現(xiàn)幾何變換n基本體素可以按需選擇，表示

6、范圍較廣n可以精確表示物體n缺點(diǎn)n物體的表示不唯一n物體的有效性難以保證構(gòu)造表示n推移表示n構(gòu)造實(shí)體幾何表示（CSG）n特征表示構(gòu)造表示-推移表示n將物體A沿著軌跡P推移得到物體B，稱B為sweep體n平移sweep-將一個(gè)二維區(qū)域沿著一個(gè)矢量方向推移構(gòu)造表示-推移表示n旋轉(zhuǎn)sweep-將一個(gè)二維區(qū)域繞旋轉(zhuǎn)軸旋轉(zhuǎn)一周n 三維形體也能在空間通過掃描變換生成新的形體：如左圖，一個(gè)圓柱體按指定方向在長(zhǎng)方體上運(yùn)動(dòng)生成新的形體，這個(gè)過程猶如長(zhǎng)方體與運(yùn)動(dòng)者的圓柱體不斷的作差運(yùn)算操作。有時(shí)經(jīng)過掃描變換所生成的形體可能會(huì)出現(xiàn)維數(shù)不一致問題。構(gòu)造表示-推移表示掃描線方向掃描線方向U U構(gòu)造表示-推移表示n廣義s

7、weepn任意物體沿著任意軌跡推移n推移過程中物體可以變形構(gòu)造表示-推移表示n優(yōu)點(diǎn)n表示簡(jiǎn)單、直觀n適合做圖形輸入手段n缺點(diǎn)n作幾何變換困難n對(duì)幾何運(yùn)算不封閉n用掃描變換產(chǎn)生的形體可能出現(xiàn)維數(shù)不一致的問題。n掃描方法不能直接獲取形體的邊界信息，表示形體的覆蓋域非常有限。構(gòu)造表示-構(gòu)造實(shí)體幾何表示(CSG).通過對(duì)體素定義運(yùn)算而得到新的形體的一種表示方法。體素可以是立方體、圓柱、圓錐等，也可以是半空間，其運(yùn)算為變換或正則集合運(yùn)算并、交、差。CSG表示可以看成是一棵有序的二叉樹。n其終端節(jié)點(diǎn)或是體素、或是形體變換參數(shù)。n非終端結(jié)點(diǎn)或是正則的集合運(yùn)算，或是變換（平移和/或旋轉(zhuǎn)）操作，這種運(yùn)算或變換只

8、對(duì)其緊接著的子結(jié)點(diǎn)（子形體）起作用。構(gòu)造表示-構(gòu)造實(shí)體幾何表示(CSG)構(gòu)造表示-構(gòu)造實(shí)體幾何表示(CSG)nCSG樹是無二義性的，但不是唯一的.CSG表示的優(yōu)點(diǎn)：n數(shù)據(jù)結(jié)構(gòu)比較簡(jiǎn)單，數(shù)據(jù)量比較小，內(nèi)部數(shù)據(jù)的管理比較容易；n物體的有效性自動(dòng)得到保證；nCSG方法表示的形體的形狀，比較容易修改。構(gòu)造表示-構(gòu)造實(shí)體幾何表示(CSG)CSG表示的缺點(diǎn)：n對(duì)形體的表示受體素的種類和對(duì)體素操作的種類的限制，也就是說，CSG方法表示形體的覆蓋域有較大的局限性。n對(duì)形體的局部操作不易實(shí)現(xiàn)，例如，不能對(duì)基本體素的交線倒圓角；n由于形體的邊界幾何元素（點(diǎn)、邊、面）是隱含地表示在CSG中，故顯示與繪制CSG表示的

9、形體需要較長(zhǎng)的時(shí)間。n表示不唯一 構(gòu)造表示-特征表示n用一組特征參數(shù)表示一組類似的物體n特征包括形狀特征、材料特征等n適用于工業(yè)上標(biāo)準(zhǔn)件的表示構(gòu)造表示的特點(diǎn)n構(gòu)造表示的特點(diǎn)：n構(gòu)造表示通常具有不便于直接獲取形體幾何元素的信息、覆蓋域有限等缺點(diǎn)，n但是，便于用戶輸入形體，在CAD/CAM系統(tǒng)中，通常作為輔助表示方法。邊界表示n邊界表示（BR表示或BRep表示）n按照體面環(huán)邊點(diǎn)的層次，詳細(xì)記錄了構(gòu)成形體的所有幾何元素的幾何信息及其相互連接的拓?fù)潢P(guān)系。n邊界表示的一個(gè)重要特點(diǎn)是在該表示法中，描述形體的信息包括幾何信息（Geometry）和拓?fù)湫畔ⅲ═opology）兩個(gè)方面。n拓?fù)湫畔⒚枋鲂误w上的頂

10、點(diǎn)、邊、面的連接關(guān)系，拓?fù)湫畔⑿纬晌矬w邊界表示的“骨架”。n形體的幾何信息猶如附著在“骨架”上的肌肉。邊界表示n邊界模型表達(dá)形體的基本拓?fù)鋵?shí)體包括：n1. 頂點(diǎn)n2. 邊。邊有方向，它由起始頂點(diǎn)和終止頂點(diǎn)來界定。邊的形狀（Curve）由邊的幾何信息來表示，可以是直線或曲線，曲線邊可用一系列控制點(diǎn)或型值點(diǎn)來描述，也可用顯式、隱式或參數(shù)方程來描述。邊界表示n3. 環(huán)。環(huán)（Loop）是有序、有向邊（Edge）組成的封閉邊界。環(huán)有方向、內(nèi)外之分，外環(huán)邊通常按逆時(shí)針方向排序，內(nèi)環(huán)邊通常按順時(shí)針方向排序。n4.面。面（Face）由一個(gè)外環(huán)和若干個(gè)內(nèi)環(huán)（可以沒有內(nèi)環(huán)）來表示，內(nèi)環(huán)完全在外環(huán)之內(nèi)。n若一個(gè)面的

11、外法矢向外，稱為正向面；反之，稱為反向面。邊界表示n面的形狀可以是平面或曲面。平面可用平面方程來描述，曲面可用控制多邊形或型值點(diǎn)來描述，也可用曲面方程（隱式、顯式或參數(shù)形式）來描述。對(duì)于參數(shù)曲面，通常在其二維參數(shù)域上定義環(huán)，這樣就可由一些二維的有向邊來表示環(huán)，集合運(yùn)算中對(duì)面的分割也可在二維參數(shù)域上進(jìn)行。n5.體。體（Body）是面的并集。邊界表示n邊界表示模型是一種采用描述形體表面的方法來描述的幾何表示模型。一個(gè)形體一般可以通過其邊界拆成一些有界的“面”或“小片”的子集來表示，而每一個(gè)面又可以通過其邊界的邊和頂點(diǎn)來表示。若面的表示無二義性，則其邊界表示模型也無二義性，但通常不一定只有唯一的表示

12、。U圖3.2.10 邊界表示邊界表示的數(shù)據(jù)結(jié)構(gòu)n邊界表示法的數(shù)據(jù)結(jié)構(gòu)有四種方法：以面為基礎(chǔ)、以頂點(diǎn)為基礎(chǔ)、以邊為基礎(chǔ)和翼邊結(jié)構(gòu)；n以面為基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)以面為基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)n以面為基礎(chǔ)，按照體、面、頂點(diǎn)坐標(biāo)的樹結(jié)構(gòu)層次組織元素?cái)?shù)據(jù)；如n面 頂點(diǎn)坐標(biāo)nF1 (X1Y1Z1,X2Y2Z2,X3Y3Z3,X4Y4Z4)nF2 (X1Y1Z1,X2Y2Z2,X6Y6Z6,X5Y5Z5) n.n其中頂點(diǎn)按照外觀順時(shí)針順序；邊界表示的數(shù)據(jù)結(jié)構(gòu)n2 2以頂點(diǎn)為基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)以頂點(diǎn)為基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)n以頂點(diǎn)/坐標(biāo)和面/頂點(diǎn)序列兩張關(guān)系表表示，如：n頂點(diǎn) 坐標(biāo) 面 頂點(diǎn)序列nV1 X1Y1Z1 F1 V1V2V3V

13、4n.n3.3.以邊為基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)以邊為基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)n以邊/頂點(diǎn)，頂點(diǎn)/坐標(biāo)，面/邊三張關(guān)系表表示；邊界表示模型n四棱椎邊界表示的例子如右，由4個(gè)面組成，且這種表示可以看作是含有體、面、邊、頂點(diǎn)為節(jié)點(diǎn)的有向圖n四棱椎邊界表示也可以基于邊界的三角形分解，即把形體的邊界拆成一些互不重疊的三角形。v1v2v3v4v5v2v3v4v5e1e2e3f1v1四棱柱四棱柱面節(jié)點(diǎn)面節(jié)點(diǎn)邊節(jié)點(diǎn)邊節(jié)點(diǎn)頂點(diǎn)坐標(biāo)頂點(diǎn)坐標(biāo)f1f2f3.e1e2e3e4.v1v2v3.(x1,y1,z1)組合組合結(jié)構(gòu)結(jié)構(gòu)坐標(biāo)坐標(biāo)信息信息.6.3 實(shí)體構(gòu)造技術(shù)實(shí)體構(gòu)造技術(shù)n由簡(jiǎn)單的物體來構(gòu)成復(fù)雜的物體由簡(jiǎn)單的物體來構(gòu)成復(fù)雜的物體n掃描

14、表示掃描表示n結(jié)構(gòu)實(shí)體幾何法結(jié)構(gòu)實(shí)體幾何法掃描表示掃描表示n思想：思想： 通過平移、旋轉(zhuǎn)及其他對(duì)稱變換來構(gòu)通過平移、旋轉(zhuǎn)及其他對(duì)稱變換來構(gòu)造三維對(duì)象造三維對(duì)象 通過指定一個(gè)二維形狀以及在空間區(qū)通過指定一個(gè)二維形狀以及在空間區(qū)域內(nèi)移動(dòng)該形狀的掃描來描述該三維域內(nèi)移動(dòng)該形狀的掃描來描述該三維物體物體zoyxAn平移掃描 二維圖形A沿Z軸平移n旋轉(zhuǎn)掃描 二維圖形A繞Z軸旋轉(zhuǎn)zByxA結(jié)構(gòu)實(shí)體幾何法結(jié)構(gòu)實(shí)體幾何法n思想思想 通過對(duì)兩個(gè)指定三維通過對(duì)兩個(gè)指定三維對(duì)象進(jìn)行并、交或差對(duì)象進(jìn)行并、交或差等集合操作產(chǎn)生一個(gè)等集合操作產(chǎn)生一個(gè)新的三維對(duì)象新的三維對(duì)象 結(jié)構(gòu)實(shí)體幾何法結(jié)構(gòu)實(shí)體幾何法物體物體A和和B差

15、差并并交交差差8.5 八叉樹八叉樹n分層樹形結(jié)構(gòu)，稱為八叉樹。分層樹形結(jié)構(gòu)，稱為八叉樹。n思想思想 利用實(shí)體的空間相關(guān)性利用實(shí)體的空間相關(guān)性n優(yōu)點(diǎn)優(yōu)點(diǎn)n減少了三維物體的存儲(chǔ)需求減少了三維物體的存儲(chǔ)需求n提供了存儲(chǔ)有關(guān)物體內(nèi)部信息的方便表示提供了存儲(chǔ)有關(guān)物體內(nèi)部信息的方便表示四叉樹四叉樹二維平面二維平面三維空間三維空間八叉樹八叉樹四四叉樹叉樹n四叉樹四叉樹n數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)n思想思想 n同質(zhì)象限同質(zhì)象限10231023n用于用于二維平面二維平面的分解的分解n對(duì)二維區(qū)域?qū)ΧS區(qū)域遞歸地等分遞歸地等分4個(gè)小正方形，這個(gè)分解過個(gè)小正方形，這個(gè)分解過程可表示為一棵樹，除葉節(jié)點(diǎn)，其每個(gè)節(jié)點(diǎn)都有四程可表示為

16、一棵樹，除葉節(jié)點(diǎn)，其每個(gè)節(jié)點(diǎn)都有四個(gè)分支，分別表示個(gè)分支，分別表示4個(gè)小正方形個(gè)小正方形n若小正方形是同質(zhì)的，則不必再分解；若小正方形是同質(zhì)的，則不必再分解；n若小正方形是非同質(zhì)的，則需將它再一分為四若小正方形是非同質(zhì)的，則需將它再一分為四n分解是遞歸的。分解是遞歸的。四四叉樹叉樹四叉樹四叉樹n例3120312001230132四叉樹四叉樹312456132519241820212223711 12891014151617具有子孫的節(jié)點(diǎn)具有子孫的節(jié)點(diǎn)空節(jié)點(diǎn)空節(jié)點(diǎn)實(shí)節(jié)點(diǎn)實(shí)節(jié)點(diǎn)245139 107811 12314 15 20 21 16 17 22 23 18 19 24 2516n三維形體的分

17、解三維形體的分解n對(duì)三維空間進(jìn)行前后、左右、上下等分為對(duì)三維空間進(jìn)行前后、左右、上下等分為8個(gè)小個(gè)小立方體，立方體，n小立方體單元均質(zhì)，則停止分解；小立方體單元均質(zhì)，則停止分解；n小立方體單元非均質(zhì)，需進(jìn)一步分解為小立方體單元非均質(zhì)，需進(jìn)一步分解為8個(gè)子立個(gè)子立方體方體n直至所有小立方體單元均質(zhì)，或已分解到規(guī)定直至所有小立方體單元均質(zhì)，或已分解到規(guī)定的分解精度為止。的分解精度為止。八叉樹八叉樹八叉樹八叉樹236720131375具有子孫的節(jié)點(diǎn)具有子孫的節(jié)點(diǎn)空節(jié)點(diǎn)空節(jié)點(diǎn)實(shí)節(jié)點(diǎn)實(shí)節(jié)點(diǎn)8.6 分形分形Fractaln歐氏幾何法歐氏幾何法&分形幾何法分形幾何法n分形基本特征分形基本特征n分形生

18、成過程分形生成過程n分形分類分形分類n分形維數(shù)概念分形維數(shù)概念nEuclidean - Geometry Methods - use equations to describe objects which have smooth surfaces and regular shapes.nFractal - Geometry Methods - use procedures to model natural objects which have irregular or fragmented features.歐氏幾何法歐氏幾何法&分形幾何法分形幾何法ninfinite detail a

19、t every point每點(diǎn)具有無限細(xì)節(jié)每點(diǎn)具有無限細(xì)節(jié)nself-similarity between the object parts and the overall features對(duì)象整體和局部之間對(duì)象整體和局部之間的自相似性的自相似性n利用一個(gè)過程來描述分形物體，利用一個(gè)過程來描述分形物體，該過程為產(chǎn)生物體局部細(xì)節(jié)指該過程為產(chǎn)生物體局部細(xì)節(jié)指定了重復(fù)操作定了重復(fù)操作distantCloserCloser yet分形基本特征分形基本特征nIdea 分形圖形的生成過程是重復(fù)使用指定的變換函數(shù)作分形圖形的生成過程是重復(fù)使用指定的變換函數(shù)作用于空間區(qū)域中的點(diǎn)的過程用于空間區(qū)域中的點(diǎn)的過程

20、Initial point P0, transformation function FP1 = F(P0), P2 = F(P1), P3 = F(P2) nExamples (P399)分形生成過程分形生成過程Von koch snowflake樹形生成元及對(duì)應(yīng)曲線樹形生成元及對(duì)應(yīng)曲線樹形生成元及對(duì)應(yīng)曲線樹形生成元及對(duì)應(yīng)曲線分形分類分形分類n類型類型n自相似自相似分形：組成部分是整個(gè)物體的收縮形式分形：組成部分是整個(gè)物體的收縮形式n自仿射自仿射分形：組成部分為不同坐標(biāo)方向上的不分形：組成部分為不同坐標(biāo)方向上的不同縮放因子形成。同縮放因子形成。n不變分形不變分形集：由非線性變換形成。集：由非線

21、性變換形成。n自平方分形自平方分形n自逆分形：由自逆過程形成。自逆分形：由自逆過程形成。nSelf-similar Fractal自相似分形自相似分形 自相似分形的組成部分是整個(gè)物體的收縮形式。從自相似分形的組成部分是整個(gè)物體的收縮形式。從初始形狀開始，對(duì)整個(gè)物體應(yīng)用縮放參數(shù)初始形狀開始，對(duì)整個(gè)物體應(yīng)用縮放參數(shù)s來構(gòu)造來構(gòu)造物體的子部件。物體的子部件。nTypesnDeterministic self-similar 確定自相似分形確定自相似分形nStatistically self-similar 統(tǒng)計(jì)自相似分形統(tǒng)計(jì)自相似分形n用于模擬樹木、灌木和其他植物用于模擬樹木、灌木和其他植物(彩頁(yè)彩頁(yè)12)分形分類分形分類nSelf-affine Fractal 自仿射分形自仿射分形 自仿射分形的組成部分由不同坐標(biāo)方向上的不同縮自仿射分形的組成部分由不同坐標(biāo)方向上的不同縮放參數(shù)放參數(shù)sx、sy、sz形成形成nTypesnDeterministic self-affine fractals確定自仿確定自仿射分形射分形nStatistically self-affine fractals統(tǒng)計(jì)自仿射統(tǒng)計(jì)自仿射分形分形n用于模擬巖層、水和云等自然