楊 剛

(陜西理工學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，漢中 723000)

虛擬植物是利用計(jì)算機(jī)模擬植物的形態(tài)、生長發(fā)育,并用可視化技術(shù)將其進(jìn)行展現(xiàn)的技術(shù).其研究涉及計(jì)算機(jī)、數(shù)學(xué)、植物學(xué)以及生態(tài)學(xué)等多個(gè)學(xué)科,并在農(nóng)業(yè)、娛樂、科研、教育等諸多領(lǐng)域具有較高的應(yīng)用價(jià)值.植物生長模擬與可視化是虛擬植物研究中最重要的兩個(gè)關(guān)鍵技術(shù),也是虛擬植物研究的核心問題.本文主要利用L系統(tǒng)理論,根據(jù)不同樹木的生成規(guī)則,建立其對應(yīng)數(shù)學(xué)模型,實(shí)現(xiàn)樹木圖形快速模擬生成;重點(diǎn)研究了隨機(jī)L系統(tǒng)中樹木的生成,并采用Visual C++生成了多種形態(tài)逼真的樹木圖形.

1 L系統(tǒng)的基本原理

1.1 概述

L系統(tǒng)是美國生物學(xué)家Aristid LindenMayer于1968年提出的,它本質(zhì)是一個(gè)重寫系統(tǒng),通過對植物對象生長過程的經(jīng)驗(yàn)式概括和抽象,初始狀態(tài)與描述規(guī)則,進(jìn)行有限次迭代,生成字符發(fā)展序列以表現(xiàn)植物的拓?fù)浣Y(jié)構(gòu),并對產(chǎn)生的字符串進(jìn)行幾何解釋,就能生成非常復(fù)雜的分形圖形.

1.2 基本原理

L系統(tǒng)的基本原理是令V表示字母集,V*表示V上所有單詞(由符號或字符組成的字符串)的集合,V+表示V上所有非空單詞的集合,利用一個(gè)三元組來表達(dá)所需要構(gòu)造的對象G=〈V，ω，P〉,其中V是一個(gè)字符集,其中的元素用來組成表示圖形命令的字符串;ω是起始元,用以確定字符串的起始狀態(tài);P是產(chǎn)生式(或叫規(guī)則)的有限集合,產(chǎn)生式P寫作α→χ,字母α和單詞χ分別稱作產(chǎn)生式的前驅(qū)和后繼[1].規(guī)定對任何字母α∈V,至少存在一個(gè)χ→V+,使得α→χ.若對給定的前驅(qū)α∈V無明確的產(chǎn)生式,則規(guī)定α→α這個(gè)特殊的產(chǎn)生式屬于規(guī)則P.

1.3 L系統(tǒng)的解釋

L系統(tǒng)中的起始元和產(chǎn)生規(guī)則都是由字符串描述的,為了使該字符串能描述某種圖形,需要給L系統(tǒng)中每一個(gè)字母賦予一個(gè)特定的圖形含義.一般用“龜圖解釋法”對L系統(tǒng)進(jìn)行圖形說明.

龜圖解釋法的基本思想是:將龜?shù)臓顟B(tài)定義為三元組(x，y，α).其中笛卡爾坐標(biāo)(x，y)表示龜?shù)奈恢?方向角α被解釋為龜頭所指的方向[2].給定步長d和角度增量δ,龜可以反饋下述符號表示的命令:

F:向前移動(dòng)步長d,龜?shù)臓顟B(tài)變?yōu)?x′，y′，α),其中x′=x+dcosα,y′=y+dsinα,在點(diǎn)(x，y)和(x′，y′)間畫一直線段;

f:向前移動(dòng)步長d,不畫線;

+δ:向左轉(zhuǎn)δ,龜形的下一狀態(tài)為(x′，y′，α+δ),角的正向?yàn)槟鏁r(shí)針方向;

-δ:向右轉(zhuǎn)δ,龜形的下一狀態(tài)為(x′，y′，α-δ),角的負(fù)向是順時(shí)針方向.

“[”和“]”: 用來描述植物的分支結(jié)構(gòu),它們是植物分支的分界符,必須成對出現(xiàn);左括號表示分支的開始,右括號表示分支的結(jié)束.

2 確定L系統(tǒng)

2.1 確定L系統(tǒng)的定義

令V表示字母集,V*表示V上所有單詞的集合,V+表示V上所有非空單詞的集合,對每個(gè)α∈V,當(dāng)且僅當(dāng)僅有一個(gè)單詞χ∈V+,使得α→χ,那么就說0L系統(tǒng)是確定的,記作D0L系統(tǒng).D0L系統(tǒng)是最初的,也是最簡單的L系統(tǒng).

