計算機圖形學 第六章

1、第六章 三維形體的表示,本 章 重 點,理解并掌握常用的幾種實體的表示方法，包括它們的基本原理、特點、數(shù)據(jù)結(jié)構(gòu)等。難點：實體表示方法的算法實現(xiàn)。,6.1 常用的幾何模型 計算機圖形處理之前，首先要做的是將物體或場景模型化，也就是通過分析研究，將三維形體模型化，形成定量的描述；再將這些描述的信息以數(shù)字化的形式送入計算機，經(jīng)過計算機處理后顯示出相應(yīng)的圖形。 物體或場景的模型化通常是采用幾何模型的形式來表示。常用

2、的幾何模型有以下三種：,1.線模型 線模型表示的是物體的棱邊，它全部是由點、直線或曲線組成。 對于僅用陰影棱線就能表示形狀的物體，可以采用線模型。該模型的主要特點是結(jié)構(gòu)簡單，模型生成和處理容易，占用的內(nèi)存容量較小，因此成本較低。 但線模型由于僅用棱邊來代表物體的形狀，它只包含了三維物體的一部分形狀信息，在信息的完整性方面是不足的。因此難以進行隱藏線消除，也不能描繪剖面圖，也不可能根據(jù)它計算物體的其它物理量(例如

3、體積、重量等)。,,,,,,,,,,,,,,,,,,,,,,,,,2.表面模型　 把線模型中棱線包圍的部分定義為面，所形成的模型就是表面模型。 采用表面模型，物體的邊界確實可以全部定義，但是物體的實心部分在邊界的哪一側(cè)是不明確的，因為它只定義了單個的表面塊，而且由于它們沒有被結(jié)合在一起，所以邊界面不能明確地定義其所包圍的實心部分，使設(shè)計者對物體缺乏整體的概念。,3. 實體模型 實體模型是從設(shè)計到生產(chǎn)過程中能夠連貫使用

4、的比較理想的模型，它與上述表面模型不同之處在于它確定了是表面的哪一側(cè)存在實體這個問題。 利用實體模型不僅能表示模型的顏色，而且還能進行陰影處理，并可對主要的特征如重量、力矩等進行定量的計算。,6.2 實體的表示方法一 .構(gòu)造實體幾何表示法 (Constructive Solid Geometry) 該方法簡稱 CSG 方法。 1. 基本原理 任何三維形體都可由一些基本體素通過集合運算的方法來構(gòu)造。

5、 常用的基本體素有：長方體、圓柱體、圓錐體、圓臺體、環(huán)、球等。 采用的集合運算是：并、交、差。 在構(gòu)造實體幾何表示法中，集合運算的實現(xiàn)過程可以用一棵二叉樹（稱為CSG樹）來描述。,在構(gòu)造實體的幾何表示法中，體素也可以用半空間的集合運算組成。一個無邊界的面可將三維空間分割成兩個無邊界的區(qū)域，每一個區(qū)域均稱為半空間。 若空間平面方程為： f ( x , y , z ) = 0 記為 f

6、i 則可定義半空間為：{ P f ( x , y , z ) ≤ 0} 或 { P f ( x , y , z ) ≥ 0} 任一個凸多面體 F 都可表示為一組( n個 )半空間的交： n

7、 F = ∩ f i i=1而任一個復雜形體都可表示為多個( m個 )凸多面體的并： m F = ∪ Fj

8、 j=1,,,,3. CSG 表示法的數(shù)據(jù)結(jié)構(gòu),,,,,,,,,OP — code (操作碼),transform (坐標變換),primitive (基本體素),left-subtree (左子樹),Right-subtree (右子樹),OP — code 0 基本體素

9、 1 求并 2 求差 3 求交,CSG 表示法只定義了物體的構(gòu)造方法— —隱式模型。,二. 邊界表示法 ( Boundary Representation ) 1 . 基本原理 邊界表示法是通過描述物體的邊界來表示一個實體。 實體的邊界面可以是平面多邊形或曲面，通常情況下，曲面最終都是被近似地離散成多邊形來處理的

10、。,,,,,,,,,,,,,,,,,,,,,,v1,v2,v3,v4,v5,e1,e2,e3,f1,四棱錐面節(jié)點 f1 f2 f3 …... 邊節(jié)點 e1 e2 e3 e4 …...頂點節(jié)點 v1 v2 v3 …… (x1,y1,z1) (…) (…),,,,,,,,

