一种基于动态子结构的三维虚拟植物构建和存储方法

摘要

本发明提出一种基于动态子结构的三维虚拟植物构建和存储方法，包括子结构参数初始化，根据动态子结构方法进行植物结构的构建，以子结构方法的数据保存，利用子结构信息进行对植物结构的交互式编辑。本发明的特征在于，对植物结构中相似的子结构定义一个子结构库，通过对其中的信息重复调用节省时间和空间。子结构库中的样本能根据需要动态产生，避免产生的子结构未被调用。能通过对重复调用的子结构只保存一个备份达到虚拟植物数据的压缩存储。能根据子结构的调用信息对构建后的植物和植物子结构进行交互式的编辑。

权利要求

1.一种基于动态子结构的三维虚拟植物构建和存储方法，其特征在于，所述方法包括步骤如下：步骤S1：子结构参数初始化，对植物结构进行分解，确定虚拟植物中分枝即子结构的类型及逐层调用关系；给定每层子结构的最大个数，即子结构库大小；

步骤S2：根据动态子结构方法构建虚拟植物结构，首先构建虚拟植物的生长轴，递归地逐层构建子结构，放入对应子结构库中，直到虚拟植物结构构建完毕，具体步骤如下：步骤21：根据植物结构模拟算法构建编号np的当前子结构的生长轴，存入子结构p所对应的子结构库中，np∈[1，Tp]，子结构p所对应的子结构库的大小为Tp；

步骤22：依次序遍历编号np的当前子结构的生长轴上的所有产生下一层子结构的位置；根据植物结构模拟算法获得编号np的当前子结构的生长轴上的下一层子结构的类别q、位置和方向；

步骤23：判断遍历是否已经结束，下一层的子结构的信息是否已包含到当前子结构；

如果遍历没有结束，还存在空缺的下一层子结构位置，则转步骤24，如果遍历已经结束，则转步骤27；

步骤24：根据编号np的当前子结构的生长轴上的下一层子结构类别q产生一个1到Tq之间的整数子结构编号mq，mq∈[1，Tq]，子结构q所对应的子结构库的大小为Tq；

步骤25：判断该编号的子结构mq是否已经在之前进行构建，已经存在于对应于类别q的子结构库中；如果不存在，则转入步骤21，对编号为mq的下一层子结构，以构建当前子结构np同样的过程进行递归构建；这时编号为mq的子结构成为当前子结构；如果下一层子结构mq已经存在于子结构q所对应的子结构库中，则转步骤26；

步骤26：根据下一层子结构mq的其位置和方向，进行几何变换后组合到当前生长轴，不再重复构建，结束后转步骤22；

步骤27：如果当前生长轴上的子结构都已经构建完毕，则当前子结构的构建结束，转上一层子结构，直至顶层结构；

步骤S3：以子结构方法的植物数据保存，或数据保存与步骤S2的植物结构构建过程同步进行；对于每一类子结构，其中植物数据是在模拟过程中创建的植物生长轴的信息，以及子结构位置上的子结构编号和变换矩阵；

步骤S4：利用子结构信息对植物结构进行交互式编辑，从步骤S3获取子结构之间的调用关系，或从步骤S2获取子结构之间的调用关系，所述交互式编辑是用户在屏幕上选取一个子结构的生长轴的某位置，选取该位置上方的所有的植物组成部分并做剪枝、疏叶、拖动的操作，创建一个新的子结构。

2.根据权利要求1所述的基于动态子结构的三维虚拟植物构建和存储方法，其特征在于，对植物结构中相似的子结构定义一个子结构库，通过对其中的信息重复调用节省时间和空间；所述子结构是在植物结构构建过程中根据需要动态创建，对不同复杂度的植物结构都能保证模拟效率高于对植物结构进行完全遍历的算法。

3.根据权利要求1所述的基于动态子结构的三维虚拟植物构建和存储方法，其特征在于，所述子结构库中的样本根据需要能动态产生，能避免产生的子结构未被调用。

