5
$\begingroup$

If you have a bunch of particles to render, using different shaders and/or render states, that have some level of transparency, the naive solution of sorting all particles by depth can be extremely inefficient since it is likely to turn a few large batch draw calls into a multitude of smaller batch calls which have expensive render state switches between those draw calls.

I know of a few ways to help fake things such as sorting particle batches by their emitter location, or using something like additive blending, which gives the same result regardless of draw order.

I also know there are some techniques out there to attempt order independent transparency, often being an approximation, requiring a (sometimes unbounded) amount of memory, or some combination thereof.

Does anyone know any pragmatic solutions (fast/low extra memory requirements/absolute correctness not required) for dealing with this situation?

$\endgroup$
4
$\begingroup$

First option should be to make all particles able to go through the same pipeline. Perhaps with an uber shader. That way you can batch them all.

Positive ieee floating point numbers can be sorted like unsigned integer. And there are O(n) algorithms to sort those for example radix sort.

$\endgroup$
  • $\begingroup$ Also you can get near n, or atleast less than n log n, with bucket sort and it is trivial to do. Even better if you begin with a BSP/occ-tree you can even get it to be less than N as you get cameara occlusion culling for free. $\endgroup$ – joojaa Sep 15 '17 at 13:03
  • $\begingroup$ BSP and octrees are kinda overrated for real-time graphics work. All the pointer chasing required is detrimental for cache performance. $\endgroup$ – ratchet freak Sep 15 '17 at 13:13
  • $\begingroup$ Not necceserily if your buckets are bigish then you divide the work, but still have the benfits of lists with very few jumps $\endgroup$ – joojaa Sep 15 '17 at 13:25
  • $\begingroup$ For me, the "ubershader" is the magic sauce here and is a good point. Thanks! $\endgroup$ – Alan Wolfe Sep 15 '17 at 13:42
  • 1
    $\begingroup$ If you have a huge amount of particles you can also sort them on the GPU with a compute shader using bitonic sort. It's n log n (i think) but parallelized so super fast. There's a working implementation in the old DirectX 2010 SDK. $\endgroup$ – russ Sep 16 '17 at 11:54
1
$\begingroup$

Sort the particles by Z each rendering cycle using an algorithm such as bubble sort which is good when element changes position in small steps. If the perspective does not change much the errors would be few enough over time to be unnoticable. The technique is easy to configure between quality and performance dependning on the target platform by adjusting how much sorting is performed each cycle.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.