Torque 2D: Informal technical overview - breakout discussion on collision detection routines.
This discussion offers a very brief overview of common collision detection schemes used in games, and relates them to the collision detection schemes used in Torque 2D. This information is part of a .plan file created during the development of Torque 2D.

Collision detection is a well-established field of study, but it’s still researched very actively, both in academic and practical / private fields like game development, CAD, CGI, robotics, and others. For anyone interested, here’s a quick aside on collision detection. The goal of this discussion isn’t to offer a super-detailed tutorial on collision detection algorithms (this .plan is getting long enough already). Rather, I hope to just give a feel for how some common collision schemes work, so you can see a context for T2D’s collision detection, if you aren’t already famliar with these algorithms.

Most modern collision detection schemes attempt to deal with convex, polygonal shapes with high poly counts and seek to return very accurate collision detail. With these kinds of target constraints, there are two common approaches taken: feature-oriented (typified by the Lin-Canny algorithm) and Simplex-oriented (typified by the GJK algorithm) collision detection schemes.

Feature-oriented collision detection tries to determine the closest “features” (vertices, edges, or faces) between two polygonal shapes. These features are compared, and disjointedness or collision is determined based on the distance between them. The Lin-Canny algorithm, which is the progenitor of feature-based techniques, does just this, and caches collision feature information in order to exploit temporal coherence and probabilistically reduce the computation required in a CD pass. Lin-Canny has spawned many variations and improvements, including some which overcome the algorithm’s Achille's heel: its inability to elegantly handle interpenetrating shapes.

Simplex-oriented collision detection, as typified by the GJK algorithm, iteratively determines the distance between two objects. A “simplex” is just a fancy term for a point, line, triangle, tetrahedron, etc—in other words, an n-triangle (technically, a simplex is defined as the convex hull of an affinely independent set of points). The GJK algorithm iteratively creates simplices of the shapes’ differences in order to determine their distance from each other, and whether they collide. For more information see here. GJK is capable of handling interpenetrating shapes, and it has also spawned many derivative algorithms which improve on its efficiency and robustness.

Some researchers in the past few years have stepped outside both feature-oriented and simplex-oriented techniques, and are coming up with some cool methods of collision detection. None (that I’m aware of) beat the LC or GJK progeny at what they do (quickly and very accurately detecting collisions between detailed convex polygonal shapes), but rather relax some constraints in order to gain speed. For example, several algorithms do a good job of utilizing simple heuristics to determine when less accurate collisions are acceptable, and trade accuracy for speed in those cases. Some of these might be very game-friendly, and we might be taking a look at them for the Torque platform eventually. :)

When relaxing the constraints on a collision detection system even further, lots of other collision schemes are acceptable. When less accurate collision schemes are desired (or when accuracy is desired and memory storage is not a constraint), space division techniques can be used exclusively in the narrow-phase. Exclusive use of bounding volume schemes can be valid as well. For example, most RTS games use only radius-based or AABB collision for all collision detection, this is true in games from Starcraft to WC3 and WH40K: Dawn of War. RPGs frequently have simplified collision requirements as well, and (IIRC) Neverwinter Nights used AABB collision only. In another example, the method of separating axes (see Eberly’s description for more details) is useful in situations where polygon face counts are relatively low.

T2D uses this technique, and it’s great for 2D collision. The method of separating axes returns very accurate collisions and is nicely performant in 2D scenes. The total number of collision edges in even the most complex 2D scene is not likely to be as high as the collision faces in a complex 3D scene, so the method of separating axes can effectively be used in crowded 2D scenes, even if it’s not suitable for analogous 3D conditions.

Research on non-polygonal collision detection has turned up interesting results, and this area is growing quickly. However most recent research focuses on algebraic surfaces which are still not feasible for use in games, so I’ll skip going over much of it here (I’m not all that familiar with this particular area of research anyway :). Solid geometry collision is still studied somewhat actively, but probably the best summary of techniques in the field remains to be here, which I point you to again.

Research on concave polygonal collision detection is more and more popular as well. Not long ago, the typical recommendation for detecting collision with concave objects was to chunk the concave object into convex pieces and collide against those sub-polyhedra. This approach is fine when dealing with shapes that have a low degree of concavity, but its suitability obviously degrades as a shape’s concavity increases. Some of the most interesting research in the field of collision detection is going on in regards to non-convex shape collisions, and we’ll see whether T2D leverages any techniques (or maybe invents some ;) in this arena in the future!

Finally, from the engineering perspective, there’s a lot of cool work lately on hardware-accelerated collision detection. I think the IBM, Intel, nVidia, and SCEA developer sites have the best papers overall on leveraging SIMD and MIMD hardware for collision detection in both the broad and narrow collision detection phases.

So, that’s a very quick 10km overview of modern real-time collision detection algorithms. I hope it helps provide some context, and if you’re interested in this area of study, the links in this section will be very helpful. I hope it’s also clear that Melv and I keep our eyes as closely as we can on the research results here, as we (and everyone here) want indies to be able to leverage the best techniques with T2D.

-Josh Williams
GarageGames
Return to the T2D informal technical overview .plan