《基于obb碰撞检测的高效三角形相交测试》由会员分享，可在线阅读，更多相关《基于obb碰撞检测的高效三角形相交测试（12页珍藏版）》请在金锄头文库上搜索。
1、基于 OBB 碰撞检测的高效三角形相交测试 李明博 （韩国汉城国立大学计算机科学与工程系，汉城 151-744）摘要：针对基于方向包围盒的碰撞检测，提出一种高效的三角形相交测试算法。在测试两个方向包围盒的叶节点（例如矩形），许多中间计算结果可以在它们 所包含的两个三角形相交测试中重复使用。当我们在边界矩形的局部坐标而不 是在物体的全局坐标中工作时，更容易检测冗余操作。我们算法的性能改善就 是基于这种消除冗余操作的观测。与传统算法相比，我们在计算时间上已经有 15-79%的改善。我们将通过几个实验结果来验证此方法的效率。关键字：三角形相交；方向包围盒；碰撞检测；坐标描述1.引言碰撞检测在各种各样
2、的应用中都很重要，在这里仅举几个例子，如计算机图形学，动画，游戏以及机器人。方向包围盒（OBB）的层次包围体（BVH）技术经常应用在三维空间带有三角网格的三围物体之间的碰撞检测1。其他传统的边界包围体包括球体，轴对齐包围盒（AABB），k-discrete orientation polytope (k-DOP) ，以及line swept sphere（LSS）2。BVH 是包围体构建的树。BVH的每一个节点是限定基元相应设置的物体。BVH的叶节点通常限定单基元。本文专注于基于OBB的层次包围体技术和三角网格之间的碰撞检测，我们会展现如何通过使用检测OBB叶节点的结果加速三角形相交测试。OB
3、B树的叶节点是限定单一三角形的矩形。因此，三角相交测试由限定它们的矩形的类似测试来计算。通过循环计算矩形测试结果，我们可以让三角测试比以往从零开始进行相交测试的传统方法3-6更加高效。在实验测试结果中，我们已经观测到计算时间有15-79%的改善。测试两个三角形之间的相交测试的第一步是要将其中一个三角形坐标转换到另一个三角形的坐标系统中。这是一个耗费大的程序。在基于OBB的环境中，我们发现可以通过循环使用矩形包围体的相似转换来简化这个步骤。而且，通过在包围矩形的局部坐标里描述每一个三角形，我们能够很容易的提取共同操作，从而消除在相交测试的剩余步骤的冗余测试。2.相关算法Moller 3 计算一个
4、包含有多个三角形的平面上的一个三角形三个顶点之间的矢量距离。如果距离全部为正或者负，就说明不存在相交。反之，通过调换两个三角形的角色，我们可以重复其他平面三角的检测。如果三角检测出相交，那么接下来的问题就简化为过同一条相交线（在包含这些三角形的平面上）的两条线段之间的重叠测试（例如三角面片相交）。Held4首先计算一个三角形与一个包含其它三角形的平面之间的线段相交，然后将问题简化至二维空间的线段与三角之间的测试。Guigue和Devillers 5继承Moller 3的方法，然而他们是使用一个由4*4矩阵的行列式所定义的方向术语。每个顶点的方向距离由这个方向术语所计算。而且，在同一个相交线上检
5、测二条线段的重叠同样可以通过使用两个方向术语的符号有效的实现。两个三角形之间的相交就简化为检测八个方向术语的符号。Tropp et al. 6采取了代数算法，然和他们的基本框架与Held4的框架类似。通过线性代数技术以及重复使用某些变量的计算结果，Tropp et al. 6使得算法更加高效。在一般的三角形之间的检测，Guigue和Devillers 5以及Tropp et al. 6通常能展示更好的性能。然而，在我们的算法中，三角形在包围矩形的局部坐标中表示，由于算法的简单，我们发现Moller 3的算法更加符合我们的意图。本文中，我们采取Moller 3的算法。3.算法3.1 矩形包围体限
6、定一个三角形的OBB叶节点就是一个矩形，这个矩形与三角形7之间共同拥有一条边与两个顶点。 图1(a)指出最小的限定矩形与钝角三角形拥有同一条最长的边。对于锐角三角形，任意一条边都可以达到目的；但是，在图1(b)中，我们取用最短的一条边，这将对应最小的接近于正方形的矩形。每一个最小矩形的面积是三角形的二倍。图1 .钝角三角形（a）与锐角三角形（b）的最小面积的矩形包围体一个矩形包围体由一个中间位置的向量 ，一个3*3方向矩阵以及两,个确定侧边长度的实数。方向矢量被设置为沿着与三角形共同拥有的边的单位矢量。单位矢量是包含三角的平面的标准单位矢量；而且有我们= 的算法与其他算法的最大区别就是我们添加
7、一个正如图2中所描述的附加参数a来简洁地在矩形包围体的局部坐标中描述每一个三角形，而且。dxadx-图 2.在矩形包围体中的三角形的位置3.2 输入传统算法例如Moller 3, Held 4,以及Guigue和Devillers 5需要输入两个三角形的全部六个顶点。另外， 对于每一个三角形，Tropp et al. 6要需要一个顶点的位置以及从此顶点到另外两个顶点的边。我们的算法需要如下输入：（1）两个矩形包围体的半边长（，）和（，）。1dx1dy2dx2dy（2）其中一个矩形相对另外一个矩形的位置和方向： 和。,（3）对于每一个三角形，第三个顶点的附加参数和（这仅仅是我们在1a2aOBB数
8、据结构的额外存储）（4）两个向量 和的内积（作为两个矩形包围体相交测试的部分，: = d的值已经被计算）。使用输入数据，两个三角形的顶点坐标可以表示为以下形式：，），（0dy-dx-p111，），（0dy-112，），（0dyap113,1= 2 2+ ,2= 2 2+ .3= 2+ 2+ 注：在剩余的计算步骤中，我们并不需要用到这全部六个顶点的坐标值。三角平面相交测试不需要任何一个顶点位置。在三角相交测试的最后阶段，我们使用顶点x或者y的坐标值。尽管六个x或者y的坐标值可以通过一次减法，五次加法或者减法以及三次乘法计算得到。3.3 三角与平面的相交Moller 3通过平面上方向坐标来确定三角
9、形是否与平面相交。在我们的算法中，三角形已经包含于xy平面，而且向量*是包含三角形的321ppp321qqq平面的普通向量。尽管方向距离很容易通过下面的计算得到：， d-rdy-r-dxdp1z10z11（1）， d-rdy-rdxdp1z10z12（2）， d-rdyradp1z10z13（3）， z22y22x1cdyr-dx-rdq（4）， z22y22x2cdyr-dxrdq（5）， z22y22x3cdyrdxrdq（6）这里，而且。在六个表达式中，一些参数= ( 0, 1, 2) = (,)出现多次，例如。因此我们可以通过只计算这些参数一次来减少算法操1z1rdy 作的复杂性。当，
10、和具有相同的符号时，不与平面内的三角形1dp2dp3dp321ppp有相交。当这三个值都为0时，这两个三角形在统一个平面上。在这种321qqq很少出现的特殊情况下，我们采取Moller 3 的算法。当三角形与包含321ppp三角形的平面相交时，或者反之，我们继续测试两个三角形之间的相交321qqq状况，正如下面的讨论。3.4 三角与三角的相交假设P是包含三角形的平面，Q是包含三角形的平面；假设L321ppp321qqq是平面P与Q的相交线。当三角形与平面Q相交时，三角形也与321ppp321ppp直线L相交于一条线段。当且仅当这两条线段相交重叠时这两个三角形相交，如图33所示。我们需要计算每一
11、条线段的终点来检测是否这两条线段重叠。这里的终点是指三角形两边与包含另外一个三角形平面的相交点。不失普遍性，我们可以假设和有不同的方向而且边与平面Q相交。边上的一点v被参数1dp2dp12化为，而且点v到平面Q的距离定义为。 1 , 0tp-ptp121），（）（121dp-dptdp 当这个距离为0时，点v包含于平面Q中；因此向量与平面Q的相交点通过下12式计算得到：（7）（12 211 1p-pdp-dpdppv没有必要精确地计算相交点的位置3。这两条线段都包含于直线L；因此即使直线L投影到本来的坐标轴3，重叠测试结果也会被保留。在我们的算法中，L的方向矢量由z轴方向向量（0,0,1）与普
12、通向量=的叉积所决定。），（2z1z0zrrr当的模比的模大时，方向向量暗示x轴与y轴是适当的坐标轴。1zr1zr），（0rr-0z1z因此，我们只需要为选定的坐标轴坐标评估公式（7）。3.5 分类消除公式（7）包含一个加法，两个减法，一个乘法和一个除法。在现在的计算机系统中，除法比其他简单的计算操作例如加减法或者乘法与比较8花费 4到 8 倍的执行时间。因此，我们移除除法，如下所示。当四个终点以这样的方式给出并且，重叠测试与使用代替初始四个终点010yxxECBDAA，1yFD的，,和1011010yyxyyxxBA1001010yyxyyxxCA1001010yyxyyxxED所得到的结果
13、一样。关于此方案的更多详细的信息请参照如1001010yyxyyxxFD下链接：http:/ 3.减少至两条线段的重叠测试接下来的关于操作数的讨论是基于 Moller3的修订版算法，正如之前所提到的移除除法的思想。4.计算次数在我们开始详细算法的计算次数之前，我们需要理解对于输入的三角形，他们的表示方法在算法所采取的坐标系中的不同之处。假设和分别是在动1T2T作和的移动下的两个移动物体和中分别包含的三角形。此外，我们1M2M1O2O还假设和分别是和的矩形包围体。在传统的碰撞检测系统中，1R2R1T2T是在物体的坐标系中所表示的。于此相反，我们是在矩形包围体）（2 , 1iiTiO的局部坐标系中
14、表示三角形的。）（2 , 1iiTiR为了测试两个三角形之间的相交测试，我们需要将这两个三角形早同一个坐标系统中表示。为了达到这个目的，传统算法在物体的坐标系中检测和1O1T（）的相交，这里=，就而言，是的相对运动。（注意：12M2T12M21- 1MM1M2M移动矩阵只为移动物体和的框架构建一次。）于此对应，我们的算法12M1O2O是在矩形包围体的局部坐标系中表示三角形和（）。注意，两个三1R1T12M2T角形的 OBB 层次包围树相交测试同样在的局部坐标系中完成。因此，在我1R们的算法中，（）的转换是测试三角相交的 OBB 算法的附加产品结果。12M2T在其他传统的算法中，我们需要从头计算（），这远比我们的算法付出12M2T的代价大。在例如 Moller3,Held4以及 Guigue 和 Devillers5的方案中，（）12M2T的转换需要 27 次乘法和 27 次加法。Tropp al.6利用一个顶点和两个向量表示每一个三角形，因此 27 次乘法与 27 次加法是必须
