基于Ｌ系統改進的虛擬植物原型系統設計

（重慶大學 計算機學院， 重慶 400044）

摘要：設計實現了基于L系統改進的虛擬植物可視化原型系統。該原型系統實現了微機平臺上可視模擬植物生長，并取得了較好的試驗效果。系統設計思想以植物可視外觀展現為主要目的，結合了L系統和基于圖像建模的優點，對植物器官的建模方法是基于能夠反映植物器官主要特征的表面建模。其實現思路是在L系統所描述的植物拓撲結構的基礎上，對預先定義好的植物器官網格面進行裝配。與L系統相比較，有更好的外觀效果和較低的時間復雜度。

關鍵詞： 虛擬植物 ； L系統； 網格面

中圖法分類號： TP391文獻標識碼： A

文章編號： 1001 3695(2006)08 0232 03

Development Prototype of Virtual Plant Based on Improved L System

LI Yun feng， ZHU Qing sheng， FU He gang， GU Ping

(College of Computer Science， Chongqing University， Chongqing 400044， China)

Abstract: A prototype of virtual plant based on improved L system is designed. The

platform can run well on personal computer， and achieved good visual result of simulating the growth of virtual plant. The method combines the characteristic of L system and the visual result of image modeling. To construct main stem and major branch based on L ystem， growing the remainder of the plant based on plant organs model of mesh. The proposedmethod reduced the complexity of L system， and resulted in realistic view of virtual plant.

Key words: Virtual Plant; L System; Mesh

自然植物計算機模擬一直是計算機圖形學的研究熱點。如何對植物模型進行有效的控制是亟待解決的問題：模型參數過少不足以表現植物復雜多樣的各種特征；參數過多則可能導致模型過于復雜，實際應用困難。L系統是一種形式語言，其本質是一個重寫系統，它通過對公理應用產生式進行有限次迭代后，對產生的字符串進行幾何解釋，就能生成非常復雜的圖形。L系統側重于植物拓撲結構的表達，具有堅實的數學理論基礎、定義簡潔、結構化程度高、易于實現等優點。但該方法無法預測植物的最終生成形狀，對重寫過程很難有效控制；同時L系統過于復雜，稍微復雜的植物其L系統規則提取困難。基于粒子的系統，如AMAP模型將地球上的植物歸類為二十多個植物結構基本模型。對于某種植物，系統通過模式識別方法提取生長規則，進行定性分析，確定描述其結構的基本模型。在此基礎上對植物結構進行定量化，應用幾何方法表達其形態規律。

本文基于一種新的建模方法（稱之為EasyL系統），該方法結合了L系統和基于圖像建模方法的優點。其基本思路是對植物主干的分枝仍采用傳統L系統建模，細節部分則采用植物器官網格面進行建模。系統利用L系統對植物主干建模表達能力強的優點，改進了單一采用L系統進行植物建模時，時間復雜度比較高以及對生成的植物外觀可控性差的缺點。因此EasyL系統與經典L系統相比較，在時間復雜度上有較好的改善。在此基礎上設計了一種基于L系統改進的虛擬植物可視化原型系統（VP1.0），滿足了在機器配置比較低的情況下模擬植物的生長要求。

1 EasyL系統

EasyL系統結合了L系統和基于圖像建模的優點，對植物器官的建模方法是基于能夠反映植物器官主要特征的表面建模。例如，對于葉建模主要提取葉的正面輪廓圖像；對于樹干建模，主要提取樹干的橫截面形狀，然后采用圖形變換方法（如拉伸、扭曲等方法）。 EasyL系統優點主要有：①提高植物生長視覺效果。對于植物器官的建模是基于植物器官圖像進行的，通過對能夠反映植物器官特點的圖像進行特征提取來生成植物器官圖形符號，因此比L系統更加真實地反映了植物器官的特點，所以整株植物在視覺效果上優于L系統。②降低了時間復雜度。在L系統中，對時間復雜度要求高的就是L系統文法的迭代過程，其時間復雜度是呈幾何級數增長的，因此在迭代步數較多的情況下，其時間復雜度是很高的。在EasyL系統中，將傳統L系統對植物器官的細節部分的描述改為傳統的基于表面的建模，有效地降低了系統的時間復雜度。

系統注重植物可視化重建的視覺效果，不是嚴格符合植物的生理模型。其實現思路是在L系統所描述的植物拓撲結構的基礎上，對預先定義好的植物器官的網格面進行裝配的過程，即植物器官建模過程是離散過程。系統采用L系統能使其連續化。

2 VP1.0系統設計

2.1 系統設計目標