4.根据权利要求1所述的基于动态子结构的三维虚拟植物构建和存储方法，其特征在于，能通过对重复调用的子结构只保存一个备份达到虚拟植物的压缩存储，能根据子结构的调用信息对构建后的植物和植物子结构进行交互式的编辑。

说明书

一种基于动态子结构的三维虚拟植物构建和存储方法

技术领域

[0001] 本发明属于虚拟现实、数字农林业、数字娱乐、景观设计等技术领域，特别是涉及虚拟植物结构的造型方法与动态展示。

背景技术

[0002] 随着三维显示技术的发展，对数字环境下显示内容的需求迅速增加。植物作为自然界重要的组成部分，对其造型与动画是数字场景构建必不可少的部分。构造实现虚拟植物三维结构的主要方法大致上可以分为两类。一类是手工交互方式，即通过应用专业设计软件定义虚拟植物的结构。简单的植物结构或者植物器官可以通过交互的方式进行手工建模，但对于复杂的植物结构，其中可能包含成百上千万个器官，完全用手工建模的方式是不可行的。另一类建模方式是基于算法的模拟，自动生成植物结构。常见的模拟算法有字符串替换系统、粒子系统、自动机等。

[0003] 在利用算法模拟植物结构时，共同的特点是要定义生长规则，描述不同顶芽或侧芽产生的分枝类别甚至包含的器官类别和个数。直观的模拟方法是在每次迭代中对所有植物结构以一定顺序进行遍历，逐个更新分枝的状态。如果所模拟的植物数量大，而且植物结构复杂，那么植物结构的遍历非常耗费计算时间，难以进行结果的调试和实际应用。

[0004] 事实上，复杂的植物结构中通常会包含大量相似分枝，在成熟的树中更为常见。根据对植物的观察，可以将整株地植物分枝划分为有限的几类。植物植物学家认为可以将分枝类型按生理年龄进行划分。植物分枝的相似特征能用于植物结构的快速构建。每类分枝可称为一种子结构，每个子结构可分解为一个生长轴和下一层的子结构，直到不再包含下一层子结构。对单株植物来说，顶层的子结构是植物本身。子结构构建方法是，对每类子结构，定义一个子结构库；植物结构的构建过程从最简单的子结构起，通过子结构的调用和几何变换，逐层自上而下地进行。此算法中，计算时间与子结构库的大小成正比，而不是和植物结构中的器官个数成正比，这对于复杂的植物结构具有明显优势。通过试验证明，对于复杂植物结构，该算法的效率高于植物结构的遍历算法。然而，以往此类方法中子结构库是按从简单到复杂、自顶向下的顺序一次性构建，不仅不直观，而且存在部分子结构未被调用而浪费资源的情况，对于简单的植物结构，模拟时间反而高于遍历算法。

[0005] 目前国际上有几款专门用于构建虚拟植物结构的商业软件，例如xfrog，Onxy tree，Speed tree，AMAP等，大多提供用于桌面设计的主流软件的插件。国内尚无此类的专业软件。本发明可以用于此类软件的算法设计。

发明内容

[0006] 本发明欲解决的技术问题是如何高效灵活地利用植物分枝的相似性，同时保留植物结构遍历算法的优势，进行虚拟植物的构建、保存、调用、交互式编辑以及压缩存储。为此，提出一种基于动态子结构的三维虚拟植物构建和存储方法。

[0007] 为实现本发明的目的，本发明基于动态子结构的三维虚拟植物构建和存储方法的步骤如下：

[0008] 步骤S1：子结构参数初始化，确定虚拟植物中分枝即子结构的类型及逐层调用关系；给定每层子结构的最大个数，即子结构库大小；

[0009] 步骤S2：根据动态子结构方法构建植物结构，首先构建虚拟植物的生长轴，对于虚拟植物生长轴上的任意子结构位置，如果对应的子结构在子结构库中已经存在，则直接从子结构库中调用，进行几何变换后组合到当前子结构；否则，递归地逐层构建子结构，放入对应子结构库中，直到虚拟植物结构构建完毕；

