一种优化森林仿真的碰撞检测及响应算法研究

王林龙,张怀清,杨廷栋,张 京,雷可欣,陈传松,张华聪,刘 洋,崔泽宇,左袁青

(1.中国林业科学研究院资源信息研究所,北京 100091;2.中国林业科学研究院林业科技信息研究所,北京 100091;3. 国家林业和草原局林业遥感与信息技术重点实验室,北京 100091;4. 中国林业科学研究院亚热带林业实验中心,江西 分宜 336600)

基于真实样地、小班或林班等不同尺度虚拟森林三维仿真,易发生物体之间相互交叉的现象,导致渲染画面的真实感大幅降低,无法满足用户对虚拟森林场景真实性、沉浸性体验的需求[1-2]。碰撞检测是判断空间上相互独立的物体之间或物体与环境之间是否发生共享同一位置空间的技术,是决定虚拟森林三维仿真质量高低的关键技术之一[3-5]。近年来,随着虚拟森林模型向大规模化、复杂化方向发展,关于树木之间的碰撞检测及其响应算法成为当前虚拟森林场景真实构建亟须开展的研究。

国内外植物碰撞检测研究常采用层次包围盒法,包括单一包围盒层次法(single axis-aligned bounding box, AABB)[6]、混合包围盒层次法(mixed bounding volume hieravehy tree, MBVT)[7]。其中,单一包围盒层次法解决了群体中植株的实时碰撞问题,但存在检测精度不高的问题,例如AABB包围盒+关键点存储技术[8]、空间散列法[9]。相对而言,混合包围盒层次法AABB用简单更新的包围盒来快速排除不发生碰撞的物体,减少了冗余的测试,能有效提高检测效率,但精测精度受包围盒紧密性影响而未发生显著提升,如AABB-OBB(oriented bounding box, 定向包围盒)包围盒[10]和AABB-FDH(fixed direction hulls,固定方向凸包)包围盒[11]。围绕包围盒紧密性问题开展一系列优化算法研究,包括层次包围盒可形变系统[12]、仿生模式的虚拟植物模型及碰撞检测方法[13]、BVHs (bounding volume hierarchies, 层次包围盒法)与分离轴定理相结合的碰撞方法[14],提高了植物碰撞检测的鲁棒性和有效性,增强了可视化的真实感。虽然已有研究通过简化碰撞检测的某一过程提升植物碰撞检测效率,但仍面临以下2个方面问题:①在大规模森林碰撞检测过程中,现有的混合包围盒层次树法MBVT仍面临碰撞检测对象冗余问题,仍需进一步优化;②现有的碰撞响应模式过于单一,并未考虑与环境因子的交互,欠缺一定的真实感。本研究选择南方典型林分——杉木(Cunninghamialanceolata)人工纯林为研究对象,基于Unity3D引擎与C# 程序开发语言, 比较单一包围盒树(AABB)、混合包围盒树(MBVT)算法及引入最近4株树搜索法的MBVT优化算法的碰撞检测效率,分析不同规模大小(20、50、100、200、400、600、800、1 000)及林分株行间距(1 m×1 m、2 m×2 m、3 m×3 m、4 m×4 m)双因子对碰撞检测效率的影响机制,最后模拟验证考虑光照因子碰撞响应策略的可行性,以期提升虚拟森林场景快速碰撞检测与真实响应。

1 材料与方法

1.1 研究区概况

研究区位于中国林业科学研究院亚热带林业实验中心山下林场(114°45′E,27°54′N),土地总面积为17.90 km2,低山丘陵地貌,海拔为80.0～507.4 m,年平均气温17.5 ℃,降水量1 593.7 mm,主要代表性树种包括杉木、木荷(Schimasuperba)、马尾松松类(Pinusmassoniana)、油茶(Camelliaoleifera)、刨花楠(Machiluspauhoi)等,森林覆盖率为95.6%。通过现地走访调查,选择具有区域代表性的人工杉木纯林作为研究对象,样地大小设置为0.1 hm2,样地内林木以杉木为主,平均树高为17.62 m,平均胸径为20.98 cm,树龄约为28 a。

1.2 研究方法

开展森林生长动态三维可视化模拟过程中,相邻树木之间出现交叉生长现象,不利于相邻树木树冠生长动态的真实模拟,从而影响虚拟森林场景三维模拟的真实性及生长预测结果的科学性。以杉木为例(图1a),从正视图与俯视图角度,描述了相邻树木之间交叉生长问题。同时,本研究采用Unity3D的Gizmos-Selection Outline组件绘制的黄色实线来显示杉木整体的轮廓信息,一旦杉木发生交叉生长现象,则表现出杉木轮廓黄色实线呈加粗状态以便于识别。

