基于关键点存取的虚拟植物碰撞检测方法的研究

郑 萍，赵春江，2*，张继成

（1.东北农业大学工程学院，哈尔滨 150030；2.国家农业信息化工程技术研究中心，北京 100097）

碰撞检测是虚拟植物模拟中的一个重要问题。虚拟植物生长环境需要处理若干个静止对象和活动对象，而且每个虚拟对象的模型都是由数以万计的基本几何元素组成的，这使得碰撞检测处理的算法复杂度大大提高。虚拟植物需要准确地判断两个物体是否发生碰撞，并且要求具有很高的实时性。精确的碰撞检测对于提高虚拟植物生长系统的拟真度、增强虚拟环境的沉浸感有着至关重要的作用。而且考虑到植物作为一个有机体，在虚拟植物生长过程中，具有碰撞规避机理，所以精确的进行碰撞检测对增加生长系统模拟的真实性也具有重要意义。

1 碰撞检测研究方法

现有的碰撞检测算法大致可划分为两大类：空间分解法和层次包容盒法。这两种方法的目的都是为了尽可能地减少需要相交测试的对象数目。

1.1 空间分解法

它是将整个虚拟空间划分成相等体积的小单元格，只对占据同一单元格或相邻单元格的几何对象进行相交测试，该方法适用于稀疏环境中分布比较均匀的几何对象间地碰撞检测。比较典型的方法有八叉树、BSP树、均匀网格等。但是空间分解法随着分化单元格的体积越小，数据处理量越大，影响了检测速度和模拟系统的连续性，该方法以牺牲时间提高精度。

1.2 层次包容盒方法

层次包容体法的核心思想是利用体积略大而几何特性简单的包容体将复杂几何对象包裹起来，在进行碰撞检测时，首先进行包容体之间相交测试，只有包容体相交时，才对其所包裹的对象做进一步的相交计算。比较典型的包容体类型有轴对齐包容盒（AABB）、包容球、有向包容盒（OBB）、DOPs和凸包等。在构造碰撞体的包容体时，若引入树状层次结构，可快速剔除不发生碰撞的元素，减少大量不必要的相交测试，从而提高碰撞检测效率。

它的关键在于包容盒类型的选择，对用于碰撞检测的包容盒有以下两方面的约束：①简单性：包容盒应该是简单的几何体，至少应该比被包容的几何对象简单。简单性不仅表现为几何形状简单易于计算，而且包括相交测试算法的快速简单。②紧密性：包容盒应该尽可能地贴近被包容的几何对象。紧密性直接关系到需要进行相交测试的包容盒的数目。该方法与空间分解法比较，缩短了检测时间，提高了显示速度。但是该方法属于粗犷型碰撞检测，对于不规则的物体（如植物等），缺失很多形态信息，导致很多互补形态结构被误认为是碰撞，使模拟的效果降低。

在虚拟植物过程中，植株不断生长，形态结构不断变化，植株间的距离也会随之改变。根据虚拟植物的这一特点，如果采用传统的检测方式，首先使用轴对齐包容盒（AABB）检测远距离植株之间的碰撞，并把八叉树结构应用到碰撞检测中，通过八叉树空间剖分技术来缩短碰撞检测的时间；在近植株的碰撞检测中，则采用路径跟踪算法，经典算法有LC算法和GJK算法。

①轴对齐包容盒（AABB），虽然AABB存在着冗余量大等缺点，但当被包容的对象发生变形时，它能够很方便地从子结点的包容盒合成父结点的包容盒，这一属性正适合不断变化的虚拟植物，而包容球和方向包容盒（OBB）则需要花费大量的时间重新计算。

一个给定对象的AABB被定义为包含该对象且各边平行于坐标轴地最小地六面体。图1给出了虚拟植物过程中一个简化了的二维平面中的例子。给定对象的AABB的计算十分简单，我们只需分别计算组成对象的基本几何元素集合中各个元素的顶点坐标最大值和最小值即可。AABB间的相交测试也比较简单，我们采用SAT（Separting-axes test）法，只需比较两个AABB包容盒分别在三个坐标轴上投影的区间的重叠情况。定义AABB的六个最大最小值分别确定了它在三个坐标轴上的投影区间，因此AABB间的相交测试最多只需要六次比较运算。

