計(jì)算機(jī)圖形學(xué)第九章

計(jì)算機(jī)圖形學(xué)第九章第1頁(yè)，共55頁(yè)，2023年，2月20日，星期二9.1造型技術(shù)概述1、造型技術(shù)：計(jì)算機(jī)內(nèi)對(duì)形狀信息的描述方法簡(jiǎn)稱為造型(Modeling)技術(shù),造型技術(shù)主要有形狀表達(dá)和形狀操作兩個(gè)部分組成。將形狀的結(jié)構(gòu)用數(shù)據(jù)結(jié)構(gòu)模擬出來。這種描述形狀的數(shù)據(jù)結(jié)構(gòu)稱為模型（Model)實(shí)現(xiàn)對(duì)模型的生成、修改、綜合、分析、計(jì)算、顯示等操作，以便完成設(shè)計(jì)過程中的各種造型任務(wù)。第2頁(yè)，共55頁(yè)，2023年，2月20日，星期二2、目前的造型技術(shù)主要有：（1）實(shí)體造型技術(shù)（SolidModeling)： 將對(duì)象分解為一組有限的三維元素的集合，以及施加在這組集合元素上的一組操作。又可分為空間分割表示、結(jié)構(gòu)實(shí)體幾何模型（CSG）、邊界模型（B—Reps)。

第3頁(yè)，共55頁(yè)，2023年，2月20日，星期二（2）曲面造型技術(shù)（SurfaceModeling)

用數(shù)學(xué)函數(shù)（如B樣條、貝塞爾）描述曲線和曲面，并提供其修改、連接、求交和顯示等操作（3）非幾何形體的造型技術(shù) 大多數(shù)自然物體，如山石、樹木、花草、云、水波、火焰的非規(guī)則形體的表達(dá)與操作方法

第4頁(yè)，共55頁(yè)，2023年，2月20日，星期二1、分形造型的概念分形是最近二十多年來發(fā)展起來的新學(xué)科。分形的原文是Fractals，是由著名數(shù)學(xué)家B.Mandelbrot于1975年用拉丁詞根構(gòu)造的單詞，他創(chuàng)立了獨(dú)立于歐幾里德幾何學(xué)之外的數(shù)學(xué)方法：分形幾何。9.2非幾何形體的造型技術(shù)第5頁(yè)，共55頁(yè)，2023年，2月20日，星期二分形具有下面列出的典型幾何性質(zhì)（１）分形集都具有任意小尺度下的比例細(xì)節(jié)，或者說它具有精細(xì)的結(jié)構(gòu)。（２）分形集不能用傳統(tǒng)的幾何語(yǔ)言來描述，它既不是滿足于某些條件的點(diǎn)的軌跡，也不是某些簡(jiǎn)單方程的解集。第6頁(yè)，共55頁(yè)，2023年，2月20日，星期二（３）分形集具有某種自相似的形式，可能是近似的或統(tǒng)計(jì)的自相似。（４）一般說來，分形集的維數(shù)是一個(gè)分?jǐn)?shù)，所以分形也稱為分?jǐn)?shù)維；（５）在大多數(shù)令人感興趣的情形下，分形集由非常簡(jiǎn)單的方法定義，可以用變換的迭代產(chǎn)生。第7頁(yè)，共55頁(yè)，2023年，2月20日，星期二分形的四種構(gòu)成方法（１）基于Ｌ系統(tǒng)的分形模型（２）迭代函數(shù)系統(tǒng)模型（３）粒子系統(tǒng)模型（４）隨機(jī)插值模型第8頁(yè)，共55頁(yè)，2023年，2月20日，星期二

第9頁(yè)，共55頁(yè)，2023年，2月20日，星期二１.Koch曲線(1)Koch曲線的生成規(guī)則

Koch曲線是VonKoch于1904年第一次描述的。它的構(gòu)造是：迭代初始把原線段去掉中間的三分之一，代之以底邊在被去線段上的等邊三角形的兩腰；以后每一步的迭代都是這樣的重復(fù)。（圖例）二、典型的分形模型第10頁(yè)，共55頁(yè)，2023年，2月20日，星期二第11頁(yè)，共55頁(yè)，2023年，2月20日，星期二從以上過程可以清楚地看出，Koch曲線（其它分形集也是如此）可以由簡(jiǎn)單的圖，稱為生成元，迭代產(chǎn)生。在這里，Koch曲線的生成元是：第12頁(yè)，共55頁(yè)，2023年，2月20日，星期二