VP1.0系統的設計目標是對EasyL系統進行建模實驗，其設計目標應該能夠滿足以下基本要求：①系統必須能夠滿足多文檔用戶的要求，也就是該系統同時可以輸入多株植物的EasyL系統文法，可以對多株植物進行顯示。②系統應該能夠提供友好的人機界面，讓用戶輸入EasyL系統的文法，并可以進行文法的錯誤檢查。③系統應該支持保存功能，即可以將EasyL系統的文法和輸出的結果等進行保存。在需要時，可以重新調入系統。④系統應該可以提供植物器官模型的導入和設置功能，可以把植物器官的三角剖分網格面導入，可以對該植物器官名字進行更改，也可以對該植物器官進行模擬顯示，并可以在三維空間里旋轉，還能夠更改該三角網格顏色的顯示。⑤系統還應該能夠對EasyL系統的字符進行設定，如設定rx字符表示繞 X 軸旋轉。⑥系統應該能夠對EasyL系統的各個演化過程后形成的最終字符串顯示給用戶，并且可以對EasyL系統的演變過程進行控制，設定EasyL系統演化的步驟及對上一個演化狀態進行顯示。⑦系統可以對EasyL系統演化后的最終字符串在三維空間中進行渲染。在渲染過程中可以通過輸入攝像機的位置，或者通過鼠標拖動改變攝像機的位置。而且用戶通過設置環境燈來控制環境的明暗程度可以移動燈光的位置和調節燈光的明暗程度。以各種方式來進行三維圖形的顯示，除了顯示攝像機的視圖外，還可以分別從 X，Y，Z 三軸的方向來觀察植物，也可以在全屏幕顯示攝像機視圖。另外，能將生成的植物導出為三維模型。⑧用戶可以設置三維渲染圖形的背景顏色并將顯示結果輸出。

2.2 開發平臺和工具的選取

硬件方面，CPU為P4 2.4GHz， 內存為512MB，顯卡為GForce4；操作系統為Windows 2000；開發工具為Microsoft Vi sual C+ + 6.0；圖形庫為OpenGL，Vcg。

2.3 VP1.0系統主要功能模塊

(1)EasyL系統存取模塊。它實現的子模塊有文檔的存盤、文檔的載入兩大模塊。文檔的存盤是將當前植株文法、器官的網格模型、植株的演變結果等存入系統的硬盤上，用戶在需要時可以從硬盤載入。

(2)文法管理模塊。它是一個簡單的文法編輯器，其子模塊有文法輸入模塊、文法編輯模塊和文法編譯模塊。文法輸入模塊讓用戶可以從指定的文本文件導入文法到編輯框中，也可以將現在編輯的文法存入到一個文本文件中;文法編輯模塊是為了方便用戶的輸入，提供拷貝、粘貼功能等；文法編譯模塊可以檢查文法輸入的語法錯誤，輸出調試信息。

(3)植物器官的建模模塊。它包括植物器官特征圖像的輸入、植物器官特征圖像的轉換和器官圖形符號變形三個子模塊。

(4)器官載入模塊。它包括器官網格面文件的讀取與寫入、網格面的顯示、三角網格面法線方向的定義以及網格面在進行渲染時顏色的定義幾個模塊。網格面的讀入與寫入模塊是系統將網格文件中的三角形的頂點讀出來，放入到系統指定的緩沖中，以便系統方便顯示出來，寫入的過程與之相反；網格面的顯示模塊是根據讀入的三角形的緩沖區的頂點數據，利用OpenGL的庫函數顯示出來，用戶可以通過鼠標拖動的方式來改變攝像機的位置，也可以選取三角形的法線方向和其他的顯示參數，如用戶可以選擇是否進行平滑處理、器官渲染的顏色等。

(5)字母表設置模塊。它是為L系統文法中除了植物模塊器官符號以外的各個字母進行設置，如定義哪個符號是旋轉的，哪個符號是縮放的等。系統根據這些設置來進行植物的圖形化顯示過程。

（6）EasyL系統演化模塊。其功能主要是將EasyL系統當前的字符串結果顯示出來，還可以手工指定系統演化步驟，除此以外，可以看到系統的上一個演化的狀態字符串。

（7）系統顯示模塊。它將EasyL系統演化后的最終字符串結果以圖形化的方式顯示出來，包括

攝像機位置的選取、燈光的設置、顯示方式幾個模塊。攝像機的位置是用戶觀察植物的位置，其選取方式包括用戶的輸入值方式和鼠標拖動方式。圖形顯示的方式包括 X，Y，Z 三個方向、攝像機視圖以及全屏方式下攝像機視圖的幾種方式。

3 系統關鍵技術分析

3.1 文法編譯器

文法編譯器主要完成分析用戶輸入的文法是否正確，如果不正確，給用戶提示；將文法分析的結果以一定的格式存放在系統中，以方便后面執行文法模塊調用;系統定義以下保留字，這些保留字在系統中均有特定含義，其他變量不能與之相沖突，否則認為是語法錯誤。符號定義為

