三維幾何造型

三維幾何造型1第1頁，課件共84頁，創(chuàng)作于2023年2月第6講幾何造型6.1概述6.2基礎(chǔ)知識6.3常用的形體表示模型6.4三維形體的多邊形表示6.5過程模型6.6常見實體造型系統(tǒng)簡介2第2頁，課件共84頁，創(chuàng)作于2023年2月6.1概述客觀世界中的物體都是三維的，真實地描述和顯示客觀世界中的三維物體是計算機圖形學(xué)研究的重要內(nèi)容。一個物體的計算機描述叫做模型，它能被計算機所懂得，并在一定的條件下（變換和投影）被轉(zhuǎn)換成相應(yīng)的圖形在屏幕顯示或在繪圖機上輸出；圖形是模型的一個具體可見像，是人們所看到的模型的表征。不能把兩者混為一談。在三維空間，描述的是幾何形體和幾何曲面，只有在平面上，它才是人們通常所稱的圖形。3第3頁，課件共84頁，創(chuàng)作于2023年2月6.1概述計算機幾何造型就是用計算機系統(tǒng)來表示、控制、分析和輸出三維形體(描述物體的幾何信息和拓撲信息)。所以幾何造型是計算機圖形學(xué)中一個十分重要的研究領(lǐng)域。幾何造型系統(tǒng)的主要功能：形體輸入，即把形體從用戶格式轉(zhuǎn)換成計算機內(nèi)部格式；形體數(shù)據(jù)的存儲和管理；形體控制，如對形體進行平移、縮放、旋轉(zhuǎn)等幾何變換；形體修改，如應(yīng)用集合運算、歐拉運算、有理B樣條等操作實現(xiàn)對形體局部或整體修改；形體分析，如形體的容差分析，物質(zhì)特性分析等；形體顯示輸出，如消隱、光照、顏色的控制等；詢問形體的屬性及其有關(guān)參數(shù)。4第4頁，課件共84頁，創(chuàng)作于2023年2月6.1概述表示形體的兩種模型:數(shù)據(jù)模型：規(guī)則形體的建模方法；用歐式幾何描述。過程模型：不規(guī)則形體的建模方法；用分形幾何描述。形體表示數(shù)據(jù)模型過程模型線框模型表面模型實體模型5第5頁，課件共84頁，創(chuàng)作于2023年2月6.1概述數(shù)據(jù)模型完全以數(shù)據(jù)描述。通常是歐式幾何所能描述的規(guī)則物體。例如：以頂點表示的立方體、以球心和半徑表示的球。按發(fā)展時間：線框模型、表面模型、實體模型；以數(shù)據(jù)文件的形式存在。(靜態(tài))本章主要介紹實體模型。6第6頁，課件共84頁，創(chuàng)作于2023年2月6.1概述過程模型以一個過程和相應(yīng)的控制參數(shù)描述。通常描述不規(guī)則的自然景物。(基于分形幾何)例如：用一些控制參數(shù)和一個生成規(guī)則描述的植物。以一個數(shù)據(jù)文件和一段代碼的形式存在；（動態(tài)）包括：隨機插值模型、迭代函數(shù)系統(tǒng)、L系統(tǒng)、粒子系統(tǒng)、動力系統(tǒng)等。7第7頁，課件共84頁，創(chuàng)作于2023年2月第6講幾何造型6.1概述6.2基礎(chǔ)知識6.3常用的形體表示模型6.4過程模型6.5三維形體的多邊形表示6.6常見實體造型系統(tǒng)簡介8第8頁，課件共84頁，創(chuàng)作于2023年2月6.2基礎(chǔ)知識1.形體2.形體表示方法3.正則集合運算4.歐拉運算9第9頁，課件共84頁，創(chuàng)作于2023年2月1.形體在計算機中，形體一般定義為六層拓撲結(jié)構(gòu)，首先介紹在三維空間中基本術(shù)語的定義。形體(object)外殼(shell)面(face)環(huán)(loop)邊(edge)頂點(vertex)曲線或直線方程點的幾何坐標10第10頁，課件共84頁，創(chuàng)作于2023年2月1.形體體 由封閉表面圍成的有效空間稱為體；一個體Q是R3空間中非空、有界的封閉子集。其邊界（記為?Q）是有限個面的并集，而外殼是形體的最大邊界。一個單位立方體可定義為： {(x,y,z)∈R3|0≤x≤1,0≤y≤1,0≤z≤1}