1.2.1 杉木纯林虚拟场景碰撞检测优化算法

结合混合包围盒层次树法MBVT + GJK(Gilbert-Johnson-Keerthi)迭代式算法,在粗检测阶段采用易构造且容易碰撞计算的AABB与OBB混合包围盒层次树,快速过滤不相交对象,减少参与碰撞检测的对象数量;在精检测阶段,采用GJK迭代式算法,通过求解对象间的Minkowski差与原点之间的距离来判断2个物体是否发生碰撞,同时可获取具体碰撞位置信息,用于设计后续的树木碰撞响应算法。为进一步提高AABB与OBB混合包围盒层次法的碰撞检测效率,本研究引入与森林空间结构单元相关的相邻最近4株树搜索法[15],按东南西北方向划分4个象限,搜索出4个象限中距离中心木最近的林木,用于进行不同林木之间的碰撞检测。

1)杉木单株的包围盒构建。采用混合包围盒层次树法MBVT构建杉木包围盒,根据杉木的枝干形态结构,将其单木模型划分为3个层级,即单木层级、多级枝系层级、树叶层级(图1b)。

①单木层级采用轴对齐包围盒AABB构建,其几何形式表示为:

RAABB=(x,y,z),|cx-x|≤rx,|cy-y|≤ry,|cz-z|≤rz。

(1)

②多级枝系层级和树叶层级采用OBB方向包围盒构建,其几何形式表示为:

ROBB={O+ar1v1+ar2v2+ar3v3|a,b,c∈(-1,1)}。

(2)

式中:ROBB表示包围盒OBB的区域范围;O表示OBB的中心;r1、r2、r3分别表示方向坐标轴上的半径,v1、v2、v3分别用于计算OBB的方向;是与坐标轴方向相互正交的向量,寻找并计算最佳方向需要均值U和协方差C。假设模型的第i个(i>0)三角面片的顶点坐标分别为Mi(Mi,X,Mi,Y,Mi,Z)、Ni(Ni,X,Ni,Y,Ni,Z)、Ki(Ki,X,Ki,Y,Ki,Z),n表示三角形的数量,则模型所有三角面片组成的集合满足:

(3)

C3×3=(amn),m,n∈{X,Y,Z};

(4)

(5)

式中:amn表示协方差矩阵C中m、n处的元素,能计算出C的3个特征向量p1、p2、p3, 3个特征向量互相正交且两两垂直。将p1、p2、p3单位化,取e1、e2、e3为OBB的基底,用dX,min、dX,max、dY,min、dY,max、dZ,min、dZ,max表示为三角面片顶点在基底e1、e2、e33个方向上投影的极大值与极小值。aXY表示矩阵C中X、Y处的元素。UY表示Y处的平均值。

2)基于虚拟场景的杉木林碰撞检测算法。引入与森林空间结构单元相关的最近4株树搜索法[15](图1c),只考虑目标林木与周围最近的4株树相交测试,与Ding 等[16]采用的存储杉木模型数组中相邻8个模型进行交叉测试不同。

①单木层级AABB包围盒碰撞检测模型:

|C1x-C2x|≤R1x+R2x;

(6)

|C1y-C2y|≤R1y+R2y;

(7)

|C1z-C2z|≤R1z+R2z。

(8)

式中:C1与R1,C2与R2分别表示邻近木1与邻近木2包围盒AABB的中心和半径大小;x、y、z表示点的坐标位置。

②多级枝系层与树叶层OBB包围盒碰撞检测模型:

(9)

D

(10)

D>Oi,max+Oj,max;

(11)

Oi,min+Oj,min

(12)

式中:D表示Oi到Oj的距离;Oi(xi,yi,zi)、Oj(xj,yj,zj)分别表示2个OBB包围盒Bi和Bj的中心;Oi,min、Oi,max和Oj,min、Oj,max分别表示包围盒Oi、Oj到其中心的最大距离和最小距离,SAT表示分离轴测试。

③潜在碰撞树叶采用GJK迭代式算法碰撞检测模型:

d(A,B)=min{‖x-y‖,x∈A,y∈B};

(13)

‖a-b‖=d(A,B),a∈A且b∈B,v(C)∈Cand‖v(C)‖=min{‖x‖,x∈C};

