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

来源:用户上传      作者:

　　摘要：碰撞检测是布尔运算中的关键步骤。针对现有的大尺度三角网格模型的布尔运算时间效率不足的问题，提出一种基于两层体素模型的碰撞检测算法，以求提高两个静置模型在布尔运算场景中碰撞检测的速度。在算法中，首先利用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 三角形的精确求交
　　在以上文的检测步骤中，主要目的是快速地筛除不可能发生碰撞的三角形对，从而缩小两个模型之间的三角形求交运算规模，提升时间效率。而在这一步骤中，逐个遍历两层体素模型中的碰撞体素，通过三角形与三角形求交算法直接获取交线的线段。 　　空间三角形之间的求交测试算法是计算机图形学的基本问题之一，Moller、Held和Devillers等人提出三种快速测试两个三角形是否发生相交的算法[10-12]。虽然Devillers的速度优于前两者，但是我们需要得出最终的交点结果，而不仅仅是两个三角形是否相交，所以这里改进了Moller的算法，他提出的算法的中间值更易于得到交点的结果。
　　三角形与三角形的求交算法输入的是两个三角形，输出的是他们发生相交的线段，算法流程如图4所示。
　　其中，v代表任一顶点，nj指的是与这个顶点另一个平面的法向量，ni指的是当前顶点所做在平面的法向量。由此可以得到三角形的三个顶点到另一平面的距离记为dist0、dist1、dist2。设定一个ε=1×10-6作为容忍值。如果dist0×dist1>ε，并且dist2×dist1>ε，就认为这三个顶点位于另一平面的同一侧，则两个三角形没有发生相交。在排除不相交的情况后，需要判断两个三角形是否有可能发生共面，即n1×n2<ε并且dist0<ε、dist1<ε、dist2<ε，则两个三角形为共面关系，对于共面的情况只需将三维转为二维求出它们的交线。
　　接着，计算出三角形每一个边与另一个平面的交线，设三角形的某一条边的方程为P（t）= p+t·v，其中p代表的是线上的某一个点，用当前边的顶点值代入即可，[t∈R]，v代表的是直线的方向向量。另一平面则用它的法向量n和平面到原点的距离D来表示。对以下方程求解，通过式（9）即可得到直线与平面的交点：
　　然后将 t重新代入原直线方程就可以得到直线与平面的交点，接着判断交点是否在线段范围内，如果在，则得到其中一个交点，反之则该边没有与平面相交。
　　通过上述运算，如图所示，可以得到三角形与平面的交点分别为i、j和k、l。此时通过判断这两个线段是否重叠，如果不重叠，则两个三角形不相交，反之对两条线段求交，如图中情况所示，则将求得的k、j两个点存入结果数组中，并将两个三角形序号以二元组形式放于两个模型的相交三角形数组中建立关联，以方便后续的计算。
　　最后，无论求得的结果如何，都要将两个三角形在文件中的序号以二元组的形式放入事先准备的已求交表中，以防止重复运算。如图5是上文例子中通过此步骤得到的算法的最终结果。
　　3 实验结果及分析
　　本文实验的硬件环境为Intel Core i5 4200M 2.50GHz处理器，8GB内存，算法在VisualStudio2017下开发，使用单线程，Release模式。对基于体素模型的碰撞检测算法和VTK中内置的基于OBB层次包围盒树的算法分别进行实验，并对实验的结果进行对比和分析，最后得出结论。为了验证本文算法的有效性，在相同的环境与相同的输入模型下，与VTK中的算法进行碰撞检测的时间的对比。实验中选用多种表面复杂并且三角形数量级达万级以上的模型进行测试，可以验证出本文算法的优劣。
　　本文算法均在VTK的框架下完成。VTK是一个开源、跨平台、成熟稳定的可视化工具，里面包含了大量稳定的计算机图形学算法的函数接口。本文算法中的基础的数据结构，STL模型文件的读入以及最终结果的渲染均采用VTK中的函数接口，这样做可以更好地控制变量与VTK的vtkIntersectionPolydataFilter类中内置的碰撞检测的算法进行对比，从而更有力地验证本文算法在针对大尺度复杂的三角网格模型上的优势。
　　在对比实验中，第一级体素模型的最短轴的划分个数设为固定值32。如表1所示是本文算法和VTK中算法的对比结果，可以看出在十万级的数量级的模型的碰撞检测中，本文算法依然可以将运算时间控制在0.2秒左右。虽然算法可能由于第一级体素划分大小的原因存在着一定的不稳定性，但是实验证明比起传统算法对于静置的大尺寸模型的碰撞检测仍有着不可比拟的优势。
　　4 结论
　　目前，虽然已经有多种不同的碰撞检测算法，但是随着三角网格模型越来越复杂并且大尺度的模型越来越多，导致布尔运算算法效率降低。本文针对这个问题提出一种基于两层体素模型的算法优化布尔运算中碰撞检测步骤的效率。
　　该算法有以下两个创新点与优势：
　　（1）提出两级体素模型：利用了体素模型的布尔运算效率高的优势，同时也消除了传统体素模型对大尺寸的模型局部无法很好地细分的劣势。相较于传统的八叉树模型减少了碰撞三角形的搜索层数。
　　（2）延迟精细体素化：细体素化的步骤往往是在建立体素模型的过程中计算量最大的步骤，本文根据布尔运算的独特场景，将体素化的步骤拆分，在进行粗体素化后，体素模型求交后只对碰撞的体素细体素化。通过这种方法可以减少不必要的运算时间，将算力用到需要的地方，这样就可以加快体素化和体素模型求交阶段的速度。
　　经过实验与VTK中的算法进行对比，验证了本文算法在碰撞检测中时间效率的提高。
　　参考文献：
　　[1] 郭开波，张李超，王从军，等.STL模型布尔运算的实现[J].华中科技大学学报（自然科学版），2006，34（7）：96-99.
　　[2] 林宇鹏. 三维网格模型的布尔运算算法研究[D]. 合肥： 中国科学技术大学， 2017.
　　[3] Feito F R，Ogayar C J，Segura R J，et al.Fast and accurate evaluation of regularized Boolean operations on triangulated solids[J].Computer-Aided Design， 2013，45（3）：705-716.
　　[4] 于瑞云，赵金龙，余龙，等.结合轴对齐包围盒和空间划分的碰撞检测算法[J].中国图象图形学报，2018，23（12）：1925-1937.
　　[5] 陈秋菊.虚拟现实中包围盒碰撞检测算法优化研究[J].电脑知识与技术，2018，14（19）：236-238.
　　[6] 靳雁霞，秦志鹏，李照.融合R-Sphere包围球的变形体碰撞检测算法[J].计算机工程与设计，2017，38（1）：92-96.
　　[7] 李玉虎，王宗彦.基于混合层次包围盒碰撞算法的改进[J].华东交通大学学报，2019，36（6）：112-118.
　　[8] 吴耕宇，潘懋，郭艳军.利用几何求交实现三角网格模型快速体素化[J].计算机辅助设计与图形学学报，2015，27（11）：2133-2141.
　　[9] 吴耕宇，潘懋，郭艳军，等.改进的点到三角网距离快捷算法[J].計算机辅助设计与图形学学报，2014，26（3）：348-355.
　　[10] M?ller T.A fast triangle-triangle intersection test[J].Journal of Graphics Tools， 1997，2（2）：25-30.
　　[11] Held M.ERIT—A collection of efficient and reliable intersection tests[J].Journal of Graphics Tools， 1997，2（4）：25-44.
　　[12] Devillers， O.， P. Guigue. Faster Triangle-Triangle Intersection Tests[J]. INRIA. 2002：44-88.
　　【通联编辑：梁书】
转载注明来源:https://www.xzbu.com/8/view-15314630.htm