0
\$\begingroup\$

Requirements: to write a test function that, given a moving OBB (oriented bounding box) and a triangle, returns true whenever the OBB hits the triangle.

The OBB is described by its half extents (h1, h2, h3), principal axes (a1, a2, a3) and center point C(cx,cy,cz). The triangle is described by its three vertices (U1, U2, U3). The OBB moves with the velocity V over a period of time of 1 second (hence V is also the displacement the OBB undergoes).

Question: I have already read Dave Eberly's mini-paper on the matter and made an attempt at an implementation. Also related to this paper, I have a question regarding the w projection of the W velocity: - is w equal to dot(W, L), where L is one of the 13 possible separating axes he considered in that paper?

\$\endgroup\$

2 Answers 2

Reset to default
2
\$\begingroup\$

An oriented bounding box is delimited by six planes (one for each face). A triangle is also delimited by three lines (one for each sides). A naive implementation (which often a good idea to start with) is thus to compute the intersection of any triangle edge with any plane and to check whether at least one intersection occur within an edge of a triangle and within a face of the OOB.

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.

It's probably easier to use a local reference frame so the OBB becomes an AABB. Then you can start to optimize.

\$\endgroup\$
4
  • \$\begingroup\$ I appreciate your description of a potential solution. However, I am considering a slightly more complicated situation where the OBB is moving (a so-called shape-cast) and the triangle is stationary. What I would like point out is that the plane-triangle intersection leads to too many false positives, besides working only for stationary objects. \$\endgroup\$ Commented Mar 11, 2015 at 16:38
  • 1
    \$\begingroup\$ If your bounding box is used for pruning, you need simple computation, or else you defeat the purpose of pruning. An easy solution is to expand/find an OOB so that they enclose both the box at the beginning and the end of the time slice. (I usually use AABB and it's even easier). \$\endgroup\$ Commented Mar 13, 2015 at 0:26
  • 1
    \$\begingroup\$ If you want exact mathematical solutions, you can also use a reference frame following the box position and orientation. That way, you transform the problem with a stationary OBB which is a AABB and a moving triangle. The sweep of the moving triangle makes a prism, with possible bending and torsion if you OBB has an non-nul torque. The difficult part here is to describe the three twisted and bended "vertical edges" of the prism. Then you can do the intersection of the curves and the axis-aligned planes of the AABB. For the efficiency, I suggest to start from a working solution first. \$\endgroup\$ Commented Mar 13, 2015 at 2:23
  • \$\begingroup\$ these are quite promising suggestions.Again, there's a "however" involved: it is not at all sufficient to do the intersection of the prism's "curvy" edges with the OBB/AABB. Simply imagine a translation of a triangle that intersects the box by first hitting a corner. Or if the triangle is simply larger than the box. I do have a somewhat working solution involving Dave Eberly's suggestion, but with totally different separating axes. BTW, thanks a lot for your comments and answer, I appreciate them a lot! \$\endgroup\$ Commented Mar 13, 2015 at 7:11
1
\$\begingroup\$

Although not 100% accurate, in the sense that it may report intersections even when the objects do not actually collide (but for that a more complex solution like GJK could be easily used), here's the solution I came up with after reading Dave Eberly's original paper on OBB vs moving triangle intersection test.

In that paper, the intersection test is performed between a triangle, described by vertices (U0, U1, U2) and edges E0 = U1 - U0, E1 = U2 - U0, E2 = E1 - E0, and an OBB, given through its center, C, principal axes, A0, A1, A2 and half extents, ha0, ha1, ha2.

The triangle is assumed to be displaced along a direction W. The W axis, in this case, is not assumed to be normalized, but has a magnitude equal to the total displacement the triangle is subjected to.

The problem is not to find an actual intersection point, but to decide whether the OBB and triangle might overlap. For this, Eberly conceived a series of 13 separating axis tests. In summary, the separating axis test works by starting with a candidate axis, L, and checks whether the projections of the boundaries of the OBB and of the swept triangle volume (in this case, an oblique triangular prism) overlap as intervals. The origin of the L axis is assumed to be at the center C of the OBB. Refer to the picture below for a better understanding enter image description here

After implementing the test in the article, I found it to perform very poorly for the case where the triangle was actually moving. In 50% of the cases, no separating axis candidate was able to separate the objects, although they were clearly not going to collide. Thus, I replaced those candidates with the following set of 7 axes, which worked reliably as an early out test in 93% of the cases:

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

The first six cases are actually less numerically demanding due to the fact that L is by definition perpendicular to W (it helps with avoiding to compute some dot products since they're 0). In the last case, things are a bit more complicated, but that's why I left it as a last resort test before deciding the objects might indeed overlap. Although not represented in this figure, D = U0 - C is one of the vectors involved in computing the projection of the triangle onto the L axis.

To efficiently compute the amounts (cross and dot products) needed for this test, I wrote a small python script to generate the first 6 cases:

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 } '''

For testing whether the projected bodies overlap, I've written two SIMD friendly functions in c++:

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); }

Finally, the L=W axis test can be written as:

// 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 }
\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.