基于八叉树三维农作物叶片的体建模算法

林金花， 刘晓东， 李万龙， 王 璐

（1．长春工业大学软件职业技术学院，吉林长春 130012；2．西安交通大学电子与信息工程学院，陕西西安 710049）

0 引 言

我们一直寻求在三维虚拟环境中绘制出棉花叶片、玉米叶片、水稻植株乃至各种农作物形态比较好的方法，从以往经验来说，利用计算机图形学技术把农作物叶片的模型建造起来不是很困难的事情，但是，结合作物生长模型，将作物叶片的内部实体属性（环境因子、三维纹理、颜色密度）描述成计算机可以控制的模型则比较困难。所以，在实现过程中必须采用一些简化思想。

首先，采用八叉树方法［1］实现三维作物叶片模型的体建模，该模型可以精确表示三维叶片内部所有点的几何位置，这种点集拓扑体模型将叶片实体内部的属性和结构看作三维实体占据的空间位置函数，由于体几何模型构造方法简单，容易离散化，所需计算及存储均很少，使得三维作物叶片的形态建模得以精确控制。然后结合知识引擎组件对象驱动作物器官组件对象生长变化，使生长模型中的属性描述与虚拟作物器官（叶片）组件分离，在生长模型脚本里定义作物生长的各种参数，知识引擎就根据这些参数来控制作物的具体生长。最后在进行虚拟试验时，通过体模型控制作物生长所需元素的变化，实现农作物叶片的真实感建模。

采用体几何模型来对作物叶片进行建模，由于体模型构造方法简单，可以表示具有凹凸表面、横截面变化连接以及旋转体等，但是，对于作物叶片这种形态较不规则的实体，为了使得叶片体模型更加真实地拟合生长过程中的叶片变化形态，引入八叉树剖分方法，将体模型剖分成一个个体元组成的集合，生成一个树形结构，采用线性八叉树链表存储，通过知识引擎组件输入叶片的属性参数，驱动作物叶片的形态建模。

体建模与八叉树技术的结合，实现了三维农作物叶片的生长形态建模，使得模型真实并且控制精确，基本满足了虚拟作物可视化平台实时性交互的要求。

1 基于八叉树的叶片模型体元化

所谓多面体的体元化是把面图形学中由边界法表示的多面体转换成体图形学中的由若干个体元［2］（即附带实体属性空间分布数据的一个体单位）组成的一个多面体。采用八叉树方法将用边界法表示的叶片几何模型转换成三维体元模型，八叉树的体元化即为面数据转换成体数据的过程，这里采用十字链表结构以及八叉树线性编码来实现。

1.1 体元数据结构

为了使八叉树剖分中的立方体与边界面更加精确地逼近相交，首先将多面体的每个面都进行三角剖分，组成一张三角面片表，这是一张由三元组构成的二维链表，用来存放多面体每个面的三角面片属性。然后根据三角面片属性表生成一个由若干个体元组成的集合，也就是将具有树形结构的三角面片链表（八叉树）转换为一种体元数据结构，采用十字链表结构来表示这种体元数据结构，每一个链表结点表示一个体元。最后采用线性八叉树编码［3］对体元链表进行编码，即对每个结点进行统一的八进制编码，可以节省内存空间，提高体绘制的索引速度，由此生成体建模所需的体元坐标。具体剖分过程如图1所示。

图1 八叉树剖分流程图

初始控制点决定了所生成模型的大致形状，应该简单并且特征突出。若控制点选取过多，就不能很好地体现整体变形简单的优势；若控制点选取过少，就很可能不能模拟出物体的特征，缺乏真实感。所以，要建立恰当的初始控制点集［4］，必须要对待建模物体进行很好的分析，用尽可能少的点集模拟出物体的大致形状和主要特征。根据文中算法中的控制点必须是原始模型上的点，同时，对初始模型细分后要保存其控制点不变的特征，选用改进的Butterfly细分规则对原始模型进行细分，再应用文中算法进行变形。根据性能测试中原始模型在不同变形效果时作物模型的细致程度和绘制速度，取得合适的变形参数，使得最终模型的真实感和生成速度有较好的折衷。这里采用十字链表结构实现这种链表间的嵌套，体元数据结构如图2所示。