(14)

d(A,B)=v(A-B),A∩B≠Ø↔0∈A-B;

(15)

d(A,B)=min{‖x‖,x∈A-B};

(16)

p(A,B)=inf{‖x‖,x∉A-B}。

(17)

式中:d(A,B)表示凸体A和B之间的距离;‖a-b‖表示离碰撞点最近的2个点a、b;v(C)表示离原点最近的点C;v(A-B)表示A、B之间距离的Minkowski表示形式;p(A,B)表示A、B之间的交叉深度。inf 表示下确界。

1.2.2 树木模型之间碰撞响应算法

树木生长过程中为争夺生长所需的空间与光照、水分等资源,相邻的树木之间存在较为强烈种间或种内竞争。因此,为便于虚拟森林场景的真实模拟,根据现地杉木纯林生长的状况,将杉木之间的碰撞响应分为3大类,例如:受植物趋光特性影响,相邻树木的树枝均同向上、同向下、同向左、同向右生长,相邻树木的树枝呈一上一下,一左一右方向生长,相邻树木的树枝呈一上一左、一上一右、一下一左、一下一右方向生长,具体效果见图1d。

为进一步真实模拟树木趋光生长特性,本研究基于Unity3D开发平台,引入兰伯特光照模型(Lambert model)来计算碰撞点周围空间位置的光照强度[17],即实际光照强度I=(Ia+Id+Is)×Fatt来确定,其中Ia、Id、Is分别表示环境光ambient、漫反射光diffuse、镜面高光specular的光照强度,Fatt表示衰减因子。衰减因子一般与离光源的距离有关,表现为受距离的增大而衰减。例如,已知某时刻太阳光照强度为I0,已知某一点P,离光源的距离为d,即某一点P的光照强度为:

(18)

式中:IP表示点P的光照强度;Kc、Kl、Kq分别表示距离衰减常量、线性衰减常量、二次衰减常量,其大小通常设置为1.000、0.090、0.032。

通过获取碰撞点的位置信息之后,采用兰伯特光照模型来计算碰撞点周边4个位置的光照强度。例如,假设已知碰撞点为P(x,y,z),冠幅年均生长量r(单位:m),计算点P前rm的圆,确定碰撞对象及其4个潜在偏移点位置为Pr=(x±r,y,z),Pup= (x±r,y+r,z),Pdown= (x±r,y-r,z),Pleft= (x±r,y,z-r),Pright= (x±r,y,z+r),并通过Lambert model计算4个点的光照强度(图1e),比较4个潜在偏移点的光照大小获取两个发生碰撞枝条的光照强度最大值B1和B2,然后根据建立的相邻树木碰撞响应函数f(B1,B2),模拟树木碰撞后可能发生的生长情景。

与Xiao 等[13]提出的利用旋转矩阵反映碰撞后可能发生的3种情况相比,本研究提出的相邻树木碰撞响应函数f(B1,B2),充分考虑树木趋光性生长的生物学特性,引入光照强度I,来模拟虚拟森林生长场景碰撞响应过程。

(19)

式中:S1—S10表示树枝之间碰撞可能发生的响应情景(图1d);P与P′表示2个树枝碰撞点;Max1与Max2表示获取2个碰撞对象的4个潜在偏移位置光照强度IP最大值的位置信息。

1.2.3 杉木林虚拟场景真实构建

通过样地外业调查,获取研究区林木的树高、胸径、冠幅、枝下高等指标参数,结合中国林业科学研究院资源信息研究所三维树木建模系统CTS,完成试验区的树木建模工作[18-23]。通过无人机激光雷达数据采集及专业点云处理软件,获取真实场景的DEM,以用于后续研究区森林场景的地形制作[24-26]。以Visual Studio2019作为开发工具,基于Unity3D仿真引擎,结合已生成的树木模型,完成研究区杉木纯林虚拟场景的构建,以用于相邻树木之间的碰撞检测研究(图1f)。场景开发环境为Win10操作系统,CPU Intel(R) Core(TM) I7-10700K / 3.80GHz,内存16GB,硬盘4T,显卡 NVIDIA GeForce RTX 3070。

2 结果与分析

2.1 不同碰撞检测算法结果比较