图1 轴对齐包容盒（AABB）Fig.1 Axis alignment bounding box

②空间八叉树剖分技术是一个空间非均匀网格剖分技术，该技术是将含有整个对象的空间立方体按三个方向中剖面分割成八个子立方体网格，组织成一棵八叉树。若某一子立方体网格中所含对象面片数大于给定阈值，则为该子立方体做进一步的剖分。上述剖分过程直至八叉树的每个叶子结点所含面片数均小于给定的阈值为止。这个技术也是利用了空间连贯性。

构造八叉树包容盒：首先，为植株建立包容盒，输入叶片（以三角形顶点的形式）的数据，遍历所有三角形的每个顶点，找出叶片中沿三个坐标轴的最大、最小值，按照最大、最小值分别对植株对象建立各条边分别平行于坐标轴方向的AABB包容盒；接着，以植株对象的AABB包容盒为例，采用自顶向下的方法构造，①确定分裂轴，分裂点：通常选择三个坐标轴分裂平面的法向轴，分裂点取AABB包容盒各条棱的中点，这样经过一次分割就可以把AABB包容盒以分八。②包容盒中元素（三角形）分属确定：一个基本的几何元素（三角形）或属于八个子包容盒的某个，或与子包容盒的某些相交。若相交，则计算该三角形的重心，通过判断重心位置属于哪个子包容盒来确定此三角形属于哪部分，若重心也恰在分裂面上，则把它分配给元素较少的那一部分，若几部分所包含的三角形一样多，则指定此三角形属于任一子包容盒。③递归构造包容盒八叉树及终止条件：分别对对于每个子包容盒中三角形运用步骤①建立AABB包容盒，并递归调用步骤②直至每个包容盒中只含有一个三角形（叶片）为止。

2 关键点存储技术

传统的碰撞检测方法具有各自的优点和适用范围，对检测结果分析具有重要意义。但在虚拟植物生长模拟过程中，应该更多的结合植物的生长发育规律进行碰撞检测，针对植物生长发育特点提高检测速度和精度，特别是对细小的植物分枝，往往忽略不计，造成了检测速度的下降。根据上述问题，利用关键点存储方法进行细小分枝的碰撞检测，是对新的检测方法的一种探索。

首先对植物生长特点进行分析，形态复杂的植株或多植株相邻生长在一起，会有大量的细小枝叶穿插生长，此时如用空间分解法就需要对空间划分非常小的格子，否则还没有进行检测两个格子就已经相互碰撞了，但是随着格子体积的减小，计算量也同样增加了，影响检测速度，如用包容盒法将植物包裹起来，就违反了植物生长特点，影响模拟效果。两种检测方法在植物碰撞检测中都具有缺点，所以有必要提出针对植物生长系统的碰撞检测方法。

在基于生物量进行植物形态模型建立之后，对于给定时刻植物模型将获得一个静态的植株。这样问题就得以简化，对于要进行碰撞检测的植株，只要对处于同一水平面上的生物点（关键点）进行比较分析，即可判断是否碰撞。下面针对碰撞检测的这一方法进行介绍。

2.1 关键点选取

将植物植株的高度设为H，在垂直方向上以步长为L对植株进行区域划分，进行横向切割，该植株将被分割成H/L+1个水平切面，对于植物就会在每个切面上形成植株的生物点，而这些生物点拼接起来就可以重现植株。在进行碰撞检测时，将同水平切面上的生物点进行对比分析，即可判断是否碰撞。这里碰撞检测的精度取决于步长L的设定，但是对于给定时刻的生长模型，各生物点的数据相当于静态的离散点，与传统检测方法比较精度和速度都有很大的提高。在本节中，把植物生物点成为检测的关键点。

2.2 关键点存储

对于已经经过水平分割处理的植株，仅需比较同层关键点是否重叠即可，使植物碰撞的三维检测降低为二维检测。将每层的关键点按照一定规律扫描存储在计算机中进行管理，本节采用邻接表的形式对关键点进行存储，为了便于分析，现将其数据结构定义见图2。

图2 植株在计算机内的存储结构Fig.2 Storage structure of plant simulation in computer

该存储结构算法：

其中，点(x，z)表示生长最低点，(xn，zn)表示生长最高点，步长为L，i表示第i个水平切面，n表示同一切面上的第n个关键点。

