Collision Detection, Part 1: Overview (2015)

The author glosses over many real-world problems. Some algorithms work badly in 32-bit floating point because they depend on small differences between large numbers. (I ran into that in the days before everybody had good 64-bit FPUs.) Convex meshes should not be triangulated, because that results in coplanar faces, and hill-climbing can get stuck on the wrong face. It's necessary to clean up convex objects a bit - require a minimum break angle of one or two degrees at each edge to make sure that they're strictly convex, not just non-concave. The author writes "One important class of objects are convex polytopes, which have the property that between any pair of points in the shape the straight line segment connecting them is also contained in the shape." That's a necessary property, but not a sufficient one; it allows coplanar faces.

Broad phase collision detection usually involves three lists of the bounding boxes of the objects, ordered by X, Y, and Z. Only if there's overlap in all three axes do you need to do the narrow-phase test. The author writes "Using output sensitive analysis, there is also a lower bound of O(n log(n) + k) (for comparison based algorithms) by reduction to the element uniqueness problem." That's also the lower bound for sorting by comparison, of course. But that's a price you only pay at cold start, when you initially sort all your objects. Thereafter, you update the ordered lists as the objects move, which, if most things are not moving at high speed, is cheap.

Large-area collision detection, for big MMOs, has an even coarser phase of binning by large areas. Just divide the world into squares and only look at your square and the neighboring squares. This parallelizes nicely.

In 2D games programming, at least in the old days, the detection effectively consisted of detecting whether NOT two objects were overlapping.

Consider this pseudocode formula:

    function isOverlapping(a, b){
      return a.x < b.x + b.w // a's left is to the left of b's right
        && // And
        a.x + a.w > b.x // a's right is to the right of b's left

Compare with this :

    function isOverlapping(a, b){
      if(a.x > b.x + b.w) return false; // was to the right
      if(a.x + a.w < b.x) return false; // was to the left
      if(a.y > b.y + b.w) return false; // was below
      if(a.y + a.h < b.y) return false;  // was above
    
      return true; // not not overlapping, so must be overlapping
    }

    function move(a, x, y){
      a.left = x;
      a.top = y;
      a.right = a.x + a.w;
      a.bottom = a.y + a.h;
    }

    if(a.left < b.right) return false;