計算機圖形學(xué)第十一章三維形體的表示

計算機圖形學(xué)第十一章三維形體的表示第1頁，共48頁，2023年，2月20日，星期二概述

三維造型技術(shù)是一項研究在計算機中，如何建立恰當(dāng)?shù)哪Ｐ蛠肀硎咀匀唤缰行螒B(tài)豐富的三維物體的技術(shù)。

三維造型技術(shù)根據(jù)造型對象分成三類：

第一類是曲面造型，這種造型方法研究在計算機內(nèi)如何描述一張曲面。第二類是立體造型方法，它研究如何在計算機內(nèi)定義、表示一個三維物體。第三類造型方法是自然景物模擬，研究如何在計算機內(nèi)模擬自然景物，如云、水流、樹等等。第2頁，共48頁，2023年，2月20日，星期二概述

三維幾何造型現(xiàn)已開始被廣泛地應(yīng)用在工業(yè)生產(chǎn)及藝術(shù)造型的各個領(lǐng)域。機械行業(yè)設(shè)計方面，幾何造型方法可以逼真地反映物體的外觀，檢查零件之間的裝配關(guān)系，高效、準(zhǔn)確地生成生產(chǎn)圖紙；分析計算方面，它可以精確地計算出零件的質(zhì)量、質(zhì)心、轉(zhuǎn)動慣量、表面積等物性參數(shù)；計算機輔助制造時，可以引用幾何造型的結(jié)果，直接規(guī)劃數(shù)控加工的刀具軌跡；運動分析方面，幾何造型系統(tǒng)可以完成機械手的動作規(guī)劃、運動模擬以及零件間的干涉檢查等。第3頁，共48頁，2023年，2月20日，星期二概述計算機藝術(shù)、動畫片制作、模擬仿真、計算機視覺、機器人等領(lǐng)域都把幾何造型作為基礎(chǔ)。利用三維幾何造型技術(shù)，既可產(chǎn)生已有物體的真實模型，也可產(chǎn)生人們頭腦中的某種設(shè)計想象或藝術(shù)模型。

第4頁，共48頁，2023年，2月20日，星期二形體的表示

在計算機中表示形體的方法通常有三種：線框模型表面模型實體模型

第5頁，共48頁，2023年，2月20日，星期二線框模型

線框模型采用三維形體的全部頂點及邊的集合來描述三維形體，即用三維形體的頂點表和邊表兩個表的數(shù)據(jù)結(jié)構(gòu)來表示三維模型。

第6頁，共48頁，2023年，2月20日，星期二線框模型

線框模型的主要優(yōu)點是結(jié)構(gòu)簡單，處理容易，在CPU時間及存儲方面開銷低。線框模型也有非常顯著的缺點。不能表示表面含有曲面的物體；不能明確地定義給定點與物體之間的關(guān)系，應(yīng)用范圍受到了很大的限制線框模型容易出現(xiàn)二義性，對于一個線框模型，可以有不同的理解。第7頁，共48頁，2023年，2月20日，星期二表面模型

表面模型在線框模型的基礎(chǔ)上，增加了物體中的面的信息，用面的集合來表示物體，而用環(huán)來定義面的邊界.

第8頁，共48頁，2023年，2月20日，星期二表面模型表面模型克服了線框模型的很多缺點，比較完整地定義了三維立體的表面，因而其造型體的覆蓋面較廣，無論解析的或非解析的目標(biāo)均可用表面模型來描述。表面模型又分為平面模型和曲面模型兩種。前者以多邊形網(wǎng)格為基礎(chǔ)。由上述頂點表、邊表和面表就可構(gòu)成平面立體的平面模型。后者是以參數(shù)曲面塊為基礎(chǔ)。表面模型也存在一些不足，這主要是它只能表示物體的表面邊界，而沒有表達出真實體屬性。因此，也就無法切開表示物體的內(nèi)部結(jié)構(gòu)。由此就很難確認一個表面模型表示的三維圖形是一個實體還是一個空殼。

第9頁，共48頁，2023年，2月20日，星期二實體模型

實體模型使用有向邊的右手法則來確定所在面的外法線方向，即用右手沿邊的順序方向握住，大拇指所指的方向為該面的外法線方向。數(shù)據(jù)結(jié)構(gòu)不僅記錄了全部的幾何信息，而且還記錄了所有的點、線、面、體的拓撲信息。這就是實體模型與線框模型或表面模型的根本區(qū)別。實體模型的構(gòu)造方法通常使用體素，經(jīng)集合論中的交、并、差運算構(gòu)成復(fù)雜形體。

