gbadev.org forum archive

This is a read-only mirror of the content originally found on forum.gbadev.org (now offline), salvaged from Wayback machine copies. A new forum can be found here.

Beginners > A Box-Plane Intersection Test

#39530 - Celeryface - Sun Apr 10, 2005 1:03 am

I'm trying to implement this algorithm for testing a box-plane intersection. Has anyone done this before?

In the algorithm it states the box and plane are overlapping when:

|d| <= a1 |n.A1| + a2 |n.A2| + a3 |n.A3|

http://www.gamasutra.com/features/19991018/Gomez_7.htm

Does anyone know what a1, a2, a3 are? I'm thinking A1, A2, A3 are the axes of the box.

Thanks in advance. :)

#39535 - sajiimori - Sun Apr 10, 2005 2:15 am

I don't know what those letters mean, but if you get the pair of box corners that are futhest along and furthest against the plane's normal, and they are on opposite sides of the plane, then there's an intersection
Code:


enum Axis
{
   AXIS_X,
   AXIS_Y,
   AXIS_Z,
   AXIS_NUM
};


enum Sign
{
   SIGN_NEG,
   SIGN_POS,
   SIGN_NUM
};


// Six box sides: left, right, bottom, top, back, front
typedef float Box[AXIS_NUM][SIGN_NUM];


Sign sign(float val)
{
   if(val < 0)
      return SIGN_NEG;
   else
      return SIGN_POS;
}


// A support point is a point on a convex shape (such as a box)
// furthest in the direction of the given vector.
Vector3 boxSupportPoint(Box box, Vector3 dir)
{
   Vector3 supportPoint;

   for(int axis = 0; axis < AXIS_NUM; ++axis)
      supportPoint[axis] = box[axis][sign(dir[axis])];

   return supportPoint;
}


float pointToPlaneDistance(Vector3 point, Plane plane)
{
   return dot(point, plane.normal) + plane.offset;
}


bool collideBoxPlane(Box box, Plane plane)
{
   return
      sign(pointToPlaneDistance(boxSupportPoint(box, plane.normal))) !=
      sign(pointToPlaneDistance(boxSupportPoint(box, -plane.normal)));
}

#39537 - Celeryface - Sun Apr 10, 2005 2:22 am

Is it as simple as checking each corner of the box, similar to how the centre of a sphere is tested for a sphere/plane intersection?

#39539 - sajiimori - Sun Apr 10, 2005 2:25 am

Thankfully you don't have to do all 8 dot products for the corners. The two support points are sufficient.

#39551 - tepples - Sun Apr 10, 2005 5:47 am

But given the fast ARM7TDMI multiply, wouldn't determining which points are support points take as much time as checking all 8 dot products?
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.

#39579 - Celeryface - Sun Apr 10, 2005 11:36 am

I found in another forum that the A's are the unit-length axes of the OBB. The small 'a's are the extents along those axes.

Does anyone know what is meant by 'extents'?

Also, is this test done in local space of the box -- where you'd have to transform the plane into the local space of the box?

The box has an OBB with its size defined as min(-1,-1,-1) and max(1,1,1). Are the unit-length axes defined by the box's rotation vector ie (0,180,0)?

#39587 - Celeryface - Sun Apr 10, 2005 3:47 pm

I believe the collision detection part is working now. Any ideas on how to find the collision point?

To find the collision point, I think it should be the distance between the centre of the box and the plane multiplied by the normal, but how do I include the orientation to find the collision point?

#39606 - sajiimori - Sun Apr 10, 2005 6:45 pm

Quote:
But given the fast ARM7TDMI multiply, wouldn't determining which points are support points take as much time as checking all 8 dot products?
Possibly. Writing optimized versions of each might make it clearer.
Quote:
Does anyone know what is meant by 'extents'?
The length, width, and height, each divided by 2.
Quote:
Also, is this test done in local space of the box -- where you'd have to transform the plane into the local space of the box?
My test is, yes. I didn't realize you were doing an oriented box.

#39682 - Celeryface - Mon Apr 11, 2005 12:10 pm

Would this test be done in degrees, or radians for the orientation of the box? Or would it work with both?

#39698 - Miked0801 - Mon Apr 11, 2005 3:15 pm

Neither - you'd use vectors for the edges and dot products for inclusion/exclusion checking.

#39704 - Celeryface - Mon Apr 11, 2005 3:35 pm

Miked0801 wrote:
Neither - you'd use vectors for the edges and dot products for inclusion/exclusion checking.


Right, but the vectors themselves would be constructed as unit vectors of their rotations.

#39712 - Miked0801 - Mon Apr 11, 2005 5:24 pm

I guess you could do it that way in which either rads or degs would work. Rotation/transform matrix doesn't care about units. Still, I believe that you'd be recontructing the normal vector when it moves/rotates to preserve accuracy. As you know, a little round off over a lot of time can kill you.