基于L系統(tǒng)的三維分形樹仿真

蔣杏麗，張巖

（沈陽師范大學(xué)數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，遼寧沈陽，110034）

0 引言

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

1 L系統(tǒng)算法

1.1 L系統(tǒng)的原理

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

1.2 龜形解釋

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

龜形的當(dāng)前狀態(tài)由一個三元組(x,y,a)[12,13]來定義，其中笛卡兒坐標(biāo)(x,y)表示海龜?shù)奈恢?，角度a為海龜?shù)那斑M(jìn)方向，可以解釋為海龜面對的方向。給出步長d和角度的增量sita，海龜根據(jù)不同符號所代表的命令做出反應(yīng)。

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

龜形位置初始化為笛卡爾坐標(biāo)系統(tǒng)的原點(diǎn),頭矢量H指向y軸的正方向,左矢量L指向x軸負(fù)方向,向上的矢量U指向z軸的正方向。龜形根據(jù)參數(shù)的解釋決定前進(jìn)的方向和狀態(tài)變化,如果有多個參數(shù),第一個參數(shù)值決定龜?shù)臓顟B(tài)。本文中L系統(tǒng)用到的主要圖形符號、其幾何意義及具體實(shí)現(xiàn)代碼如下表1。

表1 圖形符號解釋

2 三維分形樹的可視化

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

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

實(shí)現(xiàn)代碼：

nV=15; %縱向會有nV個節(jié)點(diǎn)的分支

nH=8; %橫向會有nH個節(jié)點(diǎn)的分支

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

np=10; %主干上分枝數(shù)量

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

for i=1:np

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

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

end

pT=[‘T’,pathp,’X’]; %根據(jù)重寫規(guī)則X對T中起始元是pathp字符串進(jìn)行重寫

ns=5; %主枝上分支數(shù)量

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

for i=1:ns

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

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

end

pS=[‘P’,paths,’Y’]; %根據(jù)重寫規(guī)則Y對P中起始元是paths字符串進(jìn)行重寫

for k=2:nV;

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

end

for k=2:nH;

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

end

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

運(yùn)行程序后，在二維分形樹圖形界面上點(diǎn)擊三維旋轉(zhuǎn)按鈕，拖動圖形即可出現(xiàn)三維分形樹圖像，如圖1和圖2所示。

圖1 二維分形樹

圖2 三維立體分形樹

3 結(jié)論

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