第10頁，共48頁，2023年，2月20日，星期二實體的定義

實體就是有效的物體，亦即客觀世界中確實存在的物體。比如，下圖所示的帶有懸掛面的立方體就不是實體，在客觀世界中也不存在這樣的物體。第11頁，共48頁，2023年，2月20日，星期二實體的定義

作為實體或者有效的物體應(yīng)該滿足以下的條件：①剛性。一個實體必須具有一定的形狀（流體不屬于實體造型技術(shù)描述的對象）。②維數(shù)一致性。在三維空間中，一個實體的各個部分必須都是三維的，不能存在懸掛的、孤立的邊界。③有限性。一個實體必須占有有限的空間。④邊界的確定性。根據(jù)實體的邊界可以確定實體的內(nèi)、外部。⑤封閉性。經(jīng)過一系列的剛體運動及任意序列的集合運算之后，仍然是有效的實體。

第12頁，共48頁，2023年，2月20日，星期二實體的定義

一個實體的表面必須具備以下的性質(zhì)：①連通性。實體表面上任意兩點都可用該表面上的一條路徑連接起來。②有界性。一個實體的表面把空間分為互不連通的兩部分，其中實體內(nèi)的部分是有限的。③非自相交性。一個實體的表面不可自相交。④可定向性。一個實體的表面兩側(cè)可明確定義出實體的內(nèi)側(cè)和外側(cè)。⑤封閉性。對多面體而言，一個實體表面的封閉性是由表面上多邊形網(wǎng)格各元素的拓撲關(guān)系確定的，即每條邊連接且僅連接兩個面，每條邊有且僅有兩個端點。第13頁，共48頁，2023年，2月20日，星期二實體的定義

從點集拓撲角度給出實體的定義。將三維物體看作是空間中點的集合，它由內(nèi)點與邊界點共同組成。內(nèi)點是指點集中的這樣一些點，它們具有完全包含于該點集的充分小的鄰域。邊界點就是指那些不具備此性質(zhì)的點集中的點。三維物體A可表示為：

bA為物體A的邊界點集，iA為物體A的內(nèi)部點集。第14頁，共48頁，2023年，2月20日，星期二實體的定義定義點集的正則運算r如下：

i為取內(nèi)點運算；c為取閉包運算；A為一個點集。那么i·A即為A的全體內(nèi)點組成的集合，稱為A的內(nèi)部，它是一個開集。c·i·A為A的內(nèi)部的閉包，是i·A與其邊界點的并集，它本身是一個閉集。

第15頁，共48頁，2023年，2月20日，星期二實體的定義

正則點集不一定是實體。如下圖所示的物體，它是正則點集，但它不是有效的物體。為了得到有效的物體，我們必須排除下圖所示的情況，在此我們引入二維流形的概念。所謂二維流形是指對于實體表面上的任何一點，都可以找到一個圍繞著它的任意小的鄰域，該鄰域在拓撲上與平面上的一個圓盤是等價的。

第16頁，共48頁，2023年，2月20日，星期二實體的定義

有了二維流形的概念之后，我們可以這樣來描述實體：對于一個占據(jù)有限空間的正則點集，如果其表面是二維流形，則該正則點集為實體(有效物體)。第17頁，共48頁，2023年，2月20日，星期二正則集合運算

能產(chǎn)生正則幾何體的集合運算稱為正則集合運算。正則集合運算保證集合運算的結(jié)果仍是一個正則形體，即丟棄懸邊、懸面。正則集合運算與傳統(tǒng)集合運算的區(qū)別主要是在對產(chǎn)生結(jié)果的邊界面的處理上，其內(nèi)部點是一致的。第18頁，共48頁，2023年，2月20日，星期二正則集合運算

在正則集合運算中，要考慮如何消除或不產(chǎn)生懸點，懸邊和懸面，在實體造型中，實現(xiàn)正則集合運算有兩種方法：間接法和直接法。間接法是先按普通集合運算求出結(jié)果，后用一些規(guī)則判斷，消除不符合正則幾何定義的部分(即懸邊、懸面等)，從而得到正則幾何體；直接法則是定義正則集合算子的表達式，用以直接得出符合正則幾何體定義的結(jié)果。

第19頁，共48頁，2023年，2月20日，星期二物體的CSG樹表示

物體的體素構(gòu)造表示法（CSG，ConstructiveSolidGeometry）是用兩個物體間的并、交、差正則集合運算操作生成一個新的物體的方法。用CSG法時，實體的構(gòu)造過程是集合運算的過程。這個過程可用二叉樹結(jié)構(gòu)表示，這種樹稱為CSG樹。

