計(jì)算機(jī)圖形學(xué)第八章三維對(duì)象的表示

1、第第8章章 三維對(duì)象的表示三維對(duì)象的表示內(nèi)容提要內(nèi)容提要n表示方法表示方法n多邊形表面（多邊形表面（Polygon Surfaces）n曲線(xiàn)曲面曲線(xiàn)曲面: Bzier曲線(xiàn)曲線(xiàn)n實(shí)體構(gòu)造技術(shù)實(shí)體構(gòu)造技術(shù)n八叉樹(shù)（八叉樹(shù)（Octrees）n分形（分形（Fractal ）n表示方法表示方法n圖形三維對(duì)象類(lèi)型不同、材質(zhì)表面也不同，不存在某一種方圖形三維對(duì)象類(lèi)型不同、材質(zhì)表面也不同，不存在某一種方法可以描述不同的物質(zhì)的所有特征對(duì)象法可以描述不同的物質(zhì)的所有特征對(duì)象n多邊形多邊形和和二次曲面二次曲面能夠?yàn)橹T如多面體和橢圓體等歐式對(duì)象提能夠?yàn)橹T如多面體和橢圓體等歐式對(duì)象提供精確的描述供精確的描述n樣條曲面樣

2、條曲面和和實(shí)體幾何構(gòu)造技術(shù)實(shí)體幾何構(gòu)造技術(shù)可用于設(shè)計(jì)機(jī)翼、齒輪及其它可用于設(shè)計(jì)機(jī)翼、齒輪及其它具有曲面的工程結(jié)構(gòu)具有曲面的工程結(jié)構(gòu)n過(guò)程式的方法過(guò)程式的方法如如分形結(jié)構(gòu)分形結(jié)構(gòu)和和微粒系統(tǒng)微粒系統(tǒng)用來(lái)建立地形、云、草用來(lái)建立地形、云、草叢和其它自然景物的模型叢和其它自然景物的模型n運(yùn)用運(yùn)用相互作用力的基于物理的建模方法相互作用力的基于物理的建模方法，可描述一塊布或一，可描述一塊布或一個(gè)膠狀球的非剛體行為個(gè)膠狀球的非剛體行為n八叉樹(shù)編碼八叉樹(shù)編碼可用于表示對(duì)象的內(nèi)部特征，如醫(yī)用可用于表示對(duì)象的內(nèi)部特征，如醫(yī)用CT映像映像n等值面顯示等值面顯示、體繪制體繪制或或其它可視化技術(shù)其它可視化技術(shù)可應(yīng)用到

3、三維離散數(shù)可應(yīng)用到三維離散數(shù)據(jù)集，從而獲得數(shù)據(jù)的可視表示據(jù)集，從而獲得數(shù)據(jù)的可視表示表示方法表示方法n三維對(duì)象表示方法通?？煞譃槿S對(duì)象表示方法通?？煞譃?類(lèi)類(lèi)u邊界表示邊界表示（Boundary representations）p使用一組曲面來(lái)描述三維對(duì)象，這些曲面將對(duì)象分為使用一組曲面來(lái)描述三維對(duì)象，這些曲面將對(duì)象分為內(nèi)部和外部?jī)?nèi)部和外部p典型例子：多邊形平面和樣條曲面典型例子：多邊形平面和樣條曲面u空間區(qū)分表示空間區(qū)分表示（Space-partitioning representations）p用來(lái)描述內(nèi)部性質(zhì)，將包含一個(gè)對(duì)象的空間區(qū)域分成用來(lái)描述內(nèi)部性質(zhì)，將包含一個(gè)對(duì)象的空間區(qū)域分成一

4、組較小的、非重疊的連續(xù)實(shí)體（通常是立方體）一組較小的、非重疊的連續(xù)實(shí)體（通常是立方體）p三維對(duì)象的一般空間劃分描述是三維對(duì)象的一般空間劃分描述是八叉樹(shù)表示八叉樹(shù)表示邊界表示方法邊界表示方法-圖示圖示空間區(qū)分表示方法空間區(qū)分表示方法-圖示圖示小立方體小立方體(i, j, k)kij內(nèi)容提要內(nèi)容提要n表示方法表示方法n多邊形表面多邊形表面（Polygon Surfaces）n曲線(xiàn)曲面曲線(xiàn)曲面: Bzier曲線(xiàn)曲線(xiàn)n實(shí)體構(gòu)造技術(shù)實(shí)體構(gòu)造技術(shù)n八叉樹(shù)（八叉樹(shù)（Octrees）n分形（分形（Fractal ）n多邊形表面多邊形表面n三維圖形中三維圖形中運(yùn)用邊界表示的最普遍方式運(yùn)用邊界表示的最普遍方式是是

5、使用一組使用一組包圍物體內(nèi)部的表面多邊形包圍物體內(nèi)部的表面多邊形n很多圖形系統(tǒng)以一組表面多邊形來(lái)存儲(chǔ)物體的描述很多圖形系統(tǒng)以一組表面多邊形來(lái)存儲(chǔ)物體的描述u用線(xiàn)性方程描述所有表面，因而會(huì)簡(jiǎn)化并且加速物體的表用線(xiàn)性方程描述所有表面，因而會(huì)簡(jiǎn)化并且加速物體的表面繪制和顯示面繪制和顯示n某些情況下，多邊形表示是惟一可用的某些情況下，多邊形表示是惟一可用的u很多圖形包也允許以其它方式描述物體很多圖形包也允許以其它方式描述物體p如樣條曲面，將它轉(zhuǎn)換到多邊形表示后加以處理如樣條曲面，將它轉(zhuǎn)換到多邊形表示后加以處理多邊形描述多邊形描述因此被稱(chēng)為因此被稱(chēng)為標(biāo)準(zhǔn)圖形對(duì)象標(biāo)準(zhǔn)圖形對(duì)象n可以為覆蓋對(duì)象表面的可以為覆

6、蓋對(duì)象表面的每一多邊形給出一組頂點(diǎn)每一多邊形給出一組頂點(diǎn)，以便使，以便使用一組多邊形面片描述一個(gè)對(duì)象用一組多邊形面片描述一個(gè)對(duì)象u這些面片的頂點(diǎn)坐標(biāo)和邊的信息以及每一多邊形的表面法向量等其這些面片的頂點(diǎn)坐標(biāo)和邊的信息以及每一多邊形的表面法向量等其它信息存入一張表中（參見(jiàn)它信息存入一張表中（參見(jiàn)P106的的3.15節(jié)）節(jié)）n有些圖形軟件提供生成有些圖形軟件提供生成由三角形或四邊形組成的多邊形網(wǎng)由三角形或四邊形組成的多邊形網(wǎng)的子程序的子程序n有些軟件提供有些軟件提供用多邊形面片顯示立方體、球體或圓柱體等用多邊形面片顯示立方體、球體或圓柱體等普通形狀普通形狀的子程序的子程序n多邊形表面數(shù)據(jù)分為兩組進(jìn)

7、行組織多邊形表面數(shù)據(jù)分為兩組進(jìn)行組織u幾何表幾何表：頂點(diǎn)坐標(biāo)和用來(lái)標(biāo)識(shí)多邊形表面空間方向的參數(shù)：頂點(diǎn)坐標(biāo)和用來(lái)標(biāo)識(shí)多邊形表面空間方向的參數(shù)u屬性表屬性表：指明物體透明度及表面反射度的參數(shù)和紋理特征：指明物體透明度及表面反射度的參數(shù)和紋理特征多邊形表面多邊形表面多邊形表面多邊形表面示例示例頂點(diǎn)表頂點(diǎn)表序號(hào)序號(hào)點(diǎn)坐標(biāo)點(diǎn)坐標(biāo)1x1, y1, z12x2, y2, z23x3, y3, z34x4, y4, z45x5, y5, z5邊表邊表序號(hào)序號(hào)頂點(diǎn)號(hào)頂點(diǎn)號(hào)1v1, v22v2, v33v3, v14v3, v45v4, v56v5, v1多邊形面表多邊形面表序號(hào)序號(hào)邊序號(hào)邊序號(hào)S1E1, E2,

8、 E3S2E3, E4, E5, E6E1E2E4E5S1v2v1v3v4v5E3E6S2多邊形表面多邊形表面（Polygon Surfaces）n多邊形多邊形網(wǎng)格網(wǎng)格 圖形系圖形系統(tǒng)一般統(tǒng)一般使用使用多多邊形網(wǎng)邊形網(wǎng)格格對(duì)對(duì)3D物體進(jìn)物體進(jìn)行建模行建模多邊形網(wǎng)格多邊形網(wǎng)格內(nèi)容提要內(nèi)容提要n表示方法表示方法n多邊形表面（多邊形表面（Polygon Surfaces）n曲線(xiàn)曲面曲線(xiàn)曲面: Bzier曲線(xiàn)曲線(xiàn)n實(shí)體構(gòu)造技術(shù)實(shí)體構(gòu)造技術(shù)n八叉樹(shù)（八叉樹(shù)（Octrees）n分形（分形（Fractal ）n曲線(xiàn)和曲面曲線(xiàn)和曲面n曲面邊界對(duì)象的等式可用參數(shù)或非參數(shù)形式表示曲面邊界對(duì)象的等式可用參數(shù)或非參數(shù)

