摘 要：
L系统已经成功的运用于许多生物体如植物、细胞、特别是树的生长可视化模拟。在实际的游戏和动画的开发应用中，当我们运用Ｌ系统模拟不同的树的动画时，应用程序员往往要重写代码，尽管Ｌ系统有适合于用面向对象的方法来描述的特点。在本文中，提出了一个简单的面向对象的Ｌ系统的模型，适用于各种树的动画模拟。这个模型的主要功能包括：树的生长过程的模拟，树在生长过程中与周围环境的相互作用等。应用程序员可通过输入不同的参数和字符串来改变树的形态，还可以通过参数控制树的生长速度．如果只是渲染一副静态的图像．可以关掉动画功能。基于这个基本的面向对象的Ｌ系统，程序员可大大减少代码的重写，缩短编程时间。
关键词：L系统，面向对象，树，动画，模拟
1.引言：
L系统是由著名理论生物学家Lindenmayer[1]首先于1968年提出，它一经提出，便立即吸引了许多的数学家，生物学家，和计算机学家。它是一种模拟多细胞体生长发育的形式，它为人们定量的研究生物的形态和演变过程提供了一个有力的工具。随着计算机科学的发展，L系统被广泛的应用于计算机图形学、计算机动画、虚拟农业等领域，并取得了很大的进展。Hana[2]和Przemyslaw Prusinkiewicz[9]拓展了参数L系统。Radom′r Mˇech ?和 Przemyslaw Prusinkiewicz利用开放式L系统模拟了树与环境的信息交换和相互作用的生长过程，基于植物的生物特性模拟了植物在为争夺光照和空间时的生长过程，同时还模拟了根系生长过程[3,5]。为描述植物的动态生长过程，Prusinki- ewicz等人提出了参数微分L系统（DL-System）[4]。Lars Linsen 等人通过大量的经验数据收集，描述了城市绿化用经过修剪的树的形态演变过程[7]。Joanna L. Power等人基于生物力学的方法模拟了植物的形态特征。
目前，已经已有了应用L系统开发的应用软件，如CPFG[3]。本文旨在解决游戏和动画制作中利用L系统模拟树的动画，应力求简单高效。树的生长过程可以不受其生物特性的严格限制。当我们在塑造一个大自然季节更替的童话世界时，春天来了，花草树木开始发芽，生长；或下雨了，植物开始迅速的生长；或是太阳出来了，花木开始朝着阳光的方向生长。显然，这时我们并不需要花木在生物学上的逼真。通过一定程度的模型简化和算法优化，建立一个面向对象的L系统并能达到实时的要求，这对于游戏和动画的开发来说，可以大大间少代码的重写，缩短开发周期。虽然L系统具有代码简单的特点，但为了增加真实感，对产生式的解释、选择等操作的编码也会越来越复杂，而有些操作在不同的程序中是相同的或相似的。如前面所说，L系统有适合用面向对象的方法来描述的特点，本文力求提出一个适合大部分树的生长过程的模型，用面向对象的方法来描述和实现以达到代码的重复利用。
2.L系统与乌龟几何简介
L系统使用形式语言和文法来描述生物体的生长发育过程。他的核心是“可复写”规则，其基本思想是通过迭代的利用复写规则或产生式，利用产生式的子字符串代替前一个父字符或字符串来表示一个复杂的物体。最简单的L 系统被称为0L 系统[9]，也称为上下文无关（context-free)的L 系统。也就是说字符串中的字符对应某个确定的产生式，没有受上下文的约束。如我们定义这样的两个产生式： aab,ba,表示a 可由ab 代替,b 可由a 代替,复写的开始字符串我们成为公理。假设公理只有一个字符a,则复写过程表示如下：
如果产生式依赖于上下文，称为上下文相关的L 系统（Context-sensitiveL-systems）[9]。其形式为：①al<a>arb,或②al<ab, ③ a>arb,其中②③又称为1 型L 系统（1Lsystem），①称为2 型L 系统(2Lsystem)。①式表示字符a 只有出现在al 和ar 之间时可产生b。在描述植物与其环境的的相互作用时，就是上下文相关的L 系统的一个应用。
植物生长发育是一个连续的过程，在模拟植物生长发育的过程时 ，植物在不同的方向及不同的时刻其产生的分枝的大小，速度和方向是不同的，植物的形态受到时间、空间等因素的限制，在L 系统中加入参数控制，称为参数L 系统[2，9，10]。如果一个L 系统的字符属于字符表V,其参数属于实数R，用A 表示一个模块，它可以是一个参数字或带参数的字符串，表示为 A(a1,a2,a3,…),其中a1,a2,a3..R 。模块的集合用M表示，则M=(V ×R)。如果用Σ 表示形式参数集合，用C(Σ)表示参数的逻辑表达式，用E(Σ)表示一个算术表达式，分别可以利用 〈、〉、=、！、—、|| 等逻辑及关系运算符和 +、-、*、/ 、∧等算术运算符。一个参数0L 系统可表示为四元组 〈V,Σ,ω,P> ,其中，V 是系统中的字符集合；Σ 是形式参数集合； ω是属于 (V ×R)的参数字，也是规则复写的开始，称为公理 ，R 为实数；P (V ×Σ)×C(Σ)×(V ×E(Σ) 是产生式的有限集合。从0L 参数L 系统很容易推广到上下文相关的参数L 系统，下面是一个下文相关的参数L 系统例子：
这里的x,y,z是形式参数。如果给出初始状态A(2)B(4)C(3),则采用产生P2:E(6)F(7)。为更真实的模拟植物的形态可在某些产生式附加一个0到1之间的实数，表示用此产生式的概率。因此描述一棵树的L系统可表示如下：
axiom: axiomlcontext1 < predecessor1 > rcontext1 : condition1:{ α } C { β } --> successor1 : p1lcontext1 < predecessor1> rcontext 1: condition1{ α } C { β } --> successor2 : p2lcontext1 < predecessor1 > rcontext1 : condition2:{ α } C { β } --> successor3 : p3lcontext1 < predecessor1> rcontext 1: condition2{ α } C { β } --> successor4: p4. . . .
lcontextr < predecessorr > rcontextr :conditionn{ α } C { β } --> successor : pncondition 为条件表达式，p为产生式的概率。
与L系统机密相关的是乌龟几何（turtle geometry），在我们定义了描述树模型的字符串后，需要将字符串表达的信息经过解释并绘制在屏幕上，这种解释我们称之为乌龟解释（ turtle interprets）。就像一个乌龟最初在空间中的某一个位置，并有一个爬行方向，通过解释翻译一系列字符获得新的位置和方向，乌龟沿着新的方向爬向新的位置的过程就是画线的过程。龟标的当前位置表示为p,在空间的方向表示为（h,l,u）, h,l,u 为正交的三个向量。h为向前的方向，l为相左的方向，u为向上的方向，如图1所示。
图 1：（上）龟标在每个节点出方向分别用h,l,u表示，h表示向前的方向，l表示向左的方向,u表示向上的方向。（下）各符号代表的旋转方向。
假设定义以下字符串：
F(2)[-F(1)]F(2)[+F（1）]F(1)F表示向前画一条线，括号中的参数为线长，-表示向左转30度角，+表示向右转30度角，[ 表示保存当前的位置和方向，] 为取出前一次的位置和方向。龟标的初始方向是向上的，则画出的图形为图2所示。
以下是L系统中基本的控制龟标运动状态的符号及其意义，更多的符号说明请参阅[9，13]。
F(a) 向前移动距离a+(θ) 沿u轴左旋转θ角-(θ) 沿u轴右旋转θ角&(θ) 沿l轴向上旋转θ角^(θ) 沿l轴向下旋转θ角(θ) 沿h轴向右旋转θ角/(θ) 沿h轴向左旋转θ角[ 保存当前状态信息入栈] 前一状态信息出栈
3.面向对象的L系统
面向对象的方法的核心是用用抽象的方法来描述计算机的数据处理，对相似的事务抽象出其共性，并通过类，对象、继承、多态等机制来达到代码的重复利用。对于树的模拟来说，丰富多彩的自然界给我们提供了数万甚至数十万种不同的树木，这些树木形态万千，多姿多彩，想通过一两个简单的模型来描述所有的树木特征是不可能的。例如，灌木和大树的描述模型是不同的。但我们总能找出某些或某类树木的共性。我们通过对一些绿化用树木的观察和研究，从而抽象出其共有的特性，提出了用面向对象的L系统模拟树的生长动画。但本文的目的不在于通过精确的研究树的生物特性来模拟树，而在于建立一个描述树的生长过程动画的程序模型框架，以达到代码的重复利用，从而简化程序的开发过程。
3．1 动画控制
一个模拟生物发育生长过程的程在序执行过程中，在一个贞的时间片内要依次进行字符的匹配、与环境的信息交换、规则产生、乌龟解释、图像渲染 。进入下一个时间片，改变相应的参数重复上述操作，动画过程就是这样的一个循环过程。但是，上述的循环算法的代价是比较高的。在每一个时间轮回中都要进行产生式的替代，如果利用第归算法还要进行大量的入栈和出栈操作。我们对上述的方法进行了优化。在每一次产生式的迭代替换后，进行一个内部循环，这个内部循环简化为只有乌龟解释和图像渲染两步。并在这个过程不断的改变树的主干和枝叉的直径、长度等参数。字符的匹配、子式的产生以及与环境的信息交换在产生式的迭代替换时产生。可以描述如下：
for(iterativedepth){字符匹配；环境交换信息；产生式的替换,将新的产生式插入队列；for(timesegments){乌龟解释；修改参数；渲染画面；删除对队头;}
}
if(timesegments==0){乌龟解释；渲染画面；}
当只是需要渲染一幅静态的图像时，可将第二个循环关掉，timesegments设置为0。只利用经过iterativedepth次迭代替换后的最终结果进行绘制。需要指出的是：为提高运行速度，我们没有使用第归的算法，而是定义一个队列用于存储产生式替代后的结果，在每次替代结束后，绘制队头中字符串表示的内容，绘制结束后删除队头。在每次迭代过程中将产生式替代后的结果插入队列。这样做的结果是减少了进栈和出栈的时间开销，同时实现了产生式的平行替代，使树的各部分能同步生长。但为队列而增加了内存的开销。
树的枝干的直径、长度、以及树叶的大小是时间的函数。以F(l,d)表示一个分枝，L(s)表示树叶。l和d分别代表树枝的长度和直径，s代表树叶的大小。他们虽时间变化的函数分别为：l(t), d(t), s(t)。不同种类的树这些函数也是不同的。我们可以近似的表示为： （1）l(t)=Cd?d(t) （2）s(t)=Cs?d(t) （3）C, Cd, Cs是常数。其中（3）式中的d(t)为与叶子关联的分支直径的函数。所有子分枝的直径的平方和等于其父分枝直径的平方[11]：
d(t0)为父分枝在t0时刻的直径，d1(t0)为第一个分枝在t0时刻的直径，d2(t0)为第二个分枝在t0时刻的直径。
3．2 与环境的信息交流
一个与环境互动的L系统包括树的描述模块、环境模块、以及他们之间的消息映射机制(清参阅参考文献[5])。描述模块包括树的模型信息（这里指用于描述树的公理，产生式和产生规则）和模拟生成器。环境模块包括环境的信息数据（如光照信息、空间信息等）和环境模型。设字符串？E(p1,p2..)表示需要和环境进行信息交流。如有以下定义：
#define r1 0.94 //收缩速率 1
#define r2 0.87 //收缩速率 2
#define α1 24.4 //树枝转角 1
#define α2 36.9 //树枝转角 2
#define θ 138.5 //沿h轴的扭转角度
#define prob1 0.8 //概率1
#define prob2 0.2 //概率2
w:–(90)[F(1)/?E(1)A(1)]+( θ)[F(1)/?E(1)A(1)]+( θ)[F(1)?E(1)A(1)]+( θ)[F(1)/?E(1)A(1)]+(θ)[F(1)?E(1)A(1)]
p1:?E(x)<A(v):{if x==1}[+(α2)F(v*r2)?E(r2)A(v*r2)]–(α1)F(v*r1)/?E(r1)A(v*r1) :prob1p2:?E(x)<A(v):{ifx==1}[L(1)][/L(1)][+(α2)F(v*r2)?E(r2)A(v*r2)]–(α1)F(v*r1)/?E(r1)A(v*r1)–(α1)F(v*r1)/?E(r1)A(v*r1) :prob2p3: ?E(x) →ε
F表示当前方向和核直径画一枝干，A表示分支节点。ω在初始时产生四个分枝，在字符匹配过程中，每遇到?E(x) A(v)时先和环境模块进行信息交换，如果当前位置已经被其他植物或物体占据，则环境处理模块将?E(x) 中x置0，这时采用第三个产生式，树枝在此点停止生长，(ε表示停止)。如果此处有足够的空间，将x置1，这时采用第一个或第二个产生式，p1在此处又产生两个分枝，继续生长，同时改变直径和长度等参数信息。p2产生两个树叶再产生两个分支。采用p1的概率为prob1,采用p2的概率为prob2。在本文中为了减少计算时间，将环境信息事先设置为常量。对于空间信息，我们用简单的球体来表示。假设球心的坐标为（X,Y,Z）,半径为R,当前的节点位置为（x,y,z），则(X-z)∧2+(Y-y)∧2+(Z-z)∧2）-R∧2<0或小于某个阈值时，表示此节点进入空间拥挤区域，从而通过参数的传递控制此节点的生长状态。而对于光照的信息，利用相互垂直的平面将空间划分为不同的区域，每个区域赋予不同的光照强度，对进入不同的光照强度区域的节点赋予不同的活性因子，不同的活性因子可以对应不同的产生式，也可以把活性因子作为节点分枝的长度、直径、或方向参数的系数，从而控制树在此区域的生长。
3．3 面向对象的L系统模型描述
面向对象的L系统用C++语言描述如下：
class TreeLsystem{public:
EnvironmeType EnvironData; //环境数据
string axiom; //公理
ProdutionType * productions; //产生式列表
int animation ; //动画开关
string * textdata; //纹理数据
public:
void ReplaceProductions(); //产生式替代
int InteractEnvironment( ); //与环境信息交换
void Rendering(); //绘制图像
void virtual CreateTexture()=0; //建立纹理
void virtual CreateProdutions()=0; //建立产生式列表
protected:
QueneType Quene; //用于存储产生式替代后的结果
int TextureId[] //纹理数组
StateType CurrentState; //当前龟标位置};
EnvironData存储环境信息数据，axiom是迭代的开始字符串（公理）。animation 是一个动画开关，他的值将赋于3.1所述的timesegments, animation为0时，关掉动画。当其不为0时，表示一个时间值。 Productions是一个产生式列表，通过实现虚函数CreateProdutions()来构造。它的类型可定义如下：
typedef struct{union{char c;float f;int i;}*String;float probability;} ProdutionType;Quene存储产生式叠代替换后的结果。TextureId[]是一个纹理标识符数组，通过实现虚函数CreateTexture()来创建。简单的情况下，只用到两个纹理：树皮和树叶。我们规定1为树皮纹理，2为树叶纹理。为提高运行的速度，我们没有对树叶建模，而是近似的认为树叶是一个平面，用树叶的纹理贴图来代替。树叶也可以是一个带叶的小树枝，如在模拟柏树或松树时，柏树的树叶是很小的，如果逐一描绘将耗费大量的时间，它可以用一个带叶的小树枝代替。ReplaceProductions()将每次产生式叠代后的结果放入队列。Rendering()函数将图像输至屏幕。
4．结语
本文针对如何方便实时的实现树的生长动画，在对树的生物学特性作了一定的简化后，提出了面向对象的L系统。并对动画控制、树与环境的信息交换的算法进行了优化，并给出了完整的面向对象描述的模型。利用面向对象的方法比较面向过程的方法要有较多的时间开销，但通过算法的优化，完全可以达到我们的要求，而且能实现代码的重复利用。
我们利用建立好的面向对象的L系统框架进行了实验，收到了良好的效果，完全可以实时的显示树的生长动画。可以方便的生成不同的树，它允许应用程序员输入不同产生式来生成树的不同的分枝形态，输入不同的产生式和枝叶纹理数据表现不同种类的树，从而大大简化了程序开发。
人次