Thread: Separating Axis Theorem

  1. #1
    Registered User
    Join Date
    Oct 2006
    Posts
    55

    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.

  2. #2
    Registered User
    Join Date
    Mar 2002
    Posts
    125
    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 View Post
    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.
    Typing stuff in Code::Blocks 8.02, compiling stuff with MinGW 3.4.5.

  3. #3
    Registered User
    Join Date
    Oct 2006
    Posts
    55
    ah ok thanks, i'll try to find a different tutorial on collision detection

  4. #4
    Registered User
    Join Date
    Mar 2002
    Posts
    125
    This one might be good, I dunno. I only read like half a page.
    Typing stuff in Code::Blocks 8.02, compiling stuff with MinGW 3.4.5.

  5. #5
    Registered User
    Join Date
    Oct 2006
    Posts
    55
    i've decided to do my collision detection using the center points of my objects

  6. #6
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    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.

    ...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.

    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.
    Last edited by VirtualAce; 07-13-2011 at 09:25 PM.

  7. #7
    Registered User
    Join Date
    Mar 2002
    Posts
    125
    Quote Originally Posted by VirtualAce View Post
    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 View Post
    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.
    Typing stuff in Code::Blocks 8.02, compiling stuff with MinGW 3.4.5.

  8. #8
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    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.

  9. #9

    Join Date
    May 2005
    Posts
    1,042
    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.

    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.
    I'm not immature, I'm refined in the opposite direction.

  10. #10
    Registered User VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,607
    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/
    Last edited by VirtualAce; 07-26-2011 at 09:21 PM.

  11. #11

    Join Date
    May 2005
    Posts
    1,042
    Those are good links.
    I'm not immature, I'm refined in the opposite direction.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Pythagorean Theorem Program Comment, criticize, or whatever
    By Sshakey6791 in forum C++ Programming
    Replies: 7
    Last Post: 02-13-2009, 02:48 AM
  2. Separating Axis Theorem
    By Kenki in forum Game Programming
    Replies: 20
    Last Post: 05-22-2005, 11:49 AM
  3. Pythagorans theorem
    By Dummies102 in forum C++ Programming
    Replies: 2
    Last Post: 02-20-2002, 01:46 PM
  4. Galois Theorem
    By DavidP in forum A Brief History of Cprogramming.com
    Replies: 0
    Last Post: 01-06-2002, 06:20 PM
  5. David's CProgramming Theorem
    By DavidP in forum A Brief History of Cprogramming.com
    Replies: 10
    Last Post: 08-14-2001, 12:29 AM