Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

OvRLoRD

separating axis test

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

I''m interested in doing OBB collision, and i''ve been told the easiest way to do this is using separating axis tests. I understand what it is, but not quite sure how to accomplish it. Thanks ~OvR

Share this post


Link to post
Share on other sites
Advertisement
simple stuff. If you understand it already, even better.


you need axes to tes, right? For OBB vs OBB, you need 15 axes.

Box0.Dir[0]
Box0.Dir[1]
Box0.Dir[2]

Box1.Dir[0]
Box1.Dir[1]
Box1.Dir[2]

Box0.Dir[0] x Box1.Dir[0]
Box0.Dir[0] x Box1.Dir[1]
Box0.Dir[0] x Box1.Dir[2]

Box0.Dir[1] x Box1.Dir[0]
Box0.Dir[1] x Box1.Dir[1]
Box0.Dir[1] x Box1.Dir[2]

Box0.Dir[2] x Box1.Dir[0]
Box0.Dir[2] x Box1.Dir[1]
Box0.Dir[2] x Box1.Dir[2]



for each axes, you project the box on the axes, calculate the extent of the box on that axis. Then you see if the extents of the two boxes overlap.



// tests if two extents overlap

bool ExtentsOverlap(float min0, float max0, float min1, float max1)
{
return !(min0 > max1 || min1 > max0);
}

// compute the extents of one box agaisnt one vector

void ComputeBoxExtents(Vector Axis, OBBox Box, float& min, float &max)
{
float p = Box.Position.Dot(Axis);

float r0 = fabs(Box.Dir[0],Dot(Axis)) * Box.HalfSize.x;
float r1 = fabs(Box.Dir[1],Dot(Axis)) * Box.HalfSize.y;
float r2 = fabs(Box.Dir[2],Dot(Axis)) * Box.HalfSize.z;

float r = r0+r1+r2;

min = p-r;
max = p+r;
}

bool AxisOverlap(Vector Axis, OBBox Box0, OBBox Box1)
{
float min0, max0;
float min1, max1;

ComputeBoxExtents(Axis, Box0, min0, max0);
ComputeBoxExtents(Axis, Box1, min1, max1);

return ExtentsOverlap(min0, max0, min1, max1);
}

bool BoxBoxIntersect(OBBox Box0, OBBox Box1)
{
if (!AxisOverlap(Box0.Dir[0], Box0, Box1)) return false;
if (!AxisOverlap(Box0.Dir[1], Box0, Box1)) return false;
if (!AxisOverlap(Box0.Dir[2], Box0, Box1)) return false;

if (!AxisOverlap(Box1.Dir[0], Box0, Box1)) return false;
if (!AxisOverlap(Box1.Dir[1], Box0, Box1)) return false;
if (!AxisOverlap(Box1.Dir[2], Box0, Box1)) return false;

if (!AxisOverlap(Box0.Dir[0].Cross(Box1.Dir[0]), Box0, Box1)) return false;
if (!AxisOverlap(Box0.Dir[0].Cross(Box1.Dir[1]), Box0, Box1)) return false;
if (!AxisOverlap(Box0.Dir[0].Cross(Box1.Dir[2]), Box0, Box1)) return false;

if (!AxisOverlap(Box0.Dir[1].Cross(Box1.Dir[0]), Box0, Box1)) return false;
if (!AxisOverlap(Box0.Dir[1].Cross(Box1.Dir[1]), Box0, Box1)) return false;
if (!AxisOverlap(Box0.Dir[1].Cross(Box1.Dir[2]), Box0, Box1)) return false;

if (!AxisOverlap(Box0.Dir[2].Cross(Box1.Dir[0]), Box0, Box1)) return false;
if (!AxisOverlap(Box0.Dir[2].Cross(Box1.Dir[1]), Box0, Box1)) return false;
if (!AxisOverlap(Box0.Dir[2].Cross(Box1.Dir[2]), Box0, Box1)) return false;

return true;
}


additionaly, you can find the amount of overlap and the distance of overlap, by selecting the non-degenerate axis with the minimum overlap.


bool AxisOverlap(Vector Axis, OBBox Box0, OBBox Box1, float& min0, float& max0, float& min1, float& max1)
{
ComputeBoxExtents(Axis, Box0, min0, max0);
ComputeBoxExtents(Axis, Box1, min1, max1);

return ExtentsOverlap(min0, max0, min1, max1);
}

bool BoxBoxIntersect(OBBox Box0, OBBox Box1, Vector& Ncoll, float& dcoll)
{
Vector Axis[15];
float min0[15], max0[15], min1[15], max1[15];

Axis[0] = Box0.Dir[0]; if (!AxisOverlap(Axis[0], Box0, Box1, min0[0], max0[0], min1[0], max1[0])) return false;
Axis[1] = Box0.Dir[1]; if (!AxisOverlap(Axis[1], Box0, Box1, min0[1], max0[1], min1[1], max1[1])) return false;
Axis[2] = Box0.Dir[2]; if (!AxisOverlap(Axis[2], Box0, Box1, min0[2], max0[2], min1[2], max1[2])) return false;

///.......

/// ect for the other 12 axes....



/// calculate the best candidate for a separation axis

if (!FindSeparationAxis(Axis, min0, max0, min1, max1, 15, Ncoll, dcoll)) return false;

/// make sure the normal is pointing the right way

/// the normal should point towards box0

Vector D = Box1.Position - Box0.Position;
if (D * Ncoll < 0.0f)
Ncoll *= -1.0f;

return true;
}



