移动OBB与三角形相交testing

要求 :写一个testing函数,给定一个移动的OBB(方向包围盒)和一个三角形,只要OBB碰到三角形就返回true

OBB由其半范围( h1, h2, h3 ),主轴( a1, a2, a3 )和中心点C(cx,cy,cz) 。 三角形由三个顶点( U1, U2, U3 )来描述。 OBB以1秒的时间以速度V运动(因此V也是OBB经历的位移)。

:我已经读过Dave Eberly关于这件事的小型文件 ,并试图实施。 也与本文有关,我有一个关于W速度w投影的问题: – w等于dot(W, L) ,其中L是他在文中考虑的13个可能的分离轴之一?

一个定向边界框由六个平面(每个面一个)分隔。 三角形也由三条线(每边一条)分隔。 因此,一个天真的实现(通常是一个好主意)是计算任何三角形边与任何平面的交集,并检查在三角形的边缘内和OOB的一个面内是否出现至less一个交集。

 for each edge E of the triangle, let L be the line of direction obtained by extending E for each face F of the OOB, let P be the plane obtained by extending F. let q be the intersection of L and P. if q exists and q is within E and q is within F, then An intersection occurred. 

使用本地参考帧可能更容易,所以OBB变成AABB。 然后你可以开始优化。

虽然不是100%准确的,即使它可能会报告交叉点,即使这些对象实际上没有发生碰撞(但是为了更容易使用像GJK这样的更复杂的解决scheme),这里是我读到Dave Eberly的原作 OBB上的纸与移动的三角形相交testing。

在这篇文章中,相交testing是在顶点(U0, U1, U2)和边E0 = U1 - U0, E1 = U2 - U0, E2 = E1 - E0和一个OBB中心, C ,主轴, A0, A1, A2和半范围ha0, ha1, ha2

假定三角形沿W方向移动。 在这种情况下, W轴不被假设为归一化的,而是具有等于三角形所经受的总位移的大小。

问题不在于find实际的交点,而是要确定OBB和三角形是否可能重叠。 为此,Eberly构思了一系列13个分离轴testing。 总而言之,分离轴testing通过从候选L开始起作用,并且检查OBB和扫描三角形体积(在这种情况下是斜三棱柱体)的边界的投影是否作为区间重叠。 假定L轴的原点位于OBB的中心C 请参阅下面的图片以获得更好的理解 在这里输入图像说明

在文章中进行testing之后,我发现它对三角形实际移动的情况performance很差。 在50%的情况下,没有分离轴候选人能够分离物体,尽管它们显然不会相互碰撞。 因此,我用下列7个坐标轴replace了这些候选坐标轴,这些坐标轴在93%的情况下可以作为早期testing的可靠工作:

  • L = W.cross(Ei)i = 0:2
  • L = W.cross(Ai)i = 0:2
  • L = W

前六种情况实际上在数量上要求较低,原因在于L根据定义垂直于W (这有助于避免计算某些点积,因为它们是0)。 在最后一种情况下,事情有点复杂,但这就是为什么我决定把物体确实重叠之前,把它作为最后的手段testing。 尽管在这个图中没有表示, D = U0 - C是计算三角形投影到L轴上的向量之一。

