CG2014_07_三維對象的表示

1、計算機圖形學(xué)2 27.1 三維對象表示方法概述三維對象表示方法概述7.2 多邊形表面多邊形表面7.3 二次曲面二次曲面7.4 樣條曲線概述樣條曲線概述7.5 Hermite樣條曲線樣條曲線7.6 Bzier曲線和曲面曲線和曲面7.7 B樣條曲線和曲面樣條曲線和曲面7.8 空間分區(qū)表示方法空間分區(qū)表示方法7.9 非規(guī)則對象表示方法非規(guī)則對象表示方法計算機圖形學(xué)3 37.1.1 三維圖形的基本問題三維圖形的基本問題7.1.2 數(shù)據(jù)模型數(shù)據(jù)模型7.1.3 過程模型過程模型計算機圖形學(xué)4 41. 在二維屏幕上如何顯示三維物體？在二維屏幕上如何顯示三維物體？顯示器屏幕、繪圖紙等是二維的顯示器屏幕、繪圖紙

2、等是二維的顯示對象是三維的顯示對象是三維的解決方法解決方法-投影投影三維顯示設(shè)備正在研制中三維顯示設(shè)備正在研制中2. 如何表示三維物體？如何表示三維物體？二維形體的表示二維形體的表示-直線段直線段, ,折線折線, ,曲線段曲線段, ,多邊形區(qū)多邊形區(qū)域域三維形體的表示三維形體的表示-空間直線段、折線、空間直線段、折線、曲線段曲線段、多邊形、多邊形、曲面片曲面片計算機圖形學(xué)5 5線框模型：將形體表示成線框模型：將形體表示成一組輪廓線的集合。一組輪廓線的集合。一般地，畫出了形體的棱線與輪廓一般地，畫出了形體的棱線與輪廓線就能唯一地表示出來。如圖，八線就能唯一地表示出來。如圖，八個頂點可以定義一個長

3、方體，但還個頂點可以定義一個長方體，但還不足以識別它，如果定義了棱線，不足以識別它，如果定義了棱線，則無論如何放置長方體都能唯一地則無論如何放置長方體都能唯一地表示了。對于多面體由于其輪廓線表示了。對于多面體由于其輪廓線和棱線通常是一致的，所以多面體和棱線通常是一致的，所以多面體的線模型更便于識別，且簡單。的線模型更便于識別，且簡單。e12v4v8s3e2e4e6e8e2e7e11e10e9e3e1v2v3v1v7v5v6s2s6s5s1s4計算機圖形學(xué)6 6計算機圖形學(xué)7 7計算機圖形學(xué)8 8計算機圖形學(xué)9 9線框模型線框模型用三維線框模型表示三維形體常具有用三維線框模型表示三維形體常具有二

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

5、模型及八叉樹編碼示意圖八叉樹模型及八叉樹編碼示意圖Von koch snowflake計算機圖形學(xué)1212多邊形表面分為兩組進行組織多邊形表面分為兩組進行組織幾何表：幾何表：頂點坐標(biāo)和用來標(biāo)識多邊形表面頂點坐標(biāo)和用來標(biāo)識多邊形表面空間方向的參數(shù)空間方向的參數(shù) 點表、邊表、面表點表、邊表、面表屬性表：屬性表：指明物體透明度及表面反射度的指明物體透明度及表面反射度的參數(shù)和紋理特征參數(shù)和紋理特征計算機圖形學(xué)1313頂點表頂點表序號序號點坐標(biāo)點坐標(biāo)1x1, y1, z12x2, y2, z23x3, y3, z34x4, y4, z45x5, y5, z5邊表邊表序號序號頂點號頂點號1v1, v22v

6、2, v33v3, v14v3, v45v4, v56v5, v1多邊形面表多邊形面表序號序號邊序號邊序號1E1, E2, E32E3, E4, E5, E6E1E2E4E5S1v2v1v3v4v5E3E6S2計算機圖形學(xué)1414多邊形網(wǎng)多邊形網(wǎng)格格 圖形系統(tǒng)圖形系統(tǒng)一般使用一般使用多邊形網(wǎng)多邊形網(wǎng)格對格對3D物物體進行建體進行建模模計算機圖形學(xué)1515計算機圖形學(xué)1616(a) 線框圖線框圖 野鴨模型的多邊形表示，有野鴨模型的多邊形表示，有6656個面片，個面片，3474個頂點。個頂點。(b) 原始法向著色圖原始法向著色圖(c) 平均法向著色圖平均法向著色圖計算機圖形學(xué)1717多邊形網(wǎng)格：三

7、維形體的邊界通常用多邊形多邊形網(wǎng)格：三維形體的邊界通常用多邊形網(wǎng)格（網(wǎng)格（polygon mesh）的拼接來模擬。）的拼接來模擬。球面球面橢球面橢球面環(huán)面環(huán)面超超二次曲面二次曲面二次曲面二次曲面和和超二次曲面超二次曲面 不能表達復(fù)雜的曲線不能表達復(fù)雜的曲線和曲面。例如飛機或汽車的流線表面和曲面。例如飛機或汽車的流線表面.使使用用樣條樣條表示表示計算機圖形學(xué)1818樣條的歷史樣條的歷史很早的繪圖員利用很早的繪圖員利用“ducks”和有柔性的木條（樣條）來繪和有柔性的木條（樣條）來繪制曲線制曲線木質(zhì)的樣條具有二階連續(xù)木質(zhì)的樣條具有二階連續(xù)并且通過所有的控制點并且通過所有的控制點A Duck (we

8、ight)Ducks trace out curve計算機圖形學(xué)1919樣條：通過一組指定點集而生成平滑曲線的柔性樣條：通過一組指定點集而生成平滑曲線的柔性帶帶樣條曲線在計算機圖形學(xué)中的含義樣條曲線在計算機圖形學(xué)中的含義由多項式曲線段連接而成的曲線由多項式曲線段連接而成的曲線在每段的邊界處滿足特定的連續(xù)性條件在每段的邊界處滿足特定的連續(xù)性條件樣條曲面樣條曲面使用兩組正交樣條曲線進行描述使用兩組正交樣條曲線進行描述樣條樣條計算機圖形學(xué)2020樣條在圖形學(xué)中的應(yīng)用樣條在圖形學(xué)中的應(yīng)用設(shè)計曲線、曲面設(shè)計曲線、曲面汽車車身設(shè)計、飛機和航天飛機表面的設(shè)計、船體設(shè)計汽車車身設(shè)計、飛機和航天飛機表面的設(shè)計、

