基于两层体素模型的碰撞检测算法

陈骞

摘要：碰撞检测是布尔运算中的关键步骤。针对现有的大尺度三角网格模型的布尔运算时间效率不足的问题，提出一种基于两层体素模型的碰撞检测算法，以求提高两个静置模型在布尔运算场景中碰撞检测的速度。在算法中，首先利用AABB包围盒算法确定模型的相交区域，然后在相交区域内构建起两级体素模型，检测出发生碰撞的体素后，将体素中所对应的三角面两两进行求交测试，最终以两个三角网格模型的交线集合作为碰撞检测算法的结果。经过多组表面复杂的模型测试，比VTK中的算法时间效率平均提高了90%。

关键词： 碰撞检测; 体素模型; 体素化; 布尔运算; AABB包围盒

中图分类号：TP391         文献标识码：A

文章编号：1009-3044（2020）17-0010-04

Abstract： Collision detection is a key step in the process of Boolean operations. To solve the problem of insufficient Boolean operation time efficiency of large-scale triangular mesh model， a collision detection algorithm based on a two-layer voxel model is proposed to improve the efficiency of Boolean operation. The algorithm has three stages， first use the axis-aligned bounding box determine the area of the voxel model， and then construct a two-level voxel model within the intersection area. After detecting the colliding voxel， the corresponding triangles in the voxel are carried out in pairs. For the intersection test， the intersection set of two triangular mesh models is finally used as the result of the collision detection algorithm. After multiple sets of complex triangular mesh tests， the time of this algorithm is increased by 80% on average compared to VTK.

Key words： collision detection; voxel model; voxelization; boolean operation; AABB box

1 引言

三角網格模型的布尔运算是计算机图形学领域的一个经典问题。布尔运算在3D打印、动画仿真、虚拟现实、地理信息系统等领域中有着重要的应用[1-3]。通过布尔运算可以对现有的三维几何模型进行交并差等操作得到新的模型。本文以3D打印领域中通用的文件格式STL模型作为算法的输入结果。STL模型是一种用三角网格表达模型边界信息的文件格式。该文件格式以三角面的三个顶点的空间位置和三角面的单位法向量为元素，所有元素的集合即是一个完整的三角网格模型。

现有的常见碰撞检测算法主要分为两种类型，层次包围盒树法和空间剖分法[4]。层次包围盒树法是通过使用一个形状简单的包围盒代替模型中被包围住的局部信息，如果发现两个包围盒的模型没有发生碰撞则可以直接结束检测，如果发生了碰撞，则继续查找包围盒树的子节点，逐步筛选过滤掉没有发生碰撞的部分[5]。常见的包围盒有轴对齐包围盒（Axis Aligned Bounding Box，AABB）、有向包围盒（Oriented Bounding Box，OBB）、包围球（Sphere）[6]和K-DOP包围盒（K-Discrete Oriented Polytope）等。

空间剖分的方法是将物体模型所在的空间分割成多个空间，并以此将空间中的模型分割成多个更小的群组，在当前的更小的空间内对模型进行相交测试。目前具有代表性的两种空间分割的方法是BSP树和八叉树。BSP树是二叉树结构，通过不断地加入分割平面对模型进行分割为前后两部分作为树的两个子节点，八叉树是将当前的空间八等分，并将每一个空间作为树的子节点。在相交测试中，从根节点开始，遍历空间树的每一个节点如果相交就继续遍历，如果不相交就放弃该子树，最后叶子结点进行三角面片的相交测试。

上述的两种传统的碰撞检测算法在大尺度的STL布尔运算的场景中有着不足之处：包围盒树和BSP树是二叉树，当发生碰撞的是某一个很小的三角面片时，会有着搜索树的深度过深，也就是说在最坏情况下效率低的问题。空间剖分中往往需要将与剖分面发生碰撞的三角形也进行剖分计算，这样就导致了许多不必要的冗余计算。

在模型数据量庞大的情况下，传统的碰撞检测算法的首先要构建包围盒树或是空间剖分树的结构，这就要耗去大量的时间，树的深度为O（logN），[N]是三角形的数量，并且在两个模型的检测阶段需要对树的每一层的节点深度遍历去检测。然而在实际情况中发生相交的三角面片对只占模型的很少的一部分，所以传统的碰撞检测算法计算上存在大量冗余，于是本文利用体素模型碰撞检测速度快的优势对碰撞检测算法进行优化，以求达到时间上的高效性。

2 算法实现

本文提出的基于两级体素模型的算法主要分为三个阶段：预检测阶段、体素化和体素模型求交阶段、三角形的精确相交检测阶段。在算法的预检测阶段，在模型的读取过程中构建模型的AABB包围盒，如果两个包围盒没有发生碰撞，则算法结束，如果发生碰撞，则求解两个包围盒的相交区域。接着是体素化阶段，将上一阶段得到的相交区域作为体素化空间，对模型进行体素化，构建起两层体素模型，接着对体素模型求交得到两个体素模型的碰撞体素。最后是三角形的精确相交检测阶段，对每个碰撞体素中的两个模型的三角形两两之间进行快速求交检测，并将求得的交线作为算法的最终结果。

2.1 预检测阶段

