# OBB-Triangle Intersection

This topic is 4959 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Ive 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. Ive found lots of source for AABB-triangle intersections but none for OBBs. Im 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? - Id prefer not to have to do this method. Any help on this would be much appreciated? Thanks

##### Share on other sites
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 on other sites
transform the triangle into obb space and deal with it as an aabb-tri collision test

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 on other sites
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 on other sites
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 on other sites

Thanks for all the replies,

Got it working using SAT as oliii described in his first reply.

Cheers.

##### Share on other sites

Having peformed some more tests on my apparently working test, Ive 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 - 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;

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.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 on other sites
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.

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 10
• 11
• 13
• 9
• 11
• ### Forum Statistics

• Total Topics
634090
• Total Posts
3015432
×

## Important Information

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!