基于混合层次包围盒的快速碰撞检测算法

林 菲,邹 玲,张 聪

(杭州电子科技大学计算机学院,浙江 杭州 310000)

1 引言

在虚拟现实环境中,碰撞检测用来确定虚拟场景中的物体间是否发生接触或穿透,增强人与虚拟环境之间的视觉与力觉交互体验,从而提高虚拟环境的真实感和沉浸感[1]。因此,碰撞检测是直接影响用户体验的关键指标,也是虚拟现实领域研究的关键问题之一。随着虚拟环境中模型规模和复杂度的升高,对碰撞检测算法提出了更高的要求[2,3]。当前针对碰撞检测的国内外研究主要包括基于图像的碰撞检测算法和基于图形的碰撞检测算法,前者需要借助图形硬件设备,后者从策略角度和算法角度提高碰撞检测适应性。在基于图形的碰撞检测算法中,层次包围盒算法具有存储量小、灵活性高的优点,从而被广泛应用[4]。

本文主要研究基于层次包围盒的碰撞检测算法。该类算法的主要思想是通过体积稍大且特性简单的几何体(称为包围盒)来近似地代替复杂的几何物体,进而构造层次包围盒树来提升碰撞检测算法的速度。常见的包围盒类型有轴对齐包围盒(Axis-aligned Bounding Box)[5]、包围球(Sphere)[6]、方向包围盒(Orient Bounding Box)[7]以及离散方向多面体(K-Dop)[8]等。表1为这四种常见包围盒的性能比较,从中可以看出,紧密程度和相交测试难度作为包围盒技术两个重要指标,二者始终相互制约。为了提高包围盒紧密性,研究者们提出使用三角面片面积加权的方法提高OBB包围盒紧密性[9],但其在一定程度上延长了包围盒构造时间。另一方面,为了减少相交检测难度和次数,研究者们提出了各种基于混合层次包围盒的碰撞检测算法来提升碰撞检测的效率,如OBB-Sphere[10]以及AABB-OBB[11]。尽管这些算法都进行了一定程度上的改进和提高,但是以牺牲其它方面的性能为代价,缺乏对碰撞检测整体性能的均衡考量。

表1 常见四种包围盒的性能比较

为了进一步提高碰撞检测算法整体效率,本文提出了一种基于Sphere-AABB-OBB混合层次包围盒的快速碰撞检测算法。该算法在构造OBB包围盒时,首先通过预处理顶点提取凸体后,再利用基于三角面积加权的方法计算OBB包围盒,来解决包围盒方向倾斜问题,从而提高包围盒紧密性并减少包围盒构造时间;同时,本文综合考虑了Shpere、AABB包围盒相交检测的简单性和OBB包围盒紧密性的特点,建立了一种新的混合层次包围盒结构——Sphere-AABB-OBB混合包围盒层次树,以减少相交检测的次数和时间。

2 混合包围盒构造方法

混合包围盒算法通常是在外层使用构造简单的包围盒,而在内层使用紧密性良好的包围盒,以加速排除不相交的物体。本文提出了一种新的Sphere-AABB-OBB混合层次包围盒结构,自顶向下构建层次树,树的每个节点均包含3种包围盒,从内到外依次构造OBB包围盒、AABB包围盒以及Sphere包围盒。

2.1 OBB包围盒优化

OBB包围盒是指在坐标轴的任意方向上包围物体模型的最小长方体,其结构紧凑、检测精度高于Sphere和AABB包围盒。OBB包围盒一般用一个中心点、一个旋转矩阵以及 3 个方向上的半径来表示,其常用的计算方法是一种基于主成分分析法(PCA)计算最小 OBB 的方法,这种方法主要通过计算模型所有三角形顶点的均值和协方差矩阵 C 来确定OBB 的中心点和方向,然后根据模型中所有三角形顶点在 3 条轴上的极值即可得到 OBB 的 3 条半径。

本文考虑到只有物体模型凸包上的顶点才会影响其OBB包围盒,可以忽略冗余顶点,因此提出使用Quickhull算法[12]提取物体凸包来近似代替物体模型,以减少参与OBB包围盒构造的顶点数量,从而降低OBB包围盒构造的时间。为了避免OBB包围盒向顶点密集方向倾斜,本文采用了一种基于三角面积加权的OBB包围盒中心点计算方法,将凸体的质心作为OBB包围盒中心点。

假设物体模型为S,物体模型的凸体,模型凸体中有n个三角形(qk,pk,rk),其中1≤k≤n,则协方差矩阵为

-mH,imH,j

(1)

(2)

(3)

2.2 AABB包围盒计算

AABB包围盒存在多种常见数据结构,其中中心点-边长这种数据结构更节省存储空间。在本文算法中,OBB包围盒和AABB包围盒的中心点是重合的,采用这种结构类型,只需根据已求出的OBB包围盒计算外层AABB包围盒在x、y、z轴上的边长。

假设OBB包围盒的中心点为mH,其三个基准方向分别为d1、d2、d3,其基准方向的半径分别为r1、r2、r3,可得OBB包围盒的定义区域:

R={mH+ad1r1+bd2r2+ad3r3|a,b,c∈(-1,1)}

(4)

之后,分别计算R中在x、y、z轴上的最大最小值,将最大最小值相减即可得到AABB包围盒在x、y、z轴上的边长。

2.3 Sphere包围盒计算

由于OBB是采用中心点-边长的数据结构,因此要计算它们外层的Sphere包围盒,以OBB包围盒中心作为球心,以OBB包围盒顶点中最远顶点与球心的距离为Sphere包围盒的半径。

