Separating Axis Theorem

This is a discussion on Separating Axis Theorem within the Game Programming forums, part of the General Programming Boards category; I'm currently working on a 2d, vector based game engine. Specifically, the collision detection/response parts. I thought the separating axis ...

  1. #1
    Registered User
    Join Date
    May 2005
    Location
    Sweden
    Posts
    16

    Separating Axis Theorem

    I'm currently working on a 2d, vector based game engine. Specifically, the collision detection/response parts.

    I thought the separating axis theorem would work well for detection, as it is simple and fast to perform on AABB's (axis aligned bounding boxes), OBB's (oriented bounding boxes) and any other convex hull. You also get the MTD (minimum translation distance) fairly easily when doing the collision detection.

    I've got all this nice and working already, so my actual question is: how would one perform a SAT collision check on convex shapes that can not be described by a finite number of points, ie circles, ellipses and maybe even closed splines (if it doesn't prove too slow).

    If it is unreasonably slow to perform these checks, I would of course simply approximate the curved collision geometries with polygonal geometries instead.

    I've come to understand you need the voronoi regions of the "normal" object to accurately detect collisions between "curved" and non-curved objects. Hower, I cannot quite seem to grasp how to calculate and use these regions in practice.

    Also, how would collision between two curved objects be detected?

    Any help on the way to figure out these problems will be greatly appreciated. And if you know any good link(s) about physically correct collision responses (prefferably in 2d) and/or swept collision detection, that would also be appreciated.

    Pseudo-code or real code is preferred to mathematical notation, please.

    Thanks in advance,
    Kenki

  2. #2
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,590
    As far as games go they don't calculate collisions between curved objects. They approximate collisions between the normals of the plane's that are created by the triangle(s) in question and they use the dot product to determine the glancing angle as well as to see if the object has interpenetrated or not.

    The actual physics for the objects is computed by a totally seperate engine running at a totally different framerate. The physics for the objects is actually easier than the actual process of collision detection.

    There are no true curved objects inside of 3D graphics. They are approximated curves and you approximate the collision by approximating on the curve's facets...or the surfaces created by the imperfections in the curve.

  3. #3
    Registered User
    Join Date
    May 2005
    Location
    Sweden
    Posts
    16
    Well, thanks for the reply, however... I don't mean to be rude, but did you actually read my post? It is not a 3d game engine, it's 2d.

    I figured that the performance saved in reducing the number of dimensions could be spent on more accurate collision detection and/or physics.

    I have seen this done to some extent in even flash games, so I cannot imagine that, say, a perfect circle is too expensive/complex to use. I mean, flash is hardly as fast as C/C++

  4. #4
    S Sang-drax's Avatar
    Join Date
    May 2002
    Location
    Göteborg, Sweden
    Posts
    2,072
    Collision between two circles is easy. Just measure the distance between the center points.

    I don't know of an easy way to do collision detection between bezier curves/splines, but remember that a bezier curve will always be bounded by the convex hull of its control points.
    Last edited by Sang-drax : Tomorrow at 02:21 AM. Reason: Time travelling

  5. #5
    Registered User
    Join Date
    May 2005
    Location
    Sweden
    Posts
    16
    Thanks. Unfortunately, those were things I already knew... What I want help to figure out, is how to do collision detection with:

    1) Two objects of more complex shapes than a circle (if it seems plausible) and
    2) Detection between any curved object and a normal one

    What I have thus far:
    Let's call the polygon based object A, and the curved one B. Then, when the feature of A that is closest to B is an edge, it is not too difficult, you just do normal SAT detection using B's bounding box.

    However, if the feature of A that is closest to B is a point, you have to calculate another projection direction, one that is perpedicular to the vector from the point in A to the point in B's curve closest to the same point in A. Once you have the projections along this vector it's easy.

    I think something like that would work for collision between two curved objects as well.

    So, what I haven't grasped yet, is how to calculate the feature of an object closest to another object and calculating the point on a curve closest to some other point (for a circle this is very easy, of course). Given some help with these, I should be able to figure the rest out myself.

    As I said before, if doing this with more complex shapes gets too bothersome, I'll simply use an approximation with polygons.

  6. #6
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,590
    Did you read my post?

    Don't do collision detection on curves. Period. Case closed. It's a waste of time in 2D or 3D. You can approximate these just as well with other shapes and other methods.

    Seems you already know everything so why ask us?

  7. #7
    Registered User
    Join Date
    May 2005
    Location
    Sweden
    Posts
    16
    Right, then I'll give up on exactly calculated curved object collision. However, I cannot imagine circles being too expensive to use. As I said, it has been done in even flash... Although that was only with AABB's and circles, not an arbitrary polygon, so I might be wrong.

    And no, I don't know everything. That's why I was asking
    Also, some of the things in my last post I figured out after my first post. I don't just sit idly waiting for replies...

    I still haven't figured out how to determine the feature of an object closest to another object, though, so any pointers are still welcome.

    By the way, Bubba, if physics calculations are so much easier, might you be willing to link to some good information? I can't seem to find any really good sources myself, so that would be highly appreciated.

  8. #8
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,590
    Circles are used as bounding spheres only. You were talking about curves which does not neccessitate they form a circle. Bounding spheres are easy because of what has already been posted. The distance is very simple to calculate and you can work in terms of the square of the distance so you never have to use the square root function.

    So if your bounding sphere is 100 units from left side to right side, top to bottom then you know that when an object comes within that sphere you have a possible hit. This would be your trivial rejection code and if it passed then you might move on to something more precise and more expensive. To test simply subtract the bounding sphere center of the colliding object from the center of the bounding sphere and square the components. If the result is equivalent to or less than (100*100) then you have a possible collision.

    For physics information and how to implement it into a game, consult Physics for Game Developers available at www.amazon.com. Very good book.

  9. #9
    Registered User
    Join Date
    May 2005
    Location
    Sweden
    Posts
    16
    Perhaps I was a bit diffuse with my question... When saying curved I included circles and actually meant them quite in particular. Though, I suppose that wasn't too clear.

    However, I'm not quite as convinced as you that circles are not used for collision detection in games, as N claim to do just that (scroll down a little bit to see an interactive flash demo of collision detection between a circle and an AABB) and is indeed a game.

    Anyway, thanks for the book-tip (already on the way ) and your time. In the end, I think I'll just do as you say and stay away from circles (other than as bounding ones).

  10. #10
    vae victus! skorman00's Avatar
    Join Date
    Nov 2003
    Posts
    594
    Circles and spheres are commonly used for collision detection in todays games. And don't be discouraged to use wacky curves either. No, they're not commonly used, but that's not to say it's impossible.

    For convex objects, it would be wise to have multiple bounding volumes. Have one big volume (sphere, box, whatever) that surrounds everything, then some number of volumes that encompass different sections of the object. This is a very common and easy set up.

  11. #11
    Registered User
    Join Date
    May 2005
    Location
    Sweden
    Posts
    16
    Thanks for making me stick with it skorman, 'cause I think I solved it . Well, for colliding circles with arbitrary, convex polygons at least.

    I have no proof yet, though it passes my initial (perhaps not so exhaustive) tests. I also think it should be possible to speed it up further...

    If anyone's interested, I'll post how I did it.

  12. #12
    Registered User
    Join Date
    Dec 2002
    Posts
    56
    Quote Originally Posted by Kenki
    If anyone's interested, I'll post how I did it.
    Please do, thanks

  13. #13
    Registered User
    Join Date
    May 2005
    Location
    Sweden
    Posts
    16
    Right, then... I'll assume you know basic vector maths (dot products in particular... both how to calculate them and what they mean) and also how to perform a normal SAT test with polygons. Check the tutorial linked to earlier in the thread (and at the bottom of this post) for information about that. Not the best tutorial perhaps, but with some googling there should be no problem.

    Here is some pseudo code describing how to do collision between convex polygons and circles:

    Code:
    bool CircleVsPolygonTest(circle circ, polygon poly)
    {
        /* First, make a poly vs poly test, treating the circle as an AABB with
         * width == height == radius
         */
        if(!PolyVsPolySATTest(circ, poly))
        {
        	/* If no collision was detected in the simple alogirithm, there cannot have been one:
        	 * that's because the aabb the circle was treated like is in fact its actual bounding
        	 * box. So just return false here
        	 */
        	return false;
        }
        
        // Otherwise, we have to make som more tests
        else
        {
        	/* Basically we need to determine what feature of poly lies
        	 * closest to circ. If it is an edge, then a collision is guarenteed,
        	 * otherwise a last check is needed. So, how do we check if an edge or a point lies
        	 * closest? Start with finding the point in poly that lies closest to circ's centre...
        	 */
        	int pointidx = poly.getClosestPointTo(circ.centre);
        	 
        	/* Next step is to check where circ's centre lies in relation to poly, specifically
        	 * where it lies when considering the two edges of poly that include the point
        	 * we just found.
        	 *
        	 *
        	 * As the poly's verts are stored in the order they make up the edges,
        	 * getting the two closest edges is easy
        	 */
        	Vector edge = normalize(poly.vert(pointidx-1)-poly.vert(pointidx));
        	
            /* Now, we project the circle's centre and the polygon to the 1d space defined by
             * the edge's plane
             */
            double circle_p = dotproduct(circ.centre, edge);
            
            /* These are the largest and smallest values found by projecting all of
             * the polygon's vertices
             */
            double poly_start_p = poly.minProjection(edge);
            double poly_end_p = poly.maxProjection(edge);
            
            if(poly_start_p < circle_p && poly_end_p > circle_p)
            {
                /* The circle's centre lies closer to this edge than it does to the point,
                 * so there is no need to check anything else... the initial simple test was correct.
                 */
                 
                 return true;
            }
            
            // Get the other edge
            edge = normalize(poly.vert(pointidx+1)-poly.vert(pointidx));
            
            // More of the same as above...
            circle_p = dotproduct(circ.centre, edge);
            poly_start_p = poly.minProjection(edge);
            poly_end_p = poly.maxProjection(edge);
            
            if(poly_start_p < circle_p && poly_end_p > circle_p)
            {
                return true;
            }
            
            /* So... now we know that the feature of poly that lies closest to circ
             * is the same point we found earlier. Now we just need to see if they collide
             * on the plane described by the vector between circ's centre and that same point.
             */
            edge = normalize(poly.vert(pointidx) - circ.centre);
            
            // This time we project the entire circle
            double circ_start_p = circ.minProjection(edge);
            double circ_end_p = circ.maxProjection(edge);
            poly_start_p = poly.minProjection(edge);
            poly_end_p = poly.maxProjection(edge);
            
            // Check if there is NOT a collision in 1d...
            if(circ_start_p > poly_end_p || circ_end_p < poly_start_p)
                return false;
            
            // We have a collision    
            else
                return true;
    }
    With the help of this tutorial, you should be able to figure the rest out yourself.

    As far as I can tell, this should work for any convex polygon. I suppose it might work in 3d as well, though I've not made any tests in 3d, nor have I really thought about it.

  14. #14
    Registered User
    Join Date
    May 2005
    Location
    Sweden
    Posts
    16
    Couldn't find any edit function... Suppose you can't edit after a certain period of time has passed?

    Anyway, I realized I forgot to mention one thing in the pseudo code...

    Code:
    /* Basically we need to determine what feature of poly lies
         * closest to circ. If it is an edge, then a collision is guarenteed,
         * otherwise a last check is needed. So, how do we check if an edge or a point lies
         * closest? Start with finding the point in poly that lies closest to circ's centre...
         */
        int pointidx = poly.getClosestPointTo(circ.centre);
    should have been
    Code:
    /* Basically we need to determine what feature of poly lies
         * closest to circ. If it is an edge, then a collision is guarenteed,
         * otherwise a last check is needed. So, how do we check if an edge or a point lies
         * closest? Start with finding the point in poly that lies closest to circ's centre 
         * and lies closer to circ's centre than poly's own centre does
         */
        int pointidx = poly.getClosestPointTo(circ.centre);
    Also, all of the normalizations are useless... Don't know why I wrote them in the first place. They don't really harm the outcome of the algorithm, though, only its performance.

    [edit]Actually, that was not quite what I meant... The "closest" point does not need to be closer than the centre, only part of the edge that is closer. Use the sign of the dot product of (point_to_compare-poly_centre) and (circle_centre-poly_centre) to see which side the point is on[/edit]
    Last edited by Kenki; 05-19-2005 at 07:31 PM.

  15. #15
    Super Moderator VirtualAce's Avatar
    Join Date
    Aug 2001
    Posts
    9,590
    I fail to see why you are using the dot product for such a simple task. 2D collision detection can be done quite nicely with AABB's and/or simple bounding boxes/spheres.

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. 3 axis accelerometer calculations
    By Thantos in forum Tech Board
    Replies: 1
    Last Post: 09-05-2008, 04:26 AM
  2. need help making a dot bounce up and down y axis in this prog
    By redwing26 in forum Game Programming
    Replies: 10
    Last Post: 08-05-2006, 12:48 PM
  3. AXIS and C++
    By bman1176 in forum C++ Programming
    Replies: 0
    Last Post: 03-29-2006, 10:00 AM
  4. Graph axis
    By fkheng in forum C Programming
    Replies: 2
    Last Post: 07-25-2003, 07:03 AM
  5. separating line of arrays into array of arrays
    By robocop in forum C++ Programming
    Replies: 3
    Last Post: 10-20-2001, 12:43 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21