基于L系統的三維分形樹仿真

蔣杏麗，張巖

（沈陽師范大學數學與系統科學學院，遼寧沈陽，110034）

0 引言

分形，通常被定義為“一個粗糙或零碎的幾何形狀，可以分成數個部分，且每一部分都是整體縮小后的形狀”，即具有自相似的性質[1,2]。分形技術通常用來在計算機上模擬出自然界中具有非規則生長特性的植物。分形幾何的概念 是美籍法國數學家曼德布羅[3]首先提出的，最初分形圖的計算機繪制也只是停留在二維平面，后來，一個分形體愛好者丹尼爾·懷特提出一個大膽的方法，創造出令人稱奇的3D分形影像[4]，并將它們命名為芒德球。本文在Matlab平臺上利用L系統算法實現了三維虛擬場景的樹木仿真，有效的展示了樹木的生長和拓撲結構。

1 L系統算法

1.1 L系統的原理

L系統是由生物學家Aristid Lindenmayer[5]于1968年引進的一種字符串迭代重寫機制[6]，是分形理論的一個重要分支，被認為是植物生長的數學理論。一個L系統可以用一個三元組（V，w，p）[7]來表示，其中V表示字母表；w是V中的一個非空字符串，代表初始形狀；p是一個有限集合，代表重寫規則。L系統的核心是字符串重寫[8,9,10]，即使用一個重寫規則或產生式的集合，對一開始定義好的初始字符串進行有限次數的迭代，再用龜形幾何解釋得到的新圖形去改寫替換原始的字符串[11]，最后獲取分形圖形完成三維仿真。

1.2 龜形解釋

由于L系統的產生式、初始元以及重寫后得到的元素都是以字符串的形式存在，所以為了讓這些字符串能夠具體的表示出某種圖形，將其與植物模擬聯系起來，我們引入了龜形這個概念。

龜形的當前狀態由一個三元組(x,y,a)[12,13]來定義，其中笛卡兒坐標(x,y)表示海龜的位置，角度a為海龜的前進方向，可以解釋為海龜面對的方向。給出步長d和角度的增量sita，海龜根據不同符號所代表的命令做出反應。

上面講述的龜形解釋是二維的，它可方便地擴展到三維空間，要對字符串進行三維龜圖解釋，關鍵是用三個向量H,L和U來表示空間龜的當前方位[14,15,16]。H、L、U分別為龜頭的指向、左方、上方，這些向量具有單位長度且方向正交，即滿足方程H X L=U。龜的旋轉可表示為方程: (H,L,U) =(H,L,U) R[17],其中R是3X3的旋轉矩陣。以下分別是繞矢量U、L和H旋轉α的旋轉矩陣R[18]:

龜形位置初始化為笛卡爾坐標系統的原點,頭矢量H指向y軸的正方向,左矢量L指向x軸負方向,向上的矢量U指向z軸的正方向。龜形根據參數的解釋決定前進的方向和狀態變化,如果有多個參數,第一個參數值決定龜的狀態。本文中L系統用到的主要圖形符號、其幾何意義及具體實現代碼如下表1。

表1 圖形符號解釋

2 三維分形樹的可視化

本研究利用Matlab進行模擬仿真。在模擬仿真三維生成樹的時候，會產生大量的數據，造成存儲和計算的能力[19]。MATLAB提供面向大數據處理的性能，可以方便、高效地格式化無法進入內存的文件數據，從而獲得實際意義的實時處理效率[20]。

首先定義好樹的初始字符串和產生式規則，設置樹的生長深度來控制樹的規模。再利用重寫函數repmat()根據定義好的重寫規則對字符串進行迭代重寫，最后使用strrep()函數進行生長樹替換，將初始字符串替換成重寫之后的字符串。

實現代碼：

nV=15; %縱向會有nV個節點的分支

nH=8; %橫向會有nH個節點的分支

SET=’X’; %初始字符串

np=10; %主干上分枝數量

pathp=’’; %主干上空字符串

for i=1:np

pathpi=[‘[+’,repmat(‘-’,1,i),’Y]’]; % 字符串重寫

pathp=[pathp,pathpi]; %連接每次重寫后的字符串

end

pT=[‘T’,pathp,’X’]; %根據重寫規則X對T中起始元是pathp字符串進行重寫

ns=5; %主枝上分支數量

paths=’’; %主枝上空字符串

for i=1:ns

pathsi=[‘[’,repmat(‘/’,1,i),’S]’]; % 字符串重寫

paths=[paths,pathsi]; %連接每次重寫后的字符串

end

pS=[‘P’,paths,’Y’]; %根據重寫規則Y對P中起始元是paths字符串進行重寫

for k=2:nV;

SET=strrep(SET,’X’,pT); %生長樹替換，縱向替換成pT字符串

end

for k=2:nH;

SET=strrep(SET,’Y’,pS); %生長樹替換，橫向替換成pS字符串

end

生長樹替換完成后建立三維坐標以便在三維虛擬空間呈現出分形樹的結構。首先求得生長控制參數諸如樹干長度、樹干延伸次數、樹干收縮系數、樹枝相對偏移角度以便在后續龜形圖的實現中直接使用。其次設置龜形起點，初始方向，旋轉角度，利用龜形解釋依次去讀取字符串的每個字符并解釋為幾何語言繪制出對應的圖形。

運行程序后，在二維分形樹圖形界面上點擊三維旋轉按鈕，拖動圖形即可出現三維分形樹圖像，如圖1和圖2所示。

圖1 二維分形樹

圖2 三維立體分形樹

3 結論

本文在已有的二維分形樹研究的基礎上進行了空間維度的擴展，在Matlab平臺上利用L系統對樹木結構進行解析，再根據定義的重寫規則對樹木初始字符串不斷的迭代重寫，完成樹木的分形，最后使用龜形解釋對分形得到的字符串用幾何語言描繪成圖像，實現了在三維空間的樹木建模。但該模型仍然存在不足之處，今后可以有一個改進點，即更加生動形象的模擬出樹枝搖曳的情形。