CG2014-07-三維對象的表示

計算機圖形學(xué)河南大學(xué)計算機與信息工程學(xué)院2014年2月計算機圖形學(xué)2第七章三維對象的表示7.1三維對象表示方法概述7.2多邊形表面7.3二次曲面7.4樣條曲線概述7.5Hermite樣條曲線7.6Bézier曲線和曲面7.7B樣條曲線和曲面7.8空間分區(qū)表示方法7.9非規(guī)則對象表示方法計算機圖形學(xué)37.1三維對象表示方法概述7.1.1三維圖形的基本問題7.1.2數(shù)據(jù)模型7.1.3過程模型計算機圖形學(xué)41.在二維屏幕上如何顯示三維物體？顯示器屏幕、繪圖紙等是二維的顯示對象是三維的解決方法----投影三維顯示設(shè)備正在研制中2.如何表示三維物體？二維形體的表示----直線段,折線,曲線段,多邊形區(qū)域三維形體的表示----空間直線段、折線、曲線段、多邊形、曲面片計算機圖形學(xué)5三維對象表示方法線框模型線框模型：將形體表示成一組輪廓線的集合。一般地，畫出了形體的棱線與輪廓線就能唯一地表示出來。如圖，八個頂點可以定義一個長方體，但還不足以識別它，如果定義了棱線，則無論如何放置長方體都能唯一地表示了。對于多面體由于其輪廓線和棱線通常是一致的，所以多面體的線模型更便于識別，且簡單。e12v4v8s3e2e4e6e8e2e7e11e10e9e3e1v2v3v1v7v5v6s2s6s5s1s4計算機圖形學(xué)6計算機圖形學(xué)7計算機圖形學(xué)8計算機圖形學(xué)9線框模型用三維線框模型表示三維形體常具有二義性

由于不存在面的信息，三維線框容易構(gòu)造出無效形體由于不能表示出曲面的輪廓線，所以不能正確表示曲面信息無法進行圖形的線面消隱。生成復(fù)雜形體時，線框模型要求輸入大量的數(shù)據(jù)，加重用戶的輸入負擔(dān)。難以保證數(shù)據(jù)的統(tǒng)一性和有效性。兩種看法（傘尖遠離視點或指向視點）旋轉(zhuǎn)時出現(xiàn)不同效果計算機圖形學(xué)10計算機圖形學(xué)11八叉樹模型及八叉樹編碼示意圖八叉樹Vonkochsnowflake計算機圖形學(xué)127.2

多邊形表面多邊形表面分為兩組進行組織幾何表：頂點坐標和用來標識多邊形表面空間方向的參數(shù)點表、邊表、面表屬性表：指明物體透明度及表面反射度的參數(shù)和紋理特征計算機圖形學(xué)13多邊形表面頂點表序號點坐標1x1,y1,z12x2,y2,z23x3,y3,z34x4,y4,z45x5,y5,z5邊表序號頂點號1v1,v22v2,v33v3,v14v3,v45v4,v56v5,v1多邊形面表序號邊序號1E1,E2,E32E3,E4,E5,E6E1E2E4E5S1v2v1v3v4v5E3E6S2計算機圖形學(xué)14PolygonSurfaces多邊形網(wǎng)格圖形系統(tǒng)一般使用多邊形網(wǎng)格對3D物體進行建模計算機圖形學(xué)15計算機圖形學(xué)16(a)線框圖物體的多邊形表示實例野鴨模型的多邊形表示，有6656個面片，3474個頂點。(b)原始法向著色圖(c)平均法向著色圖計算機圖形學(xué)17多邊形表面模型多邊形網(wǎng)格：三維形體的邊界通常用多邊形網(wǎng)格（polygonmesh）的拼接來模擬。球面橢球面環(huán)面超二次曲面二次曲面和超二次曲面

不能表達復(fù)雜的曲線和曲面。例如飛機或汽車的流線表面…..使用樣條表示7.3二次曲面