[0010] 步骤S3：以子结构方法的植物数据保存；对于每一类子结构，其中植物数据是在模拟过程中创建的植物生长轴的信息，以及子结构位置上的子结构编号和变换矩阵；

[0011] 步骤S4：利用子结构信息对植物结构进行交互式编辑；子结构之间的调用关系可以从步骤S3获取，也可以从步骤S2获取。

[0012] 其中，对植物结构中相似的子结构定义一个子结构库，通过对其中的信息重复调用节省时间和空间。

[0013] 其中，所述子结构库中的样本根据需要能动态产生，能避免产生的子结构未被调用。

[0014] 其中，能通过对重复调用的子结构只保存一个备份达到虚拟植物的压缩存储，能根据子结构的调用信息对构建后的植物和植物子结构进行交互式的编辑。

[0015] 本发明的有益效果：对于植物结构中重复出现的子结构，只需模拟有限的子结构样本，通过重用子结构样本的信息而提高模拟效率。注意子结构是个递归的概念。虚拟植物可以分解为主轴和直接长在主轴上的子结构，主轴上的子结构又可划分为生长轴和下一层的子结构。虚拟植物本身是森林场景中的子结构。由于本方法中子结构是在植物结构构建过程中根据需要动态创建，因此不存在子结构未被调用而产生的时间和空间的浪费，对不同复杂度的植物结构都能保证模拟效率高于对植物结构进行完全遍历的算法。用户可以改变子结构大小获得期望的效率和子结构多样性。植物的构建过程是从下而上进行，对动态创建的子结构进行遍历，比较直观。通常保存虚拟植物几何结构的文件所占用的空间随其中器官个数线性增加；对于应用动态子结构算法构建的植物结构，由于子结构的信息被重用，因此仅需要保存子结构的变换和调用信息，从而达到节省空间的目的。在读取这样的文件时，由于需要进行子结构的逐层解开和变化，需要花费一定时间，因此这是一种以时间换空间的方法。由于子结构的调用信息被保存，可以对植物进行交互式操作。

附图说明

[0016] 图1a是基于动态子结构方法的框架图。

[0017] 图1b是图1a中步骤S2的子流程图。

[0018] 图2是基于随机子结构的模拟和调用示意图。

[0019] 图3是植物结构中包含的不同类别的子结构示例。

[0020] 图4a和图4b是森林场景的子结构方法构建示意图。

[0021] 图5是青园软件中对复杂植物结构的模拟结果。

[0022] 图6是青园软件中对随机植物结构的模拟结果。

具体实施方式

[0023] 为使本发明的目的、技术方案和优点更加清楚明白，以下结合具体实施例子，并参照附图，对本发明进一步详细说明。这里假定读者熟悉植物结构模拟算法，例如自动机、字符串替换系统等，集中介绍如何在这类算法中应用动态子结构算法。

[0024] 图1a所示为实现动态子结构方法的各个部分的关系。

[0025] 步骤S1对植物结构进行参数的初始化，确定虚拟植物中分枝即子结构的类型及逐层调用关系；给定每层子结构的最大个数，即子结构库大小；要实现预期的虚拟植物结构，首先对植物结构进行分解，确定其中包含的子结构类型以及逐层组合关系；子结构类型的划分可参考植物学家提出的生理年龄。每类子结构采用相同的植物结构模拟参数。

[0026] 步骤S2根据动态子结构方法进行植物结构的构建，具体流程如图1b所示。由于子结构为递归的概念，为描述方便，当前正在构建的子结构称为当前子结构，当前子结构的生长轴上着生的子结构称为下一层子结构。当前子结构相对于下一层的子结构称为上一层子结构。当前子结构的类别用整数p表示，p＝0时表示虚拟植物本身。当前子结构中包含的下一层子结构的类别用整数q表示，一般q大于p。子结构p所对应的子结构库的大小为Tp，子结构q所对应的子结构库的大小为Tq，都在步骤S1中定义。模拟过程从植物的主轴开始(p＝0)。

