計算機圖形學第六

計算機圖形學第六第1頁，共38頁，2023年，2月20日，星期四

本章重點

理解并掌握常用的幾種實體的表示方法，包括它們的基本原理、特點、數(shù)據(jù)結(jié)構(gòu)等。難點：實體表示方法的算法實現(xiàn)。第2頁，共38頁，2023年，2月20日，星期四6.1常用的幾何模型

計算機圖形處理之前，首先要做的是將物體或場景模型化，也就是通過分析研究，將三維形體模型化，形成定量的描述；再將這些描述的信息以數(shù)字化的形式送入計算機，經(jīng)過計算機處理后顯示出相應的圖形。物體或場景的模型化通常是采用幾何模型的形式來表示。常用的幾何模型有以下三種：第3頁，共38頁，2023年，2月20日，星期四1.線模型線模型表示的是物體的棱邊，它全部是由點、直線或曲線組成。對于僅用陰影棱線就能表示形狀的物體，可以采用線模型。該模型的主要特點是結(jié)構(gòu)簡單，模型生成和處理容易，占用的內(nèi)存容量較小，因此成本較低。但線模型由于僅用棱邊來代表物體的形狀，它只包含了三維物體的一部分形狀信息，在信息的完整性方面是不足的。因此難以進行隱藏線消除，也不能描繪剖面圖，也不可能根據(jù)它計算物體的其它物理量(例如體積、重量等)。第4頁，共38頁，2023年，2月20日，星期四第5頁，共38頁，2023年，2月20日，星期四2.表面模型把線模型中棱線包圍的部分定義為面，所形成的模型就是表面模型。采用表面模型，物體的邊界確實可以全部定義，但是物體的實心部分在邊界的哪一側(cè)是不明確的，因為它只定義了單個的表面塊，而且由于它們沒有被結(jié)合在一起，所以邊界面不能明確地定義其所包圍的實心部分，使設計者對物體缺乏整體的概念。第6頁，共38頁，2023年，2月20日，星期四3.實體模型實體模型是從設計到生產(chǎn)過程中能夠連貫使用的比較理想的模型，它與上述表面模型不同之處在于它確定了是表面的哪一側(cè)存在實體這個問題。利用實體模型不僅能表示模型的顏色，而且還能進行陰影處理，并可對主要的特征如重量、力矩等進行定量的計算。第7頁，共38頁，2023年，2月20日，星期四第8頁，共38頁，2023年，2月20日，星期四6.2實體的表示方法一.構(gòu)造實體幾何表示法

(ConstructiveSolidGeometry)

該方法簡稱CSG方法。

1.基本原理任何三維形體都可由一些基本體素通過集合運算的方法來構(gòu)造。常用的基本體素有：長方體、圓柱體、圓錐體、圓臺體、環(huán)、球等。采用的集合運算是：并、交、差。在構(gòu)造實體幾何表示法中，集合運算的實現(xiàn)過程可以用一棵二叉樹（稱為CSG樹）來描述。第9頁，共38頁，2023年，2月20日，星期四U*－*構(gòu)造結(jié)果得到一棵表示物體的二叉樹第10頁，共38頁，2023年，2月20日，星期四2.正則化集合運算采用CSG方法構(gòu)造出來的三維形體應該是一個正則點集，即：具有一定的形狀；具有確定的封閉邊界；占據(jù)有限的空間；不存在懸點、懸線、懸面。

要使得構(gòu)造出來的三維形體是一個正則點集，那么在其構(gòu)造過程中所進行的集合運算即并，交，差運算不能是傳統(tǒng)的集合的并，交，差運算，而應該是一種正則化的幾何運算。∩ABA∩BA∩*B第11頁，共38頁，2023年，2月20日，星期四

在構(gòu)造實體的幾何表示法中，體素也可以用半空間的集合運算組成。一個無邊界的面可將三維空間分割成兩個無邊界的區(qū)域，每一個區(qū)域均稱為半空間。若空間平面方程為：f(x,y,z)=0記為fi

則可定義半空間為：{Pf(x,y,z)≤0}

或

{Pf(x,y,z)≥0}

任一個凸多面體F都可表示為一組(n個)半空間的交：

nF=∩fi

i=1而任一個復雜形體都可表示為多個(m個)凸多面體的并：