2.2 確定L系統(tǒng)的實(shí)現(xiàn)

利用L系統(tǒng)生成的樹,一般都有分枝結(jié)構(gòu).確定L系統(tǒng)的產(chǎn)生式(即規(guī)則)一般可以分為單規(guī)則產(chǎn)生式和多規(guī)則產(chǎn)生式,其中多規(guī)則產(chǎn)生式描述景物分枝的字母不唯一,同時(shí)字母替換的表達(dá)式也不唯一,有多種選擇[3].單規(guī)則的產(chǎn)生式一般生成的數(shù)木比較生硬、規(guī)律,而多規(guī)則的產(chǎn)生式生成的樹木比較柔和、形象.

現(xiàn)列舉一個(gè)多規(guī)則的分枝結(jié)構(gòu)實(shí)例.設(shè)初始生成元ω為F,改寫規(guī)則P1為F[-F]F[+F][-F],P2為F+[F-F+F]-[F-F+F+F],令移動(dòng)步長d=20、旋轉(zhuǎn)角度δ=20度、迭代次數(shù)為4,則繪制的圖形如下圖1所示,由圖可見繪制的樹木具有莖干的粗細(xì)相同、缺乏樹葉等缺點(diǎn).

設(shè)初始生成元ω為F,改寫規(guī)則P1為F[-F]F[+F][-F],P2為FF-[-F+F+F]+[+F-F-F],令移動(dòng)步長d=10,旋轉(zhuǎn)角度δ=20度、迭代次數(shù)為3,則繪制的圖如下圖2所示.

圖1 確定L系統(tǒng)生成的樹 圖2 改變規(guī)則后生成的樹 圖3 增加符號命令后生成的樹

如果增加符號命令:G,用于在兩點(diǎn)之間繪制一定粗細(xì)的直線,主要用于繪制樹干;H,在以兩點(diǎn)為對角線的矩形中繪制豎直放置的橢圓,主要用于繪制樹的樹葉.初始生成元ω為F,改寫規(guī)則P1為F-[F+F]+FF-[+F-F]+[-F],P2為GG-[-F[H]+F+F]+[+F-F-F],令移動(dòng)步長d=20、旋轉(zhuǎn)角度δ=20度、迭代次數(shù)為4,則繪制的圖形如下圖3所示.可見生成規(guī)則、步長、迭代次數(shù)的不同對生成的樹有較大的影響;增加符號命令后生成的樹在莖桿粗細(xì)、樹葉生成方面比原來有一定的改善.

3 隨機(jī)L系統(tǒng)

由圖1～圖3可見,確定L系統(tǒng)繪制的樹木顯得比較生硬、呆板,在真實(shí)性方面有一定的缺陷.如果在生成規(guī)則中引入隨機(jī)性可以改善這種情況,可以得到更加生動(dòng)、逼真的樹木景物.

3.1 隨機(jī)L系統(tǒng)的定義

隨機(jī)L系統(tǒng)的特點(diǎn)是它生成的植物不僅能夠保持植物的總體特征而且在細(xì)節(jié)處有所變化.這種變化可以體現(xiàn)在兩個(gè)方面:植物的幾何形狀和拓?fù)浣Y(jié)構(gòu)[5-6].

3.2 隨機(jī)L系統(tǒng)的實(shí)現(xiàn)

設(shè)初始生成元ω為F,改寫規(guī)則P1,P2,P3分別為F[+F]F[-F]F，F(xiàn)[+F]F[-F[+F]]，F(xiàn)F-[-F+F+F]+[+F-F-F],各規(guī)則出現(xiàn)的概率均為1/3;令移動(dòng)步長d=3、旋轉(zhuǎn)角度δ=30度、迭代次數(shù)為4,則繪制的圖形如下圖4所示.由圖可見隨機(jī)L系統(tǒng)繪制的樹木比較柔和、形象、自然,但這些圖形也有缺點(diǎn):和灌木比較類似.圖4中的樹木在生成時(shí), 其隨機(jī)性可以通過函數(shù)rand()實(shí)現(xiàn)的,在程序中可以添加語句“rand()%3”,此語句生成1個(gè)范圍在0～3的隨機(jī)整數(shù)(不含3在內(nèi)),這樣就可以按照一定的概率選擇產(chǎn)生規(guī)則.