9、形式表示n計(jì)算機(jī)圖形應(yīng)用中對(duì)象的描述一般都用多邊形網(wǎng)格來(lái)近似表計(jì)算機(jī)圖形應(yīng)用中對(duì)象的描述一般都用多邊形網(wǎng)格來(lái)近似表示其表面示其表面u這些對(duì)象包括二次曲面、超二次曲面、多項(xiàng)式和指數(shù)函數(shù)及樣條曲面這些對(duì)象包括二次曲面、超二次曲面、多項(xiàng)式和指數(shù)函數(shù)及樣條曲面n曲線(xiàn)曲面的生成方法曲線(xiàn)曲面的生成方法u由給定的一組數(shù)學(xué)函數(shù)生成由給定的一組數(shù)學(xué)函數(shù)生成u由給定的一組數(shù)據(jù)生成由給定的一組數(shù)據(jù)生成n一旦給定函數(shù)，圖形包將指定曲線(xiàn)方程投影到顯示平面上，一旦給定函數(shù)，圖形包將指定曲線(xiàn)方程投影到顯示平面上，且沿著投影函數(shù)路徑繪制像素位置且沿著投影函數(shù)路徑繪制像素位置n由函數(shù)式描述而生成的顯示曲面的例子有由函數(shù)式描述而

10、生成的顯示曲面的例子有二次曲面二次曲面和和超二次超二次曲面曲面 (P.334 - P.337)nOpenGL二次和三次曲面函數(shù)二次和三次曲面函數(shù)(P.337-P.341)二次曲面二次曲面n這類(lèi)物體由二次曲面的表達(dá)式（二次方程）生成。包括球面、這類(lèi)物體由二次曲面的表達(dá)式（二次方程）生成。包括球面、橢球面、環(huán)面、拋物面和雙曲面橢球面、環(huán)面、拋物面和雙曲面n球面球面u在笛卡爾坐標(biāo)系中，中心在原點(diǎn)、半徑為在笛卡爾坐標(biāo)系中，中心在原點(diǎn)、半徑為r的球面定義為滿(mǎn)的球面定義為滿(mǎn)足方程足方程x2+y2+z2=r2的點(diǎn)集的點(diǎn)集(x, y, z)n橢球面橢球面u橢球面可看作球面的擴(kuò)展：橢球面可看作球面的擴(kuò)展：3條相

11、互垂直的半徑具有不同值條相互垂直的半徑具有不同值u中心在原點(diǎn)的橢球面的笛卡爾表達(dá)式為中心在原點(diǎn)的橢球面的笛卡爾表達(dá)式為1222zyxrzryrx二次曲面二次曲面n環(huán)面：汽車(chē)輪胎狀的對(duì)象稱(chēng)為環(huán)面：汽車(chē)輪胎狀的對(duì)象稱(chēng)為環(huán)面環(huán)面或或錨狀環(huán)錨狀環(huán)u通常被描述為將圓或橢圓繞該二次曲線(xiàn)（圓或橢圓）之通常被描述為將圓或橢圓繞該二次曲線(xiàn)（圓或橢圓）之外的一個(gè)共面軸旋轉(zhuǎn)而得到的表面外的一個(gè)共面軸旋轉(zhuǎn)而得到的表面u環(huán)面的定義參數(shù)是該二次曲線(xiàn)中心到旋轉(zhuǎn)軸之間的距離環(huán)面的定義參數(shù)是該二次曲線(xiàn)中心到旋轉(zhuǎn)軸之間的距離以及該二次曲線(xiàn)的尺寸以及該二次曲線(xiàn)的尺寸raxialrzy0(0,y,z)y0 x(x,y,z)u圖圖1所

12、示圓的方程為所示圓的方程為(y-raxial)2+z2=r2。將該圓繞。將該圓繞z軸旋轉(zhuǎn)即可軸旋轉(zhuǎn)即可生成圖生成圖2所示的環(huán)面，其方程為所示的環(huán)面，其方程為圖圖1 圓的方程圓的方程圖圖2 環(huán)面的頂視圖環(huán)面的頂視圖22222rzryxaxial超二次曲面超二次曲面n超二次曲面通過(guò)將額外參數(shù)插入二次方程形成超二次曲面通過(guò)將額外參數(shù)插入二次方程形成n超橢圓超橢圓u在橢圓方程中，允許在橢圓方程中，允許x和和y項(xiàng)的指數(shù)為變量，即得超橢圓項(xiàng)的指數(shù)為變量，即得超橢圓的笛卡爾表達(dá)式的笛卡爾表達(dá)式122sysxryrxn超橢球面超橢球面u超橢球面的笛卡爾表達(dá)式通過(guò)在橢球面方程中增加超橢球面的笛卡爾表達(dá)式通過(guò)在橢

13、球面方程中增加2個(gè)指?jìng)€(gè)指數(shù)參數(shù)得到數(shù)參數(shù)得到111222222szsssysxrzryrx超橢圓形狀如超橢圓形狀如P336圖圖8.6所示所示超橢球面形狀如超橢球面形狀如P337圖圖8.7所示所示柔性對(duì)象柔性對(duì)象n柔性對(duì)象指在柔性對(duì)象指在一定運(yùn)動(dòng)狀態(tài)下一定運(yùn)動(dòng)狀態(tài)下或在或在它們接近其它對(duì)象時(shí)它們接近其它對(duì)象時(shí)會(huì)會(huì)改改變其表面形狀變其表面形狀的對(duì)象。它們的曲面表面很難用的對(duì)象。它們的曲面表面很難用常規(guī)形狀常規(guī)形狀表示表示u例如：分子形狀在獨(dú)立存在時(shí)可用球形描述，它接近其例如：分子形狀在獨(dú)立存在時(shí)可用球形描述，它接近其它分子時(shí)會(huì)改變其本身的形狀（它分子時(shí)會(huì)改變其本身的形狀（P342圖圖8.9）drd