//: 注釋一行，從“//”開始到行末的語句全部都被注釋;

/*:塊注釋的開始符號;

*/:塊注釋的結束符號;

，:分隔符;

[:字母表的開始標記和在產生式中用來表示條件的開始標記；

]:字母表的結束標記和在產生式語句中表示條件的結束標記；

{：產生式的開始標記；

}：產生式的結束標記；

(:表示參數的開始；

):表示參數的結束；

：：產生式的輸入與輸出分隔符。

EasyL進行語法分析的過程包括兩個階段，即詞法分析和語法分析階段。詞法分析階段的任務

是分析出各個詞法單元，EasyL系統中的詞法單位包括一個字母表和 n 個產生式組成；語法分析階段的任務是對產生式或者字母表進行語法的分析。系統進行編譯時要進行兩次掃描，第一次掃描分析出詞法單位，第二次掃描對各個詞法單位進行分析。

3.2 文法執行

文法執行過程是根據初始的公理，利用產生式規則產生字符串的過程，例如給定產生式規則和初始公理如下：

字母表為[A，F，S，L，rx，ry，rz]

產生式為 {A(t)，*，*，[]:<> [rz(22.5) F(t) L(t*3) A( t* 0.9)]ry( 112.5)[rz(22.5) F(t) L(t*3) A(t*0.9)]ry(112.5 ) [rz(22.5) F(t) L(t*3) A(t*0.9)]}{F(t)，*，*，[]: <> S(t) ry( 112.5) F(t) }{S(t)，*，*，[]:<> F(t) L(t*3) }

給定初始條件為A（1），則進行一次迭代后：

[rz(22.5)f(1)l(3)a(0.9)]ry( 112.5)[rz(22.5)f(1)l(3) a(0.9) ]ry( 112.5)[rz(22.5)f(1)l(3)a(0.9)]

進行二次迭代后：

[rz(22.5)s(1)ry( 112.5)f(1)l(3)[rz(22.5)f(0.9)l(2.7)a(0.81)]ry( 112.5)[rz(22.5)f(0.9)l(2.7)a(0.81)]ry( 112.5)[rz(22.5)f(0.9)l(2.7)a(0.81)]]ry( 112.5)[rz(22.5)s(1)ry ( 112.5) f(1)l(3)[rz(22.5)f(0.9)l(2.7) a(0.81)]ry( 112.5)[rz (22.5) f(0.9)l(2.7) a(0.81) ]ry( 112.5)[rz(22.5)f(0.9)l(2.7) a(0.81) ]]ry( 112.5)[rz(22.5)s(1)ry( 112.5)f(1)l(3)[rz (22.5) f(0.9)l(2.7)a(0.81)]ry( 112.5)[rz(22.5)f(0.9)l(2.7) a(0.81) ]ry( 112.5)[rz(22.5)f(0.9)l(2.7)a(0.81)]]

對初始狀態進行若干次迭代的過程就是文法的執行過程，在計算機上實現的算法如下：

（1） 數據結構

CState 狀態類，保存系統當前狀態

CStateEntry 某一個狀態

CProductionList 產生式的集合類，包含目前的文法系統中所有的產生式

定義幾個全局的對象來保存系統的狀態

CState LastState 用來保存上一個狀態字符串

CState ActualState當前的字符串

CProductionList Prod 系統的產生式集合

（2）算法

①將初始狀態A(1)的值賦給LastState和ActualState，將1值賦給 i ；迭代的步數 N ，LastState←A(1)，ActualState← A(1)，i←1。

②從ActualState中取 i 個狀態值賦給CStateEntry的臨時變量StateInput，如果第 i 個變量為空，則轉向⑥。

StateInput←ActualState[ i ]

③從StateInput中將狀態的名字和參數提取賦給Input和Param變量，將1賦給 j ；Input←

StateInput×Name，Param←StateInput×Param。

④從Prod集合中取出第 j 條產生式，如果該產生式的前綴與Input匹配，則轉向⑤；否則j + + ，轉向④。如果Prod中的所有元素均被取出，則轉向②。

⑤執行第 j 條產生式，將得到的輸出添加到臨時變量CState NextState中，轉向④。

⑥將ActualState賦給LastState，將NextState賦給ActualState。迭代步數 K 加 1，如果 K等于N ，程序結束；否則，將 i 的值賦1，轉向②。

3.3 三角網格面渲染

EasyL系統進行迭代后生長的字符串序列如何進行全三維顯示，讓用戶實時地看到植物生長的過程是系統最終的目的。在本文中，采用SGI的OpenGL庫進行植株的最終顯示，其算法如下：

(1)初始化算法中將要用到的變量：

DrawState=ActualState， i =0

(2)取ActualState的第 i 個符號賦給當前處理的變量CurrentDraw：

