基于层次包围盒与平均单元格的三角网格求交

,

(浙江工业大学 理学院，浙江 杭州 310023)

在计算机图形学、CAD/CAM中,对于任何的实体表面，都可以通过不规则三角网(TIN)[1]去逼近它,逼近的程度则取决于原始数据的分布、密度和三角形的形状等.而对于三角网格模型的处理，在虚拟现实、虚拟设计等领域,提出各式各样的问题与方法，如曲面重构、模型特征提取[2]和模型编辑造型[3]技术.而如今，随着对建模[4-7]要求的不断提高,模型中三角面片的数量也是跟着指数增长.于是三角网格求交速度问题便成了最急迫的问题，也是最基本的问题.Suri等[8]通过对层次包围盒法的分析研究,证明了较于一般的求交算法,此算法可以有效降低空间复杂度.根据划分包围盒的不同，常见的包围盒包括:AABB(Axis align bounding box)、方向包围盒OBB(Oriented bounding box)、包围球(Sphere)、固定方向凸包包围盒FDH(Fixed directions hulls)等. Gvan[9]基于AABB结构构建层次结构的二叉树，有效地剔除了不相交的三角面片.Gottschalk等[10-11]基于OBB结构构建层次结构的二叉树，有效地剔除了不相交的三角面片.魏迎梅等[12]对虚拟环境碰撞检测的研究，提出基于FDH的层次包围盒树算法.亦有其他方法，如Lo等[13]使用背景网格筛选出潜在的相交三角面片，然后求交点时，通过追踪相邻三角面片来求得相交链或者环.或者如蒋钱平等[14]提出了平均单元格法，采用划分和索引思想，将空间分割成一个个固定的小立方体进行处理.Tomas等[15]提出了快速的，内存消耗最小的射线与三角形求交算法，具体表现为:将一个三角形的3条边看作3条射线分别与另一个三角形求交计算.Tomas[16]先将两个三角形近似看成两个平面，从而简化判断两者是否相交以及求出相交线，进而再判断该相交线是否为两个三角形的公共线.徐智渊等[17]通过一条射线构造一对相互垂直的平面，然后通过任意三角形的三个点与射线所在的平面作距离运算，只需定性的判断正负,便能排除空间中不相交三角形.

上述方法要么算法实现思路较为简单，但是计算速度并不让人满意；要么实现过程较为复杂，提高了速度却浪费了大量内存，甚至在某些特殊情况下反而下降.为了高效快速解决求交运算，对于未经处理的模型,先构造AABB层次包围盒，粗略地筛选出可能相交的三角形；其次，使用平均单元格法，采用索引的思想，精确地将相交的三角形确定在一部分小单元格内；最后，逐次迭代剩余三角形，进行求交计算.

1 碰撞检测及求交点计算

对于已有的AABB层次包围盒法，不足在于：1) 随着层次的增加，空间复杂度也相应增加，当达到一个临界值时，碰撞检测的速度非但不会提高，反而会降低；2) 对于树的叶节点来说，在简单判断是否相交之后,只能对其中含有所有的三角面片进行笨拙地两两求交.同样，对于已有的平均单元格法，其不足在于：1) 单元格的边长size设定随着模型的不同而不同，且边长size的变化，对模型求交速度影响很大；2) 对于大模型来说，该算法的内存消耗巨大，不适用于大场景.

1.1 改进算法

针对以上提出的不足，此处给出混合算法的示意图，如图1所示。

图1 混合算法Fig.1 Hybrid algorithm

混合算法主要步骤:

1) 对于未经处理的模型,先构造AABB层次包围盒，分层的次数主要由模型的大小决定，并排除不相交的叶节点(其中含有大量的三角面片).对于AABB层次包围盒，它的优势在于分别对两个模型建立各自包围盒，然后使用二叉树或者八叉树，对大量的三角面片进行粗略的碰撞检测，排除绝大部分的显而易见的无关三角面片.

2) 经过AABB层次包围盒筛选，候选的相交三角面片将被限定在一个较小的范围内,此时再使用平均单元格法，选取适当的边长size，将必定相交的三角面片限定在部分小立方体内.对于平均单元格法，它的优势是可以快速地将任意一个三角面片定位在某一个预先设定的小正方体内，由于size大小接近三角面片边长,只需要处理含有来自两个模型三角面片的正方体，即可避免95%以上的不必要三角面片求交.

3) 对于同一个小立方体内的三角形，使用Ray triangle intersection算法进行两两求交.即将一个三角形的三条边看作三条射线，分别与另一个三角形求交.

基于此，算法流程图如图2所示.

图2 算法流程图Fig.2 Algorithm flow chart

1.2 连接相邻交点得到直线段