在這里，假如我們約定好記號(hào)，就可以把Koch曲線的生成元的構(gòu)造用一個(gè)字符串符號(hào)表示出來。設(shè)：

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

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

T＝FLFRRFLF（＝60o）第13頁(yè)，共55頁(yè)，2023年，2月20日，星期二曲線由把每一折線段反復(fù)迭代成縮小比例的三分之一的生成元而成。即字符串T＝FLFRRFLF中的每一個(gè)

F又是字符串

T本身。而每次迭代后，生成的曲線長(zhǎng)是原來曲線長(zhǎng)的三分之四倍?？梢?，無數(shù)次迭代后，

Koch曲線將變得具有無限長(zhǎng)度。并且，Koch曲線是永遠(yuǎn)不自相交的。第14頁(yè)，共55頁(yè)，2023年，2月20日，星期二(2)生成Koch曲線的程序函數(shù)side()，用于繪制Koch曲線的生成元，函數(shù)中所用的參數(shù)為：

xa,ya,xb,yb:線段的起點(diǎn)和終點(diǎn)坐標(biāo)；

a:線段的方向角；

n:迭代次數(shù)（遞歸深度）。第15頁(yè)，共55頁(yè)，2023年，2月20日，星期二

voidside(xa,ya,xb,yb,a,n)intn;floatxa,ya,xb,yb,a;{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第16頁(yè)，共55頁(yè)，2023年，2月20日，星期二

{

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+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);}}***第17頁(yè)，共55頁(yè)，2023年，2月20日，星期二２.Dragon曲線（１）Dragon曲線的生成規(guī)則變化的起始是一條原始直線段。第一步是將該直線段由中間點(diǎn)隆起，使其變成一個(gè)等腰直角三角形的兩腰。接下去再分別對(duì)兩腰作和前面同樣的變化，如此不斷進(jìn)行。（圖例）第18頁(yè)，共55頁(yè)，2023年，2月20日，星期二第19頁(yè)，共55頁(yè)，2023年，2月20日，星期二不難看出，Dragon曲線完全是由長(zhǎng)度相等的線段組成，且兩兩相交處都成直角。另外，每次分形后，曲線的長(zhǎng)度是原來曲線長(zhǎng)度的2倍。因此，經(jīng)過無數(shù)次變化，Dragon曲線也將變成無限長(zhǎng)。這一點(diǎn)正符合分形曲線的特點(diǎn)。第20頁(yè)，共55頁(yè)，2023年，2月20日，星期二３.其他分形實(shí)例用分形可以構(gòu)造很多自然界的形體，下面是幾種常見的例子：第21頁(yè)，共55頁(yè)，2023年，2月20日，星期二（１）分枝

Koch曲線和Dragon曲線都是連續(xù)的，分枝結(jié)構(gòu)是不連續(xù)的，它的生成元類似于圖例所示。其生成元描述為：

F:F[LF]F[RF]F***第22頁(yè)，共55頁(yè)，2023年，2月20日，星期二（２）粒子模型的圖例***（３）巖石這種分形由平面多邊形（如三角形、四邊形等）用隨機(jī)插值法迭代生成，可模擬山巒。如圖所示：取中點(diǎn)在邊直線上在中點(diǎn)上加一個(gè)隨機(jī)法向量第23頁(yè)，共55頁(yè)，2023年，2月20日，星期二第24頁(yè)，共55頁(yè)，2023年，2月20日，星期二9.3實(shí)體的定義1、定義：具有一定的形狀（非流體）具有封閉的邊界（表面）內(nèi)部連通（上圖為非有效實(shí)體）占據(jù)有限的空間（有限體積）經(jīng)過運(yùn)算后，仍然是有效的物體第25頁(yè)，共55頁(yè)，2023年，2月20日，星期二2、有關(guān)概念：內(nèi)點(diǎn)邊界點(diǎn)取內(nèi)點(diǎn)運(yùn)算i取閉包運(yùn)算c正則運(yùn)算r