9、船體設(shè)計以及家庭應(yīng)用。以及家庭應(yīng)用。曲線的產(chǎn)生曲線的產(chǎn)生給定一組離散的坐標(biāo)點，將數(shù)據(jù)集擬合成指定的曲線函給定一組離散的坐標(biāo)點，將數(shù)據(jù)集擬合成指定的曲線函數(shù)數(shù)根據(jù)曲線函數(shù)得到曲線的圖形根據(jù)曲線函數(shù)得到曲線的圖形計算機圖形學(xué)2121曲線的類型曲線的類型插值插值樣條曲線：選樣條曲線：選取的多項式使得曲取的多項式使得曲線通過每個控制點線通過每個控制點逼近逼近樣條曲線：選樣條曲線：選取的多項式不一定取的多項式不一定使曲線通過每個控使曲線通過每個控制點制點計算機圖形學(xué)2222n給定一組有序的數(shù)據(jù)點給定一組有序的數(shù)據(jù)點P Pi i，i=0, 1, i=0, 1, , n, n，構(gòu)造一條，構(gòu)造一條曲線順序曲線

10、順序通過這些數(shù)據(jù)點通過這些數(shù)據(jù)點，稱為對這些數(shù)據(jù)點進行插，稱為對這些數(shù)據(jù)點進行插值，所構(gòu)造的曲線稱為插值曲線。值，所構(gòu)造的曲線稱為插值曲線。n線性插值：線性插值：假設(shè)給定函數(shù)假設(shè)給定函數(shù)f(x)f(x)在兩個不同點在兩個不同點x1x1和和x2x2的值，用一個線形函數(shù)：的值，用一個線形函數(shù)：y=ax+by=ax+b，近似代替，稱為，近似代替，稱為的線性插值函數(shù)。的線性插值函數(shù)。n拋物線插值拋物線插值: :已知在三個互異點已知在三個互異點 的函數(shù)值的函數(shù)值為為 ，要求構(gòu)造一個函數(shù)，要求構(gòu)造一個函數(shù) 使拋物線使拋物線 在結(jié)點在結(jié)點 處與處與 在在 處處 的值相等。的值相等。cbxaxx2)()(x3

11、21,xxx321,yyy) 3 , 2 , 1( ixi)(xfix插值插值計算機圖形學(xué)2323xyo1y2y)(xfy )(xy 1x2xxyo1y2y)(xfy )(xy 1x2x3x3y(a)(a)(b)(b) 線性插值和拋物插值線性插值和拋物插值計算機圖形學(xué)2424n逼近：構(gòu)造一條曲線使之在某種意義下最接近給定的逼近：構(gòu)造一條曲線使之在某種意義下最接近給定的數(shù)據(jù)點數(shù)據(jù)點( (但未必通過這些點但未必通過這些點) )，所構(gòu)造的曲線稱為逼近，所構(gòu)造的曲線稱為逼近曲線。曲線。n在計算數(shù)學(xué)中，逼近通常指用一些性質(zhì)較好的函數(shù)近在計算數(shù)學(xué)中，逼近通常指用一些性質(zhì)較好的函數(shù)近似表示一些性質(zhì)不好的函數(shù)

12、。似表示一些性質(zhì)不好的函數(shù)。逼近逼近計算機圖形學(xué)2525 曲線的逼近曲線的逼近求給定型值點之間曲線上的點稱為求給定型值點之間曲線上的點稱為曲線的插值曲線的插值。將連接有一定次序控制點的直線序列稱為將連接有一定次序控制點的直線序列稱為控制多邊形控制多邊形或或特征多邊形特征多邊形。計算機圖形學(xué)2626 曲線的逼近曲線的逼近凸殼的定義凸殼的定義Convex hull 包含一組控制點的凸多邊形邊界包含一組控制點的凸多邊形邊界凸殼的作用凸殼的作用提供了曲線或曲面與包圍控制點的區(qū)域之提供了曲線或曲面與包圍控制點的區(qū)域之間的偏差的測量間的偏差的測量以凸殼為界的樣條保證了多項式沿控制點以凸殼為界的樣條保證了多

13、項式沿控制點的平滑前進的平滑前進計算機圖形學(xué)2727計算機圖形學(xué)2828光順光順(Firing)(Firing)指曲線的拐點不能太多。對平面曲線而指曲線的拐點不能太多。對平面曲線而言，相對光順的條件是：言，相對光順的條件是：a. a. 具有二階幾何連續(xù)性具有二階幾何連續(xù)性(G(G2 2) )；b. b. 不存在多余拐點和奇異點；不存在多余拐點和奇異點；c. c. 曲率變化較小。曲率變化較小。光順光順計算機圖形學(xué)2929假定參數(shù)曲線段假定參數(shù)曲線段 pi 以參數(shù)形式進行描述：以參數(shù)形式進行描述：t ,t t)(i1i0tppii 參數(shù)連續(xù)性參數(shù)連續(xù)性 幾何連續(xù)性幾何連續(xù)性參數(shù)連續(xù)性與幾何連續(xù)性參

14、數(shù)連續(xù)性與幾何連續(xù)性計算機圖形學(xué)30301.參數(shù)連續(xù)性參數(shù)連續(xù)性0階參數(shù)連續(xù)性階參數(shù)連續(xù)性記作記作C0連續(xù)性，是指曲線的幾何位置連接，即連續(xù)性，是指曲線的幾何位置連接，即)()(0)1()1(1iiiitptp計算機圖形學(xué)31311階參數(shù)連續(xù)性階參數(shù)連續(xù)性記作記作C1連續(xù)性，指代表兩個相鄰曲線段的方程在相交點處有連續(xù)性，指代表兩個相鄰曲線段的方程在相交點處有相同的一階導(dǎo)數(shù)：相同的一階導(dǎo)數(shù)：)()()()(0)1()1(10)1()1(1iiiiiiiitptptptp且計算機圖形學(xué)32322階參數(shù)連續(xù)性階參數(shù)連續(xù)性，記作，記作C2連續(xù)性，指兩個相鄰曲線段的方程連續(xù)性，指兩個相鄰曲線段的方程在相

15、交點處具有相同的一階和二階導(dǎo)數(shù)。在相交點處具有相同的一階和二階導(dǎo)數(shù)。 (a)0階連續(xù)性(b)1階連續(xù)性(c)2階連續(xù)性計算機圖形學(xué)33332.幾何連續(xù)性幾何連續(xù)性0階幾何連續(xù)性階幾何連續(xù)性，記作，記作G0連續(xù)性，與連續(xù)性，與0階參數(shù)連續(xù)性的定義相同，階參數(shù)連續(xù)性的定義相同，滿足：滿足： 1階幾何連續(xù)性階幾何連續(xù)性，記作，記作G1連續(xù)性，指一階導(dǎo)數(shù)在相鄰段的交點處連續(xù)性，指一階導(dǎo)數(shù)在相鄰段的交點處成比例成比例;2階幾何連續(xù)性階幾何連續(xù)性，記作，記作G2連續(xù)性，指相鄰曲線段在交點處其一階連續(xù)性，指相鄰曲線段在交點處其一階和二階導(dǎo)數(shù)均成比例。和二階導(dǎo)數(shù)均成比例。)()(0)1()1(1iiiitpt

16、p計算機圖形學(xué)3434參數(shù)參數(shù)連續(xù)性條件連續(xù)性條件 兩個相鄰曲線段在相交處的參數(shù)導(dǎo)數(shù)兩個相鄰曲線段在相交處的參數(shù)導(dǎo)數(shù)相等相等零階連續(xù)零階連續(xù)(C0連續(xù)連續(xù))：簡單地表示曲線：簡單地表示曲線連接連接一階連續(xù)一階連續(xù)(C1連續(xù)連續(xù))：說明代表兩個相鄰曲線的方程：說明代表兩個相鄰曲線的方程在相交點處有在相交點處有相同的一階導(dǎo)數(shù)相同的一階導(dǎo)數(shù)（切線）（切線）二階連續(xù)二階連續(xù)(C2連續(xù)連續(xù))：兩個曲線段在交點處有：兩個曲線段在交點處有相同的相同的一階和二階導(dǎo)數(shù)一階和二階導(dǎo)數(shù)，交點處的切向量變化率相等，交點處的切向量變化率相等計算機圖形學(xué)3535零階連續(xù)零階連續(xù) 一階連續(xù)一階連續(xù) 二階連續(xù)二階連續(xù)F(u)

17、f(u)F(1)=f(0)F(1)=f(0)F (1)=f (0)計算機圖形學(xué)3636幾何幾何連續(xù)性條件連續(xù)性條件 兩個相鄰曲線段在相交處的參數(shù)導(dǎo)數(shù)兩個相鄰曲線段在相交處的參數(shù)導(dǎo)數(shù)成比例成比例零階連續(xù)（零階連續(xù)（G0連續(xù)）：與連續(xù)）：與0階參數(shù)連續(xù)性相同，階參數(shù)連續(xù)性相同，即兩個曲線必在公共點處有相同的坐標(biāo)即兩個曲線必在公共點處有相同的坐標(biāo)一階連續(xù)（一階連續(xù)（G1連續(xù)）：表示連續(xù)）：表示一階導(dǎo)數(shù)一階導(dǎo)數(shù)在兩個相鄰在兩個相鄰曲線的交點處成比例曲線的交點處成比例二階連續(xù)（二階連續(xù)（G2連續(xù)）：表示兩個曲線段在相交處連續(xù)）：表示兩個曲線段在相交處的一階和二階導(dǎo)數(shù)均成比例的一階和二階導(dǎo)數(shù)均成比例計算機

18、圖形學(xué)37377.6.1 Bezier曲線的定義曲線的定義 Bezier Bezier曲線的例子曲線的例子計算機圖形學(xué)3838定義：定義：其中，其中，PiPi構(gòu)成該構(gòu)成該BezierBezier曲線的特征多邊形曲線的特征多邊形Bernstein基函數(shù)具有如下形式：基函數(shù)具有如下形式：注意：當(dāng)注意：當(dāng)k=0，t=0時，時，tk=1，k!=1。 nknkktBENPtp0,0,1 t)()(n,0,1,k 11!)(,knkknknknkttCttknkntBEN計算機圖形學(xué)3939 （1）正性）正性 （2）端點性質(zhì)）端點性質(zhì) otherwiseniBotherwiseiBnini0)(1) 1

