CG教案幾何建模課件

2023/7/251第7章幾何建模

客觀世界中的物體都是三維的，真實(shí)地描述和顯示客觀世界中的三維物體是計算機(jī)圖形學(xué)研究的主要內(nèi)容。人造物體：是規(guī)則的，基于歐氏幾何的幾何模型能夠較好地描述物體的幾何信息和拓?fù)湫畔ⅰＷ匀粚ο螅簶淠?、花草、河流、山川、火焰、云霧等，采用傳統(tǒng)的幾何模型很難描述，基于分形幾何的建模方法目前只能定性描述自然對象，精確描述自然對象的建模方法尚處于發(fā)展之中，本章重點(diǎn)介紹成熟的規(guī)則幾何建模方法。

2023/7/2527.1概述幾何模型描述物體的幾何信息和拓?fù)湫畔?。幾何信息是指物體在歐氏空間中的形狀、位置和大??；拓?fù)湫畔⑹侵肝矬w各分量的數(shù)目及其相互間的連接關(guān)系。表示形體的模型分類：以一個過程和相應(yīng)的控制參數(shù)描述，以一個數(shù)據(jù)文件和一段代碼的形式存在。包括——粒子系統(tǒng)、L系統(tǒng)、迭代函數(shù)系統(tǒng)、FBM等。例如：用一些控制參數(shù)和一個生成規(guī)則描述的植物。完全以數(shù)據(jù)描述、以數(shù)據(jù)文件的形式存在。如以8個頂點(diǎn)表示的立方體；以中心點(diǎn)和半徑表示的球等。2023/7/253

線框模型是早期模型。將形體表示成一組輪廓線的集合，用頂點(diǎn)和棱邊來描述物體。表示簡單，所占的存貯空間較少，處理速度快。但沒有包含全部的信息，與形體之間不存在一一對應(yīng)關(guān)系，是真實(shí)物體的高度抽象，定義的物體存在多義性，不適合真實(shí)感顯示。不能計算面積、體積等物理量；線框模型不能處理物體的側(cè)影輪廓線，也不能生成剖切圖、消隱圖、明暗色彩圖等，其應(yīng)用范圍很有限。2023/7/254“空殼”在面模型上打孔，內(nèi)部為“空洞”

面模型面模型是將形體表示成一組表面的集合。形體與其表面一一對應(yīng)，比線框模型立體感強(qiáng)，適合于真實(shí)感顯示。能夠計算面積，表達(dá)物體的表面形狀。進(jìn)行剖切操作時，內(nèi)部為空洞。2023/7/255主要用于CAD/CAM，可以理解為“實(shí)心”的。包含了描述一個實(shí)體所需的較多信息，如幾何信息、拓?fù)湫畔⒌取Ｄ軌蛴嬎泱w積、面積、重量等基本物理量；動量、轉(zhuǎn)動慣量；可以賦予材料特性；模擬物理的運(yùn)動，受力變形等。

體模型2023/7/256實(shí)體造型技術(shù)造型技術(shù)：是研究如何在計算機(jī)中建立恰當(dāng)?shù)哪Ｐ蛠肀硎菊鎸?shí)世界中千姿百態(tài)的物體的技術(shù)。實(shí)體造型技術(shù)(solidmodeling)：著重研究如何在計算機(jī)中定義、表示一個三維的物體。關(guān)注表示實(shí)體的信息的完備性和可操作性。常用的表示三維實(shí)體模型的方法：空間單元表示法（空間分割表示法）：以一組簡單物體通過“粘合”來構(gòu)造新的物體。體素構(gòu)造表示法（構(gòu)造實(shí)體幾何表示法）：將實(shí)體表示成基本體素的組合，所不同的是，這里可以采用更多的運(yùn)算，如并、交、差等。邊界表示法：通過描述構(gòu)成實(shí)體邊界的點(diǎn)、邊、面而達(dá)到表示實(shí)體的目的。2023/7/257實(shí)體的定義數(shù)學(xué)中的點(diǎn)、線、面是其所代表的真實(shí)世界中對象的一種抽象，它們之間存在著一定的差距。抽象帶來的問題計算機(jī)中表示的物體是無效的不能夠客觀存在而CAD/CAM卻要求物體客觀存在！稱為有效物體或?qū)嶓w什么是客觀存在（有效）—實(shí)體的定義具有一定的形狀具有確定的封閉的邊界（表面)內(nèi)部連通（否則，可將其看作多個物體）占據(jù)有限的空間，即體積有限經(jīng)過運(yùn)算后，仍然是有效的物體2023/7/258內(nèi)點(diǎn)邊界點(diǎn)正則運(yùn)算r下面從點(diǎn)集拓?fù)涞慕嵌冉o出實(shí)體的定義。將三維物體看做一個點(diǎn)集，它由內(nèi)點(diǎn)與邊界點(diǎn)共同組成。取內(nèi)點(diǎn)運(yùn)算i取閉包運(yùn)算c

