Sort, sweep, and prune: Collision detection algorithms (2023)

One interesting note on this approach is that the author suggests using a &quot;fast&quot; sorting algorithm like mergesort&#x2F;quicksort as the sorting algorithm for best performance. But in practice, you may get better performance from a &quot;worse&quot; sorting algorithm: insertion sort.<p>The reason is that objects in collision detection systems tend to move relatively small steps between frames, meaning you can keep lists from the previous frame that are already mostly sorted. For sorting these mostly sorted lists, insertion sort tends towards O(n) while Quicksort tends towards O(n^2)!

This was really well put together.<p>What’s funny is that I’ve been doing some form of gamedev since late 90s and most of this is abstracted by engines at this point, but this is essential to understanding how complex system simulations work.<p>Thanks to the author for making a very accessible article

I&#x27;ve always enjoyed this document regarding continuous collision detection:<p><a href="https:&#x2F;&#x2F;github.com&#x2F;bepu&#x2F;bepuphysics2&#x2F;blob&#x2F;master&#x2F;Documentation&#x2F;ContinuousCollisionDetection.md">https:&#x2F;&#x2F;github.com&#x2F;bepu&#x2F;bepuphysics2&#x2F;blob&#x2F;master&#x2F;Documentati...</a><p>The library itself is amazing in terms of performance. It is a bit challenging to integrate with though due to the amount of optimization involved.

&gt; This naive algorithm runs in O(n2) time in Big O terms.<p>Is this true? The naive algorithm&#x27;s outer loop (i) counts n - 1, while the inner loop (j) begins at i + 1 (so counts progressively less than n - 1).<p>Not a CS major, is this roughly equivalent (for large values of n) to O(n2) or is it, as it appears, something less?

I enjoyed the use of illustration. Seems like an appropriate usage.<p>Sometimes I feel like these articles with interactive illustrations are more like an excuse to put together a bunch of cool demos, like there&#x27;s a lot of fluff with not much substance (a bit like a TED talk), but this one didn&#x27;t let the illustrations take over.

Part 2: <a href="https:&#x2F;&#x2F;leanrada.com&#x2F;notes&#x2F;sweep-and-prune-2&#x2F;" rel="nofollow">https:&#x2F;&#x2F;leanrada.com&#x2F;notes&#x2F;sweep-and-prune-2&#x2F;</a><p>Check out his other goodies <a href="https:&#x2F;&#x2F;leanrada.com&#x2F;" rel="nofollow">https:&#x2F;&#x2F;leanrada.com&#x2F;</a>

A long time ago I did something similar but rather than sorting I just kept index lists for each direction and the objects sorted themselves. Meaning like there are 4 lists `objectIndicesSortedByLeftEdge&#x2F;RightEdge&#x2F;TopEdge&#x2F;BottomEdge` If an object moves horizontally then it updates its own indices in the leftEdge and rightEdge arrays. This is because as it moves it likely only has to swap 1 or 2 indices at most to move itself.

I hadn&#x27;t seen this before, but isn&#x27;t it similar to using something like a quad-tree to reduce the number of potential colliders?

Got distracted (in a good way) by this website. It&#x27;s fun and inspiring.

&gt; <i>I won’t cover other approaches, such as space partitioning or spatial tree subdivision</i><p>I&#x27;m curious about this comment, anyone know if the algorithm in the article is generally faster than space partitioning&#x2F;spatial tree subdivision?<p>A long time ago I used a spatial tree type of approach which seemed naively to be a pretty good approach, but I never investigated or compared algorithms other people were using (this was 80&#x27;s, pre-internet).

I was curious if any linear programming methods have been proposed for the problem since you just need to see if a point is inside a polyhedron or if two polyhedra intersect. There are.<a href="https:&#x2F;&#x2F;users.encs.concordia.ca&#x2F;~akgunduz&#x2F;CollisionDetection.pdf" rel="nofollow">https:&#x2F;&#x2F;users.encs.concordia.ca&#x2F;~akgunduz&#x2F;CollisionDetection...</a>

A tangent, but HNers interested in an article on collision detection might know: are there any similar articles that show how to compute the intersection of two capsules (as in the space that that a sphere moving in a straight line in a time step occupies) in 3D? My own hobby 3D game got stuck on that hurdle and I couldn’t find any examples anywhere :(

Excellent article. Sorting the list is a really simple and neat idea, without the need for clustering or a special data structure.

I&#x27;m a big fan of spatial grid hashes to simplify situations like this. Nice to see other approaches. Iterative Insertion sorting would be easier to port to a compute shader than a spatial grid hash, so maybe this method is better if we get into the millions of objects range?

Since the balls probably don’t move much per frame, should the list be considered “nearly sorted?”

Not mentioned is spatial hashing, which works well without complex data structures.<p>Also sad that you need all this complexity to test 25 balls in Javascript. 25^2 is a small number in C, especially when your balls fit in cache.<p>Still a good introduction to various algorithms, though.

The title was curious to me because I expected more a post about the `intersects` function, e.g the pip algorithm... turns out it&#x27;s more about the complexity involved by the number of objects to test, which in the end is also interesting.

This is awesome, very beautiful and well written!<p>Are there other handy 2-d algorithms that are this well explained? I know redblobgames has a treasure trove too, but curious about more.

Super interesting, my first thought before I read the article was why not a bloom filter but didn’t expect it to be “physical” collision

The animations don’t show on iOS Safari.

Very Nice animated examples