張 杰， 蔡文奇

（汕頭大學(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)

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 葉序

1.2 L系統(tǒng)原理

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=，其中，V是系統(tǒng)的字母表，w∈V+是一個(gè)非空字符串（稱為起始字符串），P?V×V+是一個(gè)產(chǎn)生式（改寫規(guī)則）的有限集合，一個(gè)產(chǎn)生式(a,x)∈P記為a→x[17]。本文用以下文法為基本理論建立植物模型（以二維二叉樹為例）

F代表初始元，“[]”表示按要求對初始元執(zhí)行偏移操作，“+”表示向左偏轉(zhuǎn)，“-”表示向右偏轉(zhuǎn)“｛｝”表示將其內(nèi)部作為一個(gè)整體執(zhí)行上移操作。用此文法構(gòu)造二叉樹的過程如圖3所示。

圖3 分形樹的生成過程(n=4)

2 改進(jìn)的三維L系統(tǒng)

2.1 改進(jìn)L系統(tǒng)的數(shù)學(xué)模型

仔細(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)所示

2.2 三維L系統(tǒng)

將上述二維的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。

3 用改進(jìn)的L系統(tǒng)建立植物模型

在以上理論中，需用鏈表結(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)。

3.1 樹的分枝結(jié)構(gòu)的建模

用n(n>0)表示樹的層數(shù)，以控制整個(gè)程序的遞歸次數(shù)；用t(t>0)表示t叉樹，即一個(gè)主干上有t個(gè)分枝；用b(b0)控制每根樹枝上葉序簇的數(shù)量；樹干的粗細(xì)、長短分別用比例系數(shù)trs、tls來控制；wt控制樹枝與父枝的夾角；wl控制葉序簇與父枝的夾角；用比例系數(shù)ls控制葉序簇的大小比例等參數(shù)。

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 生成的分形樹

3.2 樹的葉序結(jié)構(gòu)的建模

在葉序的生成過程中，用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所示。

3.3 樹葉的建模

繪制樹葉模型的基本思想是先畫一個(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 生成的葉子

4 結(jié) 束 語

本文針對傳統(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.