張 杰, 蔡文奇
(汕頭大學(xué)計(jì)算機(jī)科學(xué)系,廣東 汕頭 515063)
自然界的植物千資百態(tài)、種類繁多,貌似無章可循,無法用傳統(tǒng)的歐式幾何進(jìn)行描述。而分形算法的出現(xiàn),將這些看似毫無規(guī)律的植物的描述和模擬變成可能。植物的模擬是計(jì)算機(jī)圖形學(xué)的熱點(diǎn)和前沿課題之一,深深地吸引著研究者的眼球。國內(nèi)外有不少研究者運(yùn)用經(jīng)典的分形算法或分形算法的改進(jìn)算法,借助C++、java等語言提出了二維或三維植物的建模方法。如:Lindenmayar于1968年提出的L系統(tǒng)奠定了樹木模擬的基礎(chǔ)[1],Prusinkiewicz等[2-4]于1988~1996年間提出了基于L系統(tǒng)的樹木生長模擬系統(tǒng);國內(nèi)比較有代表性的成果有趙星等于 2001年提出的雙尺度自動機(jī)模型,反映了枝條動態(tài)彎曲過程的力學(xué)原理[5],并于2003年進(jìn)一步對花序進(jìn)行模擬研究,模擬了有限花序和無限花序以及開花的順序[6];張樹兵等于2002年提出了基于L系統(tǒng)的植物建模的改進(jìn),將系統(tǒng)代碼轉(zhuǎn)換成簡單的遞歸表達(dá)式結(jié)構(gòu),但生成的植物單一,沒有參數(shù)化[7];張帆等于2003年提出了基于VRML的簡化L系統(tǒng)算法[8],但生成的樹沒有交互性,也未提出葉序和葉子的生成算法。
模擬植物的主要分形方法有:文法構(gòu)圖算法(L系統(tǒng))、迭代函數(shù)系統(tǒng)算法(IFS算法)、分形演化算法(DLA模型)[9]。經(jīng)研究,單純用其中一種算法來對植物建模,不但在編程實(shí)現(xiàn)方面比較繁鎖,而且缺乏與用戶的交互性。本文一方面采用L系統(tǒng)與遞歸算法相結(jié)合的方法,可以方便地編程實(shí)現(xiàn)植物的建模,另一方面 , X3D結(jié)合JAVA來實(shí)現(xiàn)建模,滿足了用戶的交互性的要求。除此之外,本文提出了基于樹的生理結(jié)構(gòu)的建模,包括,分枝結(jié)構(gòu)、葉序、樹葉。
X3D(Extensible 3D)由Web3D聯(lián)盟提出,并于2004年正式通過ISO/IEC審議成為網(wǎng)絡(luò)三維國際通用標(biāo)準(zhǔn)ISO/IEC19775。它被定義為可交互操作、可擴(kuò)展、跨平臺的網(wǎng)絡(luò)3D內(nèi)容標(biāo)準(zhǔn),其前身是VRML97。X3D除了有VRML97的全部功能外,還整合了XML、JavaScript、Java和流媒體技術(shù)等先進(jìn)技術(shù),擁有更強(qiáng)大、更高效的3D計(jì)算能力、渲染質(zhì)量和傳輸速度[10]。
1.1.1 軸結(jié)構(gòu)
樹枝是構(gòu)成樹的基本骨架,它的長短及空間排列對樹的形狀起著支配作用,不同的樹有不同的分枝形式,主要有以下兩種軸結(jié)構(gòu):
1) 合軸分枝,如圖1(a)所示,即頂芽生長到一定程度后就停止生長或生長速度變慢,這時(shí)側(cè)芽將超過頂芽的生長速度,逐漸長成很大的側(cè)枝,常見的合軸分枝樹有:梧桐、桑樹等;
2) 單軸分枝,如圖1(b)所示,即樹木有明顯的主干。主干是由頂芽不斷向上生長形成的,各級分枝的生長都不超過主干,常見的單軸分枝樹有:松樹、楊樹等。1.1.2 葉序
圖1 樹的分支結(jié)構(gòu)
葉在樹枝上的排列方式稱為葉序。不同的植物有不同的葉序,主要分為:
1) 互生,如圖2(a)所示,即在樹枝的每個(gè)節(jié)點(diǎn)上交互生長出一片樹葉,葉在樹枝上呈螺旋狀分布,如:向日葵;
2) 對生,如圖2(b)所示,即樹枝的每個(gè)節(jié)點(diǎn)上相對地生長出兩片樹葉并排列于莖的兩側(cè),如:石竹;
3) 輪生,如圖2(c)所示,即樹枝上的每個(gè)節(jié)點(diǎn)上生長出3片或3片以上的葉子,也稱輪狀。如:夾竹桃;
4) 簇生,如圖2(d)所示,即兩片或兩片以上的葉子生在節(jié)間極度縮短的樹枝上,如馬尾松、銀杏等。
圖2 葉序
L系統(tǒng)描述的是植物生長的數(shù)學(xué)模型,核心概念是重寫,重寫是通過應(yīng)用一個(gè)重寫規(guī)則或產(chǎn)生式的集合,對簡單的初始目標(biāo)中的部分進(jìn)行連續(xù)置換來定義復(fù)雜目標(biāo)的技術(shù)[11]。一個(gè)L系統(tǒng)可以表示為一個(gè)有序三元組G=
F代表初始元,“[]”表示按要求對初始元執(zhí)行偏移操作,“+”表示向左偏轉(zhuǎn),“-”表示向右偏轉(zhuǎn)“{}”表示將其內(nèi)部作為一個(gè)整體執(zhí)行上移操作。用此文法構(gòu)造二叉樹的過程如圖3所示。
圖3 分形樹的生成過程(n=4)
仔細(xì)分析用L系統(tǒng)生成分形樹的過程,不難發(fā)現(xiàn)這其實(shí)是一個(gè)遞歸過程[11]。本文將參數(shù)L系統(tǒng)和此遞歸過程相結(jié)合,提取出如式(1)所示的數(shù)學(xué)模型,h(0)為初始元,函數(shù)f(i)、g(i)為生成規(guī)則(i為整數(shù)且0≤i<n,n為設(shè)定的樹的深度),i為參數(shù),也為生成元,在每一次的遞歸過程中生成元i都是不同的,根據(jù)不同的參數(shù)i,就會有相應(yīng)不同的生成規(guī)則P。如當(dāng)參數(shù)i=1時(shí),則生成元i=h(i- 1),生成規(guī)則為f(i);當(dāng)1
樹的數(shù)學(xué)模型的遞歸過程如式(2)所示
將上述二維的L系統(tǒng)擴(kuò)展為三維的L系統(tǒng),三維仿射是一個(gè)關(guān)鍵的因素。
定義:L代表原三維圖形,L′代表經(jīng)過三維仿射W后得到的新圖形,則仿射W可表示為
上式可簡化為W:L′ =L·A+T,可通過改變?nèi)S矩陣A、T即可實(shí)現(xiàn)對三維圖形的旋轉(zhuǎn)、平移、按比例縮放等操作,如
分別表示原圖形L繞X軸、Y軸、Z軸旋轉(zhuǎn)一定弧度α;
· 若T= (0,h,0 )T,則表示L沿Y軸方向平移h。
在以上理論中,需用鏈表結(jié)構(gòu)來表示二叉樹,這樣編程實(shí)現(xiàn)的效率較低。本文用 X3D結(jié)合JAVA的方式實(shí)現(xiàn)建模,大大簡化了程序的復(fù)雜度,同時(shí)也滿足了用戶實(shí)時(shí)性和交互性的要求。一方面 X3D中定義了很多幾何圖形節(jié)點(diǎn)和材質(zhì)等域,利用這些節(jié)點(diǎn)和域就可以簡單快捷地生成三維的初始元圖形;另一方面,為了節(jié)約內(nèi)存等開銷,降低編程的繁瑣度,使用戶可隨機(jī)地生成想要的圖形,本文用JAVA來實(shí)現(xiàn)用遞歸結(jié)構(gòu)來代替鏈表結(jié)構(gòu)。
用n(n>0)表示樹的層數(shù),以控制整個(gè)程序的遞歸次數(shù);用t(t>0)表示t叉樹,即一個(gè)主干上有t個(gè)分枝;用b(b
1)T是由Cylinder節(jié)點(diǎn)定義的一個(gè)半徑為r[j],高度為h[j]的圓柱體并沿Y移動-h[j]/2,r[j]、h[j](0 ≤j 2) 定義Tmax+=T[a](0 ≤a 3) 如果j= 0(0 ≤j 4) 如果j=1,則使G[0]繞Y軸旋轉(zhuǎn)一定弧度6.282 (a+1)/m,并沿Y軸平移 -h[j]·(a+ 1)·ts/m,記為T1[a],重寫Tmax,并命Tmax+=T1[a];對L=g[ 0]+Tmax+T沿Y軸平移h[j],然后繞X軸旋轉(zhuǎn)一定弧度wt,得到的結(jié)果記為g[1]; 5) 如果j=n-1,定義stbe+=tbe[i](0≤i 否則將g[j- 1]+Tmax+T沿Y軸平移h[j],然后繞Y軸旋轉(zhuǎn)一定弧度wt,此變換記為G[j],所得圖形記為g[j]; 6) 輸出圖形g[n-1],即為最終結(jié)果。只要輸入不同的參數(shù)就可以得到不同的樹,其中生成的部分分形樹效果圖如圖4所示。 圖4 生成的分形樹 在葉序的生成過程中,用n控制遞歸次數(shù),用m來控制中間生成元中樹葉的樹木和葉序的種類,用w控制樹葉與父枝的夾角,用α控制樹枝的彎曲度。以下為具體算法步驟: 1) 用Cylinder節(jié)點(diǎn)生成樹葉所附著的樹枝stick,高度為H,并將stick上移H/2; 2) 如果m=1,即要生成互生葉序,則用內(nèi)聯(lián)節(jié)點(diǎn)Inline讀取生成的樹葉節(jié)點(diǎn)leaf.x3d,并繞X軸旋轉(zhuǎn)一定弧度w,然后沿Y軸平移H,所得結(jié)果記為t[0];復(fù)制t[i-1],并繞Y軸旋轉(zhuǎn)一定弧度1.5705,然后沿Y軸平移-H/m,所得結(jié)果記為t[i](其中0≤i 3) 如果m=2,則即要生成對生葉序,則用內(nèi)聯(lián)節(jié)點(diǎn)Inline讀取生成的樹葉節(jié)點(diǎn)leaf.x3d,并繞Z軸旋轉(zhuǎn)一定弧度w,然后沿Y軸平移H;繼續(xù)導(dǎo)入leaf.x3d,,并繞Z軸旋轉(zhuǎn)一定弧度-w,然后沿Y軸平移H; 4) 否則就生成輪生或簇生葉序,則用內(nèi)聯(lián)節(jié)點(diǎn)Inline讀取生成的樹葉節(jié)點(diǎn)leaf.x3d,并繞Y軸旋轉(zhuǎn)一定弧度6.282(c/m+ 1)/m,然后沿Y軸平移 -H·c/m2,所得結(jié)果記為t[0];復(fù)制t[i-1],并繞Y軸旋轉(zhuǎn)一定弧度1.5705,然后沿Y軸平移-H/m,所得結(jié)果記為t[i](0 ≤i<m)。若c=0即為輪生葉序,否則為簇生葉序; 5) 將以上生成的圖形記為G[0]; 6) 將G[j-1]繞X軸旋轉(zhuǎn)一定弧度α,然后沿Y軸平移H;復(fù)制G[j-1],將此步驟中生成的圖形記為G[j](0 ≤j 7) 輸出圖形G[n- 1],即為最終結(jié)果,生成的葉序效果圖如圖2所示。 繪制樹葉模型的基本思想是先畫一個(gè)三角形△ABC,然后以△ABC為生成元,對它進(jìn)行旋轉(zhuǎn)、縮放等操作,然后將之前生成的總圖形作為生成元重復(fù)以上步驟就可以得到想要的結(jié)果。在建模的過程中,用n來控制遞歸次數(shù),用參數(shù)y來控制線段AB的初始長度,用β控制△ABC的寬度,用s控制線段AB與AC的長度差異,用α控制葉子的彎曲程度。具體算法步驟如下: 1) 給定初始坐標(biāo)A( 0,0,0)和B(0,y,0 ),用公式(6)求得三角形另一個(gè)頂點(diǎn)C(x′,y′,z′),其中∠CAB=β,s為線段AC的長短比例(A點(diǎn)坐標(biāo)不變),畫三角形△ABC得到圖形L[0]; 1) 將上一步中得到的圖形L繞Y軸旋轉(zhuǎn)一定弧度α,然后繞Z軸旋轉(zhuǎn)一定弧度β,得到新圖形L′; 2) 將L[0]按比例s[i]=1 + 0.2i縮放(A點(diǎn)坐標(biāo)不變)得到圖形L[i]; 3) 將前面所有步驟中得到的總圖形L+L[i]作為新的圖形L并返回步驟2),重復(fù)n次,就能得到想要的葉子圖形。 生成的樹葉模型如圖5所示,有橢圓形、針形、菱形、掌形、扇形等,只要輸入不同的參數(shù)就可以生成不同的葉子模型。 圖5 生成的葉子 本文針對傳統(tǒng)L系統(tǒng)編程實(shí)現(xiàn)繁瑣,生成的圖形沒有隨機(jī)性的不足,提出了用 X3D結(jié)合JAVA來輕松實(shí)現(xiàn)三維圖形的建模,以上所介紹的系統(tǒng)不僅可以生成逼真的三維樹,還可以通過設(shè)置不同的參數(shù),生成花、草等其他三維圖形,除此之外,可用改變參數(shù)的方式,運(yùn)用 X3D中生成動畫的節(jié)點(diǎn)可生成動態(tài)的圖形,如樹木的生長過程,花開的過程等。因此,本方法還是有一定的推廣價(jià)值。 [1]Lindenmayer A. Mathematical models for cellular interactions in development [J]. Journal of Theoretical Biology, 1968, 18: 280-315. [2]Prusinkiewicz P, et al. Developmental models of herbaceous plants for computer imagery propose [J].Computer Graphics, 1988, 22 (4): 141-150. [3]Prusinkiewicz P, et al. Synthetic topiary [C]//Computer Graphics Proceedings, Annual Conference Series,ACM SIGGAR PH,Orlando, Florida, 1994: 351-358. [4]Mech R, Prusinkiewicz P, et al. Visual models of plants interacting with their environment [C]//Computer Graphics Proceedings, Annual Conference Series,ACM SIGGAR PH, New Orleans, Louisiana, 1996:397-410. [5]趙 星, DeReffye P, 熊范綸, 等. 虛擬植物生長的雙尺度自動機(jī)模型[J]. 計(jì)算機(jī)學(xué)報(bào), 2001, 24(6):608-617. [6]趙 星, DeReffye P, 熊范綸, 等. 基于雙尺度自動機(jī)模型的植物花序模擬[J]. 計(jì)算機(jī)學(xué)報(bào), 2003, 26(1):116-124. [7]張樹兵, 王建中. 基于L系統(tǒng)的植物建模方法改進(jìn)[J].中國圖像圖形學(xué)報(bào), 2002, 7(5): 457-460. [8]張 帆, 譚建榮. VRML環(huán)境中3維分形植物的生成及應(yīng)用[J]. 計(jì)算機(jī)工程, 2003, 29(21): 110-112. [9]孫博文. 分形算法與程序設(shè)計(jì)[M]. 北京: 科學(xué)出版社, 2004: 61-216. [10]張金釗, 張金銳, 張金鏑. X3D 虛擬現(xiàn)實(shí)設(shè)計(jì)[M].北京: 電子工業(yè)出版社, 2007: 7-8. [11][加]Prusinkiewicz P, Lindenmayer A. 植物的算法美[M]. 孟 軍, 鄧華玲譯. 北京: 科學(xué)出版社,2008: 1-3.3.2 樹的葉序結(jié)構(gòu)的建模
3.3 樹葉的建模
4 結(jié) 束 語