1、2022/7/171計算機圖形基礎(chǔ)第九章 分?jǐn)?shù)維圖形2022/7/172 自然景物模擬是計算機圖形學(xué)的一個重要研究內(nèi)容。與規(guī)則幾何體不同，自然景物的表面往往包含有豐富的細節(jié)或具有隨機變化的形狀，它們很難用傳統(tǒng)的解析曲面來描述。盡管凹凸紋理映射技術(shù)可以模擬規(guī)則景物表面的幾何紋理細節(jié)，但在表達諸如山脈、云彩、火焰、樹木、浪花等自然景象時，凹凸紋理映射技術(shù)仍難以勝任。從歐氏幾何來看，這些自然景物是極端無規(guī)則的，為了解決這一問題，分?jǐn)?shù)維圖形生成技術(shù)應(yīng)運而生。分?jǐn)?shù)維圖形是利用分?jǐn)?shù)維幾何學(xué)的自相似性質(zhì)，采用各種模擬真實圖形的模型，使整個生成的景象呈現(xiàn)出細節(jié)的無窮回歸性質(zhì)。所生成的景物中，可以有結(jié)構(gòu)性較強的

2、樹，也可以是結(jié)構(gòu)性較弱的火、云、煙，甚至可生成有動態(tài)特性的火焰、浪等。2022/7/173分?jǐn)?shù)維幾何方法分?jǐn)?shù)維幾何概念 對復(fù)雜現(xiàn)象的探索早在圖形學(xué)產(chǎn)生以前就已經(jīng)開始，可以回溯到1904年，當(dāng)時von Koch研究了一種他稱為雪花的圖形，他將一個等邊三角形的三邊都三等分，在中間的那一段上再凸起一個小正三角形,如圖1所示，這樣一直下去，理論上可證明這種不斷構(gòu)造成的雪花周長是無窮，但其面積卻是有窮的。這和正統(tǒng)的數(shù)學(xué)直觀是不符的，周長和面積都無法刻劃出這種雪花的特點，歐氏幾何對這種雪花的描述無能為力。圖12022/7/174 二十世紀(jì)六十年代開始，重新研究了這個問題，并將雪花與自然界的海岸線、山、樹等

3、自然景象聯(lián)系起來，找出了其中的共性，并提出了分?jǐn)?shù)維(Fractal)的概念。 Mandelbrot曾舉了一個海洋線的例子來說明這一理論。假設(shè)我們要測量不列顛的海岸線長度，我們可以用一個1000米的尺子，一尺一尺地向前量，同時數(shù)出有多少個1000米。這樣得到一個長度為L(1000米）。然而這樣測量會漏掉許多小于1000米的小灣，因而結(jié)果不準(zhǔn)確。如果尺子縮到l米，那么我們會得到一個新的結(jié)果L(l米)，顯然L(1米)L(1000米）。一般來說,如果用長度為r的尺子來量，將會得到一個與r有關(guān)的數(shù)值L(r)。與Koch的雪花一樣r0，L(r)。也就是說，不列顛的海岸線長度是不確定的，它與測量用的尺子長度

4、有關(guān)。2022/7/175 Mandelbrot注意到von Koch雪花與海岸線的共同特點：它們都有細節(jié)的無窮回歸，測量尺度的減小都會得到更多的細節(jié)。換句話說，就是將其一部分放大會得到與原來部分基本一樣的形態(tài)，這就是Mandelbrot發(fā)現(xiàn)的轟動整個自然界的復(fù)雜現(xiàn)象的自相似性(Self Similarity）。為了定量地刻劃這種自相似性，他引入了分?jǐn)?shù)維概念，這是與歐氏幾何中整數(shù)維相對應(yīng)的,所以也稱為分?jǐn)?shù)維幾何。分?jǐn)?shù)維的引入，為研究復(fù)雜性提供了全新的角度，使人們從無序中重新發(fā)現(xiàn)了有序，許多學(xué)科象物理、經(jīng)濟、氣象等都將分?jǐn)?shù)維幾何學(xué)作為解決難題的新工具。計算機圖形學(xué)也從中受到啟發(fā)，并形成了以模擬自

5、然界復(fù)雜景象、物體為目標(biāo)的分?jǐn)?shù)維圖形學(xué)，由此方法生成的圖形稱為分?jǐn)?shù)維圖形或分形。2022/7/176統(tǒng)計自相似 對象被細分后的部分相互之間或與整體相似或相同的特性稱之為自相似。von Koch曲線是嚴(yán)格自相似的。但海岸線不同，細分放大后，海岸線的每一小部分看起來像，但不完全像一個大些部分，所以，海岸線不是嚴(yán)格自相似，而是統(tǒng)計自相似。然而，分形維數(shù)的概念也可用于這樣的統(tǒng)計自相似對象。統(tǒng)計自相似是自然界中分形的主要特征，象山、云、火、浪等都具有統(tǒng)計自相似的特性。分形的維數(shù) 分?jǐn)?shù)維圖形的細節(jié)變化可以用數(shù)字D來描述，D稱為分形維數(shù)，它是圖形粗細性的度量，同圖形每一步細分?jǐn)?shù)目和縮放倍數(shù)有關(guān)。2022/7

