Collision Detection using Spatial Hashing

Gallery
1

I have found a great YouTube channel Ten Minute Physic and in particular this video on the spatial hashing algorithm. The sketch below is based on the algorithms described in this video.

Although I have not performed any serious performance tests it appears to be of the same order of magnitude as a quadtree implementation but has a much simpler code implementation.

The full sketch code is available in the p5js web editor. If you use the p5js editor to create a copy make sure you turn off “Loop Protection" for best performance.

2

Here is a similar idea using webgl shaders. Mine is a little bit approximate, though, since each grid cell (pixel) can only list one particle. If two particles overlap and fall into the same grid cell, the first one will be forgotten for that frame or until it manages to push itself away from the second.

Using full OpenGL on Processing, you can use atomics to create a linked-list of particles in each grid cell for a fully accurate simulation.