基于研究区的杉木纯林虚拟场景,对单一包围盒树(AABB)、混合包围盒树(MBVT)算法及引入最近4株树搜索法的MBVT优化算法的碰撞检测效率进行比较分析,结果见表1。表1表明:相对单一包围盒树(AABB),MBVT算法与引入最近4株树搜索法的MBVT优化碰撞算法能减少了层次包围盒(BVHs)的构建时间t3与更新时间t4,而BVHs的交叉测试时间t2高于单一包围盒树(AABB);MBVT优化碰算法与混合包围盒树MBVT算法相比,通过引入最近4株树搜索法,能减少BVHs交叉测试时间消耗t2与BVHs构建消耗时间t3,而更新时间t4无明显差异。

表1 不同碰撞检测方法的比较分析

为进一步了解MBVT优化碰撞算法的相交测试算法性能,通过设置不同种群规模大小及林分株行间距,来分析碰撞检测效率的响应情况。t1、t2、t3和t4的取值大小主要通过Unity3D运行仿真场景过程中调用函数的时间来计算平均值获取,而t1、t2、t3和t4的取值越小,说明该算法的碰撞检测总消耗、交叉测试、构建、更新消耗时间越短,算法时间效率越高。研究结果表明,种群规模大小与BVHs碰撞检测总消耗时间t1、BVHs交叉测试时间t2及构建时间t3均表现为正相关性。具体表现为,随种群规模的增大,碰撞检测总消耗的时间t1、BVHs交叉测试时间t2及BVHs构建时间t3也呈现增加趋势(图2);同时,随种群规模增加,不同株行距的碰撞相交测试消耗时间t2与包围盒构建时间t3占比趋于平稳(图3)。

图2 不同种群规模与不同株行距下碰撞检测的时间消耗Fig. 2 Time-consumption of collision detection under different population size and plant density

图3 不同种群规模与不同株行距下BVH构建和交叉测试的时间消耗占比Fig. 3 Time-consumption percent age under different population sizes and plant density of BVH construction and intersection testing

株行距大小与碰撞检测总耗时间t1、相交测试时间t2呈负相关性,与BVHs构建时间t3无明显关联性,具体表现为:随林分株行间距的减小,碰撞检测总耗时间t1与相交测试时间t2呈增加趋势,BVHs构建时间t3几乎没有变化。例如,1 m×1 m 的t1与t2最大,2 m×2 m株行距的t1与t2次之,3 m×3 m与4 m×4 m株行距的t1与t2最小(图2)。从图2、图3中可见,随着种群规模增大与林分株行间距减小,碰撞检测总耗时间t1与相交测试时间t2呈增加趋势,然而其相应的占比并未有显著提升。

2.2 相邻杉木之间碰撞响应

选择r= 0.05 m,tree1坐标(0, 0, 0),tree2坐标 (3.93, 0, 0) 的2株发生碰撞的相邻树木对提出的碰撞响应策略进行验证,结果见图4。

红色框内为相邻树木碰撞部分。the red box is the collision part of adjacent trees.图4 相邻木碰撞前后响应变化Fig.4 Changes in the response of adjacent trees before and after collision

基于Unity3D中从运行数据可知,碰撞点坐标为(2.09, 8.55, -0.15),tree1的4个潜在偏移点位置为Pup= (2.59, 9.05, -0.15),Pdown= (2.59, 8.05, -0.15),Pleft= (2.59, 8.55, 0.35),Pright= (2.59, 8.55, -0.65),tree2的4个潜在偏移点位置为Pup= (1.59, 9.05, -0.15),Pdown= (1.59, 8.05, -0.15),Pleft= (1.59, 8.55, -0.65),Pright= (1.59, 8.55, 0.35);光源设置为平行光源(directional light),光照强度设为I0,坐标为(-52.34, -1.23, -54.36),tree1的潜在偏移点光照强度Pup、Pdown、Pleft、Pright分别为I0的 0.004 951、0.004 967、0.004 916、0.005 003倍,tree2的潜在偏移点光照强度Pup、Pdown、Pleft、Pright分别为I0的0.005 039、0.005 056、0.005 093、0.005 003倍;相邻树木发生碰撞后,tree1发生碰撞的树枝向Pright偏移,tree2发生碰撞的树枝向Pleft偏移,响应场景中FPS达到8.6 帧/s,准确度为100%,能实现相邻树木之间的精准碰撞检测与真实响应。

3 讨 论

