Hello!

I recently added a new Diligent Engine tutorial that demonstrates the usage of compute shaders and may be useful on its own. The example app implements a simple GPU particle system that consists of a number of spherical particles moving in random directions and encountering elastic collisions. The simulation and collision detection is performed on the GPU by compute shaders. To accelerate collision detection, the shader subdivides the screen into bins and for every bin creates a list of particles residing in the bin. The number of bins is the same as the number of particles and the bins are distributed evenly on the screen, thus every bin on average contains one particle. The size of the particle does not exceed the bin size, so a particle should only be tested for collision against particles residing in its own or eight neighboring bins, resulting in O(1) algorithmic complexity.

The full description of the implementation of the method is here.

O(1) algorithmic complexity would mean the execution time is invariant to the number of particles - that would be a groundbreaking discovery!

Yeah, a good remark. But what DilligentDev meant is that inside of a bin it is constant (O(1)). Not in overall :) Still a very nice implementation and a tutorial for everyone.

37 minutes ago, pcmaster said:

Yeah, a good remark. But what DilligentDev meant is that inside of a bin it is constant (O(1)). Not in overall Still a very nice implementation and a tutorial for everyone.

It read like a summary statement of the entire algorithm rather than just the last part of the process, but I can see that it could be interpreted both ways.

To @DiligentDev is there any reason you don't use SV_DispatchThreadID and instead choose to calculate it manually?

Sorry about the confusion with complexity. Overall complexity is of course O(n) (fixed this in the description). What I meant was of course the complexity of testing one particle.

2 hours ago, Adam Miles said:

To @DiligentDev is there any reason you don't use SV_DispatchThreadID and instead choose to calculate it manually?

No, not really. SV_DispatchThreadID can be totally used instead.