bool FindSeparationAxis(Vector *Axis, float* min0, float* max0, float* min1, float* max1, int NumAxes, Vector& Ncoll, float& dcoll)
{
float dmin;
float iminaxis = -1;

for(int i = 0; i < NumAxes; i ++)
{
// compute theintersection of the two extents on that axis

float min = (min0[i] > min1[i])? min0[i] : min1[i];
float max = (max0[i] < max1[i])> max1[i] : max0[i];
float d = max - min; // intersection amount


// extents not intersecting? surely this is wrong

if (d < 0.0f)
Assert("Error. Box should not be separated at this stage.");
float axis_length = Axis[i].Length();

// degenerate axis? then skip the axis

if (axis_length < 0.000000001f)
continue;

// normalise the overlap amount on that axis, so we can compare them

d /= axis_length;

// this is the separation axis with minimum depth found so far

if (d < dmin)
{
dmin = d;
Ncoll = Axis[i] / axis_length; // normalise normal

dcoll = d;
iminaxis = i; // signal we found a solution

}
}
// we failed to find a separation axis. probably because one of the box is completely degenerate (size or axes of the box are garbage)

if (iminaxis == -1)
Assert("Failed to find a separation axis.");

return true;
}



[edited by - oliii on January 13, 2004 4:52:30 AM]

Share this post


Link to post
Share on other sites
you can apply the same algorithm to find overlaps between triangles and triangles, or boxes and triangles. The only things that changes for triangles, is their extent calculation along an axis, and the number of axes. for Tri vs OBB, I think it is 13 axes, and Tri vs tri, it''s 11.

tri vs tri axes
---------------
tri0.normal
tri1.normal

tri0.edge0 x tri1.edge0
tri0.edge0 x tri1.edge1
tri0.edge0 x tri1.edge2

tri0.edge1 x tri1.edge0
tri0.edge1 x tri1.edge1
tri0.edge1 x tri1.edge2

tri0.edge2 x tri1.edge0
tri0.edge2 x tri1.edge1
tri0.edge2 x tri1.edge2


box vs tri axes
---------------
tri.normal
box.dir0
box.dir1
box.dir2

box.dir0 x tri.edge0
box.dir0 x tri.edge1
box.dir0 x tri.edge2

box.dir1 x tri.edge0
box.dir1 x tri.edge1
box.dir1 x tri.edge2

box.dir2 x tri.edge0
box.dir2 x tri.edge1
box.dir2 x tri.edge2

Share this post


Link to post
Share on other sites
and obviously, there are lots of optimisations to reduce the amounts of calcualtions. You end up with quite a small amount of calculations in the end.

Share this post


Link to post
Share on other sites
note. there are a few typos in the first post, but since the edit function screws up with two boxes of source code, I''d rather not touch the post again.

Share this post


Link to post
Share on other sites
Your triangle/triangle case is for non-planar triangles right?

Because if they had the possibility of being planar the test would look like this:

tri0.norm
tri1.norm

tri0.edg1 x tri1.edg1
tri0.edg1 x tri1.edg2
tri0.edg1 x tri1.edg3
tri0.edg1 x tri1.norm

add nausea...

Share this post


Link to post
Share on other sites
yeah, for non-planar triangles.

as for general cases, the separating axes are,

- shape0.face_normal(i)
- shape1.face_normal(j)
- combination of shape0.edge(i) x shape1.edge(j)

I'm in the process of writing a demo, basically, a bunch of OBBs and ABBs moving about the place. similar to the pong/breakout demo I wrote for the recent flipcode "Code Of The Day".

The next step will be to compute points of intersection, so I can combine it with another simplistic rigid body demo, so the boxes will rotate as well as translate.

[edited by - oliii on January 16, 2004 5:40:15 AM]

Share this post


Link to post
Share on other sites
you only need to test segment normals, for triangle, boxes, .... everything type of 2D convex polygons.

in code, the axes of separation will be

Vector2(-shape0.edge(i).y, shape0.edge(i).x);
...
...
...
Vector2(-shape1.edge(j).y, shape1.edge(j).x);

Share this post


Link to post
Share on other sites
so if i wanted to test a triangle and a square in 2D, all i would need to test would be


square.dir0 x tri.edge0
square.dir0 x tri.edge1
square.dir0 x tri.edge2

square.dir1 x tri.edge0
square.dir1 x tri.edge1
square.dir1 x tri.edge2

or is there something i'm missing?

[edited by - OvRLoRD on January 16, 2004 6:17:52 PM]

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!