mF=∪Fjj=1第12頁，共38頁，2023年，2月20日，星期四3.CSG表示法的數(shù)據(jù)結(jié)構(gòu)OP—code(操作碼)transform(坐標變換)primitive(基本體素)left-subtree(左子樹)Right-subtree(右子樹)OP—code0基本體素

1求并

2求差

3求交CSG表示法只定義了物體的構(gòu)造方法—

—隱式模型。第13頁，共38頁，2023年，2月20日，星期四二.邊界表示法(BoundaryRepresentation)1.基本原理邊界表示法是通過描述物體的邊界來表示一個實體。實體的邊界面可以是平面多邊形或曲面，通常情況下，曲面最終都是被近似地離散成多邊形來處理的。v1v2v3v4v5e1e2e3f1

四棱錐面節(jié)點f1f2f3…...邊節(jié)點e1e2e3e4…...頂點節(jié)點v1v2v3……(x1,y1,z1)(…)(…)拓撲信息幾何信息第14頁，共38頁，2023年，2月20日，星期四2.多面體及歐拉(Euler)公式組成平面多面體的基本元素是：頂點、棱邊和面。一個實體的表面必須滿足閉合性，即構(gòu)成實體的基本元素之間必須滿足一定的條件，其簡單的檢驗方法就是歐拉公式。設簡單平面多面體的頂點數(shù)、棱邊數(shù)和面數(shù)分別用V、E、F來表示，則:V－E+F=2V=8E=12F=6第15頁，共38頁，2023年，2月20日，星期四對于非簡單多面體則應滿足廣義歐拉公式：

V－E+F－H=2(C－G)其中V、E、F的含義與前相同；

H表示多面體表面上孔的個數(shù)；

C表示獨立的不相連接的多面體的個數(shù)；

G表示貫穿多面體的孔的個數(shù)。V=24H=3E=36C=1F=15G=124－36+15－3=2(1－1)第16頁，共38頁，2023年，2月20日，星期四3.邊界表示法的數(shù)據(jù)結(jié)構(gòu)拓撲信息是邊界表示法中用于表示實體邊界的主要信息之一。實體的面、邊、點之間的拓撲關系有以下9種類型：vvvvvEvvvvvFvEEEEEEEEEEEEFvFFFEFFFFFFFv→{v}v→{E}v→{F}E→{v}E→{E}E→{F}F→{v}F→{E}F→{F}第17頁，共38頁，2023年，2月20日，星期四翼邊結(jié)構(gòu)：邊界表示法中常用的一種數(shù)據(jù)結(jié)構(gòu)叫翼邊結(jié)構(gòu)，它是以邊為中心來組織數(shù)據(jù)的。v1v2EFLFRERcwERccELcwELccv1v2FLFRErccErcwElccELcw第18頁，共38頁，2023年，2月20日，星期四

邊界表示法將拓撲信息與幾何信息分開表示，其優(yōu)點是：①便于查詢物體中的各元素（點、邊、面等）。②容易支持對物體的各種局部操作（如倒角）。③對具有相同拓撲結(jié)構(gòu)，而大小尺寸不同的一類物體，可用統(tǒng)一的數(shù)據(jù)結(jié)構(gòu)來表示。④便于在數(shù)據(jù)結(jié)構(gòu)上附加各種非幾何信息（如光潔度、硬度等）。倒角操作第19頁，共38頁，2023年，2月20日，星期四三.掃描表示法(Sweep)1.基本原理空間的點、線、面沿著某一路徑掃描時，所形成的軌跡可用來定義一個一維的、二維的或三維的物體。在三維形體表示中，主要采用平移掃描法和旋轉(zhuǎn)掃描法。

2.平移掃描法：將一個二維的面沿著一個指定的方向平行移動，其軌跡便形成了一個三維形體。第20頁，共38頁，2023年，2月20日，星期四

3.旋轉(zhuǎn)掃描法：將一個二維的面繞一條母線（旋轉(zhuǎn)軸）旋轉(zhuǎn)，其軌跡便形成了一個三維形體。

4.廣義掃描法：若在平移掃描的過程中可改變截面的大小和形狀，甚至改變移動的方向，便可形成復雜的三維形體。第21頁，共38頁，2023年，2月20日，星期四第22頁，共38頁，2023年，2月20日，星期四四.八叉樹表示法