樹的葉節(jié)點表示體素或帶有幾何變換參數(shù)的體素，非終止節(jié)點表示施加于其子節(jié)點的正則集合算子，或稱布爾算子。樹的根節(jié)點表示集合運算的最終結(jié)果，也即希望得到的實體。

第20頁，共48頁，2023年，2月20日，星期二物體的CSG樹表示CSG樹節(jié)點數(shù)據(jù)結(jié)構(gòu)的一種組織方式

第21頁，共48頁，2023年，2月20日，星期二物體的CSG樹表示CSG樹中的每一節(jié)點由操作碼、坐標(biāo)變換域、基本體素指針、左子樹、右子樹等5個域組成。操作碼按約定方式取值。當(dāng)操作碼為零時，表示該節(jié)點為一基本體素，相應(yīng)左、右子樹指針取零。對于非終節(jié)點，操作碼取約定的整數(shù)，表示左子樹節(jié)點和左子樹節(jié)點間進行集合運算。裝配操作是將兩個體素并列在一起，成為一個整體，而每個體素本身仍保持原狀。節(jié)點的坐標(biāo)變換域存儲該節(jié)點所表示物體在進行新的集合運算前所作的坐標(biāo)變換信息。

第22頁，共48頁，2023年，2月20日，星期二物體的CSG樹表示CSG樹是無二義性的，但不是唯一的，它的定義域取決于其所用體素以及所允許的幾何變換和正則集合運算算子。

第23頁，共48頁，2023年，2月20日，星期二物體的CSG樹表示CSG樹表示具有以下優(yōu)點：①

數(shù)據(jù)結(jié)構(gòu)比較簡單，數(shù)據(jù)量比較小，內(nèi)部數(shù)據(jù)的管理比較容易。②

CSG表示可方便地轉(zhuǎn)換成邊界（Brep）表示。③

CSG方法表示的形體的形狀，比較容易修改。但CSG樹表示也如下的缺點：①

對形體的表示受體素的種類和對體素操作的種類的限制，也就是說，CSG方法表示形體的覆蓋域有較大的局限性。②

對形體的局部操作不易實現(xiàn)，例如，不能對基本體素的交線倒圓角。③

由于形體的邊界幾何元素（點、邊、面）是隱含地表示在CSG中，故顯示與繪制CSG表示的形體需要較長的時間。

第24頁，共48頁，2023年，2月20日，星期二邊界表示法

物體的邊界表示

邊界表示法（Brep-BoundaryRepresentation）通過描述物體的邊界來表示一個物體。所謂的邊界指的就是物體內(nèi)部點與外部點的分界面，因此，定義了物體的邊界，該物體也就被唯一地定義了。

第25頁，共48頁，2023年，2月20日，星期二邊界表示法邊界表示法的一個很重要的特點是：描述物體的信息包括幾何信息與拓樸信息兩個方面幾何信息是指物體在歐氏空間中的位置、形狀和大小；拓撲信息是指拓撲元素(頂點、邊和表面)的數(shù)量及其相互間的連接關(guān)系；拓撲信息構(gòu)成物體的“骨架”，而幾何信息則猶如附著在這一“骨架”上的“肌肉”。

第26頁，共48頁，2023年，2月20日，星期二邊界表示法

邊界表示的數(shù)據(jù)結(jié)構(gòu)

翼邊數(shù)據(jù)結(jié)構(gòu)：以邊及其相關(guān)的環(huán)和棱邊來組織數(shù)據(jù)結(jié)構(gòu)。半邊數(shù)據(jù)結(jié)構(gòu)：是對翼邊數(shù)據(jù)結(jié)構(gòu)的改進，多面體的邊界表示在拓撲上分為5個層次，即體（Solid）←→面（Face）←→環(huán)（Loop）←→半邊（HalfEdge）←頂點（Vertex）。第27頁，共48頁，2023年，2月20日，星期二半邊數(shù)據(jù)結(jié)構(gòu)

第28頁，共48頁，2023年，2月20日，星期二邊界表示法歐拉公式：對于任意的簡單多面體，其面（f）、邊（e）、頂點（v）的數(shù)目滿足：

在對形體的結(jié)構(gòu)進行修改時，必須保證這個公式成立，才能夠保證形體的有效性。

第29頁，共48頁，2023年，2月20日，星期二邊界表示法廣義歐拉公式：對于任意的正則形體，引入形體的其他幾個參數(shù)：形體所有面上的內(nèi)孔總數(shù)（r）、穿透形體的孔洞數(shù)（h）和形體非連通部分總數(shù)（s），則形體滿足公式：

