OBB-Triangle Intersection - GameDev.Net Discussion Forums

Add Forum to Favorites | Send Topic To a Friend | View Forum FAQ | Track this topic

Last Thread Next Thread

OBB-Triangle Intersection

Paul7 Member since: 1/10/2004 From: Sheffield, United Kingdom

Posted - 6/3/2005 2:36:40 PM

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

User Rating: 1049 | Rate This User

Report this Post to a Moderator | Link

oliii GDNet+ Member since: 3/21/2003 From: Ill be back before breakfast

Posted - 6/3/2005 3:55: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

That's the coolest thing since the mullet!

User Rating: 1867 | Rate This User

Report this Post to a Moderator | Link

glSmurf Member since: 12/7/2004 From: Vasteras, Sweden

Posted - 6/4/2005 9:33:46 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) =)

User Rating: 1080 | Rate This User

Report this Post to a Moderator | Link

Charles B Member since: 1/17/2002 From: France

Posted - 6/4/2005 10:30:58 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.

User Rating: 1506 | Rate This User

Report this Post to a Moderator | Link

oliii GDNet+ Member since: 3/21/2003 From: Ill be back before breakfast

Posted - 6/4/2005 11:52:34 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.

User Rating: 1867 | Rate This User

Report this Post to a Moderator | Link

Paul7 Member since: 1/10/2004 From: Sheffield, United Kingdom

Posted - 6/6/2005 8:22:13 AM

Thanks for all the replies,

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

Cheers.

User Rating: 1049 | Rate This User

Report this Post to a Moderator | Link

Paul7 Member since: 1/10/2004 From: Sheffield, United Kingdom

Posted - 6/21/2005 1:13:07 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[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;
}

User Rating: 1049 | Rate This User

Report this Post to a Moderator | Link

jyk GDNet+ Member since: 10/23/2003

Posted - 6/21/2005 1:52:46 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.

User Rating: 1984 | Rate This User

Report this Post to a Moderator | Link

All times are ET (US)

Last Thread Next Thread

Forum Rules:

You may not post new threads
You may not post replies
You may not edit your posts
You may not use HTML in your posts

Jump To: