2D Boxes

Seperating Axis Theorem works quite nicely for 2D boxes. If it's *just* boxes colliding, there are no 'special cases'. If you want to collide boxes with other shapes (still using SAT), it might require special cases. I made a SAT implementation a while back that could collide lines, points, boxes, and arbitrary convex polygons with no special cases. It could be extended to handle shapes with curves, too. Here's what I did:

Each different shape derives from a Shape class. Shapes have the member functions "GetAxises", "ProjectOntoAxis", and "CollideWith". GetAxis returns all axises (pleases tell me if that's the right plural for 'axis', I'm so confused about that) that need to be checked for collision of that shape in a list. ProjectOntoAxis takes an vector defining an axis, and projects all the points of shape onto the axis. Then, this is put into a "Projection" objects. Projection objects are little more than containers for this, but they also only store the far left and far right points for efficiency. Projections can be tested against eachother to see whether they collide.

"CollideWith" takes another Shape and calls GetAxises on it and itself. Then it loops through all the axises and calls ProjectOntoAxis for both itself and the other shape. It tests those two projections for collision.

That's about it. By supplying the axises in lists, any Shape can collide with any other Shape. I didn't see how efficient this was since I wrote it in Python and it was totally unoptimized.

Quote:

Original post by Ezbez Each different shape derives from a Shape class. Shapes have the member functions "GetAxises", "ProjectOntoAxis", and "CollideWith". GetAxis returns all axises (pleases tell me if that's the right plural for 'axis', I'm so confused about that) that need to be checked for collision of that shape in a list. ProjectOntoAxis takes an vector defining an axis, and projects all the points of shape onto the axis. Then, this is put into a "Projection" objects. Projection objects are little more than containers for this, but they also only store the far left and far right points for efficiency. Projections can be tested against eachother to see whether they collide.

Yeah, my SAT code is set up in a way similar to what Ezbez described. One of the nice things about the SAT is that if you're willing to forgo some potential optimizations, there are really no 'special cases' to speak of.

If the example code you're looking at makes it seem as if the algorithms are complex or there are a lot of special cases, it's probably because you're looking at code that's been optimized for specific pairs of shapes. Sometimes it's done this way for speed, but often it's just done this way because that's the only way the author knew how to do it! For example, the 'standard' AABB vs. AABB test is actually a special-case SAT test, but it's quite possible to write (or copy) this code with little or no understanding of how the SAT actually works.

Similarly, code for an OBB vs. OBB SAT test (especially in 3D) can be practically impenetrable when fully optimized to take advantage of the regularity of the shapes involved. Looking at such code will generally tell you very little about what the algorithm is really doing.

IMO, the SAT is probably the best solution, in terms of both stability and development time, for detecting intersections and computing contact information for polytopes in 2D. I would suggest studying up on the algorithm and writing the most generic implementation possible. It's highly unlikely that this will cause performance problems (unless you have many thousands of objects and/or your resources are very limited), and will give you greater flexibility in the sense that you'll be able to add other shapes (points, linear components, n-sided convex polygons) with ease.

One other comment. If you take the genericity of the implementation a step farther and parameterize everything by dimension, much if not all of the 2D code will work in 3D as well (with the addition of edge cross-product axis tests, of course).

(Oh, and I'm pretty sure the plural of axis is 'axes'.)

[Edited by - jyk on June 20, 2007 1:49:52 PM]

Ok, got SAT to work in a good way (it got pretty fast :) )

now, i only need to collision position to get everything else to work.. anyone have the calculus for that? (im kinda tired but i want this to work before i stop)

There's a terrific presentation on 2D box physics available here: http://gphysics.com/

It explains how to generate contact points, and a bunch of other things as well. And there's even some nice clean source code.