6、/177 設(shè)N為圖形每一步細分的數(shù)目，S為細分時縮放因子，分形維數(shù)D定義為： 分形維數(shù)不像我們所熟悉的歐氏幾何的維數(shù)是一整數(shù)，它可以是分?jǐn)?shù)，這也是其名稱的由來。如圖.2是兩個示例。圖.22022/7/178 通常一維的對象（例如線段）可被分成N個相同部分。每一部分從整體上縮小S=1/N的比例。類似地，諸如平面上方形區(qū)域的二維對象可被分成N個自相似部分，每部分縮小S=1/N1/2的比例。像固體立方體這樣的三維對象可被分成N個小立方體，每個立方體縮小S=1/N1/3的比例。按這樣的S與N的關(guān)系細分得到的是歐氏幾何的結(jié)果，維數(shù)是整數(shù)。如圖2(b)所示，若我們按歐氏幾何的方法，將一線段四等分，則N=4

7、，S=1/4，則D=1。得到的是同歐氏幾何相一致的整數(shù)維。將一正方形16等分，此時N=16，線段的放大倍數(shù)S=1/4，則D=2。 利用自相似，對分形大小的推廣是直觀的。一個D維自相似對象可被分成N個更小的部分。每一部分縮小S因子。其中或者當(dāng)D不取整數(shù)時，細分的結(jié)果是一個分?jǐn)?shù)維圖形。2022/7/179 仍以von Koch曲線為例，D非整維數(shù)(大于1而小于2)反映了曲線的特征。它從某種程度上更多填充了空間而非簡單直線(D=1),但是又小于一個歐氏平面區(qū)域(D=2)。當(dāng)D從1增加到2時，結(jié)果曲線從“線形”逐漸填充大部分平面，實際上，極限D(zhuǎn)=2產(chǎn)生一個稱為Peano曲線或空間填充曲線，如圖3所示。

8、這樣，分形維數(shù)就提供了一個曲線擺動的度量。盡管這些von Koch曲線具有1到2的分形維數(shù)，但它們均是保持具有拓樸維數(shù)1的“曲線”，即去掉一個點即可將曲線分為兩部分。2022/7/1710圖32022/7/1711 一般地說，二維空間中的一個分?jǐn)?shù)維曲線維數(shù)介于1和2之間，三維空間中的一個分?jǐn)?shù)維曲線維數(shù)在1和3之間，而三維空間中的一個分?jǐn)?shù)維曲面維數(shù)在2和3之間。9.2.1 分形生成過程 分形有二個基本特征：每點處無限的細節(jié)以及整體和局部特性之間的自相似性。自相似性質(zhì)可有不同形式，這取決于分形表示的選擇。可以用一個過程來描述分形，該過程為產(chǎn)生分形局部細節(jié)指定一重復(fù)操作。理論上自然景物用重復(fù)無限次的

9、過程來表示。實際中，自然景物的圖形僅用有限步生成。如果給定一過程變換函數(shù)，一個分形可以通過在一空間區(qū)域里對初始圖形重復(fù)使用變換函數(shù)來生成。 2022/7/1712若P0是選定的初始圖形，每次重復(fù)變換函數(shù)的計算： P1=F(P0），P2=F(P1），P3=F(P2）可得細分的圖形。增加變換次數(shù)可以產(chǎn)生更多細節(jié)，也更靠近一“真正”分形。 一般地，變換函數(shù)可以應(yīng)用于給定的點集，或者應(yīng)用于基本元素的初始集上，如直線、曲線、顏色區(qū)、表面和實體。每次重復(fù)時，我們既可用固定的也可用隨機的生成過程。變換函數(shù)也可定義成幾何變換，或者用非線性變換和決策參數(shù)來建立。 有許多種構(gòu)造變換函數(shù)的方法，它們形成不同的分?jǐn)?shù)維

10、圖形構(gòu)造模型。2022/7/17139.2.2 隨機插值模型 為了克服傳統(tǒng)模型技術(shù)中模型依賴于觀察距離的局限性，本模型不是事先決定各種圖素和尺度，而是用一個隨機過程的采樣路徑作為構(gòu)造模型的手段。例如構(gòu)造二維海岸線的模型可以選擇控制大致形狀的若干初始點。再在相鄰兩點構(gòu)成的線段上取其中點，并沿垂直連線方向隨機偏移一個距離，再將偏移后的點與該線段兩端點分別連成兩個新線段。這樣下去可得到一條曲折的有無窮細節(jié)回歸的海岸線，其曲折程度由隨機偏移量控制，它也決定了分?jǐn)?shù)維的大小。在三維情況下可通過類似過程構(gòu)造山的模型，一般通過多邊形，簡單的如三角形，細分的方法。2022/7/1714 可以在一個三角形的三條邊

