+1 Our Site! Let your friends know you like us.

Thursday, December 15, 2011

The Wonders of Collision Detection

Up to this point, collision detection has been a point of much internal dialogue for me. For instance, per-pixel collision tests are as accurate as it gets, and they provide a wonderful amount of positional information useful for many different purposes. However, it can get to be extremely expensive on the processor and GPU, so in most cases it isn't really an option.

For a while, I thought that rectangle based collision was the holy grail. It's fast, it's easy, and there's still vital mathematical information to be easily gleaned. Just try rotating your rectangles though, and you'll quickly realize that existing methods purely for rectangles will be broken.

After that, I moved on to circles. Circles are wonderfully inexpensive, and absolutely the easiest to implement. Even after parenting and otherwise layering them though, you still get  pretty inaccurate collisions in a lot of cases, such as objects with sharp angles. This can be minimized, but it takes a large amount of effort and can end up negating the speed gained over other methods.

Finally, I am where I am today. Convex polygons, as of this week, are my favorite method. I spent hours poring over different sites and their explanations of the Separating Axis Theorem. I looked at source code, I performed tests, I even looked in my Calculus textbook for help (no dice). Eventually it clicked for me, and it works wonders.

Still, there are grounds that have to be given up. SAT only works for convex polygons, which can be a bit of a hassle. You can represent any concave shape with multiple convex ones, but that is beside the point, and automagically creating multiple convex shapes from a concave source is something I have yet to understand. Also, while this method is relatively fast, it still isn't anywhere near as fast as its circle counterpart.

It is obvious to me at this point that compromises will have to be made with any method of collision, and even programming as a whole. Unfortunately, that doesn't keep it from bugging me...

No comments:

Post a Comment