论文部分内容阅读
摘 要：虚拟植物生长可视化技术忠实于植物生长机理，采用图像处理、虚拟现实、计算机仿真等技术来实现植物生长建模的可视化，具有重要的理论和实践意义。其基本的方法有迭代函数、粒子系统和L系统等。每种方法都有一定的局限性和适用范围，只能满足某一方面的需求。
关键词：建模；虚拟植物；分形
中图分类号:TP391.72文献标识码:A
Technology-based Three-dimensional Virtual Plant Modeling Research
DING Ye1,2
(1.Tongji University, Shanghai 200092；2.Huanghuai institute，Henan Zhumadian 463000)
Key words: modeling；virtual plan；fractal
在虚拟植物生长建模的可视化研究中，分形是其重要的理论基础。分形理论是一个活跃的数学分支，其研究对象是在非线性系统中产生的不光滑和不可微的极不规则几何物体。到目前为止，分形理论已成功的应用到自然科学、社会科学等很多领域，并在工程中得到了广泛的应用，分形已经成为研究许多自然现象的有力工具，在自然现象中，有大量对象不能用经典欧氏几何描述的事物，在这种情况下，分形几何就可以用来处理这不规则的几何形状。
分形几何的理论运用于多个领域，目前，虚拟植物生长建模的研究也基本上是在分形的理论基础上提出的各种建模方法，常用的植物建模方法主要有：迭代函数、粒子系统和L系统，每种方法有其相应的应用场合。
1 主要的植物建模方法
1．1迭代函数
迭代函数系统(Iterated Function Systems，简称IFS)是分形几何学科的重要分支和研究热点。分形集一般都是由某一初始状态经过若干次繁衍变化后得到，这种繁衍变化是无穷无尽的，因而分形集一般都是由无穷多个点组成，点的分布又极其复杂，不可能通过直接给定点的坐标位置来描述它，因此一般通过描述整体和局部的关系来表达。通过繁衍变化，可以生成千姿百态的图形。针对这个系统，巴恩斯利提出了完整的理论和算法，做了很多开创性的工作。
迭代函数系统理论包括以下几个方面：压缩仿射变换、不动点定理和拼贴定理等。迭代函数系统在对很多自然物体建模有很大的优势，只需给出仿射变换的系数，经过迭代运算，就可以快速生成分形物体的图像。
1．1．1压缩仿射变换
定义2.1：设w：X-〉X是完备空间(X,d)上的一个映射。如果存在一个正常数c<1,使
d(w(x),w(y))≤c*d(x,y)，x,y∈X （2-1）
则称w为(X,d)上的压缩映射，c称为压缩因子。
定义2.2：n维欧氏空间Rn中的仿射变换w:Rn →Rn具有下面的形式：
w(x)=Ax+b,(x∈Rn)，
其中A是Rn上的线性变换(可以表示成一个n×n矩阵)，而b是Rn中的一个矢量。当它的线性变换部分是压缩的，则称为压缩仿射变换。可以将压缩仿射分解为平移、旋转和比例缩小等，用下式表示：
wxy=rcosθ -qsinψrsinθ qcosψxy+ef（2-2）
其中e和f分别是x轴和y轴方向上的平移分量，θ和φ分别是绕x轴和y轴逆时针方向的旋转角度，r和q可以分别看成是x轴和y轴方向上的缩小比例。
1．1．2利用迭代系统生成图形的算法
利用迭代系统生成的图形主要有两种算法，一种是确定性算法，一种是随机算法。确定性算法是基于IFS上不动点定理和拼贴定理。但由于得到最终图像所需要的时间复杂度按指数速度增加，所以一般不实用。在实际的应用中一般是由随机迭代算法绘制的，算法的步骤如下：
①任取一点x(i,j)；②在序列{1,2,…,n}中，以概率pk选出k；③把第k个压缩仿射变换作用到点x(i,j)上，得到新的点，记作x=wk(x)；④画点x；⑤回到第二步。
通常计算机作图时，为了避免把吸引子外的点画出，刚开始的点不画，概率pi(i=1,2,…,n)应该正比于第i个压缩仿射变换中其次线性变换系数构成的四边形面积，一般可以由下式确定:
（1）粒子系统
为了更加快速、方便和真实的模拟“模糊”状态的物体，Reeves在1983年提出了一种与经典方法完全不同的建模方法，称为粒子系统。粒子系统所描述的物体包括自然界中常见现象(诸如火焰、雪花、浪花和烟云等)，它们的共性是没有固定的形状，没有规则的几何外形，更重要的一点就是它们的外观随着时间发生不确定的变化，在经典图形学的建模研究中，通常采用几何建模的方法来模拟研究对象的外形，通常采用多边形来表示轮廓，而这类“模糊”状态的物体不可能用这种多边形网格来进行表示。同时该方法无法描述其形状的不确定变化，所以必须找到一种新的途径来对这类物体进行建模，为此引入了“粒子系统”。
在对“模糊”物体进行建模的时候，粒子系统与传统的基于表面的技术相比较有如下几个比较重要的优点：一是粒子系统的计算速度快，在粒子系统中，一个粒子通常可以被认为是三维空间中的一个点来表示，在对图形可视化的过程中，一个三维空间点的处理通常比一个代表物体表面多边形的处理算法要简单很多，所以在相同的时间内，粒子系统可以处理更多的粒子，从而可以生成更为复杂的图形。二是粒子系统不需要进行人工建模过程，在基于表面的建模方法中，模型的最初获取通常是在建模工具中进行人工设计，但是在粒子系统中，模型定义是用随机数控制的一段程序，由于粒子系统是一段程序，所以可以根据需要，可对显示的精细程度进行调整。就如同分形系统一样，如果对一个粒子系统进行放大显示，就可以得到更多细节。三是粒子系统是活动的，它随时间的变化会改变其形状，然而，在基于表面的建模技术中，改变粒子系统表面的计算过程是非常复杂的。粒子系统的每一帧动画，都要经过以下的处理步骤：①新产生的粒子进入系统；②为每一个新建粒子设定属性；③如果一个粒子超过了它预设的生命时间，就会从系统中消失；④其余粒子根据它们的动态属性和最终状态进行移动或者变形；⑤对活动粒子进行渲染，放入到帧缓冲当中。
（2）L系统
自从美国生物学家Lindenmayer于1968年提出L系统后，L系统不断完善。L系统起源于分形思想，它为定义植物的构型提供了新的途径，也产生了一种重要的分形图形生成方法。1984年(A R Smith)等人将L系统引入计算机图形学，在计算机上模拟生成各种形态的植物，显示了计算机模拟植物方面的能力，为在计算机上实现虚拟植物的生长提供了理论和实际的依据。
L系统的构图原理非常简单，L-系统通过产生一系列字符串来构造图形与曲线，主要用来描述植物的形态和细节。通过对L系统进行有限次迭代，产生字符串集，然后对字符串集进行图形解释，即可生成图形。其流程图2所示，在对植物进行建模时,通常植物的一个器官(茎、花、叶等)对应于L系统的一个字符，字符串发展过程对应植物的生长过程。到目前为止，在对L系统的发展应用上，有两类L系统得到了比较成功的应用，第一个是让L系统可以和外界交互的开放L系统。另一个是可以表示植物器官的生长发育变化的微分L系统。
植物同它周围环境进行交互是影响植物生长的重要因素。Mesh等人提出了开放L系统,采用一种框架模型模拟植物同其周围环境交互。植物与周围环境的交互在概念模型上可以认为是植物和其周围环境彼此相互交互的过程，其过程包括植物内部处理和环境处理两个方面，植物内部处理过程如下：①感知植物器官所接受到的环境信息。②植物的内部处理接收到的环境信息；③植物对接收到的信息作出反映和向环境输出信息。
与植物内部处理过程相似，环境处理过程如下所示：①检测植物的反作用；②模拟环境内部处理过程(如环境内部的物质扩散的过程和光线发散的过程)；③修改环境模块参数，并且把修改后环境以植物可以感知的方式发送给植物模块。
通过对植物和环境的概念模型分析，基于可以与周围环境相互交互的系统架构，必须满足如下的要求：
①植物和环境需两个独立的，但可以相互通讯的程序。这样可以和概念模型一致，也符合结构化程序的需要，同时也可以满足分布式计算需要；
②用户可以控制植物模块和环境模块之间的信息流动数量。以满足足够(不可多也不能太少)的信息在两个应用程序中传递；
③植物模型应该是基于L系统的，并且这种L系统必须满足双向信息的传送。
Prusinkiewiczd等人提出了微分L系统，用来模拟植物生长过程中离散/连续的情况，微分L系统集成了传统L系统产生式和微分方程两种方法。其基本思想是引入了一种数学模型，这种模型可以对植物生长过程中的平滑动画进行模拟，把植物生长过程中离散/连续行为用统一的形式来表达，L系统用来表达植物生长过程中质方面的变化(比如植物产生新分支)，而用微分方程来表达植物生长过程的连续性(比如植物的茎渐渐拉长)。
微分L系统是在参数化L系统的基础上，通过引入连续时间流的信息来取代一系列离散变换过程。比如，模块A(w)只要参数w的取值范围在定义域DA中，这个模块就会连续变化，如果w的值到达了DA的边界CA.则就会触发一个产生式，植物就会产生离散的变化，此时A(w)就会被子孙模块替换。如果A(w)对应的产生式有多条，利用某条产生式要根据参数w到达的DA边界CAk是属于哪一段来决定。
2 各种植物建模方法的比较
植物建模有迭代函数，粒子系统和L系统三种常见方法,这三种方法都有各自特点和适用范围。迭代函数和L系统都是基于分形理论基础的，迭代函数是用数学方法通过压缩映射变化来描述植物总体与局部之间相似性。迭代函数优点是其理论基础牢固，压缩比很大，可以用几个参数就可以生成非常复杂的图形。其缺点是适用的范围比较狭窄，其压缩比例变换参数难以确定，尤其是对于整个虚拟植物的建模过程而言，更难以确定压缩映射变化的参数，而且迭代函数实现起来非常困难，不利于理解和应用。L系统是用形式语言来对植物生长过程进行描述，L系统的优点是表达方式非常简洁，相对于迭代函数而言，更容易理解和接受，另外L系统特别容易修改和扩充，但是L系统由于是一个并行字符串处理系统，其时间复杂度较高。如果采用微分L系统，由于还需计算植物器官连续变化的情况，其处理所需要的时间更高。
粒子系统是对“模糊”物体进行建模的方法，其优点是灵活多变，可以很真实的模拟“模糊”类的物体，且粒子系统的计算量很小，不需要像传统的基于多变形表面的建模方法一样进行人工的设计模型，但是，它的缺点是只能用于模拟“水、烟雾、云”等模糊类的物体，对植物的建模仿真效果比较差。
参考文献:
[1]高安秀树[日]著，沈步明，常子文译.分数维[M].北京：地震出版社，1989.
[2]胡包钢,赵星,严红平等.植物生长建模与可视化－回顾与展望[J].自动化学报，2001,27(6)：816-835.
[3]郎锐.数子图像处理学VisualC++实现[M].北京：北京希望电子出社,2002.
[4]孙博文.分形算法与程序设计[M].北京：科学出版社,2004.
[5]伍怡.三维植物器官的几何建模[M].北京：中国科学院自动化所,2001.
关键词：建模；虚拟植物；分形
中图分类号:TP391.72文献标识码:A
Technology-based Three-dimensional Virtual Plant Modeling Research
DING Ye1,2
(1.Tongji University, Shanghai 200092；2.Huanghuai institute，Henan Zhumadian 463000)
Key words: modeling；virtual plan；fractal
在虚拟植物生长建模的可视化研究中，分形是其重要的理论基础。分形理论是一个活跃的数学分支，其研究对象是在非线性系统中产生的不光滑和不可微的极不规则几何物体。到目前为止，分形理论已成功的应用到自然科学、社会科学等很多领域，并在工程中得到了广泛的应用，分形已经成为研究许多自然现象的有力工具，在自然现象中，有大量对象不能用经典欧氏几何描述的事物，在这种情况下，分形几何就可以用来处理这不规则的几何形状。
分形几何的理论运用于多个领域，目前，虚拟植物生长建模的研究也基本上是在分形的理论基础上提出的各种建模方法，常用的植物建模方法主要有：迭代函数、粒子系统和L系统，每种方法有其相应的应用场合。
1 主要的植物建模方法
1．1迭代函数
迭代函数系统(Iterated Function Systems，简称IFS)是分形几何学科的重要分支和研究热点。分形集一般都是由某一初始状态经过若干次繁衍变化后得到，这种繁衍变化是无穷无尽的，因而分形集一般都是由无穷多个点组成，点的分布又极其复杂，不可能通过直接给定点的坐标位置来描述它，因此一般通过描述整体和局部的关系来表达。通过繁衍变化，可以生成千姿百态的图形。针对这个系统，巴恩斯利提出了完整的理论和算法，做了很多开创性的工作。
迭代函数系统理论包括以下几个方面：压缩仿射变换、不动点定理和拼贴定理等。迭代函数系统在对很多自然物体建模有很大的优势，只需给出仿射变换的系数，经过迭代运算，就可以快速生成分形物体的图像。
1．1．1压缩仿射变换
定义2.1：设w：X-〉X是完备空间(X,d)上的一个映射。如果存在一个正常数c<1,使
d(w(x),w(y))≤c*d(x,y)，x,y∈X （2-1）
则称w为(X,d)上的压缩映射，c称为压缩因子。
定义2.2：n维欧氏空间Rn中的仿射变换w:Rn →Rn具有下面的形式：
w(x)=Ax+b,(x∈Rn)，
其中A是Rn上的线性变换(可以表示成一个n×n矩阵)，而b是Rn中的一个矢量。当它的线性变换部分是压缩的，则称为压缩仿射变换。可以将压缩仿射分解为平移、旋转和比例缩小等，用下式表示：
wxy=rcosθ -qsinψrsinθ qcosψxy+ef（2-2）
其中e和f分别是x轴和y轴方向上的平移分量，θ和φ分别是绕x轴和y轴逆时针方向的旋转角度，r和q可以分别看成是x轴和y轴方向上的缩小比例。
1．1．2利用迭代系统生成图形的算法
利用迭代系统生成的图形主要有两种算法，一种是确定性算法，一种是随机算法。确定性算法是基于IFS上不动点定理和拼贴定理。但由于得到最终图像所需要的时间复杂度按指数速度增加，所以一般不实用。在实际的应用中一般是由随机迭代算法绘制的，算法的步骤如下：
①任取一点x(i,j)；②在序列{1,2,…,n}中，以概率pk选出k；③把第k个压缩仿射变换作用到点x(i,j)上，得到新的点，记作x=wk(x)；④画点x；⑤回到第二步。
通常计算机作图时，为了避免把吸引子外的点画出，刚开始的点不画，概率pi(i=1,2,…,n)应该正比于第i个压缩仿射变换中其次线性变换系数构成的四边形面积，一般可以由下式确定:
（1）粒子系统
为了更加快速、方便和真实的模拟“模糊”状态的物体，Reeves在1983年提出了一种与经典方法完全不同的建模方法，称为粒子系统。粒子系统所描述的物体包括自然界中常见现象(诸如火焰、雪花、浪花和烟云等)，它们的共性是没有固定的形状，没有规则的几何外形，更重要的一点就是它们的外观随着时间发生不确定的变化，在经典图形学的建模研究中，通常采用几何建模的方法来模拟研究对象的外形，通常采用多边形来表示轮廓，而这类“模糊”状态的物体不可能用这种多边形网格来进行表示。同时该方法无法描述其形状的不确定变化，所以必须找到一种新的途径来对这类物体进行建模，为此引入了“粒子系统”。
在对“模糊”物体进行建模的时候，粒子系统与传统的基于表面的技术相比较有如下几个比较重要的优点：一是粒子系统的计算速度快，在粒子系统中，一个粒子通常可以被认为是三维空间中的一个点来表示，在对图形可视化的过程中，一个三维空间点的处理通常比一个代表物体表面多边形的处理算法要简单很多，所以在相同的时间内，粒子系统可以处理更多的粒子，从而可以生成更为复杂的图形。二是粒子系统不需要进行人工建模过程，在基于表面的建模方法中，模型的最初获取通常是在建模工具中进行人工设计，但是在粒子系统中，模型定义是用随机数控制的一段程序，由于粒子系统是一段程序，所以可以根据需要，可对显示的精细程度进行调整。就如同分形系统一样，如果对一个粒子系统进行放大显示，就可以得到更多细节。三是粒子系统是活动的，它随时间的变化会改变其形状，然而，在基于表面的建模技术中，改变粒子系统表面的计算过程是非常复杂的。粒子系统的每一帧动画，都要经过以下的处理步骤：①新产生的粒子进入系统；②为每一个新建粒子设定属性；③如果一个粒子超过了它预设的生命时间，就会从系统中消失；④其余粒子根据它们的动态属性和最终状态进行移动或者变形；⑤对活动粒子进行渲染，放入到帧缓冲当中。
（2）L系统
自从美国生物学家Lindenmayer于1968年提出L系统后，L系统不断完善。L系统起源于分形思想，它为定义植物的构型提供了新的途径，也产生了一种重要的分形图形生成方法。1984年(A R Smith)等人将L系统引入计算机图形学，在计算机上模拟生成各种形态的植物，显示了计算机模拟植物方面的能力，为在计算机上实现虚拟植物的生长提供了理论和实际的依据。
L系统的构图原理非常简单，L-系统通过产生一系列字符串来构造图形与曲线，主要用来描述植物的形态和细节。通过对L系统进行有限次迭代，产生字符串集，然后对字符串集进行图形解释，即可生成图形。其流程图2所示，在对植物进行建模时,通常植物的一个器官(茎、花、叶等)对应于L系统的一个字符，字符串发展过程对应植物的生长过程。到目前为止，在对L系统的发展应用上，有两类L系统得到了比较成功的应用，第一个是让L系统可以和外界交互的开放L系统。另一个是可以表示植物器官的生长发育变化的微分L系统。
植物同它周围环境进行交互是影响植物生长的重要因素。Mesh等人提出了开放L系统,采用一种框架模型模拟植物同其周围环境交互。植物与周围环境的交互在概念模型上可以认为是植物和其周围环境彼此相互交互的过程，其过程包括植物内部处理和环境处理两个方面，植物内部处理过程如下：①感知植物器官所接受到的环境信息。②植物的内部处理接收到的环境信息；③植物对接收到的信息作出反映和向环境输出信息。
与植物内部处理过程相似，环境处理过程如下所示：①检测植物的反作用；②模拟环境内部处理过程(如环境内部的物质扩散的过程和光线发散的过程)；③修改环境模块参数，并且把修改后环境以植物可以感知的方式发送给植物模块。
通过对植物和环境的概念模型分析，基于可以与周围环境相互交互的系统架构，必须满足如下的要求：
①植物和环境需两个独立的，但可以相互通讯的程序。这样可以和概念模型一致，也符合结构化程序的需要，同时也可以满足分布式计算需要；
②用户可以控制植物模块和环境模块之间的信息流动数量。以满足足够(不可多也不能太少)的信息在两个应用程序中传递；
③植物模型应该是基于L系统的，并且这种L系统必须满足双向信息的传送。
Prusinkiewiczd等人提出了微分L系统，用来模拟植物生长过程中离散/连续的情况，微分L系统集成了传统L系统产生式和微分方程两种方法。其基本思想是引入了一种数学模型，这种模型可以对植物生长过程中的平滑动画进行模拟，把植物生长过程中离散/连续行为用统一的形式来表达，L系统用来表达植物生长过程中质方面的变化(比如植物产生新分支)，而用微分方程来表达植物生长过程的连续性(比如植物的茎渐渐拉长)。
微分L系统是在参数化L系统的基础上，通过引入连续时间流的信息来取代一系列离散变换过程。比如，模块A(w)只要参数w的取值范围在定义域DA中，这个模块就会连续变化，如果w的值到达了DA的边界CA.则就会触发一个产生式，植物就会产生离散的变化，此时A(w)就会被子孙模块替换。如果A(w)对应的产生式有多条，利用某条产生式要根据参数w到达的DA边界CAk是属于哪一段来决定。
2 各种植物建模方法的比较
植物建模有迭代函数，粒子系统和L系统三种常见方法,这三种方法都有各自特点和适用范围。迭代函数和L系统都是基于分形理论基础的，迭代函数是用数学方法通过压缩映射变化来描述植物总体与局部之间相似性。迭代函数优点是其理论基础牢固，压缩比很大，可以用几个参数就可以生成非常复杂的图形。其缺点是适用的范围比较狭窄，其压缩比例变换参数难以确定，尤其是对于整个虚拟植物的建模过程而言，更难以确定压缩映射变化的参数，而且迭代函数实现起来非常困难，不利于理解和应用。L系统是用形式语言来对植物生长过程进行描述，L系统的优点是表达方式非常简洁，相对于迭代函数而言，更容易理解和接受，另外L系统特别容易修改和扩充，但是L系统由于是一个并行字符串处理系统，其时间复杂度较高。如果采用微分L系统，由于还需计算植物器官连续变化的情况，其处理所需要的时间更高。
粒子系统是对“模糊”物体进行建模的方法，其优点是灵活多变，可以很真实的模拟“模糊”类的物体，且粒子系统的计算量很小，不需要像传统的基于多变形表面的建模方法一样进行人工的设计模型，但是，它的缺点是只能用于模拟“水、烟雾、云”等模糊类的物体，对植物的建模仿真效果比较差。
参考文献:
[1]高安秀树[日]著，沈步明，常子文译.分数维[M].北京：地震出版社，1989.
[2]胡包钢,赵星,严红平等.植物生长建模与可视化－回顾与展望[J].自动化学报，2001,27(6)：816-835.
[3]郎锐.数子图像处理学VisualC++实现[M].北京：北京希望电子出社,2002.
[4]孙博文.分形算法与程序设计[M].北京：科学出版社,2004.
[5]伍怡.三维植物器官的几何建模[M].北京：中国科学院自动化所,2001.