14、rddrdrbdrbrf330,0)1(23)31()(222p軟對(duì)象模型軟對(duì)象模型使用如下函使用如下函數(shù)表示數(shù)表示p元球模型元球模型將混合對(duì)象看成幾將混合對(duì)象看成幾個(gè)二次密度函數(shù)的復(fù)合形式個(gè)二次密度函數(shù)的復(fù)合形式drdrdrdrdrrf0,0949179221)(664422n樣條的歷史樣條的歷史u很早的繪圖員利用很早的繪圖員利用“ducks”和有柔性和有柔性的木條（樣條）來(lái)繪制曲線(xiàn)的木條（樣條）來(lái)繪制曲線(xiàn)u木質(zhì)的樣條具有二階連續(xù)木質(zhì)的樣條具有二階連續(xù)u并且通過(guò)所有的控制點(diǎn)并且通過(guò)所有的控制點(diǎn)樣條表示樣條表示A Duck (weight)Ducks trace out curven樣條：通過(guò)

15、一組指定點(diǎn)集而生成平滑曲樣條：通過(guò)一組指定點(diǎn)集而生成平滑曲線(xiàn)的柔性帶線(xiàn)的柔性帶n樣條曲線(xiàn)在計(jì)算機(jī)圖形學(xué)中的含義樣條曲線(xiàn)在計(jì)算機(jī)圖形學(xué)中的含義u由多項(xiàng)式曲線(xiàn)段連接而成的曲線(xiàn)由多項(xiàng)式曲線(xiàn)段連接而成的曲線(xiàn)u在每段的在每段的邊界處邊界處滿(mǎn)足特定的連續(xù)性條件滿(mǎn)足特定的連續(xù)性條件n樣條曲面樣條曲面u使用使用2組組正交樣條曲線(xiàn)正交樣條曲線(xiàn)進(jìn)行描述進(jìn)行描述n樣條在圖形學(xué)中的應(yīng)用樣條在圖形學(xué)中的應(yīng)用u設(shè)計(jì)曲線(xiàn)、曲面設(shè)計(jì)曲線(xiàn)、曲面u汽車(chē)車(chē)身設(shè)計(jì)、飛機(jī)和航天飛機(jī)表面的設(shè)計(jì)、船體設(shè)計(jì)汽車(chē)車(chē)身設(shè)計(jì)、飛機(jī)和航天飛機(jī)表面的設(shè)計(jì)、船體設(shè)計(jì)以及家庭應(yīng)用以及家庭應(yīng)用樣條表示樣條表示n曲線(xiàn)的產(chǎn)生曲線(xiàn)的產(chǎn)生u給定一組離散的坐標(biāo)點(diǎn)（控

16、制點(diǎn)），采用給定一組離散的坐標(biāo)點(diǎn)（控制點(diǎn)），采用插值插值或或逼近逼近方方法之一選取分段連續(xù)參數(shù)多項(xiàng)式函數(shù)，將數(shù)據(jù)集擬合成法之一選取分段連續(xù)參數(shù)多項(xiàng)式函數(shù)，將數(shù)據(jù)集擬合成指定的曲線(xiàn)函數(shù)指定的曲線(xiàn)函數(shù)u根據(jù)曲線(xiàn)函數(shù)得到曲線(xiàn)的圖形根據(jù)曲線(xiàn)函數(shù)得到曲線(xiàn)的圖形n曲線(xiàn)的類(lèi)型曲線(xiàn)的類(lèi)型u插值插值樣條曲線(xiàn)：選取的多樣條曲線(xiàn)：選取的多項(xiàng)式使得曲線(xiàn)通過(guò)每個(gè)控項(xiàng)式使得曲線(xiàn)通過(guò)每個(gè)控制點(diǎn)制點(diǎn)u逼近逼近樣條曲線(xiàn)：選取的多樣條曲線(xiàn)：選取的多項(xiàng)式不一定使曲線(xiàn)通過(guò)每項(xiàng)式不一定使曲線(xiàn)通過(guò)每個(gè)控制點(diǎn)個(gè)控制點(diǎn)樣條表示樣條表示插值插值逼近逼近n插值曲線(xiàn)插值曲線(xiàn)通常用于數(shù)值化繪通常用于數(shù)值化繪圖或指定動(dòng)畫(huà)路徑圖或指定動(dòng)畫(huà)路徑n逼近曲線(xiàn)

17、逼近曲線(xiàn)一般作為設(shè)計(jì)工具一般作為設(shè)計(jì)工具來(lái)構(gòu)造對(duì)象形體來(lái)構(gòu)造對(duì)象形體凸殼凸殼n凸殼（凸殼（Convex hull）u包含一組控制點(diǎn)的凸多邊形邊界包含一組控制點(diǎn)的凸多邊形邊界n將二維曲線(xiàn)的凸殼形狀設(shè)想成一個(gè)圍繞控制點(diǎn)位置的拉緊的將二維曲線(xiàn)的凸殼形狀設(shè)想成一個(gè)圍繞控制點(diǎn)位置的拉緊的橡皮筋，使每個(gè)控制點(diǎn)在凸殼的邊界上或者凸殼內(nèi)（如下圖）橡皮筋，使每個(gè)控制點(diǎn)在凸殼的邊界上或者凸殼內(nèi)（如下圖）n凸殼的作用凸殼的作用u提供了曲線(xiàn)或曲面與包圍控制點(diǎn)的區(qū)域之間的偏差的測(cè)量提供了曲線(xiàn)或曲面與包圍控制點(diǎn)的區(qū)域之間的偏差的測(cè)量u以凸殼為界的樣條保證了多項(xiàng)式沿控制點(diǎn)的平滑前進(jìn)以凸殼為界的樣條保證了多項(xiàng)式沿控制點(diǎn)的平滑

18、前進(jìn)凸殼凸殼曲線(xiàn)的控制圖曲線(xiàn)的控制圖n對(duì)于逼近樣條，連接控制點(diǎn)序列的折線(xiàn)通常會(huì)顯示出來(lái)，以對(duì)于逼近樣條，連接控制點(diǎn)序列的折線(xiàn)通常會(huì)顯示出來(lái)，以提醒設(shè)計(jì)者控制點(diǎn)的順序。這組連接線(xiàn)通常稱(chēng)為提醒設(shè)計(jì)者控制點(diǎn)的順序。這組連接線(xiàn)通常稱(chēng)為曲線(xiàn)的控制曲線(xiàn)的控制圖圖n該控制圖還可稱(chēng)為該控制圖還可稱(chēng)為控制多邊形控制多邊形或或特征多邊形特征多邊形n為保證分段參數(shù)曲線(xiàn)從一段到另一段平滑過(guò)渡，可在連接點(diǎn)為保證分段參數(shù)曲線(xiàn)從一段到另一段平滑過(guò)渡，可在連接點(diǎn)處要求各種連續(xù)性條件處要求各種連續(xù)性條件n參數(shù)參數(shù)連續(xù)性條件：兩個(gè)相鄰曲線(xiàn)段在相交處的參數(shù)導(dǎo)數(shù)連續(xù)性條件：兩個(gè)相鄰曲線(xiàn)段在相交處的參數(shù)導(dǎo)數(shù)相等相等u零階連續(xù)零階連續(xù)(

19、C0連續(xù)連續(xù))：簡(jiǎn)單地表示曲線(xiàn)：簡(jiǎn)單地表示曲線(xiàn)連接連接u一階連續(xù)一階連續(xù)(C1連續(xù)連續(xù))：說(shuō)明代表兩個(gè)相鄰曲線(xiàn)的方程在相交：說(shuō)明代表兩個(gè)相鄰曲線(xiàn)的方程在相交點(diǎn)處有點(diǎn)處有相同的一階導(dǎo)數(shù)相同的一階導(dǎo)數(shù)（切線(xiàn)）（切線(xiàn)）u二階連續(xù)二階連續(xù)(C2連續(xù)連續(xù))：兩個(gè)曲線(xiàn)段在交點(diǎn)處有：兩個(gè)曲線(xiàn)段在交點(diǎn)處有相同的一階和相同的一階和二階導(dǎo)數(shù)二階導(dǎo)數(shù)，交點(diǎn)處的切向量變化率相等，交點(diǎn)處的切向量變化率相等參數(shù)連續(xù)性條件參數(shù)連續(xù)性條件F(u)f(u)F(1)=f(0)零階連續(xù)零階連續(xù)F(1)=f(0)一階連續(xù)一階連續(xù)F (1)=f (0)二階連續(xù)二階連續(xù)n幾何幾何連續(xù)性條件連續(xù)性條件 兩個(gè)相鄰曲線(xiàn)段在相交處的參數(shù)導(dǎo)數(shù)兩個(gè)

20、相鄰曲線(xiàn)段在相交處的參數(shù)導(dǎo)數(shù)成比例成比例u零階連續(xù)（零階連續(xù)（G0連續(xù)）：與連續(xù)）：與0階參數(shù)連續(xù)性相同，即兩個(gè)曲階參數(shù)連續(xù)性相同，即兩個(gè)曲線(xiàn)必在公共點(diǎn)處有線(xiàn)必在公共點(diǎn)處有相同的坐標(biāo)相同的坐標(biāo)u一階連續(xù)（一階連續(xù)（G1連續(xù)）：表示連續(xù)）：表示一階導(dǎo)數(shù)一階導(dǎo)數(shù)在兩個(gè)相鄰曲線(xiàn)的在兩個(gè)相鄰曲線(xiàn)的交點(diǎn)處交點(diǎn)處成比例成比例u二階連續(xù)（二階連續(xù)（G2連續(xù)）：表示兩個(gè)曲線(xiàn)段在相交處的一階連續(xù)）：表示兩個(gè)曲線(xiàn)段在相交處的一階和二階導(dǎo)數(shù)均和二階導(dǎo)數(shù)均成比例成比例幾何連續(xù)性條件幾何連續(xù)性條件樣條描述樣條描述n給定多項(xiàng)式的階和控制點(diǎn)位置后，指定一個(gè)具體的樣條表達(dá)給定多項(xiàng)式的階和控制點(diǎn)位置后，指定一個(gè)具體的樣條表達(dá)式

21、有式有3個(gè)等價(jià)方法個(gè)等價(jià)方法u列出一組加在樣條上的邊界條件列出一組加在樣條上的邊界條件u列出描述樣條特征的行列式列出描述樣條特征的行列式u列出一組混合函數(shù)或基函數(shù)，確定如何組合指定的曲線(xiàn)幾列出一組混合函數(shù)或基函數(shù)，確定如何組合指定的曲線(xiàn)幾何約束，以計(jì)算曲線(xiàn)路徑上的位置何約束，以計(jì)算曲線(xiàn)路徑上的位置n樣條曲面樣條曲面u使用某空間區(qū)域中一個(gè)控制點(diǎn)網(wǎng)指定使用某空間區(qū)域中一個(gè)控制點(diǎn)網(wǎng)指定2組正交的樣條曲線(xiàn)，組正交的樣條曲線(xiàn)，來(lái)定義一個(gè)樣條曲面來(lái)定義一個(gè)樣條曲面n修剪樣條曲面修剪樣條曲面u圖形軟件包常提供生成修剪曲線(xiàn)的函數(shù)，在樣條曲線(xiàn)上挖圖形軟件包常提供生成修剪曲線(xiàn)的函數(shù)，在樣條曲線(xiàn)上挖去一部分去一部分

22、n插值樣條曲線(xiàn)（三次樣條插值）插值樣條曲線(xiàn)（三次樣條插值）u自然三次樣條插值自然三次樣條插值uHermite樣條插值樣條插值uCardinal樣條插值樣條插值uKochanek_Bartels樣條插值樣條插值n逼近逼近樣條曲線(xiàn)樣條曲線(xiàn)uBezier曲線(xiàn)曲線(xiàn)uB_樣條曲線(xiàn)樣條曲線(xiàn)生成樣條曲線(xiàn)的方法生成樣條曲線(xiàn)的方法插值樣條曲線(xiàn)（三次樣條插值）插值樣條曲線(xiàn)（三次樣條插值）n三次樣條插值方法大多用于建立對(duì)象運(yùn)動(dòng)路徑或提供實(shí)體表三次樣條插值方法大多用于建立對(duì)象運(yùn)動(dòng)路徑或提供實(shí)體表示和動(dòng)畫(huà)，插值樣條有時(shí)也用來(lái)設(shè)計(jì)物體形狀示和動(dòng)畫(huà)，插值樣條有時(shí)也用來(lái)設(shè)計(jì)物體形狀n三次多項(xiàng)式在靈活性和計(jì)算速度之間提供了一個(gè)

23、合理的三次多項(xiàng)式在靈活性和計(jì)算速度之間提供了一個(gè)合理的折中折中方案方案：比更高次多項(xiàng)式需要：比更高次多項(xiàng)式需要更少的計(jì)算和存儲(chǔ)空間更少的計(jì)算和存儲(chǔ)空間，模擬任，模擬任意曲線(xiàn)形狀時(shí)比低次多項(xiàng)式意曲線(xiàn)形狀時(shí)比低次多項(xiàng)式更靈活更靈活n假設(shè)有假設(shè)有n+1個(gè)控制點(diǎn)，其坐標(biāo)分別為個(gè)控制點(diǎn)，其坐標(biāo)分別為pk=(xk, yk, zk) k=0,1,2, ,n，可用下列方程組來(lái)描述擬合每對(duì)控制點(diǎn)的參，可用下列方程組來(lái)描述擬合每對(duì)控制點(diǎn)的參數(shù)三次多項(xiàng)式數(shù)三次多項(xiàng)式x(u)=axu3+bxu2+cxu+dxy(u)=ayu3+byu2+cyu+dyz(u)=azu3+bzu2+czu+dz在在2條曲線(xiàn)段的條曲線(xiàn)段的

24、“交點(diǎn)交點(diǎn)”處設(shè)置足夠的邊界條件，即可對(duì)由處設(shè)置足夠的邊界條件，即可對(duì)由n+1個(gè)個(gè)控制點(diǎn)產(chǎn)生的控制點(diǎn)產(chǎn)生的n條曲線(xiàn)段確定所有系數(shù)值條曲線(xiàn)段確定所有系數(shù)值自然三次樣條自然三次樣條n自然三次樣條是原始繪圖樣條的一個(gè)數(shù)學(xué)表達(dá)式自然三次樣條是原始繪圖樣條的一個(gè)數(shù)學(xué)表達(dá)式u使用公式表示一個(gè)自然三次樣條時(shí)，需要使用公式表示一個(gè)自然三次樣條時(shí)，需要2個(gè)相鄰曲線(xiàn)段個(gè)相鄰曲線(xiàn)段在公共邊界處有相同的一階和二階導(dǎo)數(shù)，即具有在公共邊界處有相同的一階和二階導(dǎo)數(shù)，即具有C2連續(xù)性連續(xù)性n如下圖所示，需要擬合如下圖所示，需要擬合n+1個(gè)控制點(diǎn)，就需要確定個(gè)控制點(diǎn)，就需要確定n條曲線(xiàn)段條曲線(xiàn)段和和4n個(gè)多項(xiàng)式系數(shù)個(gè)多項(xiàng)式系數(shù)

25、p0pnp1p2p3pkPk+1n每個(gè)內(nèi)部控制點(diǎn)（共每個(gè)內(nèi)部控制點(diǎn)（共n-1個(gè)）有個(gè)）有4個(gè)邊界條件：該控制點(diǎn)兩側(cè)個(gè)邊界條件：該控制點(diǎn)兩側(cè)的的2個(gè)曲線(xiàn)段在該點(diǎn)處有相同的一階和二階導(dǎo)數(shù)，并且個(gè)曲線(xiàn)段在該點(diǎn)處有相同的一階和二階導(dǎo)數(shù)，并且2條曲條曲線(xiàn)段都要通過(guò)該點(diǎn)線(xiàn)段都要通過(guò)該點(diǎn)-從而得到由從而得到由4n個(gè)多項(xiàng)式系數(shù)組成的個(gè)多項(xiàng)式系數(shù)組成的4n-4個(gè)方程個(gè)方程系數(shù)求解方程分析系數(shù)求解方程分析n再給出從第再給出從第1個(gè)控制點(diǎn)個(gè)控制點(diǎn)p0(起點(diǎn)起點(diǎn))所得到的方程以及另所得到的方程以及另1個(gè)控制點(diǎn)個(gè)控制點(diǎn)pn(端點(diǎn)端點(diǎn))所得的條件。共所得的條件。共2個(gè)方程個(gè)方程n獲取另外獲取另外2個(gè)方程的方法是：方法個(gè)方

26、程的方法是：方法1、在、在p0和和pn處設(shè)處設(shè)二階導(dǎo)數(shù)為二階導(dǎo)數(shù)為0；方法；方法2、增加兩個(gè)、增加兩個(gè)“隱含隱含”的控制點(diǎn)，的控制點(diǎn)，即即p-1和和pn+1 （Cardianl樣條）樣條）n特點(diǎn)特點(diǎn)u1.只適用于控制點(diǎn)分布比較均勻的場(chǎng)合只適用于控制點(diǎn)分布比較均勻的場(chǎng)合u2.不能不能“局部控制局部控制”，如果控制點(diǎn)中任一個(gè)發(fā)生了變動(dòng)，如果控制點(diǎn)中任一個(gè)發(fā)生了變動(dòng)，則整條曲線(xiàn)都將受到影響則整條曲線(xiàn)都將受到影響Hermite樣條插值樣條插值n與自然三次樣條不同，與自然三次樣條不同，Hermite樣條可以局部調(diào)整，樣條可以局部調(diào)整，因?yàn)槊總€(gè)曲線(xiàn)段僅依賴(lài)于段點(diǎn)約束。如圖，如果控因?yàn)槊總€(gè)曲線(xiàn)段僅依賴(lài)于段點(diǎn)

