less_retarded_wiki/collision_detection.md

Collision Detection

Collision detection is an essential problem e.g. of simulating physics of mechanical bodies in physics engines (but also elsewhere), it tries to detect whether (and also how) geometric shapes overlap. Here we'll be talking about the collision detection in physics engines, but the problem appears in other contexts too (e.g. frustum culling in computer graphics). Collision detection potentially leads to so called collision resolution, a different stage that tries to deal with the detected collision (separate the bodies, update their velocities, make them "bounce off"). Physics engines are mostly divided into 2D and 3D ones so we also normally either talk about 2D or 3D collision detection (3D being, of course, a bit more complex).

There are two main types of collision detection:

• discrete: Detecting collisions only at one point in time (each engine tick or "frame") -- this is easier but can result in detecting the collisions in wrong ways or missing them completely (imagine a fast flying object that in one moment is wholly in front of a wall and at the next instant wholly behind it). Nevertheless this is completely usable, one just has to be careful enough about the extreme cases.
• continuous: Detecting collisions considering the continuous motion of the bodies (still done at discrete ticks but considering the whole motion since the last tick) -- this is more difficult to program and more costly to compute, but also correctly detects collisions even in extreme cases. Sometimes engines perform discrete detection by default and use continuous detection in special cases (e.g. when speeds become very high or in other error-prone situations). Continuous detection can be imagined as a collision detection of a higher dimensional bodies where the added dimension is time -- e.g. detecting collisions of 2D circles becomes detecting collisions of "tubes" in 3D space. If you don't want to go all the way to implementing continuous collisions, you may consider an in-between solution by detecting collisions in smaller steps (which may also be done only sometimes, e.g. only for high speed bodies or only when an actual discrete collision is detected).

Collision detection is non-trivial and in many cases really hard because we need to detect NOT JUST the presence of the collision but also its parameters which are typically the exact point of collision, collision depth and collision normal (but potentially also other ones, depending on what we're doing, e.g. volume of overlap etc.) -- these are needed for subsequently resolving the collision (typically the bodies will be shifted along the normal by the collision depth to become separated and impulses will be applied at the collision point to update their velocities). We also need to detect general cases, i.e. not just collisions of surfaces but of WHOLE VOLUMES (imagine e.g. a tiny cuboid inside an arbitrarily rotated bigger cone). This is very hard and/or expensive for some complex shapes such as general 3D triangle meshes (which is why we approximate them with simpler shapes), but even for relatively simple shapes like arbitrarily rotated 3D boxes the solution is not easy. We also want the detection algorithm to be at least reasonably fast -- for this reason collision detection mostly happens in two phases:

• broad phase: Quickly estimates which bodies MAY collide, usually with bounding volumes (such as spheres or axis aligned bounding boxes) or space indexing and algorithms such as sweep and prune. This phase quickly opts-out of checking collision of objects that definitely CANNOT collide because they're e.g. too far away.
• narrow phase: Applying the precise, expensive collision detection on the potentially colliding pairs of bodies determined in the broad phase. This yields the real collisions.

In many cases it is also important to correctly detect the order of collisions in time -- it may well happen a body collides not with one but with multiple bodies at the time of collision detection and the computed behavior may vary widely depending on the order in which we consider them. Imagine that body A is colliding with body B and body C at the same time; in real life A may have first collided with B and be deflected so that it would have never hit C, or the other way around, or it might have collided with both. In continuous collision detection we know the order as we also have exact time coordinate of each collision (even though the detection itself is still computed at discrete time steps), i.e. we know which one happened first. With discrete collisions we may use heuristics such as the direction in which the bodies are moving, but this may fail in certain cases (consider e.g. collisions due to rotations).

On shapes: general rule is that mathematically simpler shapes are better for collision detection. Spheres (or circles in 2D) are the best, they are stupidly simple -- a collision of two spheres is simply decided by their distance (i.e. whether the distance of their center points is less that the sum of the radia of the spheres), which also determines the collision depth, and the collision normal is always aligned with the vector pointing from one sphere center to the other. So if you can, use spheres -- it is even worth using multiple spheres to approximate more complex shapes if possible. Capsules ("extruded spheres"), infinite planes, half-planes, infinite cylinders (distance from a line) and axis-aligned boxes are also pretty simple. Cylinders and cuboids with arbitrary rotation are bit harder. Triangle meshes (the shape most commonly used for real-time 3D models) are very difficult but may be approximated e.g. by a convex hull which is manageable (a convex hull is an intersection of a number of half-spaces) -- if we really want to precisely collide full 3D meshes, we may split each one into several convex hulls (but we need to write the non-trivial splitting algorithm of course). Also note that you need to write a detection algorithm for any possible pair of shape types you want to support, so for N supported shapes you'll need N * (N + 1) / 2 detection algorithms.

{ In theory we may in some cases also think about using iterative/numerical methods to find collisions, i.e. starting at some point between the bodies and somehow stepping towards their intersection until we're close enough. Another idea I had was to use signed distance functions for representing static environments, I kind of implemented it in tinyphysicsengine. ~drummyfish }

TODO: some actual algorithms