3 混合包围盒相交检测方法

OBB包围盒之间的相交检测较为复杂,而Sphere包围盒和AABB包围盒的相交检测更为简单。在本文算法中,首先对物体混合包围盒外层的Sphere包围盒进行相交检测,若Sphere包围盒之间相交,则继续对AABB包围盒之间进行相交检测,若AABB包围盒相交,则继续对OBB包围盒之间进行相交检测。

3.1 Sphere包围盒相交检测

假设两个Sphere包围盒的球心和半径分别为:So、R1和:To、R2,如果圆心距的长度大于两个Sphere包围盒半径的之和,则表示两个Sphere包围盒不相交,否则两个Sphere包围盒相交,如图1所示,不等式如下:

图1 Sphere-Sphere相交检测

|SoTo|>R1+R2

(5)

3.2 AABB包围盒相交检测

AABB包围盒之间的相交检测,可通过将两个包围盒中心距离在方向轴上的投影分别与两个包围盒在该方向上的半径之和进行比较,如图2所示。

图2 AABB-AABB相交检测

其中,Uo和Vo是AABB包围盒U和AABB包围盒V的中心点,α是两个包围盒中心点与垂直方向之间的夹角,lu和lv分别为包围盒U和V水平方向上的半径,wu和wv分别为包围盒U和V垂直方向上的半径。当同时满足不等式(6)和不等式(7)时,可以确定两个AABB包围盒不相交,否则相交,如下所示

|UoVo|sinα≥(lu+lv)

(6)

|UoVo|cosα≥(wu+wv)

(7)

3.3 OBB包围盒相交检测

OBB相交检测方法一般基于分离轴定理(Separating Axis Theorem)。OBB包围盒之间的相交检测需要测试最多15个分离轴才能确定OBB的相交状态。这15个分离轴包括分别对应两个物体的3个坐标轴以及垂直于每一轴的9个轴。如果包围盒之间在这15个分离轴上都不相交,则这两个OBB包围盒不相交;否则,只要其中任意一个分离轴产生相交,即可判断包围盒相交。

在利用分离轴检测OBB包围盒之间的是否相交之前,可先通过简单计算来排除不相交情况,OBB包围盒S和OBB包围盒T及其外层Sphere包围盒之间的位置关系如图3所示。

图3 OBB-OBB相交检测

其中ls和ws是包围盒S的方向上的半径,lt和wt是包围盒T的方向上的半径。如果圆心距的长度大于两个OBB包围盒半对角线之和,则两个包围盒不相交,可用以下不等式来判断

(8)

假设物体1的混合包围盒为Sphere1、AABB1、OBB1,物体2的混合包围盒为Sphere2、AABB2、OBB2,其相交检测算法如下

算法1:混合包围盒相交检测方法

Input:物体1、物体2的混合包围盒

1) If(Sphere1和Sphere2不等式5)thenreport物体1、物体2无相交

2) else

3) If(AABB1和AABB2满足不等式(6)、不等式(7)thenreport物体1、物体2无相交

4) else

5) If(!AABB1.intersect(AABB2))thenreport物体1、物体2无相交

6) else

7) If(OBB1和OBB2满足不等式8)thenreport物体1、物体2无相交

8) else

9) If(!OBB1.intersect(OBB2))thenreport物体1、物体2无相交

10) else report 物体1、物体2OBB包围盒相交

4 实验结果及分析

为了验证本文算法的有效性,实验平台系统采用 Windows10,内存 16GB,CPU 为 Intel(R) Xeon(R) W-2133 3.6GHz,实验环境基于WebGL和 Microsoft Visual Studio Code。

为了验证OBB包围盒优化效果,本文选择了基于主成分分析的传统OBB包围盒构造算法作为基准算法,在不同物体模型上进行了包围盒构造的对照实验,结果见表2。从表中可以看出,本文提出的OBB包围盒优化算法在保持包围盒紧密性的同时(包围盒体积增长率少于6%),大幅度减少了OBB包围盒构造时间,尤其是在模型面片数量多的情况下。这是因为该优化算法只提取物体凸体顶点集来参与OBB包围盒构造的计算,顶点数量的减少使得构造时间显著缩短。

表2 包围盒构造时间和体积对比

为了更好地体现本文提出的混合包围盒结构在相交检测上的改进效果,在固定虚拟场景空间大小的情况下,将提出的Sphere-AABB-OBB(SAO)与OBB-Sphere算法(OS)、AABB-OBB算法(AO)在不同物体数量的虚拟场景中进行相交检测实验。实验结果如表3所示。由实验结果可知,在平均相交检测时间上,本文算法始终优于其它两个对比算法。其关键在于,本文算法利用外层Sphere、AABB包围盒排除一定不相交的包围盒,从而能显著减少物体相交检测时间。

表3 相交检测时间对比

5 结论

为了提高虚拟场景中碰撞检测的效率,本文提出了一种基于混合包围盒的快速碰撞检测算法。本文算法对OBB包围盒构造进行优化处理,同时在OBB包围盒外层构造Sphere包围盒以及AABB包围盒,以更快地排除不相交物体,并对OBB包围盒相交检测进行改善,这使得相交检测过程得到了进一步优化。最后,通过对比实验,证明了相对于其它基准混合包围盒的碰撞检测算法,本文算法在包围盒构造方面和包围盒相交检测方面都进行了有效优化,碰撞检测的效率得到了显著提高。