图2 体元数据结构

文中算法采用三角面片表示叶片模型的整个剖分过程，一方面为了实现整个三维环境下的可视化绘制，另一方面便于实现与作物其它器官部件的接口连接绘制。

具体的体元数据结构如下：

typedef struct VoType｛

VType vbox；／／体元类型

Vertex vo；／／体元坐标

char＊code；／／八叉树线性编码

int l；／／体元分辨率l＝2i，i为剖分次数

RGB color；／／体元颜色及对比度

struct VoType＊next；／／指向下一个体元

struct VoType＊child；／／指向子体元链表

Tlist＊Trintermesh；／／相交三角面片指针链表［5］

｝VoType；

1.2 八叉树体元化算法

具体的八叉树剖分算法如下：void Alloctree：：make＿tree（TList＊interTrmesh，TList＊primitive，octreeType＊tree，int depth）

｛

int i，j；

switch（classify（interTrmesh，primitive，tree））

／／判断当前八叉树结点，是否与其父结点相交的三角面片相交，从而得出其是No1，No2，No3结点。

在八叉树剖分算法中，最关键的是判断出哪些立方体与边界面相交，为了使利用立方体逼近的边界面更为光滑，立方体应越小越好，但是这样会使空间与时间复杂度增加，因此，在边界面上的八叉树剖分中采用提高分辨率的方法，同时保存原有体元结点，进而实现十字链表形式的八叉树结构［6］。

2 叶片生长模型的构建

生长模型就是将作物及其环境因子作为一个整体，应用系统分析的原理和方法，对作物的生育、生长的生理过程及其环境因子关系的实验数据加以整合概括和量化分析，建立相应的数学模型。将抽象出来的具有实际意义的公式、参数、变量等用XML语言包装起来，形成生长模型脚本［7］，知识引擎就可以根据这个脚本来控制作物的生长。

2.1 知识引擎组件结构

采用知识引擎组件对虚拟作物进行生长驱动，在生长模型脚本里定义作物生长的各种参数，知识引擎就根据这些参数来控制作物的具体生长。知识引擎组件结构如图3所示。

图3 知识引擎结构图

2.2 生长模型的建立

生长模型的XML脚本文件描述了环境、作物先天因素等数据与作物生长形态变化（时间与几何）之间的关系，知识引擎组件对XML脚本［8］进行分析，从中提取出一系列具有时序性的数值运算和逻辑运算，使系统中可驱动作物器官组件对象的属性发生改变。从技术角度来讲，就是通过农学知识把影响作物生长的各种因素经过一系列演算，生成作物各个阶段的生长量，然后把这个生长量作为作物器官对象的控制器官形变的属性值，驱动器官的生长。

在知识引擎组件与可驱动组件（生长模型）之间建立驱动关系的结构示意图，如图4所示。

图4 知识引擎与叶片组件之间建立子属性关系

知识引擎组件以索引属性的形式将一个驱动组件对象放于集合列表中，从而保持了对可驱动组件一对多的关联关系［9］。

3 三维叶片模型的动态体绘制

采用八叉树结构表示模型的内部属性变化，用知识引擎驱动这种变化［10］，建立作物的动态模型。由于采用八叉树将多面体剖分为体元，模型实体的空间信息已经保存在混合数据结构中，并能够方便进行查找索引，因此，采用体元组成绘制算法。

具体算法如下（以棉花叶片为例）：

1）建立模型的生长曲线，对多面体模型进行面绘制。棉花叶片形态上最大的特点是边缘呈皱褶状。我们让叶片两边的控制点随着皱褶的变化呈现高低交错的情况。叶片中间是主脉，可用叶片的空中伸展曲线来模拟它［11］。

2）用知识引擎技术驱动作物叶片的动态建模，选择相关性体元进行体绘制的象素，可以在绘制过程中组合原先帧缓存中的属性信息。

3）重新定义一个统一的分辨率进行再剖分，实现体元形状相同、大小不一的体元模型。