11、上，隨機各取一點，沿垂直方向隨機偏移一距離后得到新的三個點，再連接成四個三角形,如圖5所示，如此繼續(xù)，即可形成褶皺的山峰。山的褶皺程度由分?jǐn)?shù)維控制。該模型能有效地模擬海岸線和山等自然景象圖52022/7/1715 隨機中點位移方法是一種簡便快速逼近地面和其它自然現(xiàn)象的隨機插值方法。從一直線段開始，設(shè)線段的起點P0，終點Pn。線段中點位移值通過起點和終點的平均值加上一隨機偏移值r來獲得： PmP0Pnrr值為從O到正比于| Pn-P0|2H的均方差之間的高斯分布，其中H=2-D，D1是分形維數(shù)。對中點位移后產(chǎn)生的兩部分線段繼續(xù)進行隨機中點位移，遞歸進行可以得到模擬的自然現(xiàn)象。實際圖形生成演示20

12、22/7/1716選代函數(shù)系統(tǒng)模型 該模型以迭代函數(shù)系統(tǒng)理論作為其數(shù)學(xué)基礎(chǔ)。一個n維空間的迭代函數(shù)系統(tǒng)由兩部分組成，一是一個n維空間到自身的映射變換的有窮集合M=M1,M2,.,Mn；二是一個概率集合P=P1,P2,Pn。每個Pi與Mi相聯(lián)系，Pi=1。迭代函數(shù)系統(tǒng)是以下述方式工作的：取空間中任一點Z0，以Pi概率選取變換Mi，作變換Z1=Mi(Z0)，再以Pi的概率選取變換Mi，對Z1作變換Z2=Mi(Z1)，以此下去，得到一個無數(shù)點集，該模型方法就是要選取合適的映射集合、概率集合及初始點，使得生成的無數(shù)點集能模擬某種景物。如果選取的映射變換特征值的模小于1，則該系統(tǒng)有唯一的有界閉集，稱為迭

13、代函數(shù)系統(tǒng)的吸引子。直觀地說，吸引子就是迭代生成點的聚集處。點逼近吸引子的速度取決于特征值大小。2022/7/1717選代函數(shù)一般使用復(fù)平面，一種常用的選代函數(shù)是多項式變換函數(shù)： f(z)=z2+c 這一復(fù)映射變換的有界閉集稱為Julia集合。迭代過程寫成： zn+1=zn2+c 適當(dāng)選取c,可以生成類似于云的分?jǐn)?shù)維圖形。圖7所示是c分別取c1和c2時,生成的圖形。圖72022/7/17189.2.4 正規(guī)文法模型 該模型是1983年為模擬植物而引入的。正規(guī)文法模型能夠生成結(jié)構(gòu)性強的拓樸結(jié)構(gòu)，如植物，再通過進一步幾何解釋來形成逼真的畫面。該模型的工具是并行重寫系統(tǒng)，它與形式語言理論中的一般重寫

14、系統(tǒng)有兩點主要區(qū)別：一是該系統(tǒng)中產(chǎn)生式的匹配對一個輸入字符串的所有字符是同時進行的；二是該系統(tǒng)沒有終結(jié)符和非終結(jié)符之分。并行重寫系統(tǒng)的一個子集是L系統(tǒng)。L系統(tǒng)最簡單的類型稱作OL系統(tǒng)，它是上下文無關(guān)的。先以一個例子敘述主要思想。考慮由兩個符號a和b組成的字符串， a、b可在同一字符串中出現(xiàn)多次。每個符號與一個改寫規(guī)則有關(guān)。例如，如果寫aab，那么這表示符號a用ab替換。ba表示符號b用a替換，這便是一個改寫規(guī)則。改寫過程從一個稱作公理的符號開始，2022/7/1719 例如這個單詞僅包括一個符號b，那么，第一步，由規(guī)則ba 可知公理b被a替換；第二步由規(guī)則aab得到字符串a(chǎn)b。下一步將對ab中