19、(0)0(1)0(, ; 1, 2 , 1),1 , 0(01 , 00)(,nitttBni計算機圖形學(xué)4040（3）權(quán)性）權(quán)性 由二項式定理可知：由二項式定理可知：) 1 , 0(1)(0,ttBninininininiinnittttCtB00,1)1()1 ()(計算機圖形學(xué)4141（4）對稱性對稱性 因為因為 )()1 (,tBtBninni)1 ()1 ( )1 ()1 (1 )(,)(,tBttCttCtBniiniinininninnnin計算機圖形學(xué)4242(5）遞推性。）遞推性。 即高一次的即高一次的Bernstein基函數(shù)可由兩個低一次的基函數(shù)可由兩個低一次的Bernst

20、ein調(diào)和函數(shù)線性組合而成。因為，調(diào)和函數(shù)線性組合而成。因為，),.,1 , 0( ),()()1 ()(1, 11,nittBtBttBninini)()()1 ()1 ()1 ()1 ()1 ()()1 ()(1, 11,)1()1(111)1(1111,ttBtBttttCttCtttCCttCtBniniiniininiininiinininiinni計算機圖形學(xué)4343（6）導(dǎo)函數(shù)）導(dǎo)函數(shù) （7）最大值。）最大值。 在在 處達到最大值。處達到最大值。;, 1 , 0 ),()()(1,1, 1,nitBtBntBninini Bti n,( )tin計算機圖形學(xué)4444（8）升階公式

21、）升階公式 )(11)()11 ()()(11)()()11 ()()1 (1, 11,1, 1,1,tBnitBnitBtBnittBtBnitBtninininininini計算機圖形學(xué)4545（9）積分）積分10,11)(ntBni計算機圖形學(xué)4646 0,1 t )1 ()()(10101 ,kkktPPttBENPtp計算機圖形學(xué)4747 001201222102202,)(2)2( 0,1 t )1 (2)1 ( )()(PtPPtPPPPtPttPttBENPtpkkk21020010221211)(PPPtttp計算機圖形學(xué)4848 33,323,213, 103,033221

22、203303,)()()()( 0,1t )1 (3)1 (3)1 ( )()(PtBENPtBENPtBENPtBENPtPttPttPttBENPtpkkk33,323,223,133,0)()1 (3)()1 (3)()1 ()(ttBENtttBENtttBENttBEN計算機圖形學(xué)4949 三次三次BezierBezier曲線四個曲線四個BezierBezier基函數(shù)基函數(shù)0 0t tB B0,30,3(t)(t)B B3,33,3(t)(t)B B1,31,3(t)(t)B B2,32,3(t)(t)計算機圖形學(xué)5050bebeGMTPPPPttttp 0,1 t 00010033

23、036313311)(321023計算機圖形學(xué)51511端點端點 0, 11,000, )0()0()0( )0()0(PBENPBENPBENPBENPpnnnnnnknkknnnnnnnknkkPBENPBENPBENPBENPp )1 ()1 ()1 ( )1 ()1 (, 11,000,計算機圖形學(xué)5252 )()()1 ()!) 1(!)!1()1 ()!1() 1()!1()!1()1)()1 ()!( !)(1,1, 1) 1() 1() 1(111,tBENtBENnttknknnttknknnttknttkknkntNBEnknkknkknkkknknknk計算機圖形學(xué)535

24、3nknkkknnnnnnnknknkktBENPPntBENPPtBENPPtBENPPntBENtBENPntp11, 111, 111, 1121, 00101,1, 1)()()()()()()()()()()()()0(01PPnp)() 1 (1nnPPnp計算機圖形學(xué)5454三次三次Bezier曲線段在起始點和終止點處的一階導(dǎo)數(shù)為：曲線段在起始點和終止點處的一階導(dǎo)數(shù)為：)(3) 1 ()(3)0(2301PPpPPp計算機圖形學(xué)5555 三次三次Bezier曲線段在起始點和終止點處的二階導(dǎo)數(shù)為：曲線段在起始點和終止點處的二階導(dǎo)數(shù)為：)()(1() 1 ()()(1()0(1120

25、112nnnnPPPPnnpPPPPnnp )2(6) 1 ()2(6)0(321210PPPpPPPp 計算機圖形學(xué)5656當(dāng)當(dāng)t=0時，時，當(dāng)當(dāng)t=1時，時，上式表明：上式表明：2階導(dǎo)矢只與相鄰的階導(dǎo)矢只與相鄰的3個頂點有關(guān)，事實上，個頂點有關(guān)，事實上，r階導(dǎo)階導(dǎo)矢只與（矢只與（r+1）個相鄰點有關(guān)，與更遠點無關(guān)。）個相鄰點有關(guān)，與更遠點無關(guān)。將將 、 及及 、 代入曲率公式代入曲率公式 ，可以得，可以得到到BezierBezier曲線在端點的曲率分別為：曲線在端點的曲率分別為：)2)(1() 0 (012PPPnnP)2)(1() 1 (21nnnPPPnnP)0(P)0(P) 1 (P

26、) 1 (P3)()()()(tPtPtPtk3011201)()(1) 0 (PPPPPPnnk31121)()(1) 1 (nnnnnnPPPPPPnnk計算機圖形學(xué)5757（4）對稱性。由控制頂點對稱性。由控制頂點 構(gòu)造出的新構(gòu)造出的新Bezier曲線，與原曲線，與原Bezier曲線形狀相同，走向相反。曲線形狀相同，走向相反。因為：因為：這個性質(zhì)說明這個性質(zhì)說明Bezier曲線在起點處有什么幾何性質(zhì)，曲線在起點處有什么幾何性質(zhì)，在終點處也有相同的性質(zhì)。在終點處也有相同的性質(zhì)。),.,1 , 0( ,*niPPinininininiininininniinniittBPtBPtBPtBPt

27、C000,0,* 1 , 0 ),1 ()1 ()()()(*計算機圖形學(xué)5858niininniininniiniPtBBPtBPtB0*, 00,0,)1 ()1 ()(n nn n0 0, ,- -i in nn ni i, ,i in n- -i i, ,n n0 0n nn n, ,n nn nn n, ,- -i in nn n- -i i, ,n ni in ni i, ,0 0t t) )P P( (1 1B Bt t) )P P( (1 1B Bt t) )P P( (1 1B Bt t) )P P( (1 1B B( (t t) )P PB B( (t t) )P PB B

28、( (t t) )P PB B( (t t) )P PP P( (t t) )計算機圖形學(xué)59（5）凸包性）凸包性由于由于 ，且，且 ，這一結(jié)果，這一結(jié)果說明當(dāng)說明當(dāng)t在在0，1區(qū)間變化時，對某一個區(qū)間變化時，對某一個t值，值，P(t)是特是特征多邊形各頂點的加權(quán)平均，權(quán)因子依次是征多邊形各頂點的加權(quán)平均，權(quán)因子依次是 。在。在幾何圖形上，意味著幾何圖形上，意味著Bezier曲線曲線P(t)在在 中各點是控中各點是控制點制點Pi i的凸線性組合，即曲線落在的凸線性組合，即曲線落在Pi i構(gòu)成的凸包之中，構(gòu)成的凸包之中，如下圖所示。如下圖所示。ninitB0,1)(), 1 , 0, 10( 1

29、)(0,nittBni)(,tBni 1 , 0t Bezier Bezier曲線的凸包性曲線的凸包性凸包凸包計算機圖形學(xué)6060（6）幾何不變性。這是指某些幾何特性不隨坐標(biāo)變）幾何不變性。這是指某些幾何特性不隨坐標(biāo)變換而變化的特性。換而變化的特性。Bezier曲線位置與形狀與其特征多曲線位置與形狀與其特征多邊形頂點邊形頂點 的位置有關(guān)，它不依賴坐標(biāo)系的選的位置有關(guān)，它不依賴坐標(biāo)系的選擇。擇。), 1 , 0(niPi計算機圖形學(xué)6161（7）變差縮減性。若）變差縮減性。若Bezier曲線的特征多邊形曲線的特征多邊形 是一個平面圖形，則平面內(nèi)任意直線與是一個平面圖形，則平面內(nèi)任意直線與C(t)

30、的交點個數(shù)的交點個數(shù)不多于該直線與其特征多邊形的交點個數(shù)，這一性質(zhì)叫不多于該直線與其特征多邊形的交點個數(shù)，這一性質(zhì)叫變差縮減性質(zhì)。此性質(zhì)反映了變差縮減性質(zhì)。此性質(zhì)反映了Bezier曲線比其特征多邊曲線比其特征多邊形的波動還小，也就是說形的波動還小，也就是說Bezier曲線比特征多邊形的折曲線比特征多邊形的折線更光順。線更光順。nPPP10計算機圖形學(xué)6262（8）仿射不變性）仿射不變性對于任意的仿射變換對于任意的仿射變換A：即在仿射變換下，的形式不變。即在仿射變換下，的形式不變。)()()(,0,tBPAtBPAtPAniininii計算機圖形學(xué)63631繪圖一段繪圖一段Bezier曲線曲線

31、利用定義式利用定義式Bezier曲線的繪制，可以利用其定義式，對參數(shù)曲線的繪制，可以利用其定義式，對參數(shù)t選取選取足夠多的值，計算曲線上的一些點，然后用折線連接足夠多的值，計算曲線上的一些點，然后用折線連接來近似畫出實際的曲線。隨著選取點增多，折線和曲來近似畫出實際的曲線。隨著選取點增多，折線和曲線可以任意接近。線可以任意接近。計算機圖形學(xué)6464knCnknknknCknkn 1)!( !1nknkknknkknknkktBENztztBENytytBENxtx0,0,0,)()(0,1 t )()()()(假設(shè)給定的四個型值點是假設(shè)給定的四個型值點是P0=(1，1)，Pl=(2，3)，P2

32、=(4，3)， P3=(3，1)，則計算結(jié)果見下表。，則計算結(jié)果見下表。計算機圖形學(xué)6565t(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é)6666計算機圖形學(xué)6767

33、利用曲線性質(zhì)（幾何作圖法和分裂法）利用曲線性質(zhì)（幾何作圖法和分裂法） 幾何作圖法幾何作圖法(de Casteljau算法算法)0P1P2P11P10P20PBezierBezier曲線上的點曲線上的點 拋物線三切線定理拋物線三切線定理計算機圖形學(xué)6868)3/1(30PP 0 01 11/31/3 幾何作圖法求幾何作圖法求BezierBezier曲線曲線 上一點（上一點（n=3n=3，t=1/3t=1/3）0P1P2P3P10P11P12P20P21P計算機圖形學(xué)6969基于基于Bezier曲線的討論，我們可以方便地可以給曲線的討論，我們可以方便地可以給出出Bezier曲面的定義和性質(zhì)，曲面的

34、定義和性質(zhì)，Bezier曲線的一些曲線的一些算法也可以很容易擴展到算法也可以很容易擴展到Bezier曲面的情況。曲面的情況。計算機圖形學(xué)70701Bezier曲面曲面定義：定義：0,10,1v)(u, )()(),(00,minjnjmijivBENuBENPvupBENi,m(u)與與BENj,n(v)是是Bernstein基函數(shù)：基函數(shù)： jnjjnnjimiimmivvCvBENuuCuBEN)1 ()()1 ()(,依次用線段連接點列中相鄰兩點所形成的空間網(wǎng)格，稱之為依次用線段連接點列中相鄰兩點所形成的空間網(wǎng)格，稱之為特征網(wǎng)格。特征網(wǎng)格。計算機圖形學(xué)7171計算機圖形學(xué)72720階連續(xù)

35、性只要求相連接的曲面片具有公共的邊界階連續(xù)性只要求相連接的曲面片具有公共的邊界曲線。曲線。1階連續(xù)性則要求在邊界曲線上的任何一點，兩個階連續(xù)性則要求在邊界曲線上的任何一點，兩個曲面片跨越邊界的切線矢量應(yīng)該共線，而且兩切線曲面片跨越邊界的切線矢量應(yīng)該共線，而且兩切線矢量的長度之比為常數(shù)。矢量的長度之比為常數(shù)。計算機圖形學(xué)7373如右圖如右圖所示，所示，設(shè)兩張設(shè)兩張mn次次Bezier曲面片曲面片分別由控制頂點分別由控制頂點 和和 定義。定義。)()(),()()(),(,00,00,vBuBQvuQvBuBPvuPnjminjmiijminjnjmiij 1 , 0, vuijPijQ),(vu

36、P),(vuQ)0 , 0(P) 1 , 0(P)0 , 1 (Q) 1 , 1 (Q)0 , 0()0 , 1 (QP ) 1 , 0() 1 , 1 (QP u uv v Bezier Bezier曲面片的拼接曲面片的拼接計算機圖形學(xué)7474 BezierBezier曲面片的拼接曲面片的拼接邊界線邊界線P0,0Q3,0P3,3(Q0,3)P0,3Q3,3P3,1(Q0,1)P3,0(Q0,0)P3,2(Q0,2)計算機圖形學(xué)7575Bezier曲線和曲面的不足：曲線和曲面的不足：Bezier曲線或曲面不能作局部修改；曲線或曲面不能作局部修改；Bezier曲線或曲面的拼接比較復(fù)雜曲線或曲面的

37、拼接比較復(fù)雜計算機圖形學(xué)7676 B B樣條曲線（構(gòu)造具有局部性的調(diào)和函數(shù)）樣條曲線（構(gòu)造具有局部性的調(diào)和函數(shù)） 給定給定n+1n+1個控制點個控制點P P0 0，P P1 1，P Pn n，它們所確定，它們所確定的的k k階階B B樣條曲線是：樣條曲線是： n n0 0i ii iP P( (u u) )k ki i, ,N NP P( (u u) )其中其中N Ni i，k k( (u u) )遞歸定義如下：遞歸定義如下： 計算機圖形學(xué)7777 這里這里u u0 0，u u1 1，u un n+ +k k，是一個，是一個非遞減非遞減的的序列，稱為節(jié)點，序列，稱為節(jié)點，( (u u0 0，u

38、 u1 1，u un n+ +k k) )稱為稱為節(jié)點向量節(jié)點向量。定義中可能出現(xiàn)。定義中可能出現(xiàn) ，這時約定，這時約定為為0 0。 n ni i1 1, ,0 0k k( (u u) ), ,1 1k k1 1, ,i iN N1 1i iu uk ki iu uu uk ki iu u( (u u) )1 1k ki i, ,N Ni iu u1 1k ki iu ui iu uu u( (u u) )k ki i, ,N N其其它它0 0, ,1 1k kn ni i, ,0 01 1i iu uu ui iu u1 1，( (u u) )i i, ,1 1N N0 00 0計算機圖形學(xué)

39、7878取取n=3，m=3，則，則n+m=6，不妨設(shè)節(jié)點矢量為：，不妨設(shè)節(jié)點矢量為：T=(0,1,2,3,4,5,6)： tNmtmktNmkttNtNmkmkmkk1, 11,1 ,11)( 01iti 1)(其它計算機圖形學(xué)79其它1t0 01)(1 , 0tN2t11t0 2 ) 1()2()( )()2()()(1 , 01 , 01 , 11 , 02, 0tttNtttNtNtttNtN計算機圖形學(xué)80803t2 )3(212t1 )3)(1(21)2(211t0 21 ) 1(23)(2 )(222, 01 , 03 , 0tttttt tNttNttN基函數(shù)由遞推轉(zhuǎn)換到直接定義

40、可以把不同段的時間進行移動基函數(shù)由遞推轉(zhuǎn)換到直接定義可以把不同段的時間進行移動例如：例如：t t在在22，3 3 設(shè)置為設(shè)置為 t=t-2t=t-2；依次改為；依次改為 t=t-1 t=t-1 ；t=tt=t注意順序顛倒。即注意順序顛倒。即t=t-2t=t-2變?yōu)樽優(yōu)镕 F0,3 0,3 。以下相同處理。以下相同處理。計算機圖形學(xué)81814t3 )4(213t2 )4)(2(21)3)(1(212t1 ) 1(21)(223 , 1tttttttN5t4 )5(214t3 )5)(3(21)4)(2(213t2 )2(21)(223 , 2tttttttN計算機圖形學(xué)82826t5 )6 (2

41、15t4 )6)(4(21)5)(3(214t3 ) 3(21)(223 , 3tttttttNt tB Bk k, ,3 3( (t t) )2 21 14 43 35 51 1 四段二次四段二次( (三階三階) )均勻均勻B樣條基函數(shù)樣條基函數(shù)N N0,30,3(t)(t)N N1,31,3(t)(t) N N2,32,3(t)(t)N N3,33,3(t)(t)計算機圖形學(xué)83831局部支柱性局部支柱性 B樣條的基函數(shù)是一個分段函數(shù)，其重要特征是樣條的基函數(shù)是一個分段函數(shù)，其重要特征是在在參數(shù)變化范圍內(nèi)，每個基函數(shù)在參數(shù)變化范圍內(nèi)，每個基函數(shù)在tk到到tk+m的子區(qū)間的子區(qū)間內(nèi)函數(shù)值不為

42、零，在其余區(qū)間內(nèi)均為零內(nèi)函數(shù)值不為零，在其余區(qū)間內(nèi)均為零，通常也，通常也將該特征稱為局部支柱性。將該特征稱為局部支柱性。計算機圖形學(xué)8484 B樣條曲線的局部支柱性樣條曲線的局部支柱性P P0 0P P1 1P P2 2P P3 3P4P4P P5 5P P6 6P P7 7P P4 4P4P4計算機圖形學(xué)8585B樣條的凸組合性和樣條的凸組合性和B樣條基函數(shù)的數(shù)值均大于樣條基函數(shù)的數(shù)值均大于或等于或等于0保證了保證了B樣條曲線的凸包性，即樣條曲線的凸包性，即B樣條曲樣條曲線必處在控制多邊形所形成的凸包之內(nèi)。線必處在控制多邊形所形成的凸包之內(nèi)。 t ,t t 1)(1n1 -m0,nkmktB

43、計算機圖形學(xué)8686 B樣條曲線與樣條曲線與 Bezier曲線的凸包性比較曲線的凸包性比較B B樣條曲線樣條曲線BezierBezier曲線曲線BezierBezier曲線曲線B B樣條曲線樣條曲線m=3m=3m=4m=4m=5m=5(a) B(a) B樣條曲線和樣條曲線和BezierBezier曲線的凸包比較曲線的凸包比較(b) B(b) B樣條曲線和樣條曲線和BezierBezier曲線的比較曲線的比較B B樣條凸包樣條凸包BezierBezier凸包凸包B B樣條凸包樣條凸包B B樣條凸包樣條凸包BezierBezier凸包凸包BezierBezier凸包凸包計算機圖形學(xué)8787定義：定

44、義：1212112212,00( , )( )( )nnk kk mkmkkp u vPNu Nv 控制頂點、控制網(wǎng)格（特征網(wǎng)格）、控制頂點、控制網(wǎng)格（特征網(wǎng)格）、B樣條基函數(shù)。樣條基函數(shù)。 B樣條曲面具有與樣條曲面具有與B樣條曲線相同的局部支柱性、凸包性、樣條曲線相同的局部支柱性、凸包性、連續(xù)性、幾何變換不變性等性質(zhì)。連續(xù)性、幾何變換不變性等性質(zhì)。計算機圖形學(xué)8888B樣條曲線包括其特例的樣條曲線包括其特例的Bezier曲線都不能精確表示出曲線都不能精確表示出拋物線外的二次曲線，拋物線外的二次曲線，B樣條曲面包括其特例的樣條曲面包括其特例的Bezier曲面都不能精確表示出拋物面外的二次曲面，

45、而只能曲面都不能精確表示出拋物面外的二次曲面，而只能給出近似表示。給出近似表示。提出提出NURBS方法，即非均勻有理方法，即非均勻有理B樣條方法主要是為樣條方法主要是為了找到與描述自由型曲線曲面的了找到與描述自由型曲線曲面的B樣條方法既相統(tǒng)一、樣條方法既相統(tǒng)一、又能精確表示二次曲線弧與二次曲面的數(shù)學(xué)方法。又能精確表示二次曲線弧與二次曲面的數(shù)學(xué)方法。計算機圖形學(xué)8989NURBS曲線的定義曲線的定義NURBS曲線是由分段有理曲線是由分段有理B樣條多項式基函數(shù)定義的樣條多項式基函數(shù)定義的nikiinikiinikiiitRPtNtNPtP0,0,0,)()()()(njkjjkiikitNtNtR

46、0,)()()(計算機圖形學(xué)9090Ri,k(t)具有具有k階階B樣條基函數(shù)類似的性質(zhì)：樣條基函數(shù)類似的性質(zhì)：局部支承性：局部支承性：Ri,k(t)=0，t ti, ti+k權(quán)性：權(quán)性：可微性：如果分母不為零，在節(jié)點區(qū)間內(nèi)是無限次可微性：如果分母不為零，在節(jié)點區(qū)間內(nèi)是無限次連續(xù)可微的，在節(jié)點處連續(xù)可微的，在節(jié)點處 (k-1-r)次連續(xù)可導(dǎo)，次連續(xù)可導(dǎo)，r是該節(jié)是該節(jié)點的重復(fù)度。點的重復(fù)度。若若 i=0，則，則Ri,k(t)=0；若若 i=+ ，則，則Ri,k(t)=1；nikiuR0,1)(計算機圖形學(xué)9191NURBS曲線與曲線與B樣條曲線具有類似的幾何樣條曲線具有類似的幾何性質(zhì)：性質(zhì)：局部

47、性質(zhì)。局部性質(zhì)。變差減小性質(zhì)。變差減小性質(zhì)。凸包性。凸包性。在仿射與透射變換下的不變性。在仿射與透射變換下的不變性。在曲線定義域內(nèi)有與有理基函數(shù)同樣的可微性。在曲線定義域內(nèi)有與有理基函數(shù)同樣的可微性。計算機圖形學(xué)9292如果某個權(quán)因子為零，那么相應(yīng)控制頂點對曲線沒如果某個權(quán)因子為零，那么相應(yīng)控制頂點對曲線沒有影響。有影響。若若 ，則當(dāng)，則當(dāng) 時，時，Bezier曲線曲線和和非有理非有理B樣條曲線樣條曲線是是NURBS曲線的特曲線的特殊情況殊情況i,kiitttiPtP)(計算機圖形學(xué)9393計算機圖形學(xué)9494NURBS曲面可由下面的有理參數(shù)多項式函曲面可由下面的有理參數(shù)多項式函數(shù)表示：數(shù)表示

48、： 1212121122121212112212,00,00( )( )( , )( )( )nnk kk kk mkmkknnk kk mkmkkwPNu Nvp u vwNu Nv計算機圖形學(xué)9595NURBS曲面可由下面的有理參數(shù)多項式函曲面可由下面的有理參數(shù)多項式函數(shù)表示：數(shù)表示：,0,0( )( )( )( )( )nkk mkkk mk mnjj mjp tP Rtw BtRtw Bt計算機圖形學(xué)9696既為自由型曲線曲面也為初等曲線曲面的精既為自由型曲線曲面也為初等曲線曲面的精確表示與設(shè)計提供了一個公共的數(shù)學(xué)形式，確表示與設(shè)計提供了一個公共的數(shù)學(xué)形式，因此，一個統(tǒng)一的數(shù)據(jù)庫就能夠

49、存儲這兩類因此，一個統(tǒng)一的數(shù)據(jù)庫就能夠存儲這兩類形狀信息。形狀信息。為了修改曲線曲面的形狀，既可以借助調(diào)整為了修改曲線曲面的形狀，既可以借助調(diào)整控制頂點，又可以利用權(quán)因子，因而具有較控制頂點，又可以利用權(quán)因子，因而具有較大的靈活性。大的靈活性。計算穩(wěn)定且速度快。計算穩(wěn)定且速度快。計算機圖形學(xué)9797NURBS有明確的幾何解釋，使得它對良好有明確的幾何解釋，使得它對良好的幾何知識尤其是畫法幾何知識的設(shè)計人員的幾何知識尤其是畫法幾何知識的設(shè)計人員特別有用。特別有用。NURBS具有強有力的幾何配套計算工具，具有強有力的幾何配套計算工具，包括節(jié)點插入與刪除、節(jié)點細分、升階、節(jié)包括節(jié)點插入與刪除、節(jié)點細

50、分、升階、節(jié)點分割等，能用于設(shè)計、分析與處理等各個點分割等，能用于設(shè)計、分析與處理等各個環(huán)節(jié)。環(huán)節(jié)。NURBS具有幾何和透視投影變換不變性。具有幾何和透視投影變換不變性。計算機圖形學(xué)9898NURBS是非有理是非有理B樣條形式以及有理與非有理樣條形式以及有理與非有理Bezier形式的合適的推廣。形式的合適的推廣。需要額外的存儲以定義傳統(tǒng)的曲線曲面。需要額外的存儲以定義傳統(tǒng)的曲線曲面。權(quán)因子的不合適應(yīng)用可能導(dǎo)致很壞的參數(shù)化，甚權(quán)因子的不合適應(yīng)用可能導(dǎo)致很壞的參數(shù)化，甚至毀掉隨后的曲面結(jié)構(gòu)。至毀掉隨后的曲面結(jié)構(gòu)。某些技術(shù)用傳統(tǒng)形式比用某些技術(shù)用傳統(tǒng)形式比用NURBS工作得更好。例工作得更好。例如，

51、曲面與曲面求交時，如，曲面與曲面求交時，NURBS方法特別難于處方法特別難于處理剛好接觸的情況。理剛好接觸的情況。某些基本算法，例如求反曲線曲面上的點的參數(shù)某些基本算法，例如求反曲線曲面上的點的參數(shù)值，存在數(shù)值不穩(wěn)定問題。值，存在數(shù)值不穩(wěn)定問題。由簡單的物體來構(gòu)成復(fù)雜的物體由簡單的物體來構(gòu)成復(fù)雜的物體掃描表示掃描表示結(jié)構(gòu)實體幾何法結(jié)構(gòu)實體幾何法計算機圖形學(xué)9999思想：思想： 通過平移、旋轉(zhuǎn)及其他對稱變換來構(gòu)造通過平移、旋轉(zhuǎn)及其他對稱變換來構(gòu)造三維對象三維對象 通過指定一個二維形狀以及在空間區(qū)域通過指定一個二維形狀以及在空間區(qū)域內(nèi)移動該形狀的掃描來描述該三維物體內(nèi)移動該形狀的掃描來描述該三維物

52、體計算機圖形學(xué)100100zoyxA平移掃描平移掃描 二維圖形二維圖形A沿沿Z軸平移軸平移計算機圖形學(xué)101101旋轉(zhuǎn)掃描旋轉(zhuǎn)掃描 二維圖形二維圖形A繞繞Z軸旋軸旋轉(zhuǎn)轉(zhuǎn)zByxA計算機圖形學(xué)102102思想思想 通過對兩個指定三維通過對兩個指定三維對象進行并、交或差對象進行并、交或差等集合操作產(chǎn)生一個等集合操作產(chǎn)生一個新的三維對象新的三維對象 計算機圖形學(xué)103物體物體A和和B差差并并交交差差計算機圖形學(xué)104104分層樹形結(jié)構(gòu)，稱為八叉樹。分層樹形結(jié)構(gòu)，稱為八叉樹。思想思想 利用實體的空間相關(guān)性利用實體的空間相關(guān)性優(yōu)點優(yōu)點減少了三維物體的存儲需求減少了三維物體的存儲需求提供了存儲有關(guān)物體內(nèi)部

53、信息的方便表示提供了存儲有關(guān)物體內(nèi)部信息的方便表示計算機圖形學(xué)105105四叉樹四叉樹二維平面二維平面三維空間三維空間八叉樹八叉樹計算機圖形學(xué)106106四叉樹四叉樹數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)思想思想 同質(zhì)象限同質(zhì)象限10231023計算機圖形學(xué)107107用于用于二維平面二維平面的分解的分解對二維區(qū)域?qū)ΧS區(qū)域遞歸地等分遞歸地等分4個小正方形，這個分解過個小正方形，這個分解過程可表示為一棵樹，除葉節(jié)點，其每個節(jié)點都有四程可表示為一棵樹，除葉節(jié)點，其每個節(jié)點都有四個分支，分別表示個分支，分別表示4個小正方形個小正方形若小正方形是同質(zhì)的，則不必再分解；若小正方形是同質(zhì)的，則不必再分解；若小正方形是非同質(zhì)的