正則運(yùn)算的作用是去除與物體維數(shù)不一致的懸掛部分或孤立部分，如三維物體的懸掛面、線，二維物體的懸掛線等。2023/7/259正則點(diǎn)集的定義：

r·A

稱為A的正則點(diǎn)集。稱A為正則點(diǎn)集，如果它滿足r·A=A。問題：正則點(diǎn)集是實(shí)體？是正則點(diǎn)集，但不是有效物體。不是內(nèi)部連通的！2023/7/2510二維流形是指這樣一些面，其上任意一點(diǎn)都存在充分小的鄰域，該鄰域與平面上的圓盤同構(gòu)，即在該鄰域與圓盤之間存在連續(xù)的一一映射。對于任何一個客觀存在的物體，如立方體，其表面上任一點(diǎn)都存在與圓盤同構(gòu)的鄰域，從而是流形。

實(shí)體的定義：占據(jù)有限空間的正則點(diǎn)集；表面是二維流形。（該條件在計算機(jī)中是可計算、可檢測的）2023/7/2511正則集合運(yùn)算為什么需要正則集合運(yùn)算用簡單實(shí)體（集合）運(yùn)算構(gòu)造復(fù)雜實(shí)體是一個有效的構(gòu)造實(shí)體的方法；普通的集合運(yùn)算會產(chǎn)生無效物體。2023/7/2512正則集合運(yùn)算的定義正則并正則交正則差2023/7/25137.2體素構(gòu)造表示法基本體素體素是可以用有限個尺寸參數(shù)定位和定形的體，常用3種形式定義：從實(shí)際形體中選擇出來，可用一些確定的尺寸參數(shù)控制最終位置和形狀的一組單元。如長方體、圓柱體、圓環(huán)體、球體等。有參數(shù)定義的一條（或一組）截面輪廓線沿一條（或一組）空間參數(shù)曲線做掃描運(yùn)動而產(chǎn)生的形體。用代數(shù)半空間定義的形體。在此半空間中點(diǎn)集可定義為：{(x,y,z)|f(x,y,z)≤0}，此處的f應(yīng)該是不可約多項式，多項式系數(shù)可以是形狀參數(shù)。半空間定義法只適用于正則形體。2023/7/2514并交體素間的交、并、差運(yùn)算差體素：球和柱球－柱柱－球2023/7/2515CSG樹只定義了它所表示物體的構(gòu)造方式，既不反映物體的面、邊、頂點(diǎn)等有關(guān)邊界信息，也不顯式說明三維點(diǎn)集與所表示的物體在實(shí)際空間的一一對應(yīng)關(guān)系。因此，這種表示又被稱為物體的隱式模型或過程模型。

物體的

CSG樹一個復(fù)雜物體可由一些比較簡單、規(guī)則的物體經(jīng)過布爾運(yùn)算而得到。因而，這個復(fù)雜的物體可描述為一棵樹。這棵樹的終端結(jié)點(diǎn)為基本體素(如立方體、圓柱、圓錐)，而中間結(jié)點(diǎn)為正則集合運(yùn)算結(jié)點(diǎn)。這棵樹叫做CSG樹，如圖所示。

