Thread: Separating Axis Theorem

Originally Posted by Bubba

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.

Acctualy I dissagree with "There are no true curves facets or surfaces". Nurbs are curves. Theyr are pure curves. Though no game supports them they are used alot im movies.

Originally Posted by Kenki

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.

Ok the only way I know of to find a collision between uneven surfaces would be to set a bunch of points around the objects then calculate the distance between them, and all the other objects. Make sure you use arrays. I cant really explain this through C++, but Iv done this before in Flash.

Lemme try and explain this more clearly.

Lets say you have a circle, and you want to find out when it collides with something like, lets say a square, but you want the collision detection to take note of the circles curves. Well first you need to set a desired amount of points around the circle so it makes a border of points. Lets call these points "Target Points". Then set Target Points around the square. All you have to do is calculate the distance between the target points, if their distance is 0, then they are colliding. You might want to put it all in an array that way it takes account of all the Target Points. I havent tested this is C++, but its pretty easy in flash.


Only other way to do the collision detection like that is Pixel Perfect Collision detection(Which I have no clue)

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.

Well... I fail to see why I shouldn't...

The reasons why I should?
1) It gives me the choice to use more accurate collision detection should I so desire. Or the choice not to. And choice is a good thing.
2) The AABB vs AABB and Circle vs Circle algorithms suffer no penalties from just having more accurate alogrithms (having != using). Thus there are no negative consequences.
3) For what I have in mind, only bounding spheres or bounding boxes is not enough. At the very least, I want triangle/triangle collision detection as well (which I have). You might argue I could approximate a circle with, say, 6 triangles in a triangle fan, but that might actually be slower (haven't run any profiler yet, but I intend to) while not offering the same precision.

So basically, there's no reason at all why I shouldn't, except maybe the time it takes to code. Which is not really an issue anymore, as I've already coded it.

Bladerunner627, what you suggest sounds like having a set of convex polygons (like triangles) approximate a concave object. I already do that, if that's what you mean? Depending on the amount of polygons used, it can give pretty accurate results (at the expense of performance of course). Per pixel collision is not really interesting, as the engine won't be sprite based.

You might argue I could approximate a circle with, say, 6 triangles in a triangle fan, but that might actually be slower (haven't run any profiler yet, but I intend to) while not offering the same precision.

you don't need to approximate a bounding circle, use a center point and a radius. You would only have to approximate like that if you want to draw it to the screen. It's more of a comfort question I think: are you more comfortable using the vectors or the other trig calculations?

Also, I wouldn't say that using vectors and dot products provides more accurate collision detection. However, they can be used to create accurate collison reactions easily. Not that it's hard with AABB's or spheres using algebra and trig.

I don't understand all the argument about 2D. Geez use a box and check against it. 3D is a lot more complex because you are dealing with volumes - hence depth. Dot product is extremely useful there, but I fail to see why we are even discussing such a simple task - I think you are making this far too complicated for simple 2D detection. This has been done in the past using well known, well-published techniques - use them.

When I said "approximate a circle with..." I didn't mean when colliding a circle with another circle, I meant when colliding it with a polygon. As it is, I don't need an approximation in either case. And I know there are easier ways to see if a circle collides with a convex shape but as far as I can tell, they do not allow for as easy calculation of the minimum translation distance needed to "uncollide" the objects.

And as for using just boxes, that might not be enough. Let's say I have a star shaped object boucing around... Using one bounding box (whether axis aligned or not), is simply not enough. It would look really weird if it bounced off an edge without ever touching it.
Using a bounding box for each point might work, but I'm not entirely sure... I will have to wait until I see it in action before I decide exatly which method(s) to use, which is basically the point of it all - I can choose and test.

I might just want some very complex objects rolling, bouncing or in some other way moving around, without being limited in the way collisions are handled. If I find that boxes are indeed sufficient, then I shall bow to your greater wisdom, Bubba. As it is, though, I want to see all methods in action before making a decision such as this.