(a) (b) (c) (d)圖4 隨機(jī)L系統(tǒng)生成的樹

(a) (b) (c) (d) (e) (f)圖5 添加隨機(jī)數(shù)種子后隨機(jī)L系統(tǒng)生成的樹

現(xiàn)在為了使隨機(jī)L系統(tǒng)生成更加豐富類型的樹木,可以修改程序中體現(xiàn)隨機(jī)性的代碼.具體可以在程序中體現(xiàn)隨機(jī)性的代碼前面添加隨機(jī)數(shù)種子,即srand((unsigned) time(NULL)),這樣就可以使rand()產(chǎn)生真正的隨機(jī)數(shù).此時(shí)L系統(tǒng)生成的樹木如圖5所示.比較圖4和圖5可見,語句srand((unsigned) time(NULL))對繪圖結(jié)果的影響是十分顯著的,繪制植物的幾何形狀和拓?fù)浣Y(jié)構(gòu)都發(fā)生了較大的變化.

(a) (b)圖6 開花的分形樹

4 開花的分形樹的生成

在生活中有些樹可以開花,繪制這種樹就比較復(fù)雜,需要對L系統(tǒng)的算法進(jìn)行改進(jìn).設(shè)初始生成元ω為F,改寫規(guī)則P1,P2分別為F,FF-[-F+F+F]+[+F-F-F],各規(guī)則出現(xiàn)的概率均為1/2;令移動(dòng)步長d=6、旋轉(zhuǎn)角度δ=25度、迭代次數(shù)為4,再添加控制兩節(jié)點(diǎn)之間線段寬度和樹木干莖顏色的變量flag并給它加上一個(gè)隨機(jī)增量rand()%5,在Visual C++中編程實(shí)現(xiàn)開花的樹的繪制,則繪制的圖形如圖6所示(其中圖a中flag初值取為4,圖b中flag初值取為5).可見，此時(shí)繪制的樹色彩十分豐富、細(xì)節(jié)繪制處理的比較別致,圖形比較有特色.

5 結(jié)語

本文研究了L系統(tǒng)的基本原理、確定L系統(tǒng)、隨機(jī)L系統(tǒng),并給出具體的實(shí)例,在Visual C++下編程實(shí)現(xiàn)了樹木的生成.研究中發(fā)現(xiàn),利用L系統(tǒng)的分形技術(shù)可以較好地模擬樹木等植物;但對于一組具體的規(guī)則很難預(yù)料到經(jīng)多次迭代后生成樹木的具體形態(tài),甚至有時(shí)產(chǎn)生的繪制結(jié)果令人感到意外;同樣對于給定的是樹木,要想找到其L系統(tǒng)的生長規(guī)則是一件不容易的工作,許多時(shí)候需要經(jīng)驗(yàn)和不斷地試探、修改,有時(shí)甚至是不可能的.另外,給定一組生成規(guī)則,程序中細(xì)節(jié)處理的不同對最終生成的植物形態(tài)有很大影響;研究中還發(fā)現(xiàn)在程序中巧妙地利用隨機(jī)性可以生成許多粗細(xì)變化的、顏色豐富、拓?fù)浣Y(jié)構(gòu)變化的植物圖形.

參 考 文 獻(xiàn)

[1] 丁 歡,萬旺根,黃炳,王道臣.三維嵌套L系統(tǒng)及其在植物模擬中的應(yīng)用[J].計(jì)算機(jī)工程與應(yīng)用,2009,45(5):207-209,242.

[2] 黃爭舸.虛擬自然場景建模和可視化的若干問題研究[D].杭州:浙江大學(xué),2008.

[3] 孫天凱,邵曉根,王興元.擴(kuò)展的分形L-系統(tǒng)與自然景觀的動(dòng)態(tài)模擬[J].計(jì)算機(jī)工程與應(yīng)用,2009,45(2):182-184,190.

[4] J.S.Hanan.Parametric L-Systems and Their Application to the Modelling and Visualization of Plants[D].Canada:University of Regina,1992.

[5] 王曉軍,吳 健,夏 潔,崔志明.基于L-系統(tǒng)的三維分形圖形描述語言系統(tǒng)[J].計(jì)算機(jī)工程,2009,35(12):194-197.

[6] 陳 曉,彭國華,趙 叢.基于分形三維L系統(tǒng)的真實(shí)樹木搖拽動(dòng)態(tài)模擬[J].計(jì)算機(jī)工程與應(yīng)用,2008,44(26):77-79,94.