3 方法检验

将植株的关键点以这种邻接表的形式进行存储，然后采用深度优先遍历法进行查找，即在同一水平面上的生物点进行比较查找，即具有相同y轴坐标的关键点进行比较查找，这样将降低检测数量。然后将对x轴坐标进行比较，如果具有相同的x坐标值，将进一步比较，否则放弃。

通过这种方式比较将急剧减少关键点的比较数量，提高了碰撞检测速度。具体的检测算法如下：

该方法中设植物高度为H，垂直方向分割步长为L，则植物分层从0至H/L层。则碰撞检测需检测H/L+1各平面，即H/L+1次。对于每一个平面内关键点数假设为vetexCount。根据上述算法需要进行碰撞检测次数为：（H/L+1）*vetexCount。当L取值接近1/N时，vetexCount取值接近N时，该算法拥有的最坏时间复杂度为O（N2）；当L与vetexCount取值都接近常数时，该算法的最好时间复杂度为O（1）；其余取值时间复杂度为O（N）。

目前的碰撞检测方法中，多为虚拟现实中场景的检测，很少有特为植物碰撞检测进行的算法设计。本节在虚拟植物模型建立的基础上，提出了关键点存取思想进行检测，在一般的碰撞检测要求下，其算法优势明显。

根据上述方法，可以快速有效地进行碰撞检测，在此之后，碰撞处理按照后生成器官让位于先生成器官的原则，即某器官在生成过程中，经过检测发现与已生成的器官有坐标重叠现象，则对该器官进行适当的位置修改，再进行检测，直到没有发生碰撞现象为止，才进行该器官显示（见图3）。

图3 模拟效果Fig.3 Simulation effect

4 结论

本文利用了关键点存取思想的检测方法是在给定生长模型基础上，针对植株生长提出的。将植株进行切片分层，碰撞检测简化成各离散关键点的检测，然后分别对坐标分量进行比较分析，进行碰撞监测，能够降低检测方法的复杂度并提高检测精度。

[1] 苏中滨,战守义,郑萍,等.作物高光效株型数字化设计方法研究[J].农业工程学报,2008,24(1)：203-207.

[2] 苏中滨，郑萍,孙红敏,等.大豆形态生长系统的组件化设计方法[J].微型电脑应用,2008,24(2)：53-55.

[3] 苏中滨,张继成,郑萍.作物高光效株型数字化设计的方法研究[J].计算机科学与应用,2008,25(5)：269-270.

[4] 章德宾,胡斌,张金隆.多线程技术与分布式并发离散事件仿真[J].计算机仿真,2007(1):97-100.

[5] 熊邦毛,熊叶明,张再萍.用多线程技术解决单线程冲突问题[J].计算机与数字工程,2007(1):115-119.

[6] 张乐平,孔玉,雷长海,等.基于多线程技术的实时检测[J].医疗卫生装备,2005(6):1-2.

[7] 翟巍,迟忠先,方芳.大规模三维场景可视化的数据组织方法研究[J].计算机工程,2003,29(20):26-27.

[8] 唐珉,胡占义.参数空间分解法[J].计算机学报,2001,9(22):911-917.

[9] 黄娟,顾寄南.装配仿真中碰撞干涉检查研究的综述[J].科学通报,2002,2(23):17-21.

[10] 陈尚飞.基于分离轴理论的有向包围盒重叠测试算法 [J].广西科学院学报,2005,3(21):196-198.

[11] 牛立新,刘旭敏,王功明.基于空间八叉剖分的面聚类网格简化算法[J].计算机工程，2007,20(33):228-238.

[12] 周之平,张少博,吴介一,等.基于非线性规划理论的凸多面体最小平移距离算法[J].中国图象图形学报,2006,10(11):1487-1492.

[13] 孙红敏,郑萍,张继成.大豆叶片生长特征的动态模拟研究[J].东北农业大学学报,2007,38(4):446-448.

[14] 李晓明,赵春江,郑萍.基于Agent的植物生长系统结构[J].东北农业大学学报,2010,41(8)：127-130.

[15] 孙红敏,李晓明.大豆叶片形态模拟模型建立方法的研究[J].农机化研究,2007(11)：48-50.