CurrentDraw=ActualState[ i ]

如果CurrentDraw的值為空，則整個處理過程完畢，算法終止。

(3)根據符號CurrentDraw的不同類型進行相應的處理。如果CurrentDraw的類型為變換函數，則對當前的對象符號進行變換處理，如放大、縮小、坐標變換等；如果為入棧符號，則保留當前的坐標位置到棧中，如果為出棧，則將棧頂元素彈出；如果為器官符號，設定變量 j 的初始值為1，設置OpenGL的繪圖模式為三角面的繪圖模式和顏色，轉向(4)。

上面是對當前字符串進行處理的基本過程，另外，在對其進行渲染的過程中，還應該處理如燈光、攝像機等其他參數，處理多視圖觀察模式和全屏模式下的區別，不過總的算法流程如前所述。如果假定當前狀態的符號數為 N ，每一個器官符號的三角形平均數量為 M ，則上面的渲染過程的時間復雜度是O(M×N )。 此算法的時間復雜度是多項式時間復雜度，在演化的步數不是很多的情況下，即 N 值不是很大的情況下，系統運行的效率是比較高的。在我們的實驗環境下，基本上可以做到實時的渲染。圖1給出了一棵灌木的生長過程。

3.4 系統運行結果

下面以一個文法系統為例，利用該系統來進行虛擬植物可視化建模：

(1)在文法編輯器中輸入文法系統（圖2）。

(2)用鼠標選取Compile，編譯該文法如果沒有錯誤，則進入Mesh Setup，設定系統的器官符號(圖3)，可以對器官的顏色進行設定等。

(3)植物渲染后的結果如圖1所示。

4 結論

本文給出了一種新的建模方法， 結合了L系統和基于圖像建模的優點，對植物器官的建模方法是基于能夠反映植物器官主要特征的圖像的方法。該方法與L系統相比，有更低的時間復雜度并滿足了在微機平臺上模擬植物的生長要求。本文設計實現了基于上述思想的虛擬植物可視化原型系統。目前的原型系統仍需進一步完善，未來的可能研究方向如下：植物器官建模方法仍需改進，根據植物的生理模型，還應該對植物最后的器官網格面進行變形等；植物沒有與環境進行交互，現在只是考慮單株植物的情況，沒有考慮諸如水分、陽光、溫度等環境因素的影響。在以后的研究中，應該加強這方面的研究，讓植物能夠與周圍的環境進行交互，提供L系統文法輸入的自動導航功能，讓用戶使用更加方便。該系統的開發是在Andrea Esuli等人在網上公開的圖形庫和L系統原型的基礎上進行研發的，借鑒了很多其他人的研究成果，在此表示謝意。

參考文獻：

[1] Bedrich Benes， Erik Uriel Millian. Virtual Climbing Plants Competing for pace[

C].Proceedings of the Computer Animation，Geneva，Switzerland，2002.33-43.

[2] R L Ogniewicz， O Kubler. Hierarchic Voronoi Skeletons[J]. Pattern Recognition， 1995，28（3）:345-359.

[3] 陳昭炯. 基于L 系統的植物結構形態模擬方法[J].計算機輔助設計與圖形學學報，2000，12(8):571-574．

[4] M Teichmann， S Teller. Assisted Articulation of Closed Polygonal Models[C]. Proc. of the 9th Eurographics Workshop on Animation and Simulation，New York：ACM Press，1998.254-268.

[5] Jaeger M， de Reffye P.Basic Concepts of Computer Simulation of Plant Growth[J].J. Biosci.， 1992，17(3):275-291.

[6] 張樹兵，王建中.基于L系統的植物建模方法改進[J].中國圖像圖形學報，2002，7A(5):457-459.

[7] Bedrich Benes， Juan Miguel. Clustering in Virtual Plant Ecosystems[C].WSCG2004，2004.9-17.

[8] Radoslaw Karwowski， Brendan Lane. L Studio 4.0[EB/OL].http://www.cpsc.ucalgary.ca/Research/bmv/lstudio，2004.

[9] Przemyslaw Prusinkiewicz.The Use of Positional Information in the Modeling of Plants[C]. ACM SIGGRAPH，2001.289-300. 

[10] C Godin， Y Caraglio. A Multiscale Model of Plant Topological Structures[J].J.Theor.Biol.，1998，19(1):1-46. 

作者簡介：李云峰(1975-)，男，河南臨潁人，講師，博士研究生，研究方向為圖像分割、文檔圖像處理、虛擬植物、虛擬現實、負載平衡、數據挖掘；朱慶生(1956-)， 男，中國計算機學會常務理事， 院長，教授，博導，博士，主要研究方向為多媒體數據壓縮、網絡數字文檔、軟件方法和重用技術、電子商務等。

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。