U－CSG樹2023/7/25167.3邊界表示法（B－rep）三維物體可以通過描述它的邊界來表示。2023/7/2517邊界表示（B-Reps:BoundaryRepresentation）：通過描述實(shí)體的邊界來表示一個實(shí)體的方法。物體的邊界與物體一一對應(yīng)，確定了物體的邊界也就確定了物體本身。實(shí)體的邊界面可以是平面多邊形或曲面片。一、多面體及歐拉公式什么是多面體？表面由曲面或平面構(gòu)成的三維體。平面多面體表面由平面多邊形組成。其表面上的每條邊被偶數(shù)個多邊形共享。為了排除非實(shí)體的多面體，要求多面體表面具有二維流形性質(zhì)，即要求多面體上的每條邊只嚴(yán)格屬于兩個多邊形。2023/7/2518簡單多面體指與球拓?fù)渫瑯?gòu)的多面體，即它可以連續(xù)變換成一個球。簡單多面體滿足歐拉公式:歐拉公式只是必要條件，不是充分條件。2023/7/2519廣義歐拉公式：必要不充分條件r為多面體表面上孔的個數(shù)，h為貫穿多面體的孔洞個數(shù)，s為相互分離的多面體數(shù)。2023/7/2520邊界表示的優(yōu)缺點(diǎn)優(yōu)點(diǎn)精確表示物體表示能力強(qiáng)幾何變換容易適于顯示處理缺點(diǎn)表示復(fù)雜有效性難以保證集合運(yùn)算復(fù)雜2023/7/2521三、邊界表示的數(shù)據(jù)結(jié)構(gòu)一個好的數(shù)據(jù)結(jié)構(gòu)必須同時正確完整地表示出邊界的幾何信息和拓?fù)湫畔?。幾何信息指的是頂點(diǎn)、邊、面的位置、大小、形狀等幾何數(shù)據(jù)。拓?fù)湫畔⒅傅氖琼旤c(diǎn)、邊、面之間的連接關(guān)系。多面體的頂點(diǎn)、邊、面之間的拓?fù)潢P(guān)系可用9種不同的形式：2023/7/2522圖8-8頂點(diǎn)、棱邊、表面之間的拓?fù)潢P(guān)系

數(shù)據(jù)結(jié)構(gòu)中保存的拓?fù)潢P(guān)系越多，對多面體的操作越方便，但是占用的存儲空間也就越大。在表示法種究竟采用哪種拓?fù)潢P(guān)系或哪幾種關(guān)系的組合取決于邊界表示所支持的運(yùn)算，以及存儲空間的限制。因此要根據(jù)實(shí)際情況選擇拓?fù)潢P(guān)系，以提高系統(tǒng)的整體效率。2023/7/2523

翼邊數(shù)據(jù)結(jié)構(gòu)

邊界表示法中最為典型的數(shù)據(jù)結(jié)構(gòu)是翼邊結(jié)構(gòu)。翼邊結(jié)構(gòu)是美國斯坦福大學(xué)的B.G.Baugart等人于1972年提出來的，它是一個多面體表達(dá)模式。在表面、棱邊、頂點(diǎn)組成的形體三要素中，翼邊結(jié)構(gòu)以邊為核心來組織數(shù)據(jù)，如圖8-9所示。

圖8-9翼邊結(jié)構(gòu)

2023/7/2524圖8-10半邊結(jié)構(gòu)邊界表示的另一種比較典型的數(shù)據(jù)結(jié)構(gòu)是半邊數(shù)據(jù)結(jié)構(gòu)。它是作為一種多面體的表示方法在20世界80年代提出來的。在構(gòu)成多面體的三要素(頂點(diǎn)、邊、體)中，半邊數(shù)據(jù)結(jié)構(gòu)以邊為核心，將一條邊表示成拓?fù)湟饬x上的方向相反的兩條“半邊”，所以稱為半邊數(shù)據(jù)結(jié)構(gòu)。2023/7/2525圖8-11半邊數(shù)據(jù)結(jié)構(gòu)的層次關(guān)系半邊數(shù)據(jù)結(jié)構(gòu)在拓?fù)渖戏譃槲鍌€層次，即體—面—環(huán)—半邊—頂點(diǎn)。2023/7/2526掃描法（sweeping，也稱推移表示）其基本思想非常簡單：“運(yùn)動的物體”加上“軌跡”。常用的掃描方式有：平移式、旋轉(zhuǎn)式和廣義式。平移掃描法：沿垂直于二維集合進(jìn)行掃描；旋轉(zhuǎn)掃描法：繞某一軸線旋轉(zhuǎn)某一角度；廣義掃描法：二維幾何集合沿一條空間曲線的集合掃描；

平移掃描法廣義掃描法旋轉(zhuǎn)掃描法7.4其他表示方法2023/7/2527sweep表示的特點(diǎn)優(yōu)點(diǎn)表示簡單、直觀適合做圖形輸入手段缺點(diǎn)作幾何變換困難對正則集合運(yùn)算不封閉如圖a、b所示：(a)兩個簡單的平移sweep體(b)兩者之間的正則并不是平移sweep體2023/7/2528

立方體網(wǎng)格模型

該方法容易實(shí)現(xiàn)實(shí)體的集合運(yùn)算以及體積計算等。但是這種方法不是一種精確的表示法，其近似程度完全取決于分割的精度，與幾何體的復(fù)雜程度無關(guān)。另外更重要的是要存儲全部的有關(guān)信息需要大量的存儲空間。

