Sign in to follow this  
Paul7

OBB-Triangle Intersection

Recommended Posts

Paul7    174
I`ve recently got OBB-OBB intersection working using the separating axis theorem (SAT) and have now moved on to OBB-triangle intersection but am unsure how to go about doing this. I`ve found lots of source for AABB-triangle intersections but none for OBB`s. I`m thinking that its done using a variation of the SAT used for OBB-OBB but am unsure as how to change it to accommodote the triangle. Other thoughts I had are, if it possible to do so, is to transform the OBB to an AABB using its inverse transformation and then use the source I found to do that? - I`d prefer not to have to do this method. Any help on this would be much appreciated? Thanks

Share this post


Link to post
Share on other sites
oliii    2196
the transform should work well enough (you will have to re-transform the result fo the test if you have collision points and normals).

As for OBB-tri, it's the same principle as OBB-OBB. In that case you have 13 tests (instead of 15 for OBB-OBB).

given OBB (C, A[3], a[3]), where A[3] is the three perpendicular axis representing the orientation of the box, and a[3] the extents along each axis.

also, a triangle (N, V[3]), where N is the normal, V are the vertices.

axes are :

N

A[0]
A[1]
A[2]

A[0] x E[0]
A[0] x E[1]
A[0] x E[2]

A[1] x E[0]
A[1] x E[1]
A[1] x E[2]

A[2] x E[0]
A[2] x E[1]
A[2] x E[2]

E[3] are the edges of the triangle

E[0] = V[1] - V[0]
E[1] = V[2] - V[1]
E[2] = V[0] - V[2]


You have to take care in case of degenerate axes, as usual.

Oh, and shameless plug

Share this post


Link to post
Share on other sites
glSmurf    216
transform the triangle into obb space and deal with it as an aabb-tri collision test


[edit] maybe I should read through your question before I answer =)

if the tri is in world space then just multiply each vertex by the inverse of the obb's rotation matrix then add the obb's position to the vertex position

blaba (Im in a hurry so sorry if I missed something) =)

Share this post


Link to post
Share on other sites
Charles B    863
You'll have to transform back and forth anyway, implicitely or explicitely.

Whatever the math, after you optimize, eliminate common subexpressions, etc.. you necessarilly have the same operations in the end.

So if you already have the AAB-triangle case implemented, just use it. It will not be fully optimized, but already very well.

Share this post


Link to post
Share on other sites
oliii    2196
yeah, the simpler the better. If performance is a problem, optimise with a special OBB test. Besides, transforming vs explicit test isn't necessarly slower. transforming is not exactly just-in-time like for an optimised explicit test, but tyeh performance gain might be marginal.

Share this post


Link to post
Share on other sites
Paul7    174

Having peformed some more tests on my apparently working test, I`ve now found that its not actually working correctly as it is also selecting the triangle when the OBB is slightly outside of it.

I was slightly unsure as what to use in place of the vector between the two OBB's centers in the OBB-OBB test, I thought maybe the vector from the centers to the vertex of the tri furthest away, but am now unsure as to whether this is correct.

Can anyone see anything that could be wrong? heres my source:

Thanks


bool intersectOBBTriangle ( // TRUE if intersection found
//A
CVector &a, //extents
CVector &Pa, //position
CVector *A, //orthonormal basis
//B
CVector &N, //Triangle Normal
CVector *v) //Triangle Verts
{
//calculate triangle edge vectors
CVector E[3];
E[0] = v[1] - v[0];
E[1] = v[2] - v[1];
E[2] = v[0] - v[2];

//calculate distance between box centre and the tris furthest away vertex
CVector T, Ttemp;
f32 maxMag = 0.0;
int i, j;
for(i = 0; i < 3; i++)
{
Ttemp = v[i] - Pa;
f32 mag = Ttemp.Magnitude3();
if( mag > maxMag)
{
T = Ttemp;
maxMag = mag;
}
}

/*ALGORITHM: Use the separating axis test for all 13 potential
separating axes. If a separating axis could not be found, the two
overlap. */

f32 ra, rb;
CVector L;

//Triangle's Normal
L = N;

ra = (a.getElement(0)*fabs(A[0].DotProduct(L))) + (a.getElement(1)*fabs(A[1].DotProduct(L))) + (a.getElement(2)*fabs(A[2].DotProduct(L)));

rb = fabs(E[0].DotProduct(L)) + fabs(E[1].DotProduct(L)) + fabs(E[2].DotProduct(L));

//If separating axis found no collision so return
if( fabs(T.DotProduct(L)) > (ra + rb) )
return false;

//A's basis vectors
for( i=0 ; i<3 ; i++ )
{
L = A[i];

ra = (a.getElement(0)*fabs(A[0].DotProduct(L))) + (a.getElement(1)*fabs(A[1].DotProduct(L))) + (a.getElement(2)*fabs(A[2].DotProduct(L)));

rb = fabs(E[0].DotProduct(L)) + fabs(E[1].DotProduct(L)) + fabs(E[2].DotProduct(L));

//If separating axis found no collision so return
if( fabs(T.DotProduct(L)) > (ra + rb) )
return false;
}

//A's basis vectors cross all the triangle edges
for( i=0 ; i<3 ; i++ )
{
for( j = 0; j <3; j++)
{
L = A[i].CrossProduct(E[j]);

ra = (a.getElement(0)*fabs(A[0].DotProduct(L))) + (a.getElement(1)*fabs(A[1].DotProduct(L))) + (a.getElement(2)*fabs(A[2].DotProduct(L)));

rb = fabs(E[0].DotProduct(L)) + fabs(E[1].DotProduct(L)) + fabs(E[2].DotProduct(L));

//If separating axis found no collision so return
if( fabs(T.DotProduct(L)) > (ra + rb) )
return false;
}
}
/*no separating axis found,
the two overlap */

return true;
}


Share this post


Link to post
Share on other sites
jyk    2094
It looks like you've tried to adapt the OBB test directly for OBB/triangles? I don't think this will work, as unlike an OBB a triangle projection does not have a clearly defined center and radius.

One way or another I think you'll have to find the actual projection (min and max) of the triangle for each axis, and compare that to the OBB radius. There are various shortcuts for finding this projection for each axis, but for testing purposes you could just brute-force it by finding the min and max among the three projected vertices.

Also (unless I missed it in your code), at some point you'll probably want to add a check for degenerate cross products.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this