在预检测阶段，本文采用构建AABB包围盒的方法来确定两个物体的可能相交的区域，并且这个步骤在模型数据的读取期间就可以完成。这一步的目的是初步筛除部分三角形减少了后续计算的数据量，并且可以确立出体素空间的边界。对于一个AABB包围盒，我们用一个左下角的点和一个右上角的点来定义，这两个点的坐标值分别（xmin，ymin，zmin）和（xmax，ymax，zmax），在模型的读取期间不断地更新这6个值，即可完成两个模型AABB包围盒的构建。然后通过判断两个包围盒的在各个轴的投影是否有重叠来判断两个包围盒是否发生相交，如果都没有发生相交则算法结束，两个模型没有发生碰撞，如果发生相交，则对两个包围盒求交集，通过对两个包围盒的投影求交可以快速地构建待体素化区域S。

在式（2）中 S表示求解的待体素化区域，p是在S区域中的点，A、B代表两个模型的包围盒，Ux为A、B的包围盒在X轴上投影的交集，Uy为A、B的包围盒在Y轴上投影的交集，Uz为A，B的包围盒在Z轴上投影的交集。

接着，筛除不与体素空间相交的三角形。将两个模型中与体素空间发生相交的三角形序号分别保存进两个新的数组中。这里以两个三角网格模型为例，一个是兔子模型，一个是四面体桁架模型。如图1所示，是两个模型读取完成时，对其AABB包围盒的构建。如图2所示，是两个模型求交后的体素空间以及保留的两个模型的三角网格信息。

2.2 体素化和体素模型求交阶段

在体素化阶段，首先要以区域S为体素空间进行网格划分建立第一级体素模型。由于体素空间是长方体，如果以正方体为体素，那么边界情况就需要特殊处理，所以为了能够统一化处理，将每一个体素划分为近似正方体的长方体。比较区域S在各个轴上的投影，找到投影距离最小的轴，划分等分区间，以这个区间长度为基准，对其他两个轴进行划分。下面以X轴投影最小为例，将X轴划分为dimx个等分区间，通过式（3）可以求解出其他轴上的划分：

建立起一级体素空间后，则将在其中的三角面进行体素化。体素化的过程就是在与当前三角形发生相交的每一个体素中记录下三角形的ID号。模型的体素化方法有许多种，如截平面法，三角面取特征点法，空间距离法和网格线求交法等[8]。根据场景的不同，算法的适用性也不同。布尔运算中碰撞检测的目的是快速的地找出相交三角面对，并且精确地计算与三角形发生相交的体素会占用不必要的时间，所以这里采用一种精细体素化延迟的方法。这种方法将体素化的步骤拆分为两步：粗体素化和细体素化。在粗体素化中以三角形的包围盒代替三角形去体素化。完成粗体素化后，对两个体素模型进行求交运算，对发生碰撞的体素与其记录的三角形精确运算，即细体素化，将没有发生相交的三角形筛除。

首先是粗体素化的过程，在这一步骤中，遍历模型与体素空间发生相交的三角形数组中的每一个三角形。对每一个三角形的包围盒的两个顶点（xmin，ymin，zmin）、（xmax，ymax，zmax），如果两点都在体素空间中，则将其映射到体素空间的坐标（Xmin，Ymin，Zmin）、（Xmax，Ymax，Zmax）。对每一个在其范围内的体素遍历，将当前三角形的ID号插入进体素的表中。同样的，如果三角形的包围盒只有一个点在体素空间内，则先用三角形的包围盒与体素空间求交，将求交后的包围盒放入体素空间中进行体素化。

接着，遍历体素空间中每一个体素，如果体素中同时存放有两个模型的三角形序号，则为碰撞体素。

然后是细体素化的过程，目的是筛除碰撞体素中没有与体素相交的三角形，这里采用欧式距离法判断三角形是否与体素相交[9]。遍历碰撞体素中的三角形，求解碰撞体素中心点C（x0，y0，z0）到三角形平面的距离D，判断其是否大于体素包络球的半径R，如果大于，则从碰撞体素中删除这个三角形的序号。

至此，完成了第一级的体素模型的建立。

大尺度的三角网格模型会出现某个局部的三角面数量密集的情况，所以当一个碰撞体素中两个模型的三角形数量过多时，会导致算法效率的降低。这里通过建立第二级体素模型来解决这个问题。

第二级体素模型是对第一级体素模型中的碰撞的体素更加精细的划分。当在第一级体素模型的体素中两个模型的三角形数量均超过某一数量N时，以当前体素作为新的体素空间，以它的表中存放的两个模型的三角形序号作为输入的三角形，建立新的体素模型。由于更进一步的划分会导致更多的内存占用，而且因为三角网格模型在局部上往往三角形的大小相近，所以通过对当前第一体素内的三角形進行采样作为划分依据。采样依据是提取每个模型的前N个三角形的包围盒，取其最短轴的平均值作为新的体素空间的划分依据，从而完成对新体素空间的划分。之后通过与第一级体素构建相同的方法对其进行体素化，将三角形分配进各个体素中，再对体素模型进行求交得到相交的体素。

如图3所示是在上文例子中的两个模型，在完成体素化求解碰撞体素后的结果。

2.3 三角形的精确求交

在以上文的检测步骤中，主要目的是快速地筛除不可能发生碰撞的三角形对，从而缩小两个模型之间的三角形求交运算规模，提升时间效率。而在这一步骤中，逐个遍历两层体素模型中的碰撞体素，通过三角形与三角形求交算法直接获取交线的线段。