r·A=c·i·A第26頁(yè)，共55頁(yè)，2023年，2月20日，星期二結(jié)論：（1）一個(gè)物體只能占據(jù)有限空間，它是封閉的，具有一定的體積；（2）物體中不允許存在孤立點(diǎn)、懸掛的線或面。第27頁(yè)，共55頁(yè)，2023年，2月20日，星期二3、物體間的正則集合運(yùn)算物體間的并（U）、交（）、差（—）是造型系統(tǒng)中最基本的手段之一。集合運(yùn)算式構(gòu)造復(fù)雜物體的有效方法為什么需要正則集合運(yùn)算普通的集合運(yùn)算會(huì)產(chǎn)生無效物體第28頁(yè)，共55頁(yè)，2023年，2月20日，星期二（1）線框模型 將形體表示成一組輪廓線的集合，只存儲(chǔ)所畫圖形的頂點(diǎn)及頂點(diǎn)間的連接關(guān)系。優(yōu)點(diǎn)：適合圖形的幾何變換和交互顯示。簡(jiǎn)單、處理速度快與形體之間不存在－－對(duì)應(yīng)關(guān)系，是真實(shí)物體的高度抽象，缺點(diǎn)：a、無法實(shí)現(xiàn)圖形的消隱；b、數(shù)據(jù)定義的模糊性；c、無法處理曲面的側(cè)影輪廓線；d、復(fù)雜物體的數(shù)據(jù)多、繁，且難以保證有效性和統(tǒng)一性。e、所不適合真實(shí)感顯示。9.4實(shí)體造型技術(shù)(顯示)第29頁(yè)，共55頁(yè)，2023年，2月20日，星期二（2）表面模型（曲面造型） 將形體表示成一組表面的集合形體與其表面一一對(duì)應(yīng)，著重于準(zhǔn)確地描述和控制物體的外形，適合于真實(shí)感顯示（著色、光照）第30頁(yè)，共55頁(yè)，2023年，2月20日，星期二9.5八叉樹表示空間分割表示常用方法：（1）空間位置枚舉法（2）單元分解表示法（3）八叉樹表示法第31頁(yè)，共55頁(yè)，2023年，2月20日，星期二1、空間位置枚舉法（1）選擇一個(gè)包含物體的立方體空間，將它均勻劃分。其中△為小立方體的邊長(zhǎng)。三維數(shù)組的大小取決于空間分辨(△)的大小和我們感興趣的立方體的大小。第32頁(yè)，共55頁(yè)，2023年，2月20日，星期二（2）用三維數(shù)組C[I][J][K]表示物體，數(shù)組中的元素與單位小立方體一一對(duì)應(yīng)當(dāng)C[I][J][K]=1時(shí)，表示對(duì)應(yīng)的小立方體被物體占據(jù)當(dāng)C[I][J][K]=0時(shí)，表示對(duì)應(yīng)的小立方體沒有被物體占據(jù)優(yōu)點(diǎn)可以表示任何物體容易實(shí)現(xiàn)物體間的集合運(yùn)算容易計(jì)算物體的整體性質(zhì)，如體積等缺點(diǎn)占用大量的存儲(chǔ)空間，如1024*1024*1024=1Gbits沒有邊界信息，不適于圖形顯示對(duì)物體進(jìn)行幾何變換困難，如非90度的旋轉(zhuǎn)變換是物體的非精確表示第33頁(yè)，共55頁(yè)，2023年，2月20日，星期二2、單元分解表示對(duì)空間位置枚舉表示的空間分割方法作了改進(jìn)：?jiǎn)我惑w素多種體素通過粘合運(yùn)算：使兩個(gè)實(shí)體在邊界面上相接觸，但它們的內(nèi)部不相交。第34頁(yè)，共55頁(yè)，2023年，2月20日，星期二3、八叉樹表示：（1）是一種層次數(shù)據(jù)結(jié)構(gòu),首先在空間中定義一個(gè)能包含所表示物體的立方體。立方體的三條棱邊與x,y,z軸平行。若立方體內(nèi)空間完全由這個(gè)立方體予以表示（標(biāo)識(shí)為FULL），否則標(biāo)識(shí)為（PARTIAL）將立方體等分為8等分，依次編號(hào)。依此方式判斷小立方體的狀態(tài)（FULL、PARTIAL或EMPTY），若為PARTIAL，則繼續(xù)分……第35頁(yè)，共55頁(yè)，2023年，2月20日，星期二（2）、二維物體的四叉樹表示：第36頁(yè)，共55頁(yè)，2023年，2月20日，星期二（3）、三維物體的八叉樹表示（例）：第37頁(yè)，共55頁(yè)，2023年，2月20日，星期二第38頁(yè)，共55頁(yè)，2023年，2月20日，星期二第39頁(yè)，共55頁(yè)，2023年，2月20日，星期二（3）、八叉樹表示的優(yōu)、缺點(diǎn)：優(yōu)點(diǎn)：