11、,,,,,,,,拓撲信息,幾何信息,,,2. 多面體及歐拉( Euler )公式 組成平面多面體的基本元素是：頂點、棱邊和面。 一個實體的表面必須滿足閉合性，即構(gòu)成實體的基本元素之間必須滿足一定的條件，其簡單的檢驗方法就是歐拉公式。 設(shè)簡單平面多面體的頂點數(shù)、棱邊數(shù)和面數(shù)分別用V 、 E 、 F來表示，則: V － E + F = 2,,,,,,,,,,V = 8 E = 12

12、 F = 6,對于非簡單多面體則應(yīng)滿足廣義歐拉公式： V － E + F － H = 2( C － G )其中 V 、E 、F 的含義與前相同； H 表示多面體表面上孔的個數(shù)； C 表示獨立的不相連接的多面體的個數(shù)； G 表示貫穿多面體的孔的個數(shù)。,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,V = 24 H = 3E = 36

13、 C = 1F = 15 G = 124 －36 + 15 －3 = 2( 1－1 ),3. 邊界表示法的數(shù)據(jù)結(jié)構(gòu) 拓撲信息是邊界表示法中用于表示實體邊界的主要信息之一。 實體的面、邊、點之間的拓撲關(guān)系有以下 9 種類型：,,,,,,,v,,v,,v,,v,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,v,,E,,v,,

14、v,,v,,v,,v,F,,v,,E,,E,,E,,E,,E,,E,,E,,E,,E,,E,,E,,E,F,,v,F,F,F,,E,F,F,F,F,F,F,F,v→{v},v →{E},v →{F},E →{v},E →{E},E →{F},F →{v},F →{E},F →{F},翼邊結(jié)構(gòu)： 邊界表示法中常用的一種數(shù)據(jù)結(jié)構(gòu)叫翼邊結(jié)構(gòu)，它是以邊為中心來組織數(shù)據(jù)的。,,,,,,,,,,,,v1,v2,E,FL,FR,ERcw,E

15、Rcc,ELcw,ELcc,,,,,,,v1,v2,FL,FR,Ercc Ercw Elcc ELcw,邊界表示法將拓撲信息與幾何信息分開表示，其優(yōu)點是：① 便于查詢物體中的各元素（點、邊、面等）。② 容易支持對物體的各種局部操作（如倒角）。③ 對具有相同拓撲結(jié)構(gòu)，而大小尺寸不同的一類物體，可用統(tǒng) 一的數(shù)據(jù)結(jié)構(gòu)來表示。④ 便于在數(shù)據(jù)結(jié)構(gòu)上附加各種非幾何信息（如光潔度、硬度 等）。,,,,,,,,,,,

16、,,倒角操作,三.掃描表示法 (Sweep) 1.基本原理 空間的點、線、面沿著某一路徑掃描時，所形成的軌跡可用來定義一個一維的、二維的或三維的物體。 在三維形體表示中，主要采用平移掃描法和旋轉(zhuǎn)掃描法。 2.平移掃描法： 將一個二維的面沿著一個指定的方向平行移動，其軌跡便形成了一個三維形體。,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,3.旋轉(zhuǎn)掃描法：將一個二維的面繞一條母線（旋轉(zhuǎn)軸

17、）旋轉(zhuǎn)，其軌跡便形成了一個三維形體。,,,,,,,,,,,,,,,,,,,,,,,4.廣義掃描法：若在平移掃描的過程中可改變截面的大小和形狀，甚至改變移動的方向，便可形成復雜的三維形體。,,,,,,,,,,,四. 八叉樹表示法 1. 基本原理 將所要表示的三維形體占據(jù)的空間分割成大小不同的立方體網(wǎng)格，并用這樣一個立方體序列來描述實體。 2. 表示方法,,,,,,,,,,,,,,,,,,x,y,z,,,,,,,,,,

18、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,F,F,F,F,P,E,E,E,,,,,,,,,F,E,F,E,F,P,E,E,,,,,,,,,E,E,E,E,F,F,E,E,P,,,,,,,,,,,,,,,,,,,,,,,,,F (FULL) 充滿 E (EMPTY) 無關(guān) P (PARTIAL) 相交,

19、,,,,,3.數(shù)據(jù)結(jié)構(gòu),,,,,,,,,,,1 2 3 4 5 6 7 8 9 10,其中：1——節(jié)點標志域 2——指向父節(jié)點的指針。若為根節(jié)點時，該域為0。 3～10——指向八個子節(jié)點的指針。若為終端節(jié)點時， 這些域的狀態(tài)為空。 八叉樹表示的特點： ① 定義形式簡單。 ② 易于實現(xiàn)物體間的集合