27、約束。如圖，如果控制點(diǎn)制點(diǎn)pk和和pk+1之間的曲線(xiàn)段是參數(shù)三次函數(shù)之間的曲線(xiàn)段是參數(shù)三次函數(shù)p(u)，n那么邊界條件是那么邊界條件是u假設(shè)已知端點(diǎn)一階導(dǎo)數(shù)假設(shè)已知端點(diǎn)一階導(dǎo)數(shù)Dpk、Dpk+1up(0)=pkup(1)=pk+1up(0)=Dpkup(1)=Dpk+1pkPk+1p(u)=(x(u), y(u), z(u)Bzier曲線(xiàn)和曲面曲線(xiàn)和曲面n法國(guó)工程師法國(guó)工程師Bzier使用逼近樣條為雷諾汽車(chē)公司使用逼近樣條為雷諾汽車(chē)公司設(shè)計(jì)汽車(chē)外形而開(kāi)發(fā)。數(shù)學(xué)基礎(chǔ)簡(jiǎn)單，容易實(shí)現(xiàn)設(shè)計(jì)汽車(chē)外形而開(kāi)發(fā)。數(shù)學(xué)基礎(chǔ)簡(jiǎn)單，容易實(shí)現(xiàn)n Bzier樣條在各種樣條在各種CAD系統(tǒng)、大多數(shù)圖形系統(tǒng)、系統(tǒng)、大多數(shù)圖

28、形系統(tǒng)、相關(guān)繪圖和圖形軟件包中有廣泛應(yīng)用相關(guān)繪圖和圖形軟件包中有廣泛應(yīng)用n假定給出假定給出n+1個(gè)個(gè)控制點(diǎn)控制點(diǎn)位置：位置：pk=(xk,yk,zk), k取值范圍取值范圍為為0到到n，這些坐標(biāo)值用于合成向量，這些坐標(biāo)值用于合成向量 P(u), P(u) = Pk* Bk,n(u)nBzier混合函數(shù)混合函數(shù)Bk,n(u)是是Bernstein多項(xiàng)式多項(xiàng)式Bk,n(u) = C(n,k) * uk*(1-u)n-k其中，其中，C(n,k) = n! / (k!(n-k)!)Bzier 曲線(xiàn)公式曲線(xiàn)公式k=0n0u 1例例1：二次二次Bzier曲線(xiàn)曲線(xiàn) n由由3個(gè)控制點(diǎn)生成個(gè)控制點(diǎn)生成uB0,2

29、(u) = (1-u)2uB1,2(u) = 2u(1-u)uB2,2(u) = u2 例例2：三次三次Bzier曲線(xiàn)曲線(xiàn) n由由4個(gè)控制點(diǎn)生成個(gè)控制點(diǎn)生成uB0,3(u) = (1-u)3uB1,3(u) = 3u(1-u)2uB2,3(u) = 3u2(1-u)uB3,3(u) = u3 Bzier 曲線(xiàn)例子曲線(xiàn)例子Bzier 曲線(xiàn)生成程序見(jiàn)曲線(xiàn)生成程序見(jiàn)P357-359將將n=2代入公式代入公式Bk,n(u) = C(n,k) * uk*(1-u)n-k得例得例1，將將n=3代入該公式得例代入該公式得例2P0P1P2P0P1P2P3P0P1P2P3P0P1P2P3P4P0P1P2P3(a

30、)(b)(c)(d)(e)由由3個(gè)、個(gè)、4個(gè)和個(gè)和5個(gè)控制點(diǎn)生成的二維個(gè)控制點(diǎn)生成的二維Bzier曲線(xiàn)曲線(xiàn)的例子的例子虛線(xiàn)連接了虛線(xiàn)連接了控制點(diǎn)的位置控制點(diǎn)的位置nBzier多項(xiàng)式次數(shù)控制點(diǎn)個(gè)數(shù)多項(xiàng)式次數(shù)控制點(diǎn)個(gè)數(shù)-1nBzier曲線(xiàn)總是通過(guò)第一個(gè)和最后一個(gè)控制點(diǎn)，即曲線(xiàn)總是通過(guò)第一個(gè)和最后一個(gè)控制點(diǎn)，即曲線(xiàn)在曲線(xiàn)在2個(gè)端點(diǎn)處的邊界條件是個(gè)端點(diǎn)處的邊界條件是P(0) = p0, P(1) = pnn任何任何 Bzier曲線(xiàn)總是落在控制點(diǎn)的凸殼（凸多邊形曲線(xiàn)總是落在控制點(diǎn)的凸殼（凸多邊形邊界）內(nèi)，這些點(diǎn)由邊界）內(nèi)，這些點(diǎn)由Bzier混合函數(shù)給出，其值滿(mǎn)混合函數(shù)給出，其值滿(mǎn)足如下關(guān)系足如下關(guān)系n

31、Bk,n(u) = 1Bzier曲線(xiàn)的特性曲線(xiàn)的特性k=0nn第第1和最后和最后1個(gè)控制點(diǎn)重合生成封閉個(gè)控制點(diǎn)重合生成封閉Bzier 曲線(xiàn)曲線(xiàn)n多個(gè)控制點(diǎn)位于同一位置會(huì)對(duì)該位置加以更多的權(quán)（如下圖多個(gè)控制點(diǎn)位于同一位置會(huì)對(duì)該位置加以更多的權(quán)（如下圖1所示）所示）u下圖下圖2中，輸入一個(gè)坐標(biāo)位置作為中，輸入一個(gè)坐標(biāo)位置作為2個(gè)控制點(diǎn)，這樣產(chǎn)生個(gè)控制點(diǎn)，這樣產(chǎn)生的曲線(xiàn)更接近該位置的曲線(xiàn)更接近該位置使用使用Bzier曲線(xiàn)的設(shè)計(jì)技術(shù)曲線(xiàn)的設(shè)計(jì)技術(shù)p1p0=p5p4p2p3p0p1=p2p3p4圖圖1圖圖2p0p1p2P0P1P2P3零階參數(shù)連續(xù)零階參數(shù)連續(xù)Bzier曲線(xiàn)的構(gòu)造曲線(xiàn)的構(gòu)造一階參數(shù)連續(xù)一階

32、參數(shù)連續(xù)Bzier曲線(xiàn)的構(gòu)造曲線(xiàn)的構(gòu)造 n可使用任意數(shù)目的控制點(diǎn)來(lái)擬合一條可使用任意數(shù)目的控制點(diǎn)來(lái)擬合一條 Bzier 曲線(xiàn)，但這需要曲線(xiàn)，但這需要計(jì)算更高次的多項(xiàng)式計(jì)算更高次的多項(xiàng)式n復(fù)雜曲線(xiàn)可由幾個(gè)較低次數(shù)的復(fù)雜曲線(xiàn)可由幾個(gè)較低次數(shù)的Bzier曲線(xiàn)段連接而成曲線(xiàn)段連接而成u由于由于Bzier曲線(xiàn)通過(guò)端點(diǎn)，因此比較容易匹配曲線(xiàn)段（曲線(xiàn)通過(guò)端點(diǎn)，因此比較容易匹配曲線(xiàn)段（0階連續(xù)性）階連續(xù)性）nBzier曲線(xiàn)的另一重要性質(zhì)：曲線(xiàn)在端點(diǎn)處的切向量位于端點(diǎn)曲線(xiàn)的另一重要性質(zhì)：曲線(xiàn)在端點(diǎn)處的切向量位于端點(diǎn)和相鄰控制點(diǎn)的連線(xiàn)上和相鄰控制點(diǎn)的連線(xiàn)上u如下圖，新段中控制點(diǎn)如下圖，新段中控制點(diǎn)p0和和p1與前

33、段中控制點(diǎn)與前段中控制點(diǎn)pn-1和和pn處于同一直線(xiàn)處于同一直線(xiàn)上上Bzier曲面曲面n可使用兩組正交的可使用兩組正交的Bzier曲線(xiàn)來(lái)設(shè)計(jì)一個(gè)對(duì)象曲面曲線(xiàn)來(lái)設(shè)計(jì)一個(gè)對(duì)象曲面nBzier曲面的參數(shù)向量函數(shù)可按照曲面的參數(shù)向量函數(shù)可按照Bzier混合函數(shù)混合函數(shù)的笛卡爾積形式描述的笛卡爾積形式描述,00( , )( )( )mnj kj mk njkPu vP Bv Bu 其中其中pj,k指定了指定了(m+1)*(n+1)個(gè)控制點(diǎn)個(gè)控制點(diǎn)Bk,m(v) = C(m,k) * vk*(1-v)m-kBj,n(u) = C(n,j) * uj*(1-u)n-j內(nèi)容提要內(nèi)容提要n表示方法表示方法n多邊

34、形表面（多邊形表面（Polygon Surfaces）n曲線(xiàn)曲面曲線(xiàn)曲面: Bzier曲線(xiàn)曲線(xiàn)n實(shí)體構(gòu)造技術(shù)實(shí)體構(gòu)造技術(shù)n八叉樹(shù)（八叉樹(shù)（Octrees）n分形（分形（Fractal ）n實(shí)體構(gòu)造技術(shù)實(shí)體構(gòu)造技術(shù)n由簡(jiǎn)單的物體來(lái)構(gòu)成復(fù)雜的物體由簡(jiǎn)單的物體來(lái)構(gòu)成復(fù)雜的物體u掃描表示法掃描表示法u結(jié)構(gòu)實(shí)體幾何法結(jié)構(gòu)實(shí)體幾何法n掃描表示法掃描表示法u通過(guò)平移、旋轉(zhuǎn)及其他對(duì)稱(chēng)變換來(lái)構(gòu)造三維對(duì)象通過(guò)平移、旋轉(zhuǎn)及其他對(duì)稱(chēng)變換來(lái)構(gòu)造三維對(duì)象u通過(guò)指定一個(gè)二維形狀以及在空間區(qū)域內(nèi)移動(dòng)該形狀的通過(guò)指定一個(gè)二維形狀以及在空間區(qū)域內(nèi)移動(dòng)該形狀的掃描來(lái)描述該三維物體掃描來(lái)描述該三維物體u可將一組二維基本圖形，如圓或矩

35、形等作為菜單選項(xiàng)來(lái)可將一組二維基本圖形，如圓或矩形等作為菜單選項(xiàng)來(lái)提供掃描表示提供掃描表示獲得二維圖形的其它方法有封閉樣條曲線(xiàn)構(gòu)造和實(shí)體剖面片獲得二維圖形的其它方法有封閉樣條曲線(xiàn)構(gòu)造和實(shí)體剖面片實(shí)體造型軟件包通常提供多種構(gòu)造技術(shù)實(shí)體造型軟件包通常提供多種構(gòu)造技術(shù)zoyxAn平移掃描平移掃描 二維圖形二維圖形A沿沿Z軸平移軸平移n旋轉(zhuǎn)掃描旋轉(zhuǎn)掃描 二維圖形二維圖形A繞繞Z軸旋轉(zhuǎn)軸旋轉(zhuǎn)zByxA掃描表示掃描表示-示例示例結(jié)構(gòu)實(shí)體幾何法結(jié)構(gòu)實(shí)體幾何法n通過(guò)對(duì)兩個(gè)指定三維對(duì)象通過(guò)對(duì)兩個(gè)指定三維對(duì)象進(jìn)行并、交或差等集合操進(jìn)行并、交或差等集合操作產(chǎn)生一個(gè)新的三維對(duì)象作產(chǎn)生一個(gè)新的三維對(duì)象的建模方法稱(chēng)為的建

36、模方法稱(chēng)為結(jié)構(gòu)實(shí)體結(jié)構(gòu)實(shí)體幾何幾何（Constructive Solid Geometry，CSG）法）法 結(jié)構(gòu)實(shí)體幾何法結(jié)構(gòu)實(shí)體幾何法(a) 物體物體A和和B(d)差差(b)并并(c)交交(e)差差結(jié)構(gòu)實(shí)體幾何法結(jié)構(gòu)實(shí)體幾何法nCSG的應(yīng)用開(kāi)始于三維對(duì)象的初始集。稱(chēng)為的應(yīng)用開(kāi)始于三維對(duì)象的初始集。稱(chēng)為CSG基基本圖元，如長(zhǎng)方體、棱錐、圓柱體、圓錐體、球體本圖元，如長(zhǎng)方體、棱錐、圓柱體、圓錐體、球體和某些使用樣條曲面的實(shí)體和某些使用樣條曲面的實(shí)體n基本圖元可作為基本圖元可作為CSG軟件包的菜單選項(xiàng)來(lái)提供，基軟件包的菜單選項(xiàng)來(lái)提供，基本圖元本身可使用掃描算法、樣條構(gòu)造或其它建模本圖元本身可使用掃

37、描算法、樣條構(gòu)造或其它建模程序形成程序形成n使用交互式使用交互式CSG軟件包構(gòu)造對(duì)象的過(guò)程軟件包構(gòu)造對(duì)象的過(guò)程u首先選擇首先選擇2個(gè)基本圖元并拖到某空間位置個(gè)基本圖元并拖到某空間位置u指定一個(gè)組合操作（并、交或差）創(chuàng)建一個(gè)新對(duì)象指定一個(gè)組合操作（并、交或差）創(chuàng)建一個(gè)新對(duì)象u該新對(duì)象與一個(gè)已存在的形體組合生成另一新對(duì)象該新對(duì)象與一個(gè)已存在的形體組合生成另一新對(duì)象u繼續(xù)構(gòu)造新對(duì)象，直到形成所需新對(duì)象繼續(xù)構(gòu)造新對(duì)象，直到形成所需新對(duì)象CSG二叉樹(shù)二叉樹(shù)nCSG 利用基本體元或體素和每一步新創(chuàng)建的物體的利用基本體元或體素和每一步新創(chuàng)建的物體的組合，構(gòu)造新物體，直到形成所需的物體。這種方組合，構(gòu)造新物體

38、，直到形成所需的物體。這種方法可表示成一個(gè)二叉樹(shù)法可表示成一個(gè)二叉樹(shù)內(nèi)容提要內(nèi)容提要n表示方法表示方法n多邊形表面（多邊形表面（Polygon Surfaces）n曲線(xiàn)曲面曲線(xiàn)曲面: Bzier曲線(xiàn)曲線(xiàn)n實(shí)體構(gòu)造技術(shù)實(shí)體構(gòu)造技術(shù)n八叉樹(shù)八叉樹(shù)（Octrees）n分形（分形（Fractal ）n八叉樹(shù)八叉樹(shù)n三維空間的八叉樹(shù)編碼過(guò)程是四叉樹(shù)編碼的二維空間編碼方三維空間的八叉樹(shù)編碼過(guò)程是四叉樹(shù)編碼的二維空間編碼方法的擴(kuò)展法的擴(kuò)展u連續(xù)將二維空間（通常為正方形）分成連續(xù)將二維空間（通常為正方形）分成4等分得到四叉樹(shù)等分得到四叉樹(shù)u四叉樹(shù)的每個(gè)節(jié)點(diǎn)有四叉樹(shù)的每個(gè)節(jié)點(diǎn)有4個(gè)數(shù)據(jù)元素，每個(gè)象限在此區(qū)域內(nèi)個(gè)

39、數(shù)據(jù)元素，每個(gè)象限在此區(qū)域內(nèi)0321四分象限四分象限四分象限四分象限四分象限四分象限四分象限四分象限0312二維空間的區(qū)域二維空間的區(qū)域描述四叉樹(shù)節(jié)點(diǎn)的數(shù)據(jù)元素描述四叉樹(shù)節(jié)點(diǎn)的數(shù)據(jù)元素p如果一個(gè)象限中如果一個(gè)象限中所有像素的顏色相同所有像素的顏色相同（均質(zhì)均質(zhì)象限），此節(jié)點(diǎn)內(nèi)的數(shù)據(jù)元素存儲(chǔ)該顏色象限），此節(jié)點(diǎn)內(nèi)的數(shù)據(jù)元素存儲(chǔ)該顏色 此外，在數(shù)據(jù)元素中設(shè)定一標(biāo)記以標(biāo)明此象限是此外，在數(shù)據(jù)元素中設(shè)定一標(biāo)記以標(biāo)明此象限是均質(zhì)的均質(zhì)的p否則，此象限稱(chēng)為否則，此象限稱(chēng)為非均質(zhì)非均質(zhì)的象限，該象限再的象限，該象限再分成分成4個(gè)象限個(gè)象限生成四叉樹(shù)的生成四叉樹(shù)的算法算法n測(cè)試指定區(qū)域內(nèi)賦給對(duì)象的測(cè)試指定區(qū)域

40、內(nèi)賦給對(duì)象的像素顏色強(qiáng)度值，并建立相像素顏色強(qiáng)度值，并建立相應(yīng)的四叉樹(shù)編碼應(yīng)的四叉樹(shù)編碼312031200132312013120 如果原區(qū)域中每個(gè)象限有如果原區(qū)域中每個(gè)象限有單單一的顏色一的顏色規(guī)格，則四叉樹(shù)只規(guī)格，則四叉樹(shù)只有有一個(gè)節(jié)點(diǎn)一個(gè)節(jié)點(diǎn) 對(duì)于一個(gè)對(duì)于一個(gè)非均質(zhì)非均質(zhì)的區(qū)域，連的區(qū)域，連續(xù)續(xù)細(xì)分象限，直到所有的象細(xì)分象限，直到所有的象限都是同質(zhì)的限都是同質(zhì)的大區(qū)域中包括一個(gè)具有大區(qū)域中包括一個(gè)具有單一顏色單一顏色（不同于大區(qū)域中其它部分的顏色不同于大區(qū)域中其它部分的顏色）的小區(qū)域）的小區(qū)域四叉樹(shù)四叉樹(shù)-示例示例312456132519241820212223711 128910141

41、51617具有子孫的節(jié)點(diǎn)具有子孫的節(jié)點(diǎn)空節(jié)點(diǎn)空節(jié)點(diǎn)實(shí)節(jié)點(diǎn)實(shí)節(jié)點(diǎn)245139107811 12314 15 20 21 16 17 22 23 18 19 24 2516擴(kuò)展為多擴(kuò)展為多次劃分的次劃分的象限區(qū)域象限區(qū)域 每個(gè)單色區(qū)域使用一個(gè)節(jié)點(diǎn)表示，每個(gè)單色區(qū)域使用一個(gè)節(jié)點(diǎn)表示，空間區(qū)域存在空間區(qū)域存在較大的單一顏色區(qū)域較大的單一顏色區(qū)域時(shí)，四叉樹(shù)編碼能時(shí)，四叉樹(shù)編碼能節(jié)省存儲(chǔ)空間節(jié)省存儲(chǔ)空間 含有含有2n2n個(gè)像素的區(qū)域，四叉樹(shù)個(gè)像素的區(qū)域，四叉樹(shù)表示表示至多至多有有n層。四叉樹(shù)中每個(gè)節(jié)層。四叉樹(shù)中每個(gè)節(jié)點(diǎn)點(diǎn)至多至多有有4個(gè)直接后代個(gè)直接后代n八叉樹(shù)編碼方法將三維空間區(qū)域（一般是立方體）分成八

42、叉樹(shù)編碼方法將三維空間區(qū)域（一般是立方體）分成8等等分，并且樹(shù)上每個(gè)節(jié)點(diǎn)處存儲(chǔ)分，并且樹(shù)上每個(gè)節(jié)點(diǎn)處存儲(chǔ)8個(gè)數(shù)據(jù)元素個(gè)數(shù)據(jù)元素八叉樹(shù)八叉樹(shù)n三維空間中的每個(gè)元素稱(chēng)為體素或體元，三維空間中的每個(gè)元素稱(chēng)為體素或體元，八叉樹(shù)中的一個(gè)體元存儲(chǔ)一個(gè)均值均質(zhì)八叉樹(shù)中的一個(gè)體元存儲(chǔ)一個(gè)均值均質(zhì)子區(qū)域的特征值子區(qū)域的特征值n獲取八叉樹(shù)的算法獲取八叉樹(shù)的算法u將三維空間按照前后、左右、上下等分為將三維空間按照前后、左右、上下等分為8個(gè)個(gè)小立方體，小立方體，u如果小立方體單元均質(zhì)，則停止分解如果小立方體單元均質(zhì)，則停止分解u否則，進(jìn)一步分解為否則，進(jìn)一步分解為8個(gè)子立方體個(gè)子立方體u直至所有小立方體單元均質(zhì)，或已

43、分解到規(guī)直至所有小立方體單元均質(zhì)，或已分解到規(guī)定的分解精度定的分解精度7321045601234567描述八叉樹(shù)節(jié)點(diǎn)的數(shù)據(jù)元素描述八叉樹(shù)節(jié)點(diǎn)的數(shù)據(jù)元素八叉樹(shù)八叉樹(shù)-示例示例八叉樹(shù)八叉樹(shù)n可以建立為以任何形式定義的對(duì)象生成八叉樹(shù)的算法，可以建立為以任何形式定義的對(duì)象生成八叉樹(shù)的算法，如多邊形網(wǎng)格、曲面片或?qū)嶓w幾何構(gòu)造如多邊形網(wǎng)格、曲面片或?qū)嶓w幾何構(gòu)造n對(duì)單個(gè)對(duì)象，利用對(duì)象的坐標(biāo)范圍確定一個(gè)包圍盒對(duì)單個(gè)對(duì)象，利用對(duì)象的坐標(biāo)范圍確定一個(gè)包圍盒（平行六面體）來(lái)生成八叉樹(shù)表示（平行六面體）來(lái)生成八叉樹(shù)表示n一旦對(duì)實(shí)體建立一個(gè)八叉樹(shù)表示，可應(yīng)用執(zhí)行集合操一旦對(duì)實(shí)體建立一個(gè)八叉樹(shù)表示，可應(yīng)用執(zhí)行集合操作的算