其中一個表面可表示為：

{(1,y,z)∈R3|0≤y≤1,0≤z≤1}必須注意：并沒有規(guī)定形體必須是一個連續(xù)的封閉集合，目的是用這樣的定義來擴大幾何造型的域，使得形體可以由不連續(xù)的體素，或是僅有某些相交的形體組成。xzy11第11頁，課件共84頁，創(chuàng)作于2023年2月1.形體面

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

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

fi，fJ∈

?Q，使得邊e∈fi∩fj；形體Q的邊框線WF(Q)是由有序?qū)?V(Q),E(Q))所組成。v1v2ef1f214第14頁，課件共84頁，創(chuàng)作于2023年2月1.形體頂點 邊的端點稱為頂點，頂點不能出現(xiàn)在邊的內(nèi)部，也不能孤立地位于物體內(nèi)、物體外或面內(nèi)，頂點又是?F中兩條不共線的線段的交點。假設(shè)Q是一個形體，V(Q)是所有頂點P的集合，Pf是含面f的唯一平面，則存在3個面f1,f2,f3∈?Q，一點P∈V(Q)，使得|P|=f1∩f2∩f3=Pf1∩Pf2∩Pf3。v1v2ef1f215第15頁，課件共84頁，創(chuàng)作于2023年2月1.形體幾何信息 用來表示形體的幾何性質(zhì)和度量關(guān)系稱為幾何信息。拓撲信息 用來表示形體之間的連接關(guān)系稱為拓撲信息。16第16頁，課件共84頁，創(chuàng)作于2023年2月6.2基礎(chǔ)知識1.形體2.形體表示方法3.正則集合運算4.歐拉運算17第17頁，課件共84頁，創(chuàng)作于2023年2月2.形體表示方法形體常用的3種表示方法：

線框模型、表面模型和實體模型:線框模型早期模型。用頂點和棱邊來描述物體。一般地，畫出了形體的棱線(邊)與輪廓線就能唯一地表示出來。如上圖，八個頂點可以定義一個長方體，但還不足以識別它，如果定義了棱線，則無論如何放置長方體都能唯一地表示了。e12v4v8e2e4e6e8e2e7e11e10e9e3e1v2v3v1v7v5v618第18頁，課件共84頁，創(chuàng)作于2023年2月V1V2V3V4V5V6V7V8E8E10E1E2E3E4E5E6E7E9E11E12abcXZY下圖和表說明了線框模型在計算機內(nèi)存儲的數(shù)據(jù)結(jié)構(gòu)原理。組成長方體的頂點和邊

頂點表V1V2V3V4V5V6V7V8x坐標aaaa0000y坐標0bb00bb0z坐標00cc00cc長方體的頂點表

19第19頁，課件共84頁，創(chuàng)作于2023年2月邊號E1E2E3E4E5E6E7E8E9E10E11E12起點號V1V2V3V4V5V6V7V8V1V2V3V4終點號V2V3V4V1V6V7V8V5V5V6V7V8長方體的邊表

V1V2V3V4V5V6V7V8E8E10E1E2E3E4E5E6E7E9E11E12abcXZY組成長方體的頂點和邊

20第20頁，課件共84頁，創(chuàng)作于2023年2月2.形體表示方法線框模型

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

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

向相反，則表明表面一側(cè)存在實體。P27第27頁，課件共84頁，創(chuàng)作于2023年2月6.2基礎(chǔ)知識1.形體2.形體表示方法3.歐拉運算28第28頁，課件共84頁，創(chuàng)作于2023年2月6.2基礎(chǔ)知識1.形體2.形體表示方法3.歐拉運算29第29頁，課件共84頁，創(chuàng)作于2023年2月4.歐拉運算歐拉公式：

V-E+F=2 （V為頂點數(shù)，E為棱線數(shù)，F(xiàn)為面數(shù)）凡是滿足歐拉公式的形體均稱為歐拉形體。歐拉公式是必要條件。V=4,E=6,F=4 v2v1v3v4v4v1v5v8v6v3v2v7V=8,E=12,F=6V=10,E=15,F=730第30頁，課件共84頁，創(chuàng)作于2023年2月4.歐拉運算擴展的歐拉公式：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

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