計算機圖形學(xué)18樣條的歷史很早的繪圖員利用“ducks”和有柔性的木條（樣條）來繪制曲線木質(zhì)的樣條具有二階連續(xù)并且通過所有的控制點ADuck(weight)Duckstraceoutcurve7.4樣條曲線概述計算機圖形學(xué)19樣條：通過一組指定點集而生成平滑曲線的柔性帶樣條曲線在計算機圖形學(xué)中的含義由多項式曲線段連接而成的曲線在每段的邊界處滿足特定的連續(xù)性條件樣條曲面使用兩組正交樣條曲線進行描述樣條計算機圖形學(xué)20樣條在圖形學(xué)中的應(yīng)用設(shè)計曲線、曲面汽車車身設(shè)計、飛機和航天飛機表面的設(shè)計、船體設(shè)計以及家庭應(yīng)用。曲線的產(chǎn)生給定一組離散的坐標點，將數(shù)據(jù)集擬合成指定的曲線函數(shù)根據(jù)曲線函數(shù)得到曲線的圖形計算機圖形學(xué)21曲線的類型插值樣條曲線：選取的多項式使得曲線通過每個控制點逼近樣條曲線：選取的多項式不一定使曲線通過每個控制點計算機圖形學(xué)22給定一組有序的數(shù)據(jù)點Pi，i=0,1,…,n，構(gòu)造一條曲線順序通過這些數(shù)據(jù)點，稱為對這些數(shù)據(jù)點進行插值，所構(gòu)造的曲線稱為插值曲線。線性插值：假設(shè)給定函數(shù)f(x)在兩個不同點x1和x2的值，用一個線形函數(shù)：y=ax+b，近似代替，稱為的線性插值函數(shù)。拋物線插值:已知在三個互異點的函數(shù)值為，要求構(gòu)造一個函數(shù)使拋物線在結(jié)點處與在處的值相等。插值計算機圖形學(xué)23xyo1y2y)(xfy=)(xyj=1x2xxyo1y2y)(xfy=)(xyj=1x2x3x3y(a)(b)

線性插值和拋物插值計算機圖形學(xué)24逼近：構(gòu)造一條曲線使之在某種意義下最接近給定的數(shù)據(jù)點(但未必通過這些點)，所構(gòu)造的曲線稱為逼近曲線。在計算數(shù)學(xué)中，逼近通常指用一些性質(zhì)較好的函數(shù)近似表示一些性質(zhì)不好的函數(shù)。逼近計算機圖形學(xué)25

曲線的逼近求給定型值點之間曲線上的點稱為曲線的插值。將連接有一定次序控制點的直線序列稱為控制多邊形或特征多邊形。計算機圖形學(xué)26

曲線的逼近凸殼凸殼的定義Convexhull

包含一組控制點的凸多邊形邊界凸殼的作用提供了曲線或曲面與包圍控制點的區(qū)域之間的偏差的測量以凸殼為界的樣條保證了多項式沿控制點的平滑前進計算機圖形學(xué)27凸殼計算機圖形學(xué)28光順(Firing)指曲線的拐點不能太多。對平面曲線而言，相對光順的條件是：a.具有二階幾何連續(xù)性(G2)；b.不存在多余拐點和奇異點；c.曲率變化較小。光順計算機圖形學(xué)29假定參數(shù)曲線段pi以參數(shù)形式進行描述：參數(shù)連續(xù)性幾何連續(xù)性參數(shù)連續(xù)性與幾何連續(xù)性計算機圖形學(xué)301.參數(shù)連續(xù)性0階參數(shù)連續(xù)性記作C0連續(xù)性，是指曲線的幾何位置連接，即計算機圖形學(xué)311階參數(shù)連續(xù)性記作C1連續(xù)性，指代表兩個相鄰曲線段的方程在相交點處有相同的一階導(dǎo)數(shù)：計算機圖形學(xué)322階參數(shù)連續(xù)性，記作C2連續(xù)性，指兩個相鄰曲線段的方程在相交點處具有相同的一階和二階導(dǎo)數(shù)。

計算機圖形學(xué)332.幾何連續(xù)性0階幾何連續(xù)性，記作G0連續(xù)性，與0階參數(shù)連續(xù)性的定義相同，滿足：1階幾何連續(xù)性，記作G1連續(xù)性，指一階導(dǎo)數(shù)在相鄰段的交點處成比例;2階幾何連續(xù)性，記作G2連續(xù)性，指相鄰曲線段在交點處其一階和二階導(dǎo)數(shù)均成比例。計算機圖形學(xué)34參數(shù)連續(xù)性條件兩個相鄰曲線段在相交處的參數(shù)導(dǎo)數(shù)相等零階連續(xù)(C0連續(xù))：簡單地表示曲線連接一階連續(xù)(C1連續(xù))：說明代表兩個相鄰曲線的方程在相交點處有相同的一階導(dǎo)數(shù)（切線）二階連續(xù)(C2連續(xù))：兩個曲線段在交點處有相同的一階和二階導(dǎo)數(shù)，交點處的切向量變化率相等參數(shù)連續(xù)性條件計算機圖形學(xué)35曲線分段構(gòu)造時參數(shù)連續(xù)性條件零階連續(xù)一階連續(xù)二階連續(xù)F(u)f(u)F(1)=f(0)F'(1)=f'(0)F''(1)=f''(0)計算機圖形學(xué)36幾何連續(xù)性條件兩個相鄰曲線段在相交處的參數(shù)導(dǎo)數(shù)成比例零階連續(xù)（G0連續(xù)）：與0階參數(shù)連續(xù)性相同，即兩個曲線必在公共點處有相同的坐標一階連續(xù)（G1連續(xù)）：表示一階導(dǎo)數(shù)在兩個相鄰曲線的交點處成比例二階連續(xù)（G2連續(xù)）：表示兩個曲線段在相交處的一階和二階導(dǎo)數(shù)均成比例幾何連續(xù)性條件計算機圖形學(xué)377.6Bezier曲線7.6.1Bezier曲線的定義Bezier曲線的例子計算機圖形學(xué)38定義：其中，Pi構(gòu)成該Bezier曲線的特征多邊形Bernstein基函數(shù)具有如下形式：注意：當k=0，t=0時，tk=1，k!=1。

計算機圖形學(xué)397.6.2Betnstein基函數(shù)的性質(zhì)

（1）正性

（2）端點性質(zhì)

計算機圖形學(xué)40（3）權(quán)性

由二項式定理可知：計算機圖形學(xué)41（4）對稱性

因為

計算機圖形學(xué)42(5）遞推性。

即高一次的Bernstein基函數(shù)可由兩個低一次的Bernstein調(diào)和函數(shù)線性組合而成。因為，計算機圖形學(xué)43（6）導(dǎo)函數(shù)

（7）最大值。在處達到最大值。計算機圖形學(xué)44（8）升階公式

計算機圖形學(xué)45（9）積分計算機圖形學(xué)461．一次Bezier曲線(n=1)

計算機圖形學(xué)472．二次Bezier曲線(n=2)

計算機圖形學(xué)483．三次Bezier曲線(n=3)

計算機圖形學(xué)49

三次Bezier曲線四個Bezier基函數(shù)0tB0,3(t)B3,3(t)B1,3(t)B2,3(t)計算機圖形學(xué)50計算機圖形學(xué)517.6.2Bezier曲線的性質(zhì)1．端點

計算機圖形學(xué)522．一階導(dǎo)數(shù)

計算機圖形學(xué)53計算機圖形學(xué)54

三次Bezier曲線段在起始點和終止點處的一階導(dǎo)數(shù)為：計算機圖形學(xué)553．二階導(dǎo)數(shù)

三次Bezier曲線段在起始點和終止點處的二階導(dǎo)數(shù)為：計算機圖形學(xué)56當t=0時，當t=1時，上式表明：2階導(dǎo)矢只與相鄰的3個頂點有關(guān)，事實上，r階導(dǎo)矢只與（r+1）個相鄰點有關(guān)，與更遠點無關(guān)。將、及、代入曲率公式，可以得到Bezier曲線在端點的曲率分別為：計算機圖形學(xué)57（4）對稱性。由控制頂點構(gòu)造出的新Bezier曲線，與原Bezier曲線形狀相同，走向相反。因為：這個性質(zhì)說明Bezier曲線在起點處有什么幾何性質(zhì)，在終點處也有相同的性質(zhì)。計算機圖形學(xué)58計算機圖形學(xué)59（5）凸包性由于，且，這一結(jié)果說明當t在[0，1]區(qū)間變化時，對某一個t值，P(t)是特征多邊形各頂點的加權(quán)平均，權(quán)因子依次是。在幾何圖形上，意味著Bezier曲線P(t)在中各點是控制點Pi的凸線性組合，即曲線落在Pi構(gòu)成的凸包之中，如下圖所示。Bezier曲線的凸包性凸包計算機圖形學(xué)60（6）幾何不變性。這是指某些幾何特性不隨坐標變換而變化的特性。Bezier曲線位置與形狀與其特征多邊形頂點的位置有關(guān)，它不依賴坐標系的選擇。計算機圖形學(xué)61（7）變差縮減性。若Bezier曲線的特征多邊形是一個平面圖形，則平面內(nèi)任意直線與C(t)的交點個數(shù)不多于該直線與其特征多邊形的交點個數(shù)，這一性質(zhì)叫變差縮減性質(zhì)。此性質(zhì)反映了Bezier曲線比其特征多邊形的波動還小，也就是說Bezier曲線比特征多邊形的折線更光順。計算機圖形學(xué)62（8）仿射不變性對于任意的仿射變換A：即在仿射變換下，的形式不變。計算機圖形學(xué)637.6.5Bezier曲線的生成1．繪圖一段Bezier曲線①利用定義式Bezier曲線的繪制，可以利用其定義式，對參數(shù)t選取足夠多的值，計算曲線上的一些點，然后用折線連接來近似畫出實際的曲線。隨著選取點增多，折線和曲線可以任意接近。計算機圖形學(xué)64假設(shè)給定的四個型值點是P0=(1，1)，Pl=(2，3)，P2=(4，3)，P3=(3，1)，則計算結(jié)果見下表。計算機圖形學(xué)65t(1-t)33t(1-t)23t2(1-t)t3P(t)01000(1,1)0.150.6140.3250.05740.0034(1.5058,1.765)0.350.2750.4440.2390.043(2.248,2.376)0.50.1250.3750.3750.125(2.75,2.5)0.650.0430.2390.4440.275(3.122,2.36)0.850.00340.05740.3250.614(3.248,1.75)10001(3,1)計算機圖形學(xué)66計算機圖形學(xué)67②利用曲線性質(zhì)（幾何作圖法和分裂法）幾何作圖法(deCasteljau算法)0P1P2P11P10P20PBezier曲線上的點

拋物線三切線定理計算機圖形學(xué)68)3/1(30PP=011/3

幾何作圖法求Bezier曲線

上一點（n=3，t=1/3）0P1P2P3P10P11P12P20P21P計算機圖形學(xué)697.6.6Bezier曲面基于Bezier曲線的討論，我們可以方便地可以給出Bezier曲面的定義和性質(zhì)，Bezier曲線的一些算法也可以很容易擴展到Bezier曲面的情況。計算機圖形學(xué)701．Bezier曲面定義：BENi,m(u)與BENj,n(v)是Bernstein基函數(shù)：

依次用線段連接點列中相鄰兩點所形成的空間網(wǎng)格，稱之為特征網(wǎng)格。計算機圖形學(xué)71計算機圖形學(xué)722．Bezier曲面的拼接0階連續(xù)性只要求相連接的曲面片具有公共的邊界曲線。1階連續(xù)性則要求在邊界曲線上的任何一點，兩個曲面片跨越邊界的切線矢量應(yīng)該共線，而且兩切線矢量的長度之比為常數(shù)。計算機圖形學(xué)73如右圖所示，設(shè)兩張m×n次Bezier曲面片

分別由控制頂點和定義。),(vuP),(vuQ)0,0(P)1,0(P)0,1(Q)1,1(Q)0,0()0,1(QP=)1,0()1,1(QP=uvBezier曲面片的拼接計算機圖形學(xué)74

Bezier曲面片的拼接邊界線P0,0Q3,0P3,3(Q0,3)P0,3Q3,3P3,1(Q0,1)P3,0(Q0,0)P3,2(Q0,2)計算機圖形學(xué)757.7B樣條曲線Bezier曲線和曲面的不足：Bezier曲線或曲面不能作局部修改；Bezier曲線或曲面的拼接比較復(fù)雜計算機圖形學(xué)767.7.1B樣條曲線B樣條曲線（構(gòu)造具有局部性的調(diào)和函數(shù)）給定n+1個控制點P0，P1，…，Pn，它們所確定的k階B樣條曲線是：

其中Ni，k(u)遞歸定義如下：

計算機圖形學(xué)77

這里u0，u1，…，un+k，是一個非遞減的序列，稱為節(jié)點，(u0，u1，…，un+k)稱為節(jié)點向量。定義中可能出現(xiàn)，這時約定為0。

計算機圖形學(xué)78均勻二次（三階）B樣條曲線

取n=3，m=3，則n+m=6，不妨設(shè)節(jié)點矢量為：T=(0,1,2,3,4,5,6)：計算機圖形學(xué)79計算機圖形學(xué)80基函數(shù)由遞推轉(zhuǎn)換到直接定義可以把不同段的時間進行移動例如：t在[2，3]設(shè)置為t=t-2；依次改為t=t-1；t=t注意順序顛倒。即t=t-2變?yōu)镕0,3。以下相同處理。計算機圖形學(xué)81計算機圖形學(xué)82tBk,3(t)214351

四段二次(三階)均勻B樣條基函數(shù)N0,3(t)N1,3(t)N2,3(t)N3,3(t)計算機圖形學(xué)837.7.2B樣條曲線的性質(zhì)1．局部支柱性

B樣條的基函數(shù)是一個分段函數(shù)，其重要特征是在參數(shù)變化范圍內(nèi)，每個基函數(shù)在tk到tk+m的子區(qū)間內(nèi)函數(shù)值不為零，在其余區(qū)間內(nèi)均為零，通常也將該特征稱為局部支柱性。計算機圖形學(xué)84

B樣條曲線的局部支柱性P0P1P2P3P″4P5P6P7P4P′4計算機圖形學(xué)852．B樣條的凸組合性質(zhì)

B樣條的凸組合性和B樣條基函數(shù)的數(shù)值均大于或等于0保證了B樣條曲線的凸包性，即B樣條曲線必處在控制多邊形所形成的凸包之內(nèi)。

計算機圖形學(xué)86B樣條曲線與Bezier曲線的凸包性比較B樣條曲線Bezier曲線Bezier曲線B樣條曲線m=3m=4m=5(a)B樣條曲線和Bezier曲線的凸包比較(b)B樣條曲線和Bezier曲線的比較B樣條凸包Bezier凸包B樣條凸包B樣條凸包Bezier凸包Bezier凸包計算機圖形學(xué)877.7.5B樣條曲面定義：控制頂點、控制網(wǎng)格（特征網(wǎng)格）、B樣條基函數(shù)。B樣條曲面具有與B樣條曲線相同的局部支柱性、凸包性、連續(xù)性、幾何變換不變性等性質(zhì)。計算機圖形學(xué)88

有理樣條曲線曲面：NURBSB樣條曲線包括其特例的Bezier曲線都不能精確表示出拋物線外的二次曲線，B樣條曲面包括其特例的Bezier曲面都不能精確表示出拋物面外的二次曲面，而只能給出近似表示。提出NURBS方法，即非均勻有理B樣條方法主要是為了找到與描述自由型曲線曲面的B樣條方法既相統(tǒng)一、又能精確表示二次曲線弧與二次曲面的數(shù)學(xué)方法。計算機圖形學(xué)89NURBS曲線的定義NURBS曲線是由分段有理B樣條多項式基函數(shù)定義的計算機圖形學(xué)90Ri,k(t)具有k階B樣條基函數(shù)類似的性質(zhì)：局部支承性：Ri,k(t)=0，t

[ti,ti+k]權(quán)性：可微性：如果分母不為零，在節(jié)點區(qū)間內(nèi)是無限次連續(xù)可微的，在節(jié)點處(k-1-r)次連續(xù)可導(dǎo)，r是該節(jié)點的重復(fù)度。若

i=0，則Ri,k(t)=0；若

i=+

，則Ri,k(t)=1；計算機圖形學(xué)91NURBS曲線與B樣條曲線具有類似的幾何性質(zhì)：局部性質(zhì)。變差減小性質(zhì)。凸包性。在仿射與透射變換下的不變性。在曲線定義域內(nèi)有與有理基函數(shù)同樣的可微性。計算機圖形學(xué)92如果某個權(quán)因子為零，那么相應(yīng)控制頂點對曲線沒有影響。若，則當時，Bezier曲線和非有理B樣條曲線是NURBS曲線的特殊情況計算機圖形學(xué)93計算機圖形學(xué)94NURBS曲線曲面的定義NURBS曲面可由下面的有理參數(shù)多項式函數(shù)表示：計算機圖形學(xué)95NURBS曲線曲面的性質(zhì)NURBS曲面可由下面的有理參數(shù)多項式函數(shù)表示：計算機圖形學(xué)96NURBS曲線曲面的特點既為自由型曲線曲面也為初等曲線曲面的精確表示與設(shè)計提供了一個公共的數(shù)學(xué)形式，因此，一個統(tǒng)一的數(shù)據(jù)庫就能夠存儲這兩類形狀信息。為了修改曲線曲面的形狀，既可以借助調(diào)整控制頂點，又可以利用權(quán)因子，因而具有較大的靈活性。計算穩(wěn)定且速度快。計算機圖形學(xué)97NURBS曲線曲面的特點NURBS有明確的幾何解釋，使得它對良好的幾何知識尤其是畫法幾何知識的設(shè)計人員特別有用。NURBS具有強有力的幾何配套計算工具，包括節(jié)點插入與刪除、節(jié)點細分、升階、節(jié)點分割等，能用于設(shè)計、分析與處理等各個環(huán)節(jié)。NURBS具有幾何和透視投影變換不變性。計算機圖形學(xué)98NURBS曲線曲面的特點NURBS是非有理B樣條形式以及有理與非有理Bezier形式的合適的推廣。需要額外的存儲以定義傳統(tǒng)的曲線曲面。權(quán)因子的不合適應(yīng)用可能導(dǎo)致很壞的參數(shù)化，甚至毀掉隨后的曲面結(jié)構(gòu)。某些技術(shù)用傳統(tǒng)形式比用NURBS工作得更好。例如，曲面與曲面求交時，NURBS方法特別難于處理剛好接觸的情況。某些基本算法，例如求反曲線曲面上的點的參數(shù)值，存在數(shù)值不穩(wěn)定問題。7.8空間分區(qū)表示由簡單的物體來構(gòu)成復(fù)雜的物體掃描表示結(jié)構(gòu)實體幾何法7.8.2八叉樹計算機圖形學(xué)99掃描表示思想：通過平移、旋轉(zhuǎn)及其他對稱變換來構(gòu)造三維對象通過指定一個二維形狀以及在空間區(qū)域內(nèi)移動該形狀的掃描來描述該三維物體計算機圖形學(xué)100zoyxA平移掃描二維圖形A沿Z軸平移計算機圖形學(xué)101旋轉(zhuǎn)掃描二維圖形A繞Z軸旋轉(zhuǎn)zByxA計算機圖形學(xué)102結(jié)構(gòu)實體幾何法思想通過對兩個指定三維對象進行并、交或差等集合操作產(chǎn)生一個新的三維對象

計算機圖形學(xué)103結(jié)構(gòu)實體幾何法物體A和B差并交差計算機圖形學(xué)1047.8.2八叉樹分層樹形結(jié)構(gòu)，稱為八叉樹。思想利用實體的空間相關(guān)性優(yōu)點減少了三維物體的存儲需求提供了存儲有關(guān)物體內(nèi)部信息的方便表示計算機圖形學(xué)105四叉樹二維平面三維空間八叉樹計算機圖形學(xué)106四叉樹四叉樹數(shù)據(jù)結(jié)構(gòu)思想同質(zhì)象限10231023計算機圖形學(xué)107用于二維平面的分解對二維區(qū)域遞歸地等分4個小正方形，這個分解過程可表示為一棵樹，除葉節(jié)點，其每個節(jié)點都有四個分支，分別表示4個小正方形若小正方形是同質(zhì)的，則不必再分解；若小正方形是非同質(zhì)的，則需將它再一分為四分解是遞歸的。四叉樹計算機圖形學(xué)108四叉樹例3120312001230132計算機圖形學(xué)109四叉樹31245613251924182021222371112891014151617具有子孫的節(jié)點空節(jié)點實節(jié)點24513910781112314152021161722231819242516計算機圖形學(xué)110計算機圖形學(xué)111四叉樹二維圖的四叉樹表示三維形體的分解對三維空間進行前后、左右、上下等分為8個小立方體，小立方體單元均質(zhì)，則停止分解；小立方體單元非均質(zhì)，需進一步分解為8個子立方體直至所有小立方體單元均質(zhì)，或已分解到規(guī)定的分解精度為止。八叉樹計算機圖形學(xué)112八叉樹236720131375具有子孫的節(jié)點空節(jié)點實節(jié)點計算機圖形學(xué)113計算機圖形學(xué)114BSP樹二叉空間分割（BinarySpacePartitioning，BSP）樹方法是一種類似于八叉樹的空間分割方法，它每次將一實體用任一位置和任一方向的平面分為二部分（不同于八叉樹方法的每次將實體用平行于笛卡爾坐標平面的三個兩兩垂直的平面分割）。7.9非規(guī)則對象表示方法

7.9.1分形Fractal歐氏幾何法&分形幾何法分形基本特征分形生成過程分形分類分形維數(shù)概念計算機圖形學(xué)115Euclidean-GeometryMethods--useequationstodescribeobjectswhichhavesmoothsurfacesandregularshapes.Fractal-GeometryMethods--useprocedurestomodelnaturalobjectswhichhaveirregularorfragmentedfeatures.

歐氏幾何法&分形幾何法計算機圖形學(xué)116infinitedetailateverypoint每點具有無限細節(jié)self-similaritybetweentheobjectpartsandtheoverallfeatures對象整體和局部之間的自相似性利用一個過程來描述分形物體，該過程為產(chǎn)生物體局部細節(jié)指定了重復(fù)操作

distantCloserCloseryet分形基本特征計算機圖形學(xué)117計算機圖形學(xué)118分形幾何(fractalgeometry)分形(Fractal)的主要特征：自相似性質(zhì)：分形物體的任何一個部分都和物體整體具有某種程度的相似無限小細節(jié)性質(zhì)：當無限地放大分形物體時，物體總是表現(xiàn)有細節(jié)，而不是像歐氏空間的物體一樣最終會表現(xiàn)出光滑性維數(shù)非整數(shù)計算機圖形學(xué)119分形舉例：Koch雪花曲線Koch雪花曲線中間曲線的每一個線段