計(jì)算機(jī)圖形基礎(chǔ)第九章分?jǐn)?shù)維圖形

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

18、F,=45產(chǎn)生圖10(b) 所示的樹，而FFFFFFFFF, =45產(chǎn)生圖10(c)所示的樹。圖102022/7/1724 圖11(a)(b)(c)中的三個(gè)圖是采用這種帶括號(hào)的產(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年提出的又一個(gè)隨機(jī)模型，用于模擬諸如云、煙、火等具有變化形狀的自然景物。粒子系統(tǒng)采用粒子圖元(Particle）來描述景物。粒子可以

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