44、法作的算法u“并并”操作，新八叉樹(shù)通過(guò)合并同一區(qū)域內(nèi)的每個(gè)八叉樹(shù)構(gòu)操作，新八叉樹(shù)通過(guò)合并同一區(qū)域內(nèi)的每個(gè)八叉樹(shù)構(gòu)造造u“交交”操作，尋找操作，尋找2棵輸入的八叉樹(shù)的重疊區(qū)域執(zhí)行交操作棵輸入的八叉樹(shù)的重疊區(qū)域執(zhí)行交操作u“差差”操作，存儲(chǔ)僅由一個(gè)對(duì)象占據(jù)，而不被另一對(duì)象占據(jù)操作，存儲(chǔ)僅由一個(gè)對(duì)象占據(jù)，而不被另一對(duì)象占據(jù)的八等分的八等分八叉樹(shù)的優(yōu)缺點(diǎn)八叉樹(shù)的優(yōu)缺點(diǎn)n優(yōu)點(diǎn)優(yōu)點(diǎn)u可表示任何物體，且表示的數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)單可表示任何物體，且表示的數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)單u簡(jiǎn)化了物體的集合運(yùn)算簡(jiǎn)化了物體的集合運(yùn)算p只需同時(shí)遍歷參加集合運(yùn)算的兩物體相應(yīng)的八叉樹(shù)，無(wú)需進(jìn)行只需同時(shí)遍歷參加集合運(yùn)算的兩物體相應(yīng)的八叉樹(shù)，無(wú)需進(jìn)行復(fù)