又稱為空間位置枚舉表示。這種模型將包含實(shí)體的空間分割成均勻的小立方體，建立一個三維數(shù)組，使數(shù)組中的每一個元素與(i,j,k)的小立方體相對應(yīng)。當(dāng)該立方體被物體所占據(jù)時，其值為1，否則為0。2023/7/2529八叉樹表示對立方體網(wǎng)格模型的空間分割方法作了改進(jìn)： 均勻分割→自適應(yīng)分割。八叉樹建立過程八叉樹的根節(jié)點(diǎn)對應(yīng)整個物體空間如果它完全被物體占據(jù)，將該節(jié)點(diǎn)標(biāo)記為F(Full)，算法結(jié)束；如果它內(nèi)部沒有物體，將該節(jié)點(diǎn)標(biāo)記為E(Empty)，算法結(jié)束；如果它被物體部分占據(jù)，將該節(jié)點(diǎn)標(biāo)記為P(Partial)，并將它分割成8個子立方體，對每一個子立方體進(jìn)行同樣的處理。2023/7/2530八叉樹表示中，節(jié)點(diǎn)的編碼：230167452023/7/2531實(shí)體的八叉樹表示：（設(shè)陰影部分為實(shí)體）2023/7/2532優(yōu)點(diǎn)可以表示任何物體容易實(shí)現(xiàn)實(shí)體間的正則集合運(yùn)算容易計算物體的整體性質(zhì)，如質(zhì)量、體積等容易實(shí)現(xiàn)隱藏線與隱藏面的消除較空間位置枚舉表示占用的存貯空間少缺點(diǎn)沒有邊界信息，不適于圖形顯示對物體進(jìn)行幾何變換困難是物體的非精確表示2023/7/2533便于做有限元分析、數(shù)據(jù)場可視化

四面體網(wǎng)格模型是將包含實(shí)體的空間分割成四面體單元的集合，與六面體網(wǎng)格模型相比，四面體網(wǎng)格模型可以以邊界面片為四面體的一個面，模型精度高，能夠構(gòu)建復(fù)雜形體的網(wǎng)格模型，在復(fù)雜對象的科學(xué)計算和工程分析中具有重要的應(yīng)用。但四面體網(wǎng)格模型數(shù)據(jù)結(jié)構(gòu)復(fù)雜，實(shí)現(xiàn)復(fù)雜空間域邊界一致的四面體剖分是近年來的研究熱點(diǎn)。

四面體網(wǎng)格模型2023/7/2534幾何建模方法的應(yīng)用與發(fā)展不同的幾何建模方法可以滿足不同的應(yīng)用需求，對計算機(jī)軟硬件的要求也不同。早期計算機(jī)軟硬件性能有限，只能采用線框模型表達(dá)不太復(fù)雜的對象。隨著計算機(jī)軟硬件的快速發(fā)展，計算機(jī)的運(yùn)算速度、內(nèi)存容量以及圖形運(yùn)算的軟硬件加速，為復(fù)雜對象的計算機(jī)表達(dá)創(chuàng)造了條件，即使如此，目前計算機(jī)軟硬件條件要實(shí)現(xiàn)三維實(shí)體的真實(shí)感實(shí)時動態(tài)顯示仍有一定的困難，應(yīng)用過程中要根據(jù)實(shí)際需求采用合適的幾何模型，如復(fù)雜物體動態(tài)真實(shí)感顯示有困難，可在旋轉(zhuǎn)、平移或縮放過程中顯示線框模型，選定參數(shù)后可用靜態(tài)的真實(shí)感圖片表示設(shè)計結(jié)果。目前常用的CAD軟件一般都包含線框模型、面模型、體模型，根據(jù)需要，可靈活使用。基于體元的體繪制方法是計算機(jī)圖形學(xué)最新的發(fā)展分支，在CT、核磁共振等規(guī)則數(shù)據(jù)的處理中獲得了應(yīng)用。體繪制的方法簡化了物體的建模過程，豐富了傳統(tǒng)計算機(jī)圖形學(xué)的研究內(nèi)容，未來會在更多的領(lǐng)域獲得應(yīng)用。2023/7/2535不規(guī)則形體的建模方法迭代函數(shù)系統(tǒng)基于文法的模型粒子系統(tǒng)動力系統(tǒng)2023/7/2536L系統(tǒng)（1/6）L系統(tǒng)：由美國生物學(xué)家Lindenmayer創(chuàng)立，基本思想是：用文法表示植物的拓?fù)浣Y(jié)構(gòu)；通過圖形學(xué)方法生成逼真的畫面。D0L系統(tǒng)“D”代表“確定的”（Determined），“0”代表簡單的意思。D0L系統(tǒng)指確定的上下文無關(guān)的L系統(tǒng)。我們以Fibonacci的兔子模型為例說明。