[0027] 步骤21：根据植物结构模拟算法构建编号np的当前子结构的生长轴，存入子结构p所对应的子结构库中，np∈[1，Tp]；

[0028] 步骤22：以一定次序遍历编号np的当前子结构的生长轴上的所有产生下一层子结构的位置。根据植物结构模拟算法获得编号np的当前子结构的生长轴上的下一层子结构的类别q、位置和方向。

[0029] 步骤23：判断遍历是否已经结束，下一层的子结构的信息是否已包含到当前子结构；如果遍历没有结束，还存在空缺的下一层子结构位置，则转步骤24，如果遍历已经结束，则转步骤27。

[0030] 步骤24：根据编号np的当前子结构的生长轴上的下一层子结构类别q产生一个1到Tq之间的整数子结构编号mq，mq∈[1，Tq]。

[0031] 步骤25：判断该编号的子结构mq是否已经在之前进行构建，已经存在于对应于类别q的子结构库中。如果存在，则转入步骤21，对编号为mq的下一层子结构，以构建当前子结构np同样的过程进行递归构建；这时编号为mq的子结构成为当前子结构。如果下一层子结构mq已经存在于子结构q所对应的子结构库中，则转步骤26。

[0032] 步骤26：根据下一层子结构mq的其位置和方向，进行几何变换后组合到当前生长轴，不再重复构建，结束后转步骤22。

[0033] 步骤27：如果当前生长轴上的子结构都已经构建完毕，则当前子结构的构建结束，转上一层子结构，直至顶层结构。

[0034] 图2是基于随机子结构的模拟和调用示意图，表示动态子结构方法进行植物结构的构建的过程。其中，黑色的虚线箭头为子结构的模拟顺序，而绿色的弯箭头的子结构的返回顺序。S1表示要构建的虚拟植物，蓝色轴为其生长轴。各级子结构库的大小均为5。当对其中的椭圆形内的子结构进行构建时，首先判断该子结构在对应于S2的子结构库中是否存在，如果不存在则进入到S2这一层的子结构样本构建：模拟S2子结构库中的子结构样本的生长轴，遍历所有子结构位置，判断某编号的子结构是否存在。如果不存在则进入下一层进行构建。这样一直进行直到最简单的一层子结构S4。之后逐层调用返回。

[0035] 步骤S3表示以子结构方法的植物数据保存；对于每一类子结构，其中植物数据是在模拟过程中创建的植物生长轴的信息，以及子结构位置上的子结构编号和变换矩阵。当存在子结构大量重复调用时，对重复的子结构数据仅保存一个备份。数据保存可以与步骤S2的植物结构构建过程同步进行，也可以在步骤S2完成之后实现。植物器官可以看作子结构的一个特例，其几何结构单独定义。每种器官对应于一个器官描述文件，器官描述文件包含器官的几何模型、纹理坐标等信息，可由专业软件手工创建。以子结构方式保存的植物数据中仅保存该器官的一个标识，从而节省空间。描述一个子结构的基本数据结构如下：

[0036] SUBSTRUCTURE

[0037] {

[0038] int ID； //子结构的标识；

[0039] int length； //所包含器官个数；

[0040] ORGAN O(length)；//所包含的器官列表

[0041] }

[0042] 其中，ID为子结构的特征，说明该子结构的类别。length为其生长轴中包含的器官个数，包括普通的器官，例如节间、叶子、果实等，也包括其中的下一级子结构。O(length)为对每个器官的具体描述。其数据结构ORGAN的描述如下：

[0043] ORGAN

[0044] {

[0045] int symbol； //器官类别；

[0046] int ID； //器官标识；

[0047] float Mo(3，4)； //几何变换矩阵；

[0048] float So(2)； //对于器官为器官大小，对于子结构则无意义。

[0049] int num_sons； //所指向的器官个数

[0050] int id_sons(num_sons)； //所指向的子器官标识

[0051] int id_parent； //父器官标识

[0052] }