45、雜的求交運(yùn)算復(fù)雜的求交運(yùn)算u簡(jiǎn)化了隱藏線(xiàn)（或面）的消除簡(jiǎn)化了隱藏線(xiàn)（或面）的消除p因?yàn)樵诎瞬鏄?shù)表示中，物體上各元素已按空間位置排成了一定因?yàn)樵诎瞬鏄?shù)表示中，物體上各元素已按空間位置排成了一定的順序的順序u算法適合于并行處理算法適合于并行處理n缺點(diǎn)缺點(diǎn)u沒(méi)有邊界信息，不適于圖形精確顯示沒(méi)有邊界信息，不適于圖形精確顯示u對(duì)物體進(jìn)行幾何變換困難對(duì)物體進(jìn)行幾何變換困難u是物體的非精確表示是物體的非精確表示u占用大量存儲(chǔ)。實(shí)際上，八叉樹(shù)表示是以存儲(chǔ)空間換取算法的效率占用大量存儲(chǔ)。實(shí)際上，八叉樹(shù)表示是以存儲(chǔ)空間換取算法的效率BSP樹(shù)樹(shù)n利用二叉空間分割樹(shù)（利用二叉空間分割樹(shù)（Binary-Space-Pa

46、rtitioning, BSP樹(shù)），可以每次將一場(chǎng)景根據(jù)任意位置和任意樹(shù)），可以每次將一場(chǎng)景根據(jù)任意位置和任意方向的平面分為方向的平面分為2部分部分n相對(duì)于使用空間細(xì)分法，相對(duì)于使用空間細(xì)分法，BSP樹(shù)提供了一種更有效樹(shù)提供了一種更有效的分割方法：可根據(jù)適合對(duì)象的空間分布來(lái)確定分的分割方法：可根據(jù)適合對(duì)象的空間分布來(lái)確定分割平面的位置和方向割平面的位置和方向n與八叉樹(shù)的對(duì)比與八叉樹(shù)的對(duì)比u每次將空間分成每次將空間分成2部分，而不是部分，而不是8部分部分u可減少場(chǎng)景樹(shù)的表示深度，從而減少搜索樹(shù)的空間可減少場(chǎng)景樹(shù)的表示深度，從而減少搜索樹(shù)的空間uBSP樹(shù)可有效識(shí)別可視面和使用光線(xiàn)追蹤算法對(duì)空間進(jìn)行

