WebGPU Cloth Simulation 03 - Collision Detection & Response Techniques (Spatial Indexing Method)
Collision Detection Optimization Techniques
1. Case Study: Water Simulation using webGPU:
https://github.com/piellardj/water-webgpuhttps://piellardj.github.io/water-webgpu/
- All particles in the scene share the same size.
- They evolve inside a delimited spatial domain (a unit cube).
- Particles collide with each other, so that there is no interpenetration.
- Particles are subject to gravity.
2. Spatial Indexing Method
A simple implementation of these equations would be for each sphere to check every other sphere for collision. However:- This is not scalable.
- This is wasting a lot of resources, because if two spheres are too far from one another, there is no need to compute their interaction.
The solution to both these issues is to use spatial indexing, so that:
- Each particle only checks the particles near it and skips the ones far away;
- Particles that are spatially close are adjacent in the GPUBuffer, which is favorable for GPU cache.
In this example there are 7 spheres (in blue), and the domain is divided into 16 cells (in black). Each cell is given a unique scalar identifier.
Then I count the number of spheres in each cell (pCount in these diagrams), and I assign a local id to each sphere (in blue).
Then I compute a prefix sum (exclusive scan): the cStart of each cell is the sum of the pCount of the previous cells.
Then to each particle, I assign a global id (in red) which is the sum of the cell's cStart and the particle's local id. This global id is unique to each particle, and is then used to reorder particles.
Finally, I reorder the particles according to their global id.
- I easily can get the list of particles in a cell: they are the ones with ids ranging from cStart to cStart + pCount.
In this example, if I want to compute the collisions for particle 1.
- I start by computing the cell id (cell #2)
- I then lookup particles in adjacent cells (#1, #2, #3, #5, #6, #7): in cells #1,#3,#5,#6 pCount=0 so no particles, in cell #2 particles 0 to 0+3 (0, 1, 2), in cell #7 particles 5 to 5+1 (5).
- Each particle only checks the particles near it and skips the ones far away;
- Particles that are spatially close are adjacent in the GPUBuffer, which is favorable for GPU cache.
Spatial Indexing Algorithms
Spatial indexing algorithms help manage and query spatial data efficiently, reducing the computational overhead of detecting interactions like collisions and querying positions.In this example there are 7 spheres (in blue), and the domain is divided into 16 cells (in black). Each cell is given a unique scalar identifier.
Then I count the number of spheres in each cell (pCount in these diagrams), and I assign a local id to each sphere (in blue).
Then I compute a prefix sum (exclusive scan): the cStart of each cell is the sum of the pCount of the previous cells.
Then to each particle, I assign a global id (in red) which is the sum of the cell's cStart and the particle's local id. This global id is unique to each particle, and is then used to reorder particles.
Finally, I reorder the particles according to their global id.
Once this indexing is done:
- the particles were reordered;- I easily can get the list of particles in a cell: they are the ones with ids ranging from cStart to cStart + pCount.
In this example, if I want to compute the collisions for particle 1.
- I start by computing the cell id (cell #2)
- I then lookup particles in adjacent cells (#1, #2, #3, #5, #6, #7): in cells #1,#3,#5,#6 pCount=0 so no particles, in cell #2 particles 0 to 0+3 (0, 1, 2), in cell #7 particles 5 to 5+1 (5).
Spatial Index Implementation
1. Reset Cells -
2. Count Particles Per Cell -
3. Prepare Prefix Sum -
4. Prefix Sum -
5. Finalize Prefix Sum -
6. Reorder Particles -
7. Indexing
Comments
Post a Comment