20、運算(并、交、差)。 ③ 可簡化消隱算法，便于計算物體的體積、質(zhì)量等。 ④ 存儲量大。,改進：線性八叉樹，前例可表示為 ： {1，2，3，4，51，53，55，565，566}，,,,,,,,,,,,,,P,P,F,F,F,F,F,F,F,F,F,,,,,,,,,,,,五. 分形表示法 歐氏幾何的主要描述工具是：直線、平滑的曲線、平面、邊界整齊的平滑曲面。這些工具在描述一些抽象

21、圖形或人造物體的形態(tài)時是非常有力的，但對一些復雜的自然景象形態(tài)就顯得無能為力了。 為了解決復雜圖形的生成，分數(shù)維(Fractal)造型技術(shù)應(yīng)運而生。,從Koch的雪花圖形 Mandelbrot的海岸線問題,,,,,,,,,,,,,,,,,,,,,,,設(shè)N為每一步細分的數(shù)目 S為細分時的放大或縮小倍數(shù)則分數(shù)維定義為：

22、log N log（1/S）,,D =,雪花邊線的分數(shù)維： N=4 ；S=1/3 log 4 log 3,,D =,= 1.2619,分數(shù)維的計算已有大量試驗性的研究成果： 例如 海岸線 1 < D < 1.3

23、 山地表面 2.1< D < 2.9 河流水系 1.1 < D < 1.85 云 D ≈ 1.35

24、 人肺 D ≈ 2.17 血管 D ≈ 2.3 人腦表面 2.73 < D < 2.79,分數(shù)維造型的常用模型有：隨機插值模型——模擬海岸線和山等自然景象；粒子系統(tǒng)模型——模擬動態(tài)變化的火焰、煙等；正規(guī)文

25、法模型——模擬植物（樹）的生長；迭代函數(shù)系統(tǒng)模型——模擬云彩等景物。,Koch 曲線,( 1 ) Koch 曲線的生成規(guī)則迭代初始把原線段去掉中間的三分之一，代之以底邊在被去線段上的等邊三角形的兩腰；以后每一步的迭代都是這樣的重復。,Koch曲線（其它分形集也是如此）可以由簡單的圖形（生成元），迭代產(chǎn)生。在這里，Koch曲線的生成元是：生成元表示：約定記號，用一個字符串符號表示。設(shè)： F　從當前點開始，向前移動一距離

26、d L　向左（逆時針）轉(zhuǎn)一定角? R　向右（順時針）轉(zhuǎn)一定角?則Koch曲線的生成元可表示為： T＝ F L F R R F L F 　（ ?＝60º）,曲線由把每一折線段反復迭代成縮小比例的三分之一的生成元而成。即字符串T＝ F L F R R F L F 中的每一個F 又是字符串 T 本身。 每次迭代后，生成的曲線長是原來曲線長的三分之四倍。 可見，無數(shù)次迭代后，Koch 曲線將變

27、得具有無限長度。并且，Koch 曲線是永遠不自相交的。,（2）生成Koch 曲線的程序 函數(shù) side：用于繪制Koch 曲線的生成元， xa, ya, xb, yb ：線段的起點和終點坐標； a ：線段的方向角； n ：迭代次數(shù)（遞歸深度）。,void side ( float xa, ya, xb, yb, a, int n ){ float x1, y1, x2, y2, x3, y3,

28、dl, a1, a2 ; int xs, ys, xe, ye ; if (n==0) { xs=(int)(xa+0.5) ; ys=(int)(ya+0.5) ; xe=(int)(xb+0.5) ; ye=(int)(yb+0.5) ; moveto(xs,480-ys) ; lineto(xe,480-ye); }

29、 else,{ 　 dl=sqrt((xb-xa)*(xb-xa)+(yb-ya)*(yb-ya)) / 3. ; x1=xa+(xb-xa) / 3. ; y1=ya+(yb-ya) / 3. ; side(xa, ya, x1, y1, a, n-1) ; a1=a+AF ; x2=x1+dl*cos(a1) ; y2=y1+

30、dl*sin(a1) ; side(x1, y1, x2, y2, a1, n-1) ; a2=a1-2.*AF ; x3=x2+dl*cos(a2) ; y3=y2+dl*sin(a2) ; side(x2, y2, x3, y3, a2, n-1) ; side(x3, y3, xb, yb, a, n-1) ; 　

31、　 }// end of else　 }// end of side,本 章 小 結(jié)1。三維形體（被描述的對象）在計算機中的表示是用計算機繪 制三維形體的前提，實際上就是采用某種表示方法及其相應(yīng) 的數(shù)據(jù)結(jié)構(gòu)來描述三維形體。2。實體模型能夠比較完整地描述三維形體，因此是最常用的一 類幾何模型。3。構(gòu)造實體幾何表示法（CSG）、邊界表示法、八叉樹表示法、 掃描表示法(Sweep)等都是實體模型的具體