为了有效地计算这个testing所需的数量(交叉和点积),我写了一个小的python脚本来生成前6个例子:

 def symCross(i, j): k = {0, 1, 2}.difference({i, j}) k = next(iter(k)) if (i == 0 and j == 1) or (i == 1 and j == 2) or (i == 2 and j == 0): return k else: return -k WcrossAi = set() WcrossEi = set() WcrossEidotAj = set() WdotAi = set() print "Real p0, p1, p2, R; \n"; # L = WxAi for i in range(0,3): print "// L = WcrossA%d" % (i); L = "WcrossA" + `i` if L not in WcrossAi: WcrossAi.add(L) print " Vector4 WcrossA"+`i` + "; WcrossA"+`i` +".setCross(W,a"+`i`+");" if "WcrossE0" not in WcrossEi: WcrossEi.add("WcrossE0") print " Vector4 WcrossE0; WcrossE0.setCross(W, E0);" if "WcrossE1" not in WcrossEi: WcrossEi.add("WcrossE1") print " Vector4 WcrossE1; WcrossE1.setCross(W, E1);" if "WcrossE0dotA{0}".format(`i`) not in WcrossEidotAj: WcrossEidotAj.add("WcrossE0dotA"+`i`); print " Real WcrossE0dotA"+`i`+ " = WcrossE0.dot3(a"+`i`+");" if "WcrossE1dotA{0}".format(`i`) not in WcrossEidotAj: WcrossEidotAj.add("WcrossE1dotA"+`i`); print " Real WcrossE1dotA"+`i`+ " = WcrossE1.dot3(a"+`i`+");" print " p0 = WcrossA{0}.dot3(D);".format(`i`) print " p1 = p0 - WcrossE0dotA{0};".format(`i`) print " p2 = p0 - WcrossE1dotA{0};".format(`i`) # R R = " R = " for k in range(0,3): if i != k: l = {0, 1, 2}.difference({i, k}) l = next(iter(l)) if "WdotA"+`l` not in WdotAi: WdotAi.add("WdotA"+`l`) print " Real WdotA"+`l`+" = W.dot3(a"+`l`+");" R += "+ha"+`k`+"*fabs(WdotA"+`l`+") " R += ";" print R #heredoc test print ''' if (ProjectedDistanceOveralp(p0, p1, p2, R) == false) { return false; // no intersection } ''' # L = WxEi for i in range(0,3): print "// L = WcrossE"+`i` if "WcrossE"+`i` not in WcrossEi: WcrossEi.add("WcrossE"+`i`) print " Vector4 WcrossE{0}; WcrossE{0}.setCross(W,E{0});".format(`i`) print " p0 = WcrossE{0}.dot3(D);".format(`i`) p1 = " p1 = p0" p2 = " p2 = p0" if i == 0: p1 += ";" p2 += " + WdotN;"; elif i == 1: p1 += " - WdotN;" p2 += ";" else: p1 += " - WdotN;" p2 += " - WdotN;" print p1 print p2 R = " R = "; for k in range(0,3): if "WcrossE{0}dotA{1}".format(`i`,`k`) not in WcrossEidotAj: WcrossEidotAj.add("WcrossE{0}dotA{1}".format(`i`,`k`)) print " Real WcrossE{0}dotA{1} = WcrossE{0}.dot3(a{1});".format(`i`, `k`) R += " + ha{1} * fabs( WcrossE{0}dotA{1} ) ".format(`i`,`k`) R += ";" print R #heredoc test print ''' if (ProjectedDistanceOveralp(p0, p1, p2, R) == false) { return false; // no intersection } ''' 

为了testing投影物体是否重叠,我用c ++编写了两个SIMD友好的函数:

 bool ProjectedDistanceOveralp(Real p0, Real p1, Real p2, Real R) { Vector4 p012; p012.set(p0, p1, p2); Vector4 Rplus; Rplus.setAll(R); Vector4 Rminus; Rminus.setAll(-R); Mask4 greaterThanR = p012.greater(Rplus); Mask4 lessThanR = p012.less(Rminus); return !(greaterThanR.getMask() == Mask4::MASK_XYZ || lessThanR.getMask() == Mask4::MASK_XYZ); } bool ProjectedDistanceOveralpWithW(Real p0, Real p1, Real p2, Real R, Real w) { Vector4 p012; p012.set(p0, p1, p2); Vector4 Rplus; Rplus.setAll(R); Vector4 Rminus; Rminus.setAll(-R - w); Mask4 greaterThanR = p012.greater(Rplus); Mask4 lessThanR = p012.less(Rminus); return !(greaterThanR.getMask() == Mask4::MASK_XYZ || lessThanR.getMask() == Mask4::MASK_XYZ); } 

最后, L=W轴testing可以写成:

 // L = W Real WdotW = W.dot3(W).getReal(); p0 = W.dot3(D).getReal(); p1 = p0 + W.dot3(E0).getReal(); p2 = p0 + W.dot3(E1).getReal(); R = ha0 * fabs(WdotA0) + ha1 * fabs(WdotA1) + ha2 * fabs(WdotA2); if (ProjectedDistanceOveralpWithW(p0, p1, p2, R, WdotW) == false) { return false; // no intersection }