a代表成年兔，b代表未成年兔。a、b構(gòu)成字母表，由a、b組成的字符串稱為單詞，b->a表示用字母a來代替b，成為改寫規(guī)則（重寫法則）。假設(shè)初始單詞為b，改寫規(guī)則為b->a、a->ab，可得序列：b，a，ab，aba，abaab，abaababa，abaababaabaab……這樣迭代得到的字符串可用來表示生長過程。2023/7/2537規(guī)定對任何字母a∈V，至少存在一個非空單詞x，使得a->x。若對給定的前驅(qū)a∈V無明顯的產(chǎn)生式，則規(guī)定a->a。對每個a∈V，當(dāng)且僅當(dāng)恰有一個非空單詞x使a->x，則0L系統(tǒng)是確定的，稱為D0L系統(tǒng)。令：V----表示字母集合；V*----表示V上所有單詞的集合；ω----是一個非空單詞，稱為公理；

P----產(chǎn)生式（生成規(guī)則）的有限集合；產(chǎn)生式寫作a->x，字母a和單詞x分別稱為產(chǎn)生式的前驅(qū)和后繼。一個字符串0L系統(tǒng)就是一個有序的三元組<V，ω，P>。L系統(tǒng)（2/6）2023/7/2538L系統(tǒng)（3/6）例子——Koch雪花曲線V：{F,+,-}ω：FP：F->F+F--F+Fn=1：Fn=2：F+F--F+Fn=3：F+F--F+F+F+F--F+F--F+F--F+F+F+F--F+Fn=4：幾何解釋F：向前畫一條線+：左轉(zhuǎn)δ=600-：右轉(zhuǎn)δ=600

2023/7/2539L系統(tǒng)（4/6）

解釋重寫以后的字符串，要借助LoGo-StyleTurtle表示法，它最早是由Szilard和Quiuton提出的。Turtle表示法 設(shè)v是一個字符串，(x0,y0,α0)是龜?shù)某跏紶顟B(tài)，d是前進(jìn)增量，δ是角增量參數(shù)，通過龜對字符串v的解釋所畫出的圖稱為v的turtle表示。龜按以下命令動作：F：向前移動一步，步長為d。龜?shù)漠?dāng)前狀態(tài)為(x,y,α)，新位置為(x',y',α)，其中x'=x+d·cosα，y'=y+d·sinα

從(x,y)向(x',y')畫一直線段；E：向前移動一步，步長為d，不畫；+：向左旋轉(zhuǎn)δ角，則龜?shù)南乱粻顟B(tài)為(x,yα+δ)。規(guī)定逆時針方向?yàn)檎蚪?，順時針方向?yàn)樨?fù)向角。-：向右旋轉(zhuǎn)δ角，則龜?shù)南乱粻顟B(tài)為(x,yα-δ)。2023/7/2540BracketedL系統(tǒng)（帶括號的D0L系統(tǒng)）增加如下兩個字符[：壓棧]：出棧例子——

植物w：FP：F->F[+F]F[-F]FL系統(tǒng)（5/6）2023/7/2541L系統(tǒng)（6/6）分形分類類型自相似分形：組成部分是整個物體的收縮形式自仿射分形：組成部分為不同坐標(biāo)方向上的不同縮放因子形成。不變分形集：由非線性變換形成。自平方分形自逆分形：由自逆過程形成。Self-similarFractal自相似分形

自相似分形的組成部分是整個物體的收縮形式。從初始形狀開始，對整個物體應(yīng)用縮放參數(shù)s來構(gòu)造物體的子部件。TypesDeterministicself-similar確定自相似分形Statisticallyself-similar統(tǒng)計自相似分形用于模擬樹木、灌木和其他植物(彩頁12)

分形分類Self-affineFractal自仿射分形

自仿射分形的組成部分由不同坐標(biāo)方向上的不同縮放參數(shù)sx、sy、sz形成TypesDeterministicself-affinefractals確定自仿射分形Statisticallyself-affinefractals統(tǒng)計自仿射分形用于模擬巖層、水和云等自然景物(彩頁13)

分形分類InvariantFractalSets不變分形集由非線性變換形成Typesself-squaringfractals自平方分形self-inversefractals自逆分形彩頁14

分形分類Mandelbro