47、樹(shù)可有效識(shí)別可視面和使用光線(xiàn)追蹤算法對(duì)空間進(jìn)行分割分割內(nèi)容提要內(nèi)容提要n表示方法表示方法n多邊形表面（多邊形表面（Polygon Surfaces）n曲線(xiàn)曲面曲線(xiàn)曲面: Bzier曲線(xiàn)曲線(xiàn)n實(shí)體構(gòu)造技術(shù)實(shí)體構(gòu)造技術(shù)n八叉樹(shù)（八叉樹(shù)（Octrees）n分形分形（Fractal ）nn歐氏幾何法歐氏幾何法u使用方程描述對(duì)象形狀的方法使用方程描述對(duì)象形狀的方法u適用于討論加工過(guò)的對(duì)象：具有平滑的表面和規(guī)則的形狀適用于討論加工過(guò)的對(duì)象：具有平滑的表面和規(guī)則的形狀n分形幾何法（分形幾何法（Fractal-geometry）u使用過(guò)程而不是方程為對(duì)象建模使用過(guò)程而不是方程為對(duì)象建模u能真實(shí)地描述自然景物；

48、計(jì)算機(jī)圖形學(xué)中，使用分形方法產(chǎn)生自然能真實(shí)地描述自然景物；計(jì)算機(jī)圖形學(xué)中，使用分形方法產(chǎn)生自然景物以及各種數(shù)學(xué)和物理系統(tǒng)的可視化景物以及各種數(shù)學(xué)和物理系統(tǒng)的可視化n分形對(duì)象具有分形對(duì)象具有2個(gè)基本特征個(gè)基本特征u每點(diǎn)具有無(wú)限的細(xì)節(jié)每點(diǎn)具有無(wú)限的細(xì)節(jié)u對(duì)象整體和局部特性之間的自相似性對(duì)象整體和局部特性之間的自相似性n利用一個(gè)過(guò)程來(lái)描述分形物體，該過(guò)程為產(chǎn)生物體局部細(xì)節(jié)利用一個(gè)過(guò)程來(lái)描述分形物體，該過(guò)程為產(chǎn)生物體局部細(xì)節(jié)指定了重復(fù)操作指定了重復(fù)操作分形分形-歐氏幾何法歐氏幾何法&分形幾何法分形幾何法不同放大級(jí)別中山的粗不同放大級(jí)別中山的粗糙輪廓表面糙輪廓表面圖圖1 遠(yuǎn)看的山遠(yuǎn)看的山圖圖2

49、近看的山近看的山圖圖3 更近看的山更近看的山n如果放大一連續(xù)的歐氏形狀，如果放大一連續(xù)的歐氏形狀，不管其有多復(fù)雜，最終可得到不管其有多復(fù)雜，最終可得到平滑的放大圖像平滑的放大圖像n放大分形對(duì)象，則會(huì)連續(xù)地看放大分形對(duì)象，則會(huì)連續(xù)地看到原圖中出現(xiàn)更多的細(xì)節(jié)到原圖中出現(xiàn)更多的細(xì)節(jié)u從圖從圖1到圖到圖3的越來(lái)越近的位置觀的越來(lái)越近的位置觀察山，會(huì)明顯地看見(jiàn)類(lèi)似的鋸齒察山，會(huì)明顯地看見(jiàn)類(lèi)似的鋸齒形狀形狀u再靠近一些觀察山，一個(gè)個(gè)突出再靠近一些觀察山，一個(gè)個(gè)突出物和石塊的小細(xì)節(jié)會(huì)出現(xiàn)在眼前物和石塊的小細(xì)節(jié)會(huì)出現(xiàn)在眼前u再靠近一些，可看見(jiàn)巖石的輪廓，再靠近一些，可看見(jiàn)巖石的輪廓，石子、沙子等石子、沙子等輪

50、輪廓廓顯顯示示得得更更彎彎曲，曲，更更傾傾斜斜分形幾何法的特點(diǎn)和用途分形幾何法的特點(diǎn)和用途n通過(guò)選擇一個(gè)分形的局部，并且在同樣大小的觀察區(qū)內(nèi)顯示，通過(guò)選擇一個(gè)分形的局部，并且在同樣大小的觀察區(qū)內(nèi)顯示，可得到分形對(duì)象的放大顯示可得到分形對(duì)象的放大顯示u對(duì)分形對(duì)象的該部分再進(jìn)行構(gòu)造操作，可得到放大級(jí)的增加的細(xì)節(jié)對(duì)分形對(duì)象的該部分再進(jìn)行構(gòu)造操作，可得到放大級(jí)的增加的細(xì)節(jié)-重復(fù)這一過(guò)程，可顯示越來(lái)越多大的細(xì)節(jié)重復(fù)這一過(guò)程，可顯示越來(lái)越多大的細(xì)節(jié)n因?yàn)闃?gòu)造過(guò)程包含無(wú)窮性，并且分形對(duì)象沒(méi)有確定大小，所因?yàn)闃?gòu)造過(guò)程包含無(wú)窮性，并且分形對(duì)象沒(méi)有確定大小，所以考慮越來(lái)越多細(xì)節(jié)時(shí)，對(duì)象的大小趨于無(wú)限以考慮越來(lái)越多

51、細(xì)節(jié)時(shí)，對(duì)象的大小趨于無(wú)限n可使用一個(gè)被稱(chēng)為可使用一個(gè)被稱(chēng)為“分形維數(shù)分形維數(shù)”的數(shù)字來(lái)描述對(duì)象細(xì)節(jié)的變的數(shù)字來(lái)描述對(duì)象細(xì)節(jié)的變化。該數(shù)字不一定是整數(shù)化。該數(shù)字不一定是整數(shù)-有時(shí)被稱(chēng)為分?jǐn)?shù)維數(shù)有時(shí)被稱(chēng)為分?jǐn)?shù)維數(shù)n分形幾何法的用途分形幾何法的用途u分形表示用于模擬巖層、云、水、樹(shù)以及其它植物、羽毛、毛皮和分形表示用于模擬巖層、云、水、樹(shù)以及其它植物、羽毛、毛皮和各種表面紋理各種表面紋理u分形模型用于星體分布、河流、月球隕石坑、雨地，以及表示股市分形模型用于星體分布、河流、月球隕石坑、雨地，以及表示股市變化、音樂(lè)、交通流量、人口資源利用、數(shù)字分析技術(shù)收斂區(qū)域的變化、音樂(lè)、交通流量、人口資源利用、數(shù)

52、字分析技術(shù)收斂區(qū)域的邊緣邊緣名稱(chēng)名稱(chēng)“分形分形”的基礎(chǔ)的基礎(chǔ)n對(duì)一個(gè)空間區(qū)域中的點(diǎn)重復(fù)使用指定的變換函數(shù)，即可生對(duì)一個(gè)空間區(qū)域中的點(diǎn)重復(fù)使用指定的變換函數(shù)，即可生成一個(gè)分形對(duì)象成一個(gè)分形對(duì)象n假設(shè)假設(shè)P0(x0, y0, z0)是選定的初始點(diǎn)，每次重復(fù)變換函數(shù)是選定的初始點(diǎn)，每次重復(fù)變換函數(shù)F的計(jì)的計(jì)算，可生成細(xì)節(jié)后繼層算，可生成細(xì)節(jié)后繼層P1=F(P0), P2=F(P1), P3= F(P2)n變換函數(shù)一般可應(yīng)用于給定的點(diǎn)集，或?qū)⒆儞Q函數(shù)應(yīng)用于變換函數(shù)一般可應(yīng)用于給定的點(diǎn)集，或?qū)⒆儞Q函數(shù)應(yīng)用于基本函數(shù)的初始集上，如直線(xiàn)、曲線(xiàn)、顏色區(qū)或表面基本函數(shù)的初始集上，如直線(xiàn)、曲線(xiàn)、顏色區(qū)或表面n變換

