基于L-系统的随机树模型

摘要：由于每次由同一个确定L-系统生成的植物模型都是固定不变的，而且显得很死板。本文在考虑植物生长规律的前提下，利用随机L-系统生成了一个随机树模型，该模型形态自然、具有很强的真实感。

Abstract: Plant model generated by the same deterministic L-system was identical, and appeared to be stiff. Considering the law of plant growth, a random tree model using stochastic L-system was generated, which appeared to be natural and had a strong sense of reality.

关键词：随机L-系统；随机树；生长规律

Key words: stochastic L-system；a random tree model；the law of growth

中图分类号：TP18 文献标识码：A 文章编号：1006-4311（2011）24-0149-02

0引言

利用计算机对植物进行建模和仿真现已成为人们研究植物学、生态学、农学等的重要方法之一。

L-系统是丹麦植物学家A Lindenmayer提出的一种并行文法，它以形式化的语言描述植物的结构和生长，现在已成为植物建模的重要工具。由确定L-系统生成植物的过程中，由于每次迭代都应用相同的产生式，所以经过相同次数的迭代后每次都生成相同的植物模型，而且在进行几何解释的过程中，各种数据都是固定不变的，所以经过有限次迭代以后生成的植物模型也是相同的。在植物生长中往往会受到各种随机因素的影响，所以引入了随机L-系统。

随机L-系统的随机性可用在字符解释上，如步长的值可以是随机的，分枝角度也可以是随机的，同时也可以用在产生式上。前者保持基本拓扑结构不变，而后者生成的植物模型的基本拓扑结构发生了变化，几何性质也发生了改变。参考文献[1]中利用同一个随机L-系统生成了几个不同的形态“活泼”的植物结构，但是这只是追求视觉上的变化，而没有考虑植物生长过程中的因素。本文结合植物生长规律，应用随机L-系统生成了形态自然的植物模型。

1L-系统表达机制

1.1 L-系统重写机制最简单的L-系统是D0L-系统，可以描述为令V表示一个字符集，V*表示V上所有单词（由符号或字符组成的字符串）的集合，一个0L-系统可以用一个有序的三元组L=来表示，其中ω是（ω∈V*）一个非空单词，称为公理，P是产生式规则的有限集合，产生式记作cs，字符c和单词s分别叫做产生式的前驱和后继。如果对每一个字母c∈V，当且仅当有一个非空单词s，使得cs，则0L-系统是确定的[2]，即不考虑前驱字符的上下文语义。

L-系统的核心思想便是重写，即从公理ω开始，按照产生式规则，依次替换ω中的每个字符，得到新的字符串，对新的字符串再进一步对每个字符进行替换，按照上述规则一直替换下去，直到满足终止条件。

1.2 龟形解释为了把通过L-系统的重写机制生成的字符串描述成具体的植物形态，需要使用龟形系统[3]对生成的字符串进行几何解释。具体地做法是对迭代生成的字符串从左至右连续扫描，并对每一个字符做出相应的几何解释，这样就由字符串得到相应的植物形态。乌龟的爬行可以在二维或三维空间中进行。其中三维空间是对在二维空间的基础上进行扩展。龟形有它的状态，包括笛卡尔坐标系下的位置和方向，还有一些附加的属性，如当前的颜色和线宽。位置由矢量P定义，其中三维空间的方向由矢量H，L，U定义，分别表示乌龟的头方向和向左、向上的方向，如图1所示。

这三个矢量都是单位长，且互相垂直，满足H×L=U。因此，龟形的旋转可以用下面的式子表示：[ H′L′U′]=[HLU]R

这里的R是一个3×3的旋转矩阵。分别绕矢量U,L和H旋转α的旋转矩阵为：RU(α)=cosasina0-sina cosa00 0 1

RL(α)=cosa 0-sina01 0sina0cosa

RH(α)=1 000cosa-sina0sina cosa

龟行位置初始化为笛卡尔坐标系的原点，头矢量H指向y轴的正方向，左矢量L指向x轴的负方向，向上的矢量U指向Z轴的正方向。常用的龟行符号有：

引起龟行旋转的符号：

-：绕U向左旋转一定的角度；+：绕U向右旋转一定的角度；

&：绕L向下旋转固定的角度；^：绕L向上旋转固定的角度；

\：绕H向下旋转固定的角度；/：绕H向上旋转固定的角度；

表示树枝分叉的符号：

[：把当前状态压入堆栈，（包括当前位置、方向、颜色、线宽（或半径）等）；

] ：当前状态出栈，作为龟形的当前状态；