[0053] 其中，symbol用于标识数据结构ORGAN保存的是器官或子结构，不同的器官有不同的类别，与器官描述文件相对应。ID为器官的特征。Mo包含器官或子结构的旋转和平移变换矩阵。如果symbol表示当前的子结构是器官，则So为器官的大小，否则无意义。num_sons表示当前器官的子器官个数。对于节间，其上着生的器官和子结构及其顶端的节间均视为其子器官。id_sons(num_sons)即存放了所有子器官的标识。类似地，id_parent存放了当前器官的父器官的标识。所有的器官或子结构数据以标准的方向和大小存放，在调用时给出其在生长轴上的大小、方向和位置。

[0054] 对于以子结构方式保存的数据，可以递归地解析出完整的植物几何信息，进行后续的处理。以伪代码方式描述的解析过程如下：

[0055] Read_Substructure(SUBSTRUCTURE s)

[0056] {

[0057] for i＝1 to s.length

[0058] if O(i).symbol<>’子结构’

[0059] Output_Substructure(O(i))；//输出器官的信息

[0060] else

[0061] Read_Substructure(O(i))；

[0062] end

[0063] end

[0064] }

[0065] 其中，函数Read_substructure逐个读取当前子结构中包含的器官信息，如果该器官是子结构，则进一步对其中的子结构进行解析。如果该器官为普通器官(即s.symbol<>’子结构’)，则直接读取器官描述文件的信息，根据变换矩阵Mo进行变换并返回。由于每个子结构的ID是唯一的，因此通过ID对子结构进行直接访问，从而可以得到任意位置的子结构信息。例如图3是植物结构中包含的不同类别的子结构示例，从左到右分别是具有包含关系的不同类别的子结构。

[0066] 步骤S4利用子结构信息对植物结构进行交互式编辑。例如用户进行枝条修剪、拖动等操作。在进行交互过程中需要子结构之间的调用关系，使得用户在屏幕上选取一个子结构的生长轴的某位置后，该位置上方的所有的植物组成部分都能被选取。子结构之间的调用关系可以从步骤S3获取，也可以从步骤S2获取，后者意味着在模拟过程中进行交互式编辑。选取以后可以进行例如剪枝、疏叶、拖动等动作等。上述操作相当于创建了一个新的子结构。这时需要修改子结构之间的连接关系，将新的子结构的编号保存在上一级子结构中，而旧子结构被调用的次数减少。修改后的信息传回步骤S2或步骤S3.

[0067] 上述基于动态子结构的植物结构构建的思想可推广到植物群落的构建，即如图4a和图4b示出森林场景的子结构方法构建示意图，当构建包含大量植物个体的场景时，仅模拟有限的几个植物样本，然后通过重用这些信息来构建群落。如图4a表示虚拟植物样本，图4b表示重复应用这几个样本而构建的植物场景。

[0068] 这里我们给出了在“青园”软件中的实施结果。“青园”是本课题组自行开发的一个基于GreenLab功能结构模型的植物生长和结构模拟软件，可以用于构建各种作物和植物。GreenLab模型是一个通用的数学模型，基于植物学的基本假设而建立。青园软件用c++语言实现了本发明所描述的方法，并且进行了测试。PC机的配置为Intel Core(TM)21.86G的CPU，2G的内存，操作系统为Windows XP Professional。图5为青园软件中对复杂植物结构的模拟结果，一棵基于确定性子结构的复杂的杨树的模拟，其中包含了1210.6万个器官，模型计算时间为10.2秒。图6为青园软件中对随机植物结构的模拟结果为基于随机子结构的松树的模拟，其中子结构库的大小为5。表明在这样较小的子结构大小下，可以得到很好的视觉效果。

[0069] 以上所述，仅为本发明中的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉该技术的人在本发明所揭露的技术范围内，可理解想到的变换或替换，都应涵盖在本发明的权利要求书的保护范围之内。