53、函數(shù)可定義為幾何變換（對(duì)稱(chēng)、平移、旋轉(zhuǎn)），或者變換函數(shù)可定義為幾何變換（對(duì)稱(chēng)、平移、旋轉(zhuǎn)），或者利用非線(xiàn)性變換和統(tǒng)計(jì)決策參數(shù)來(lái)建立利用非線(xiàn)性變換和統(tǒng)計(jì)決策參數(shù)來(lái)建立n雖然分形對(duì)象在雖然分形對(duì)象在定義上定義上包含無(wú)限的細(xì)節(jié)包含無(wú)限的細(xì)節(jié)，但是我們只運(yùn)用，但是我們只運(yùn)用有限次變換函數(shù)，使得顯示的對(duì)象具有有限維數(shù)。增加變有限次變換函數(shù)，使得顯示的對(duì)象具有有限維數(shù)。增加變換次數(shù)以產(chǎn)生更多的細(xì)節(jié)時(shí)，過(guò)程性表示將接近換次數(shù)以產(chǎn)生更多的細(xì)節(jié)時(shí)，過(guò)程性表示將接近真正的真正的“分形分形”n包括在包括在最終圖形顯示中的細(xì)節(jié)數(shù)量最終圖形顯示中的細(xì)節(jié)數(shù)量依賴(lài)于依賴(lài)于重復(fù)執(zhí)行的次數(shù)重復(fù)執(zhí)行的次數(shù)和和顯示系統(tǒng)的分辨率顯示

54、系統(tǒng)的分辨率分形生成過(guò)程分形生成過(guò)程分形分形-示例示例科赫雪花科赫雪花(Von koch snowflake)分形分形-示例示例圖圖1樹(shù)形生成元及對(duì)應(yīng)曲線(xiàn)樹(shù)形生成元及對(duì)應(yīng)曲線(xiàn)圖圖2分形分類(lèi)分形分類(lèi)n自相似自相似分形：組成部分是整個(gè)物體的收縮形式分形：組成部分是整個(gè)物體的收縮形式u分為分為2類(lèi)：類(lèi)：“確定確定自相似分形自相似分形”和和“統(tǒng)計(jì)統(tǒng)計(jì)自相似分形自相似分形”u前者從初始形狀開(kāi)始，對(duì)整個(gè)物體應(yīng)用縮放參數(shù)前者從初始形狀開(kāi)始，對(duì)整個(gè)物體應(yīng)用縮放參數(shù)s來(lái)構(gòu)造物體的子來(lái)構(gòu)造物體的子部件；對(duì)子部件使用相同的縮放參數(shù)部件；對(duì)子部件使用相同的縮放參數(shù)s構(gòu)造其子部件；或者使用不構(gòu)造其子部件；或者使用不同的

55、縮放因子構(gòu)造對(duì)象的不同收縮部分同的縮放因子構(gòu)造對(duì)象的不同收縮部分u后者對(duì)收縮部分使用隨機(jī)變量。使各部分具有相同的統(tǒng)計(jì)性質(zhì)。統(tǒng)后者對(duì)收縮部分使用隨機(jī)變量。使各部分具有相同的統(tǒng)計(jì)性質(zhì)。統(tǒng)計(jì)自相似分形常用于模擬樹(shù)木、灌木和其他植物計(jì)自相似分形常用于模擬樹(shù)木、灌木和其他植物(彩頁(yè)彩頁(yè)P(yáng)12)n自仿射自仿射分形：組成部分由不同坐標(biāo)方向上的不同縮放因子分形：組成部分由不同坐標(biāo)方向上的不同縮放因子sx、sy、sz形成。也可引入隨機(jī)變量，獲得隨機(jī)自仿射分形形成。也可引入隨機(jī)變量，獲得隨機(jī)自仿射分形u巖層、水和云是應(yīng)用隨機(jī)自仿射分形構(gòu)造方法的典型例子巖層、水和云是應(yīng)用隨機(jī)自仿射分形構(gòu)造方法的典型例子(彩頁(yè)彩頁(yè)P(yáng)

56、13)n不變分形不變分形集：由非線(xiàn)性變換形成集：由非線(xiàn)性變換形成(彩頁(yè)彩頁(yè)P(yáng)14)u自平方分形自平方分形u自逆分形：由自逆過(guò)程形成自逆分形：由自逆過(guò)程形成分形分類(lèi)分形分類(lèi)-示例示例植物植物(彩頁(yè)彩頁(yè)P(yáng)12)巖層巖層(彩頁(yè)彩頁(yè)P(yáng)13)曼德勃羅集曼德勃羅集 (Mandelbrot set)朱利亞集朱利亞集 (Julia set)四元數(shù)分形四元數(shù)分形(Quartic fractals)分形分類(lèi)分形分類(lèi)-不變分形集不變分形集示例示例彩頁(yè)彩頁(yè)P(yáng)14分形的維數(shù)分形的維數(shù)n分形的維數(shù)：分形對(duì)象的細(xì)節(jié)變化可以使用數(shù)字分形的維數(shù)：分形對(duì)象的細(xì)節(jié)變化可以使用數(shù)字D描述，描述，D稱(chēng)為分形維數(shù)稱(chēng)為分形維數(shù)uD是對(duì)象粗

57、糙性或細(xì)碎性的度量是對(duì)象粗糙性或細(xì)碎性的度量u對(duì)象有較大的鋸齒形時(shí)，其分形維數(shù)較大對(duì)象有較大的鋸齒形時(shí)，其分形維數(shù)較大n生成分形對(duì)象時(shí)與分形維數(shù)相關(guān)的生成分形對(duì)象時(shí)與分形維數(shù)相關(guān)的2種方法種方法u建立一個(gè)使用選定的建立一個(gè)使用選定的D值的交互過(guò)程值的交互過(guò)程u從構(gòu)造對(duì)象的特性來(lái)確定分形維數(shù)從構(gòu)造對(duì)象的特性來(lái)確定分形維數(shù)n計(jì)算計(jì)算D以拓?fù)鋵W(xué)中定義的維數(shù)概念為基礎(chǔ)以拓?fù)鋵W(xué)中定義的維數(shù)概念為基礎(chǔ)分形的維數(shù)分形的維數(shù)n1nLLDE=1, s= , n=2n1L11nsAnAA DE=2, n=4211ns VnVV 12nsDE=3, n=8311ns 13ns下面表示縮放因子下面表示縮放因子s與單位

58、線(xiàn)段、正方與單位線(xiàn)段、正方形和立方體的再分?jǐn)?shù)目形和立方體的再分?jǐn)?shù)目n之間的關(guān)系之間的關(guān)系1因此，確定性自相似分形維數(shù)因此，確定性自相似分形維數(shù)D = ln n / ln(1/s) 其中：其中：n是再分?jǐn)?shù)目、是再分?jǐn)?shù)目、s是縮放因子是縮放因子分形的維數(shù)分形的維數(shù)n對(duì)于每一個(gè)物體，子部分?jǐn)?shù)目與縮放因子的關(guān)系式是對(duì)于每一個(gè)物體，子部分?jǐn)?shù)目與縮放因子的關(guān)系式是nsD=1 n求得求得D的表達(dá)式為：的表達(dá)式為：D=ln n/ln (1/s) n對(duì)于不同部分由不同的縮放因子構(gòu)造而成的自相似分形那么對(duì)于不同部分由不同的縮放因子構(gòu)造而成的自相似分形那么分形維數(shù)可由下列關(guān)系式得到分形維數(shù)可由下列關(guān)系式得到其中：其

59、中：sk是第是第k個(gè)子部分的縮放因子個(gè)子部分的縮放因子1DksK=1, 2, 3, , nn上面考慮了簡(jiǎn)單物體的細(xì)分，如果有曲線(xiàn)和曲面物體的復(fù)雜上面考慮了簡(jiǎn)單物體的細(xì)分，如果有曲線(xiàn)和曲面物體的復(fù)雜的形狀的物體，確定子部分的結(jié)構(gòu)和性質(zhì)會(huì)更加復(fù)雜的形狀的物體，確定子部分的結(jié)構(gòu)和性質(zhì)會(huì)更加復(fù)雜n對(duì)于一般物體的形狀，可以采用拓?fù)涓采w方法，該方法對(duì)于一般物體的形狀，可以采用拓?fù)涓采w方法，該方法是采用簡(jiǎn)單形狀來(lái)逼近物體的子部分是采用簡(jiǎn)單形狀來(lái)逼近物體的子部分拓?fù)涓采w拓?fù)涓采wn拓?fù)涓采w一般用于將常見(jiàn)形狀的幾何性質(zhì)擴(kuò)充到非標(biāo)準(zhǔn)形狀拓?fù)涓采w一般用于將常見(jiàn)形狀的幾何性質(zhì)擴(kuò)充到非標(biāo)準(zhǔn)形狀u如：如：Hausdorff

60、-Besicovitch維數(shù)的方式是運(yùn)用球或圓的覆維數(shù)的方式是運(yùn)用球或圓的覆蓋方法進(jìn)行擴(kuò)充，一般的方法是采用方框覆蓋（蓋方法進(jìn)行擴(kuò)充，一般的方法是采用方框覆蓋（box-convering）方法進(jìn)行估算，該方法利用了正方形或平行）方法進(jìn)行估算，該方法利用了正方形或平行六面體六面體綠色區(qū)域區(qū)域面積，可以通過(guò)小的綠色區(qū)域區(qū)域面積，可以通過(guò)小的覆蓋正方形面積之和進(jìn)行估算覆蓋正方形面積之和進(jìn)行估算方框覆蓋方法過(guò)程方框覆蓋方法過(guò)程n1) 首先確定物體坐標(biāo)范圍（即覆蓋物體的矩形區(qū)域）首先確定物體坐標(biāo)范圍（即覆蓋物體的矩形區(qū)域）n2)然后利用給定的縮放因子然后利用給定的縮放因子s將物體分成很多小框?qū)⑽矬w分成很多小框覆