1.基本原理將所要表示的三維形體占據(jù)的空間分割成大小不同的立方體網(wǎng)格，并用這樣一個立方體序列來描述實體。

2.表示方法xyzFFFFPEEEFEFEFPEEEEEEFFEEP

F(FULL)充滿

E(EMPTY)無關

P(PARTIAL)相交第23頁，共38頁，2023年，2月20日，星期四3.數(shù)據(jù)結(jié)構(gòu)12345678910其中：1——節(jié)點標志域

2——指向父節(jié)點的指針。若為根節(jié)點時，該域為0。

3～10——指向八個子節(jié)點的指針。若為終端節(jié)點時，這些域的狀態(tài)為空。八叉樹表示的特點：①定義形式簡單。②易于實現(xiàn)物體間的集合運算(并、交、差)。③可簡化消隱算法，便于計算物體的體積、質(zhì)量等。④存儲量大。第24頁，共38頁，2023年，2月20日，星期四改進：線性八叉樹，前例可表示為：

{1，2，3，4，51，53，55，565，566}，PPFFFFFFFFF第25頁，共38頁，2023年，2月20日，星期四五.分形表示法歐氏幾何的主要描述工具是：直線、平滑的曲線、平面、邊界整齊的平滑曲面。這些工具在描述一些抽象圖形或人造物體的形態(tài)時是非常有力的，但對一些復雜的自然景象形態(tài)就顯得無能為力了。為了解決復雜圖形的生成，分數(shù)維(Fractal)造型技術(shù)應運而生。第26頁，共38頁，2023年，2月20日，星期四

從Koch的雪花圖形

Mandelbrot的海岸線問題設N為每一步細分的數(shù)目

S為細分時的放大或縮小倍數(shù)則分數(shù)維定義為：

logNlog（1/S）D=雪花邊線的分數(shù)維：

N=4；S=1/3log4log3D==1.2619第27頁，共38頁，2023年，2月20日，星期四

分數(shù)維的計算已有大量試驗性的研究成果：例如海岸線1<D<1.3

山地表面2.1<D<2.9

河流水系1.1<D<1.85

云D≈1.35

人肺D≈2.17

血管D≈2.3

人腦表面2.73<D<2.79第28頁，共38頁，2023年，2月20日，星期四分數(shù)維造型的常用模型有：隨機插值模型——模擬海岸線和山等自然景象；粒子系統(tǒng)模型——模擬動態(tài)變化的火焰、煙等；正規(guī)文法模型——模擬植物（樹）的生長；迭代函數(shù)系統(tǒng)模型——模擬云彩等景物。第29頁，共38頁，2023年，2月20日，星期四第30頁，共38頁，2023年，2月20日，星期四第31頁，共38頁，2023年，2月20日，星期四第32頁，共38頁，2023年，2月20日，星期四Koch曲線(1)Koch曲線的生成規(guī)則迭代初始把原線段去掉中間的三分之一，代之以底邊在被去線段上的等邊三角形的兩腰；以后每一步的迭代都是這樣的重復。第33頁，共38頁，2023年，2月20日，星期四Koch曲線（其它分形集也是如此）可以由簡單的圖形（生成元），迭代產(chǎn)生。在這里，Koch曲線的生成元是：生成元表示：約定記號，用一個字符串符號表示。設：

F從當前點開始，向前移動一距離dL向左（逆時針）轉(zhuǎn)一定角

R向右（順時針）轉(zhuǎn)一定角則Koch曲線的生成元可表示為：

T＝FLFRRFLF（＝60o）第34頁，共38頁，2023年，2月20日，星期四

曲線由把每一折線段反復迭代成縮小比例的三分之一的生成元而成。即字符串T＝FLFRRFLF中的每一個F又是字符串T本身。每次迭代后，生成的曲線長是原來曲線長的三分之四倍?？梢姡瑹o數(shù)次迭代后，Koch曲線將變得具有無限長度。并且，Koch曲線是永遠不自相交的。第35頁，共38頁，2023年，2月20日，星期四（2）生成Koch曲線的程序函數(shù)side：用于繪制Koch曲線的生成元，

xa,ya,xb,yb：線段的起點和終點坐標；

a：線段的方向角；

n：迭代次數(shù)（遞歸深度）。voidside(floatxa,ya,xb,yb,a,intn){floatx1,y1,x2,y2,x3,y3,dl,a1,a2;intxs,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);}else第36頁，共