Thread: 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

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.

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

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.

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?

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.

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.

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

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.

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.

Originally Posted by Kenki

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

Please do, thanks

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.

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.