🔒 Locked 🎮 Unity

OBB-Triangle Intersection

Started by Paul7 Jun 3, 2005 at 1:36 PM 6 replies 7.6k views

Original Post

Jun 3, 2005 at 1:36 PM

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 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? - I`d prefer not to have to do this method. Any help on this would be much appreciated? Thanks

oliii

Jun 3, 2005 at 2:55 PM

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

glSmurf

Jun 4, 2005 at 8:33 AM

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) =)

Charles B

Jun 4, 2005 at 9:30 AM

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.

oliii

Jun 4, 2005 at 10:52 AM

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.

Paul7

Jun 6, 2005 at 7:22 AM

Thanks for all the replies,

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

Cheers.

Paul7

Jun 21, 2005 at 12:13 PM

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

Zakwayda

Jun 21, 2005 at 12:52 PM

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.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.