15、的a與b分別施行相應(yīng)的替換，得到新的字符串a(chǎn)ba，接著由aba生成abaab，由abaab又生成abaababa，繼而生成abaababaabaab。過程如下列所示： b a ab aba abaab abaababa abaababaabaab這個例子說明怎樣從一個符號出發(fā)，依據(jù)兩條規(guī)則，遞歸地產(chǎn)生新的字符串。這種作法可以用來表示生長過程。2022/7/1720令V表示符號集合，OL系統(tǒng)是一個有序的3元素集合： G=（V,P,S）這里S是一個非空起始符，稱作公理；P是產(chǎn)生式或重寫規(guī)則集合，產(chǎn)生式的前驅(qū)和后繼用“”相連，如aab。 要模擬具體的景物，除拓撲結(jié)構(gòu)外，還需要加上幾何形狀，諸如線段的

16、長度和線段的轉(zhuǎn)角。設(shè)想一只烏龜在平面上爬行，其狀態(tài)用三個值來描述，記以(x,y,),其中x,y為龜所在位置的直角坐標(biāo)，表示爬行的朝向，另外給出爬行步長d及扭轉(zhuǎn)方向的角度增量。為了產(chǎn)生幾何形狀。定義下面符號的含義： F：向前移動一步，步長為d。龜?shù)男聽顟B(tài)為(x,y,),其中2022/7/1721從(x,y)向(x,y)畫一直線段；+：向左轉(zhuǎn)角，龜?shù)南乱粻顟B(tài)為(x,y,+)，規(guī)定正向角是逆時針方向，負向角是順時針方向；-：向右轉(zhuǎn)角，龜?shù)南乱粻顟B(tài)為(x,y,+)。 現(xiàn)在給出一個字符串的例子： FFFFFFFFFFFFFF =90則生成的圖形如圖8所示。圖82022/7/1722令步長d在相鄰兩級子圖

17、之間縮短4倍，規(guī)定后繼多邊形線(折線)端點之間的距離等于前驅(qū)線段的長度，起始符S和重寫規(guī)則P及轉(zhuǎn)角分別為： S：FFFF P：FFFFFFFFF =90其中，S表示一個封閉的正方形邊界曲線。經(jīng)過三次改寫，我們得到n=1,n=2,n=3的von Koch曲線，也稱為“Koch島”。如圖9所示。圖92022/7/1723 為了形式化地描述許多植物的分支結(jié)構(gòu)，引入兩個新的字符，其含義為： : 將當(dāng)前烏龜爬行的狀態(tài)壓入堆棧。信息包括烏龜所在的位置與方向等； : 從堆棧中彈出一個狀態(tài)作為烏龜?shù)漠?dāng)前狀態(tài)，但不畫線。 新字符的引入，使得分支結(jié)構(gòu)能以簡單的方式進行描述，例如，從圖10(a)開始，字符串 FFF

18、F,=45產(chǎn)生圖10(b) 所示的樹，而FFFFFFFFF, =45產(chǎn)生圖10(c)所示的樹。圖102022/7/1724 圖11(a)(b)(c)中的三個圖是采用這種帶括號的產(chǎn)生式生成的分支結(jié)構(gòu)，其中 （a） n=5，=30 S：F P：FFFFFF (b) n=5，=20 S: F P：FFFFFF （c） n=4，=20.5 S: F P：FFFFFFFFF 圖112022/7/17259.2.5 粒子系統(tǒng)模型 粒子系統(tǒng)模型是W.T.Reeves 在1983年提出的又一個隨機模型，用于模擬諸如云、煙、火等具有變化形狀的自然景物。粒子系統(tǒng)采用粒子圖元(Particle）來描述景物。粒子可以

19、隨時間推移發(fā)生位置和形態(tài)變化。每個粒子的位置、取向及動力學(xué)性質(zhì)都是由一組預(yù)先定義的隨機過程來說明的。每個粒子均有一定的生命周期，它們不斷改變形狀、不斷運動。粒子系統(tǒng)的這一特征，使得它充分體現(xiàn)了不規(guī)則模糊物體的動態(tài)性和隨機性，很好地模擬了火、云、水、森林和原野等自然景觀。 粒子系統(tǒng)最初引入時是為了模擬火焰。火焰被看成是一個噴出許多粒子的火山，粒子運動的軌跡構(gòu)造了火焰的模型，每個粒子都有一組隨機取值的屬性，如起始位置、初速度、顏色及大小。后來又用該模型來模擬叢草、森林等全景要求高的景象。2022/7/1726粒子形狀可以是小球、橢球、立方體或其它形狀，粒子的大小和形狀隨時間變化。其它性質(zhì)如粒子透明度、顏色和移動等都隨機地變化。為模擬生長和衰亡過程，每個粒子均被賦予一定的生命周期，它將經(jīng)歷出生、成長、衰老和死亡的過程，不斷有舊的粒子消失，新的粒子加入。粒子系統(tǒng)生成一嫻幕靜街枋牽 （1）生成新的粒子，并賦予每一新粒子以一定的