对于任意相交的三角形ABC和EFD，用之前提到的方法，即将1个三角形的3条边看作3条射线，分别与另1个三角形求交，那么相交的情况可以分为2大类7种情况，如图3所示.

图3 三角形相交的种类Fig.3 The kind of intersection of triangles

第1类共面

1) 交线为一个封闭的三角形，如图3(a)所示.

2) 交线为一个封闭的四边形，如图3(b)所示.

3) 交线为一个封闭的五边形，如图3(c)所示.

4) 交线为一个封闭的六边形，如图3(d)所示.

第2类不共面

1) 2个交点.图3(e)有2个交点都来自于一个三角形的边；图3(f)有2个交点分别来自两个三角形的边.

2) 3个交点.图3(g)有2个交点刚好落在一个顶点上.

3) 4个交点，图3(h)有2对交点刚好分别落在2个顶点上;图3(i)有4个交点都落在一个顶点上.

注意两点：1) 正确性.由于两个三角形相交要么产生一个封闭三角形，要么产生一条线段，因此，求得一组交点便要进行标记，防止此交点组与另外其他交点作连线；2) 连通性.因为采用的数据结构为半边结构，相应的交点会被求解两次，所以交线段便会被很好的连接在一起，图3(j)中POQ按顺序连接.

2 实验结果与分析

实验在酷睿CPU频率2.2 GHz，内存4 GB的笔记本上进行，算法在VS2010环境下实现.对以下3个例子分别运用AABB包围盒、平均单元格和改进算法，并且进行了反复实验统计与分析，实验数据有3种情况.

1) 给定的模型由2 956个和8 874个三角形组成，一幅为模型，一幅为模型的相交线，如图4所示.

图4 狗模型与鱼模型相交Fig.4 Intersection of dog model and fish model

2) 给定的模型分别由30 326个和29 014个三角形组成，一幅为模型，一幅为模型的相交线，如图5所示.

图5 熊模型和桶模型相交Fig.5 Intersection of bear model and bucket model

3) 给定的模型分别由15 142个和27 100个三角形组成，一幅为模型，一幅为模型的相交线，如图6所示.

图 6 杯子模型和轴承模型相交Fig.6 Intersection of cup model and bearing model

实验结果如表1，2所示.

表1 比较算法运算速度Table 1 Operation speed of comparison algorithm

表2比较算法对模型构建单元格的个数

Table2Comparealgorithmstothenumberofcellsthatthemodelbuilds

求交算法单元格的数量/个图4图5图6平均单元格36 480119 991179 400改进算法(5层)13 07298 393142 945改进算法(10层)8 39878 66477 385

表1为改进的混合算法，速度普遍快于AABB层次包围盒法，实验结果令人满意.而且它的速度相较于平均单元格法也是有优势的，特别是在两个模型相交的部分少，如图5所示，相交部分只有四只脚部分，当分层的次数不太多，且能大量排除无关的三角形时，省下的时间可以弥补分层所用的时间，与此同时，由于平均单元格法空间复杂度较大，对于大型的模型，使用该方法会消耗大量内存，以至于普遍都不采用.

表2为平均单元格法可以看作是混合算法的一种特殊情况，即不进行分层.平均单元格空间复杂度为O(lmn)，混合算法空间复杂度为O(lmn/2k).其中k为算法层次划分的层次数，显而易见，次数越大，则复杂度越低，在大部分情况下，改进算法能够节省较多的空间.图5分割5层后，需要构建的小正方体单元格数量减少了10%；例子1，3分割10层后，则减少了60%以上.随着分割层次增加，算法的内存消耗下降，速度也有所放缓，但速度仍然快于AABB层次包围盒法，与平均单元格相差无几，很好地做到了平衡.

3 结 论

对已有的层次包围盒法和平均单元格法算法进行了分析与实现，并比较了各自的优缺点，进行了相应的改进，主要表现为在粗略检测的时候使用层次包围盒法，排除了大量的无关的三角面的求交计算.此步骤只需分层，并比较叶节点包围盒之间是否相交，而并不需要对每个包围中的每个三角形进行求交运算.在精确检测时使用的是平均单元格法，因为剩余的三角形已经大大减少，再用包围盒的意义已经不大，并且随着分层次数的增加速度反而会下降，因此用单元格反而大大提高了求交效率，减少了运算时间,较大地减少了内存的消耗，然后使用Ray triangle intersection将三角形的3条边分别看成3条射线与另一个三角形求交计算.因此，改进算法在一定程度上，要优于前2种，而且较好的平衡了计算的速度和内存的消耗，更加适合巨大模型场景的计算，实验数据也表明了在提高了速度的同时，避免了内存的大量消耗.在后续的工作中，将进一步研究一对三角形之间的求交计算方法，从而可以从质上提高计算速度而不是筛选数量上.