Separating Axis Theorem

Hi guys, I found an example of collision detection on this page (section 3): http://www.geometrictools.com/Docume...ratingAxes.pdf

Code:

---


    int WhichSide(PointSet S, Point D, Point P)
    {
        // S vertices are projected to the form P+t*D. Return value is +1 if all t > 0,
        // -1 if all t < 0, 0 otherwise, in which case the line splits the polygon.
        positive = 0; negative = 0;
        for (i = 0; i < C.N; i++)
        {
            t = Dot(D,S.V(i)-P);
            if(t>0)
            {
                positive++;
            }
            else if(t<0)
            {
                negative++;
            }
            if(positive && negative)
            {
                return 0;
            }
        }
        return (positive ? +1 : -1);
    }
    bool TestIntersection2D (ConvexPolygon C0, ConvexPolygon C1)
    {
        // Test edges of C0 for separation. Because of the counterclockwise ordering,
        // the projection interval for C0 is [m,0] where m <= 0. Only try to determine
        // if C1 is on the ‘positive’ side of the line.
        for (i0 = 0, i1 = C0.N-1; i0 < C0.N; i1 = i0, i0++)
        {
            D = Perp(C0.V(i0) - C0.V(i1));
            if(WhichSide(C1.V,D,C0.V(i0)) > 0)
            { // C1 is entirely on ‘positive’ side of line C0.V(i0)+t*D
                return false;
            }
        }
        // Test edges of C1 for separation. Because of the counterclockwise ordering,
        // the projection interval for C1 is [m,0] where m <= 0. Only try to determine
        // if C0 is on the ‘positive’ side of the line.
        for (i0 = 0, i1 = C1.N-1; i0 < C1.N; i1 = i0, i0++)
        {
            D = Perp(C1.V(i0) - C1.V(i1));
            if (WhichSide(C0.V,D,C1.V(i0)) > 0)
            { // C0 is entirely on ‘positive’ side of line C1.V(i0)+t*D
                return false;
            }
        }
        return true;
    }

---

I'm wondering if someone could help me understand this code. I know the basics of collision detection and SAT, but I have a few questions.

what is C.N in the top for statement? what is V in the code a little further down. Does this code use an objects vertex position or it's center position?

thanks.

As far as I can tell that C.N is a typo and should be S.N (i.e. the number of points in S). S.V is probably an array of points with length S.N.

Quote:

---

Originally Posted by Astra

Does this code use an objects vertex position or it's center position?

---

All this code does is check whether two convex 2d polygons (given by the absolute coordinates of the points making them up in counterclockwise order) overlap or not. It doesn't really deal with objects.

ah ok thanks, i'll try to find a different tutorial on collision detection :(

This one might be good, I dunno. I only read like half a page. :)

i've decided to do my collision detection using the center points of my objects

Separating axis theorem is adequate for any trivial rejection test in a collision detection system. I have used it and found it to be reliable and it never misses a possible collision. Of course you would want to do more precise and expensive tests once this test passed but it is a very good start.

Quote:

---

...It doesn't really deal with objects.

---

What does this mean? Most objects will have AABB's, OOBB's, and/or collision meshes. You would never test the extremely detailed render mesh for collision so I'm not sure why you say the algorithm is not meant for objects? Objects really come down to pieces that occupy 3D space and that space is described by AABBs, OOBBs, and/or collision meshes. You can also use separating axis theorem on OOBBs. Gamasutra has a very good article on this theorem as well as example code.

Quote:

---

All this code does is check whether two convex 2d polygons (given by the absolute coordinates of the points making them up in counterclockwise order) overlap or not.

---

Actually the theorem can be used both in 2D and 3D. As well it does not test if two objects overlap but more 'when' they overlap. Because it tests the 'when' instead of the 'if' it is more accurate. It tests whether object A and object B collided at any point between time T and T2. If they did not collide IE: the interval is infinite it reports that. If they do collide it reports the separation distance and/or time interval at which they did collide. The point of collision then is a simple linear interpolation along the velocity vector of A.

So if A(t) is the position of object A at time T and A(t2) is the position of object A at time t2 and the interval of collision is 0.5 then the point of collision is A(t) + 0.5 * (A(t2) - A(t)).
Remember that A(t2) is A(t) + A.velocityVector * (t2 - t). It is a very good algorithm and I highly recommend it to anyone looking for a good and fast trivial rejection test.

Quote:

---

Originally Posted by VirtualAce

What does this mean?

---

It means precisely what it says: the code doesn't deal with objects. Which is not the same as "The code is not meant to deal with objects".
Obviously you can associate a polygon with a game object and pass those polygons into this function to detect whether two objects collide, but the code doesn't care whether the polygons are associated with a cat or a tree or a spaceship; it just checks whether two polygons overlap.

Quote:

---

Originally Posted by VirtualAce

Actually the theorem can be used both in 2D and 3D.

---

Yes, it can. However this code checks whether two convex polygons overlap. It also doesn't do anything with movement or calculating when objects collide. I'm sure how to do this is covered later in the tutorial, but this code doesn't do it.

Does the code have to care about the owners of the convex polygons? This code does not fully implement the separating axis theorem for sure but to say it does not deal with objects is a bit of a broad statement. Another system could maintain the objects and pass their convex collision mesh, AABB, or OOBB's to a function that only performed the separating axis theorem on them. A collision function does not need to know anything about the objects. A collision response function would need to know much more.

I thought the tenet of SAT was to project points, whether they're from a bounding box or polygons, onto a characteristic axis then measure distances.

Quote:

---

what is C.N in the top for statement? what is V in the code a little further down. Does this code use an objects vertex position or it's center position?

---

Perhaps collision normal and velocity.

Indeed it projects the edges of objects along a line or axis and then tests the intersection or overlap along that line or axis. I'm sure you have used it Bob but there is more info on Gamasutra about it as well as some examples of ways to use it. Several graphics books also discuss this approach and show several ways to use it and/or implement it. It is supposed to test when T(enter) happens which is the first time of collision. From there given the velocity vector of the object you can calculate the exact point of intersection.

http://www.gamasutra.com/view/featur...es.php?print=1
http://www.gamasutra.com/view/featur...n_.php?print=1
http://www.gamasutra.com/view/featur..._new_year_.php
http://www.gamasutra.com/view/featur...s_collide_.php

Book source code d/l page that shows one sample implementation of the algorithm.
http://www.gamemath.com/downloads.htm

Link to the book on amazon:
http://www.amazon.com/exec/obidos/ASIN/1556229119/

Those are good links.