Often the graphical mesh can be very detailed and complex - even simple meshes can be in the tens of thousands! Which is fine for `graphics` - but when we have to interact with these meshes we don't want to go cycling through all these triangles and checking for collisions.
We could calculate a bounding sphere or box - but we want something a bit more flexible and detailed!
Lots of Spheres
One solution is to use the GPU to calculate a simplified sphere grid - we want to do this on the GPU as these graphical meshes can be big - and we don't want to go looping over all of these triangles/vertices - it can be slow! The GPU however, can do this in parallel - distribute the calculations across multiple cores.
Example of high resolution mesh model (king chess character) converted to a grid of spheres.
Algorithm Steps
Details about the algorithm (high-level overview)
1. Load the mesh (obviously)
2. Iterate over the mesh and find the `minimum` and `maximum`
3. Decide on a level of detail - granuarity (e.g., 16x16x16 cells)
4. Each of the 16x16x16 cells is run on a GPU thread
5. Each thread has access to all the triangles and the bounds
6. We use an atomic to keep track of which cells have been used avoid duplicating spheres 7. Each thead loops over the triangles and calculates the bounding box for each triangle - then it finds which cells (multiple cells) and adds a sphere to a list
8. That's it! We have a list of spheres that reresents the mesh
The algorithm can also use a Seperating Axis Test (SAT) for each triangle-cell (box) check - if the triangles are large (better fit).
Skull mesh with various grid resolutions (16, 32, 64).
The complete source code and various test versions/proof of concept (and other WebGPU examples) is provided in the resource section at the end.