a.容易實(shí)現(xiàn)實(shí)體間的正則集合運(yùn)算；

b.簡(jiǎn)化隱藏線和隱藏面的消除。（消隱算法的核心是排序）

c.易于計(jì)算物體的體積（或質(zhì)量）第40頁(yè)，共55頁(yè)，2023年，2月20日，星期二缺點(diǎn)：占用存儲(chǔ)多（如圓柱、球等）解決方法：線性八叉樹方法（GARG82）即：采用可變長(zhǎng)度的線性結(jié)構(gòu)存儲(chǔ)八叉樹（如可變長(zhǎng)度的一維數(shù)組），數(shù)組中只存放八叉樹中那些狀態(tài)為F（FULL）的葉結(jié)構(gòu)。第41頁(yè)，共55頁(yè)，2023年，2月20日，星期二（5X、74X，75X）第42頁(yè)，共55頁(yè)，2023年，2月20日，星期二4、三種空間分割方法的比較空間位置枚舉表示——同樣大小立方體粘合在一起表示物體八叉樹表示——不同大小的立方體粘合在一起表示物體單元分解表示——多種體素粘合在一起表示物體第43頁(yè)，共55頁(yè)，2023年，2月20日，星期二9.6物體的邊界表示

(B-Reps:BoundaryReprensentation)1、概念：（1）物體的邊界表示：三維物體可以通過描述它的邊界來表示；（2）邊界：物體內(nèi)部與外部點(diǎn)的分界面。第44頁(yè)，共55頁(yè)，2023年，2月20日，星期二第45頁(yè)，共55頁(yè)，2023年，2月20日，星期二2、特點(diǎn)： 描述物體的信息包括幾何信息和拓?fù)湫畔?。?）幾何信息：大小、尺寸、位置、形狀等，如頂點(diǎn)在三維空間的位置（三維坐標(biāo)）、棱邊的曲線方程、物體表面的曲面方程等；（2）拓?fù)湫畔ⅲ何矬w上所有的頂點(diǎn)、棱邊、表面間是怎樣連接的。第46頁(yè)，共55頁(yè)，2023年，2月20日，星期二3、邊界表示法中的數(shù)據(jù)結(jié)構(gòu)（1）半邊結(jié)構(gòu)（以邊為核心）為了方便表達(dá)拓?fù)潢P(guān)系。它將一條邊表示成拓?fù)湟饬x上方向相反的兩條“半邊”邊v1v1v2v2左環(huán)左半邊右環(huán)右半邊第47頁(yè)，共55頁(yè)，2023年，2月20日，星期二邊界表示多邊形的頂點(diǎn)順序與法矢量,若規(guī)定一個(gè)面的外環(huán)為逆時(shí)針,則內(nèi)環(huán)為順時(shí)針空間多邊形的平面方程計(jì)算頂點(diǎn)不共面用最小二乘法求出一張平面，使其距所有頂點(diǎn)的距離之和最小第48頁(yè)，共55頁(yè)，2023年，2月20日，星期二（2）半邊數(shù)據(jù)結(jié)構(gòu)的層次結(jié)構(gòu)多面體prevsnext面prevsnext環(huán)prevsnext半邊prevsnext半邊prevsnext第49頁(yè)，共55頁(yè)，2023年，2月20日，星期二4、歐拉運(yùn)算（1）對(duì)于任意的簡(jiǎn)單多面體，其面(f)、邊(e)、頂點(diǎn)(v)的數(shù)目滿足歐拉公式：

v-e+f=2.第50頁(yè)，共55頁(yè)，2023年，2月20日，星期二（2）對(duì)于任意的正則形體，引入形體的其它幾個(gè)參數(shù)：形體所有面上的內(nèi)孔總數(shù)(r)、穿透形體的孔洞數(shù)(h)和不相連接的物體個(gè)數(shù)(s)，為了保證形體的有效性，則形體須滿足廣義歐拉公式：

v-e+f=2(s-h)+r.

第51頁(yè)，共55頁(yè)，2023年，2月20