4 实验结果

以棉花和玉米叶片为例来验证文中算法。在显示的时候把叶鞘与叶片设置为属于同一个体元集合，因此叶片在u方向（局部坐标）的控制点个数和叶鞘必须相等，最终叶片的控制点设定为两边各1组和中间紧密的5组，共7组。传统算法是将模型剖分成均匀大小的体元，文中算法把模型剖分成不同大小的体元集合，以棉花叶片为例，不同算法的棉花叶片体建模效果如图5所示。

图5 不同算法的棉花叶片体建模效果

传统算法的空间开销为2 221个体元，效果见图5（a）。文中算法空间开销为5 272个体元，效果见图5（b），显示效果真实感较好，如果采用传统算法要达到相同效果，则体元数要达14 760个。可见文中算法可以在较小的空间开销下，达到较好的显示效果。

玉米叶片的建模效果［12］如图6所示。

图6 文中算法绘制的玉米叶片模型

5 结 语

三维实体的体建模技术是体图形学的重要组成部分，传统的体建模方法仅适用于均匀大小的体元模型［13］，而对于农作物叶片模型，其叶片纹理、旋转角度以及颜色分布等内部属性受环境因子的影响，使得叶片模型应具有不规则性。为了解决这一问题，文中引入八叉树剖分技术将叶片模型剖分成不均匀的体元模型，生成一个十字链表结构，用八叉树体元实现叶片模型的不规则显示，通过知识引擎组件驱动作物叶片的形态建模。实验表明，文中算法对作物叶片整体建模效果较好，适用于虚拟作物实验系统的开发与应用。

［1］ Stachniak S，Stuerzlinger W．An algorithm for automated fractal terrain deformation［J］．Computer Graphics and Artificial Intelligence，2005，5：64－76．

［2］ Kruer J，Kipfer P，Ondratieva P，et al．A particle system for interactive visual－ization of 3Dflows［J］．IEEE Transactions on Visual－ization and Computer Graphics，2005，11（6）：744－756．

［3］ Su Z X，Li B J，Liu X P，et al．Rapid evaluation ofregular quad－mesh interpolatory subdivision surfaces based on parametric decomposition［J］．Journal of Software，2007，8：18－25．

［4］ Kruer J，Kipfer P，Ondratieva P，et al．A particle system for interactive visual－ization of 3Dflows［J］．IEEE Transactions on Visual－ization and Computer Graphics，2005，11（6）：744－756．

［5］ Hu S M，Zhang H，Tai C L，et al．Direct manipulation of FFD：Efficient explicit solutions and decomposible multiple point constraints［J］．The Visual Computers，2010，17（6）：370－379．

［6］ Huijing Zhao，Ryosuke Shibasaki．Reconstructing a textured CAD model of an urban environment using vehicle－borne laser range scanners and line cameras［J］．Machine Vision and Applications，2003，14（1）：222－225．

［7］ 胡小红，周旺，黄临平，等．三维散乱点的八叉树建模及程序实现［J］．东华理工学院学报，2007，5（6）：41－43．

［8］ 洪雄，张建勋，曾庆森．基于似三棱柱构模的三维地质体的剖切［J］．计算机工程与技术，2008，15（5）：273－275．

［9］ 连纪恩，张凤军，付永刚，等．虚拟环境下基于语义的三维交互技术［J］．软件学报，2006（7）：1535－1543．

［10］ 王亮．虚拟环境中基于语义的三维交互技术研究及应用［D］：［硕士学位论文］．合肥：中国科技大学，2008．

［11］ 曹彤，刘臻．用于建立三维GIS的八叉树编码压缩算法［J］．中国图象图形学报，2002，7（A1）：50－54．

［12］ 吕广宪，潘懋，王占刚，等．面向体数据的虚拟八叉树模型研究［J］．计算机应用，2006，26（12）：1535－1543．

［13］ 林金花，李万龙，王璐，等．一种基于B－样条曲面控制的自由变形方法［J］．长春工业大学学报：自然科学版，2011，32（6）：574－580．