54、，則需將它再一分為四若小正方形是非同質(zhì)的，則需將它再一分為四分解是遞歸的。分解是遞歸的。計算機圖形學(xué)108108例例3120312001230132計算機圖形學(xué)109109312456132519241820212223711 12891014151617具有子孫的節(jié)點具有子孫的節(jié)點空節(jié)點空節(jié)點實節(jié)點實節(jié)點245139 107811 12314 15 20 21 16 17 22 23 18 19 24 2516計算機圖形學(xué)110110計算機圖形學(xué)111111四叉樹四叉樹二維圖的四叉樹表示二維圖的四叉樹表示三維形體的分解三維形體的分解對三維空間進行前后、左右、上下等分為對三維空間進行前后、左右

55、、上下等分為8個小個小立方體，立方體，小立方體單元均質(zhì)，則停止分解；小立方體單元均質(zhì)，則停止分解；小立方體單元非均質(zhì)，需進一步分解為小立方體單元非均質(zhì)，需進一步分解為8個子立個子立方體方體直至所有小立方體單元均質(zhì)，或已分解到規(guī)定的直至所有小立方體單元均質(zhì)，或已分解到規(guī)定的分解精度為止。分解精度為止。計算機圖形學(xué)112112236720131375具有子孫的節(jié)點具有子孫的節(jié)點空節(jié)點空節(jié)點實節(jié)點實節(jié)點計算機圖形學(xué)113113計算機圖形學(xué)114114二叉空間分割（二叉空間分割（Binary Space Partitioning，BSP）樹方法是一種類似于）樹方法是一種類似于八叉樹的空間分割方法，它每