第30頁，共48頁，2023年，2月20日，星期二歐拉操作歐拉公式給出了形體的點、邊、面、體、孔、洞數(shù)目之間的關(guān)系，在對形體的結(jié)構(gòu)進行修改時，必須保證這個公式成立，才能夠保證形體的有效性。由此而構(gòu)造出一套操作，來完成對形體部分幾何元素的修改，修改過程中保證各幾何元素的數(shù)目保持這個關(guān)系式不變，這一套操作就是歐拉操作。

第31頁，共48頁，2023年，2月20日，星期二掃描表示

掃描（Sweep）表示是基于一個基體（一般是一個封閉的平面輪廓）沿某一路徑運動而產(chǎn)生形體。掃描表示需要兩個分量：被運動的基體；基體運動的路徑；如果是變截面的掃描，還要給出截面的變化規(guī)律。

第32頁，共48頁，2023年，2月20日，星期二掃描表示

有3種掃描方式：平移Sweep旋轉(zhuǎn)Sweep廣義Sweep

第33頁，共48頁，2023年，2月20日，星期二平移Sweep

將物體A沿著軌跡P平移得到物體B，稱B為sweep體平移sweep----將一個二維區(qū)域沿著一個矢量方向推移。第34頁，共48頁，2023年，2月20日，星期二旋轉(zhuǎn)Sweep

將一個二維區(qū)域繞旋轉(zhuǎn)軸旋轉(zhuǎn)一周。第35頁，共48頁，2023年，2月20日，星期二廣義Sweep

廣義sweep任意物體沿著任意軌跡推移；推移過程中物體可以變形。第36頁，共48頁，2023年，2月20日，星期二八叉樹法

三維物體的八叉樹表示是一種層次數(shù)據(jù)結(jié)構(gòu)，它首先在三維空間中定義一個能夠包含所表示物體的立方體，且立方體的3條棱邊分別與x、y、z軸平行，邊長為2n。若立方體內(nèi)空間完全由所表示的物體所占據(jù)，則物體可用這個立方體予以表示，否則將立方體等分為8個小塊，每塊仍為一個子立方體，其邊長為原立方體邊長的1/2。將這8個子立方體依次編號為0，1，2，…，7，并對每一個子立方體重復(fù)上述分割過程。若子立方體的體內(nèi)空間全部被所表示的物體占據(jù)，則為“滿”；若它與所表示物體無交，則為“空”；該子立方體可停止分解，否則就繼續(xù)分割下去，直至子立方體的邊長為單位長。依此方式，物體在計算機內(nèi)可表示為一棵八叉樹。由上述可以看出，八叉樹表示形式是一種近似方法。

第37頁，共48頁，2023年，2月20日，星期二八叉樹法

八叉樹表示法優(yōu)點主要是：①形體表示的數(shù)據(jù)結(jié)構(gòu)簡單。②簡化了形體的集合運算。③簡化了隱藏線（或面）的消除。④分析算法適合于并行處理。八叉樹表示的缺點也是明顯的，主要是占用的存儲多，只能近似表示形體，以及不易獲取形體的邊界信息等。

第38頁，共48頁，2023年，2月20日，星期二分型幾何方法—自然景物的模擬

分形指的是數(shù)學(xué)上的一類幾何形體，在任意尺度上都具有復(fù)雜并且精細的結(jié)構(gòu)。一般來說分形幾何體都是自相似的，即圖形的每一個局部都可以被看作是整體圖形的一個縮小的復(fù)本。第39頁，共48頁，2023年，2月20日，星期二分形造型的常用模型

隨機插值模型粒子系統(tǒng)模型正規(guī)文法模型迭代函數(shù)系統(tǒng)模型

第40頁，共48頁，2023年，2月20日，星期二隨機插值模型模型不是事先決定各種圖素和尺度，而是用一個隨機過程的采樣路徑作為構(gòu)造模型的手段。構(gòu)造二維海岸線的模型可以選擇控制大致形狀的若干初始點在相鄰兩點構(gòu)成的線段上取其中點，并沿垂直連線方向隨機偏移一個距離，再將偏移后的點與該線段兩端點分別連成兩個線段。這樣下去可得到一條曲折的有無窮細節(jié)回歸的海岸線。第41頁，共48頁，2023年，2月20日，星期二粒子系統(tǒng)模型它是用大量的粒子圖元來描述景物的。粒子可以隨時間推移發(fā)生位置和形態(tài)的變化。每個粒子的位置、取向及動力學(xué)性質(zhì)都是由一