#### Archived

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

# separating axis test

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

## 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 on other sites
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 overlapbool ExtentsOverlap(float min0, float max0, float min1, float max1){    return !(min0 > max1 || min1 > max0);}// compute the extents of one box agaisnt one vectorvoid 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 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 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 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 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

##### 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 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 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]

1. 1
Rutin
26
2. 2
3. 3
4. 4
5. 5

• 11
• 9
• 9
• 9
• 14
• ### Forum Statistics

• Total Topics
633312
• Total Posts
3011310
• ### Who's Online (See full list)

There are no registered users currently online

×