56、次將一實體用八叉樹的空間分割方法，它每次將一實體用任一位置和任一方向的平面分為二部分（不任一位置和任一方向的平面分為二部分（不同于八叉樹方法的每次將實體用平行于笛卡同于八叉樹方法的每次將實體用平行于笛卡爾坐標(biāo)平面的三個兩兩垂直的平面分割）。爾坐標(biāo)平面的三個兩兩垂直的平面分割）。歐氏幾何法歐氏幾何法&分形幾何法分形幾何法分形基本特征分形基本特征分形生成過程分形生成過程分形分類分形分類分形維數(shù)概念分形維數(shù)概念計算機圖形學(xué)115115Euclidean - Geometry Methods - use equations to describe objects which have smoo

57、th surfaces and regular shapes.Fractal - Geometry Methods - use procedures to model natural objects which have irregular or fragmented features.歐氏幾何法歐氏幾何法&分形幾何法分形幾何法計算機圖形學(xué)116116infinite detail at every point 每點具有無限細節(jié)每點具有無限細節(jié)self-similarity between the object parts and the overall features 對象整體和局部之間對象整體和局部之間的自相似性的自相似性利用一個過程來描述分形物體，利用一個過程來描述分形物體，該過程為產(chǎn)生物體局部細節(jié)指定該過程為產(chǎn)生物