引起乌龟前进的符号有：

F：乌龟向前爬行一定距离并画线（或圆柱）；

f：乌龟向前爬行一定距离，不画线（或圆柱）。

2随机L-系统

2.1 随机L-系统的基本理论在利用确定L-系统生成植物时，由于每次迭代都应用相同的产生式，所以经过相同次数的迭代后每次都生成相同的植物模型，而且生成的植物模型显得很死板，一个随机0L-系统[4]是一个有序的四元组：

GΠ=（1）

其中字符集V，公理ω和产生式集P与D0L-系统[2]相同，函数Π用来确定每个产生式P被应用的概率。设α为V中任意字符，以α为前驱的产生式可以有多个，但这些产生式的概率之和应该为1。随机L-系统的产生式记作：

pred：condsucc: prob（2）

其中pred和succ分别称为前驱和后继，cond为应用该产生式的条件，prob为本产生式被应用的概率。

这样，在随机L-系统中，对于同样的产生式模块，经过相同的迭代次数可以生成不同的植物结构。

下面给出一个随机L-系统的实例：

ω：A（1）B（3）A（5）

p1:A（x）A（x+1）：2

p2:A（x）B（x-1）：3

p3:A（x）:x>3C（x）：x

p4:B（x）B（2*x）A（x）：1（4）

在字符串重写时，A（x）在x3时，例如x=5，p1被应用的概率是2/（2+3+5）=0.2，p1被应用的概率是3/（2+3+5）=0.3，p3被应用的概率是5/（2+3+5）=0.5，产生式p4的应用概率为1。经过一次迭代的结果可能为A（1）B（3）A（5）A（2）B（6）A（3）C（5）（5）

这里的p1被应用到对A（1）的改写，而p3被用到对A（5）的改写。

2.2 随机树模型

2.2.1 随机树模型的植物学理论许多简单的分枝模型（如由确定L-系统生成的植物），分枝量都是呈指数增加。Borchert和Slade[5]对小白杨和掌叶黄钟木两种植物进行了观测，观测数据表明这种分枝数目的指数增长只是发生在植物的幼苗期，一旦超过了某个时期，这种分枝速度就会降低。基于Borchert和Slade的分析，下面提出一个树的随机模型，这种模型的建立符合以下植物学假设：①该模型是从一个不带分枝的嫩枝（带叶的分枝）开始的，假设生长季节设为变量k，k=1。②在以后的每一个季节，新枝就会从上一年分枝末端的芽发出。这是一个常数，bmax＞1，决定了最大分支率（也就是说，嫩枝的最大数目位于母枝处）。③所有分枝结构的长度大致相同（都为l），和它们的位置和树的年龄无关，这些分枝伸展开来，形成一个半球形的树冠。④在当年生长的终端枝条上长出来许多树叶，因此在树冠周围又形成了一个半球形的树叶层。常数σmin，决定了要想产生一个新的分枝，树叶接受阳光的最小面积。

3结论

在利用确定L-系统模拟植物时，由于迭代过程中每次都使用相同的产生式，所以生成的植物显得很生硬，而且分枝增长率是按指数增加，显然不符合自然规律。在利用随机L-系统进行植物模拟时，如果随机因素应用在字符解释上，虽然视觉上产生了一定的变化，不像确定L-系统那么呆板，但是基本拓扑结构一样，而且这只是追求视觉上的美观，并不一定符合植物生长规律。本文利用随机L-系统生成的植物模型，符合一定的植物生长规律，而且形态自然。

参考文献：

[1]黄艳峰，薛占熬，陈涛.基于L-系统的植物模拟研究[J].计算机工程与应用，2005，41，（19）:53-55.

[2]齐东旭.分形及其计算机生成[M].北京：科学出版社，1996.

[3]Przemyslaw Prusinkiewicz，Mark Hammel，Eric Mjolsness. Animation of Plant Development.ACM SIGGRAPH93：351-360.

[4]刘阁，周国民.L-系统理论及其应用综述[J].农业网络信息，2008，9:21-23.

[5]R.Borchert and N.Slade.Bifurcation ratios and the adaptive geometry of trees.Botanical Gazette，142，（3）:394-401.

[6]Przwmyslaw Prusinkiewicz，Mark Hammel，Jim Hanan etal.Visual models of plant development[C]//Grzegorz Rozenberg，Arto salomaa.Handbook of formal languages.New York:Springer-Verlag，1997:535-597.