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
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:2L = W.cross(Ai), i = 0:2L = 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
}