为优化基于混合包围盒层次树MBVT算法的碰撞对象数量,本研究在混合包围盒层次树MBVT方法中,引入考虑森林空间结构单元的最近4株树搜索法[15],通过遍历杉木模型数组,得到象限Ⅰ—Ⅳ中距离对象木最近的4株林木,进行碰撞相交测试,代替MBVT方法中采用数组中相邻8个植物模型进行碰撞测试,减少了一半的碰撞对象数量,从而提高杉木林虚拟场景的碰撞检测效率。研究结果表明,相对混合包围盒树MBVT算法,本研究基于最近4株树搜索法的混合包围盒层次树MBVT优化算法,缩短了13.75 ms,约为原MBVT算法耗时的29%,能减少BVHs交叉测试时间消耗t2约7.37 ms,为原交叉测试时间的16%与BVHs构建消耗时间t3约5.62 ms,为原构建消耗时间的12%,而更新时间t4约缩短0.76 ms,为原更新时间的2%。这表明混合包围盒层次树MBVT优化算法通过引入最近4株树搜索法,将目标树最近4株树当作一个空间结构单元,以减小碰撞检测对象数量,主要减少BVHs交叉测试和构建消耗时间,从而有效提高杉木林虚拟场景的碰撞检测效率。此外,本研究加入单一包围盒层次树AABB方法,以比较单一包围盒与混合包围盒层次树法的碰撞检测效率,结果表明:相对单一包围盒层次树AABB,MBVT算法与基于最近4株树搜索法MBVT优化算法,分别缩短了124.93、138.68 ms,约为单一包围盒层次树法AABB总耗时的73%、81%,这表明相对单一包围盒层次树法,混合包围盒层次树法具有更高的碰撞检测速率,这与大多数研究结果相一致[10,14,16],其原因是相对单一包围盒层次树AABB,混合包围盒MBVT的紧密性更高一些。

以往的研究仅考虑规模大小单因素对碰撞检测效率的影响[14,27],本研究结合林业实际情况,引入林分株行距因子,分析种群规模大小与林分株行距大小双因子对碰撞检测效率的影响。研究结果表明,随种群规模增大,株行距减小,总碰撞时间消耗t1、BVHs交叉测试时间t2呈增加趋势,而BVHs构建时间t3几乎没有变化;种群规模大小与BVHs碰撞检测总消耗时间t1、BVHs交叉测试时间t2及构建时间t3均表现为正相关性。这可能是随种群规模增大,株行距减小,相邻树木之间的碰撞次数增多,从而引起包围盒BVHs交叉测试时间t2增加。然而,由于株行距缩小使碰撞次数增加,从而引起包围盒BVHs生成的时间也随之增加,从而碰撞交叉测试与包围盒生成时间占比并未有大幅提升,整体上趋于平稳。关于模型数量为100、200和400时,BVHs交叉测试时间t2与种群规模、株行距大小并未呈现规律性变化,这可能是基于Unity3D获取仿真场景交叉测试函数平均消耗时间的过程,存在一定的系统性误差与人为主观判断影响所导致的。从实验数据上看,当种群规模大小为100～200,株行距为1 m×1 m、2 m×2 m、3 m×3 m、4 m×4 m,三角面片数为1.566×105～3.145×105帧/s时,杉木林虚拟场景的渲染帧率均小于24 帧/s,无法进行实时碰撞检测。

目前关于碰撞响应的研究相对较少,且大多数集中在碰撞自剔除、或利用旋转矩阵模拟,并未考虑与环境因子交互[11,13,16]。光照作为影响树木生长的关键因子,对树冠生长动态三维可视化真实模拟具有重要的参考价值。本研究基于Unity3D平台,结合兰伯特光照模型 (Lambert model),来计算相邻树木之间碰撞点周围4个位置的光照强度,从而根据树木向光性生长的特性进行仿真,即采用f(B1,B2)函数来确定发生碰撞的树枝潜在响应状态,最终通过偏移与自旋转发生碰撞树枝的位置,直至两者之间未发生碰撞即可。相对传统的碰撞响应模式,本研究基于光照因子的碰撞响应算法,考虑了植物的趋光性生长特征,模拟的杉木林虚拟场景更为真实。

通过引入与森林空间结构单元相关的最近4株树搜索法,优化混合包围盒层次树法MBVT的碰撞检测对象数量,减少了BVHs交叉测试和构建消耗时间,从而有效提高杉木林虚拟场景的碰撞检测效率。充分考虑树木的趋光生长特性,利用GJK迭代式算法获取碰撞位置的准确信息,通过兰伯特光照模型与相邻树木碰撞响应函数f(B1,B2),完成树木碰撞后可能发生的情景模拟,提高了杉木林虚拟场景的真实感。