H=2,B=1,P=1

(圓柱孔上取四點）31第31頁，課件共84頁，創(chuàng)作于2023年2月第6講幾何造型6.1概述6.2基礎(chǔ)知識6.3常用的形體表示模型6.4三維形體的多邊形表示6.5過程模型6.6常見實體造型系統(tǒng)簡介32第32頁，課件共84頁，創(chuàng)作于2023年2月6.3常用的形體表示模型1.模型的考慮2.掃描變換(Sweep)表示模型3.構(gòu)造實體幾何(CSG)表示模型4.邊界表示(B-Rep)模型5.空間分割模型33第33頁，課件共84頁，創(chuàng)作于2023年2月1.模型的考慮必須考慮以下一些問題：根據(jù)形體邊界給定的信息，是否能自動的獲取形體的幾何特征？如何確定對形體操作數(shù)據(jù)的有效性？形體的表示模型是否唯一？不同的表示模型是否可以轉(zhuǎn)換？是否最佳表示模型？34第34頁，課件共84頁，創(chuàng)作于2023年2月1.模型的考慮在實體模型的表示中，基本上可以分為分解表示、構(gòu)造表示和邊界表示三大類。目前常用的形體表示模型有：掃描變換表示模型(Sweep)構(gòu)造實體幾何表示模型(CSG:ConstructiveSolidGeometry)邊界表示模型(B-rep：BoundaryRepresentations)空間分割模型對于幾何造型系統(tǒng)來說，按照不同的目的可以采用不同的最佳表示模型。后面將介紹四種模型。35第35頁，課件共84頁，創(chuàng)作于2023年2月6.3常用的形體表示模型1.模型的考慮2.掃描變換(Sweep)表示模型3.構(gòu)造實體幾何(CSG)表示模型4.邊界表示(B-Rep)模型5.空間分割模型36第36頁，課件共84頁，創(chuàng)作于2023年2月2.Sweep表示模型掃描變換表示模型的基本思想非常簡單：“物體”+“運動的軌跡”。掃描變換表示模型是基于一個基體

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

<CSG樹>::=<體素葉子> |<CSG樹><正則集合運算><CSG樹> |<CSG樹><幾何變換><變換參數(shù)>48第48頁，課件共84頁，創(chuàng)作于2023年2月3.CSG表示模型例如：體素π1、π2和平移變換Δx作為3個葉節(jié)點，π1-π2和π2(Δx)的操作結(jié)果作為兩個中間節(jié)點(非葉節(jié)點)，最終的形體(π1-π2)-π2(Δx)作為根節(jié)點。49第49頁，課件共84頁，創(chuàng)作于2023年2月3.CSG表示模型構(gòu)造實體幾何表示模型的幾何造型系統(tǒng)一般由兩部分組成：一部分是描述通過集合運算和幾何變換操作連接體素所生成子形體的CSG樹的數(shù)據(jù)結(jié)構(gòu)；另一部分是描述相應(yīng)體素的大小、形狀、位置和方向等幾何參數(shù)。通過以上給定的構(gòu)造實體幾何表示模型可以計算出其形體的邊界表示。其計算過程如下：對單個形體，計算其表面在何處被截斷，哪些邊或頂點被產(chǎn)生或刪除？對兩個相交形體，計算由于其相交而產(chǎn)生的新邊：計算兩相交形體的相交線段；按幾何元素分類，確定相交線段的哪一部分真正屬于新形體的邊（有效邊）。50第50頁，課件共84頁，創(chuàng)作于2023年2月3.CSG表示模型CSG表示的優(yōu)點：數(shù)據(jù)結(jié)構(gòu)比較簡單，數(shù)據(jù)量比較小，內(nèi)部數(shù)據(jù)的管理比較容易；CSG表示可方便地轉(zhuǎn)換成邊界（B-Rep）表示；CSG方法表示的形體的形狀，比較容易修改。CSG表示的缺點：是一種體表示方法，顯示/繪制時需進行轉(zhuǎn)換；對形體的表示受體素的種類和對體素操作的種類的限制，也就是說，CSG方法表示形體的覆蓋域有較大的局限性。對形體的局部操作不易實現(xiàn)。例如：彎曲表面，對交線倒圓角；所以在使用CSG表示模型的系統(tǒng)中需要結(jié)合其他表示模型或算法來解決有關(guān)問題。51第51頁，課件共84頁，創(chuàng)作于2023年2月6.3常用的形體表示模型1.模型的考慮2.掃描變換(Sweep)表示模型3.構(gòu)造實體幾何(CSG)表示模型4.邊界表示(B-Rep)模型5.空間分割模型52第52頁，課件共84頁，創(chuàng)作于2023年2月4.邊界表示(B-Rep)模型CSG表示與B-Rep表示曾為兩大主流方法。80’，ACMSolidmodeling、歐洲CSG會議當前B-Rep表示一統(tǒng)天下。在一個幾何造型系統(tǒng)中，往往是多種方法并存，互相補充。53第53頁，課件共84頁，創(chuàng)作于2023年2月4.邊界表示模型邊界表示模型是一種采用幾何和拓撲信息來描述的表示模型。一個形體一般可以通過其邊界拆成一些有界的“面”或“小片”的子集來表示，而每一個面又可以通過其邊界的邊和頂點來表示。若面的表示無二義性，則其邊界表示模型也無二義性，但通常不一定只有唯一的表示。四棱椎邊界表示的例子如右，由4個面組成，且這種表示可以看作是含有體、面、邊、頂點為節(jié)點的有向圖四棱椎邊界表示也可以基于邊界的三角形分解，即把形體的邊界拆成一些互不重疊的三角形。v1v2v3v4v5v2v3v4v5e1e2e3f1v1四棱柱面節(jié)點邊節(jié)點頂點坐標f1f2f3….e1e2e3e4….v1v2v3….(x1,y1,z1) 組合

結(jié)構(gòu) 坐標

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

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

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

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

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

指局部與整體相似的性質(zhì)。一座座山峰和整體山脈，河流中一個個支流和整體河川，茂密的樹木上的一條條樹杈和整體樹木等，均具有自相似性。如圖所示的是蕨類植物葉子上的細葉和整體葉子的相似性。71第71頁，課件共84頁，創(chuàng)作于2023年2月分形物體的基本特征：2.無標度性

標度是計量單位的刻度。比如長度的標度是米；重量的標度是公斤；面積的標度是平方米等。對歐氏幾何學(xué)內(nèi)的不同形體，可以選擇不同的標度去度量。例如，直線是多長，面積是多大，體積是多少。自然界中很多的物體具有特征長度，如人有高度、山有海拔等等。1.分形幾何72第72頁，課件共84頁，創(chuàng)作于2023年2月1.分形幾何分形的定義。一般認為，滿足下列條件的圖形稱為分形集：分形集具有任意尺度下的比例細節(jié)，或者說具有無窮的精細結(jié)構(gòu)；分形集是不規(guī)則的，以致于不能用傳統(tǒng)的幾何語言來描述。分形集通常具有某種自相似性，或許是近似的或許是統(tǒng)計意義下的自相似。分形集在某種方式下定義的“分數(shù)維”一般大于它的拓撲維數(shù)。分形集的定義常常是非常簡單的，或許是遞歸的。73第73頁，課件共84頁，創(chuàng)作于2023年2月2.隨機插值模型1982年由AlainFournier，DonFussell和LorenCarpenter提出：能有效地模擬海岸線和山等自然景象，不是事先決定各種圖素和尺度，而是用一個隨機過程的采樣路徑作為構(gòu)造模型的手段。構(gòu)造二維海岸線的模型可以選擇控制大致形狀的若干初始點。再在相鄰兩點構(gòu)成的線段上取其中點。并沿垂直連線方向隨機偏移一個距離，再將偏移后的點與該線段兩端點分別連成兩個新線段。這樣下去可得到一條曲折的有無窮細節(jié)回歸的海岸線，其曲折程度由隨機偏移量控制，它也決定了分數(shù)維的大小。74第74頁，課件共84頁，創(chuàng)作于2023年2月2.隨機插值模型在三維情況下可通過類似過程構(gòu)造山的模型，一般通過多邊形（簡單的如三角形）細分的方法?？梢栽谝粋€三角形的三邊上，隨機各取一點，沿垂直方向隨機偏移一段距離得到新的三個點，再連接成四個三角形，如此繼續(xù)，即可形成皺褶的山峰。山的褶皺程度由分數(shù)維控制。75第75頁，課件共