pouët.net

Particle Z-sorting

category: code [glöplog]
Hey,

Off topic:
Sorry for my temper the other day (if you were a victim of it), I was in a regretfully bad mood at the time.

On topic:
A good algorithm for particle Z-sorting
(for slow-moving semi-transparent occluding particles like fog etc),
the best I can think of is
Qsort which seems not the best solution...
added on the 2009-08-27 11:44:25 by jaw jaw
jaw: for fog-ish effects etc you don't need exact sorting, only rough, so something simple like radix sort could be good enough.
added on the 2009-08-27 11:49:08 by kusma kusma
never heard that anyone implemented it (speed reasons?) but perhaps depthpeeling or reversed depthpeeling could do the job (its per pixel "sorting")..
added on the 2009-08-27 11:52:55 by mad mad
'Bitonic Merge Sort' on the GPU. whatever that is
added on the 2009-08-27 11:56:43 by the_Ye-Ti the_Ye-Ti
http://research.microsoft.com/apps/pubs/default.aspx?id=70307

Accelerated depth peeling at least.. definetly worth looking into. From a quick glance of the PDF - doesn't say wether it runs well in realtime or not but I'll try it. Thanks!
added on the 2009-08-27 11:59:25 by jaw jaw
depends on the number of particles and how fast they are moving.
1000 particles - radix sort. static particles - presorted indexbuffers from the 6 major view axes. 1million fast moving particles - something on gpu like bitonic sort or a gpu bucket sort (which is how i did it).
added on the 2009-08-27 11:59:38 by smash smash
cuda sdk comes with a nice demo and sourcecode called "particles" or something that does radix along the way (in the gpu, obviously).
added on the 2009-08-27 12:02:25 by Hyde Hyde
Don't know if that's applicable in your case but if the particles are moving slowly and the camera is relatively stable, surely the list of particles could be pre sorted and when updating a particle, you could check if it just passed ahead of it's immediate sibbling and swap them. That type of sort has a bad big O complexity but it seems like a very good fit for a flock of particles moving together with little shuffling.
added on the 2009-08-27 12:03:48 by p01 p01
The ancient glue-method does 5-pass radix sort on CPU (first make 4 histograms, then sort by each byte), but if you have _lots_ of stuff you'll probably want to do it with GPU.
GPU sorting is a complex topic. There are lot of approaches and all seem to suck in one way or another but the immense processing power makes up for that.
Method 1: Sorting network. Downside: Requires a lot of passes. Not asymptotically perfect either. (I don't see why people prefer bitonic over odd-even, but there's probably some tradeoff involved)
Method 2: Vertex shader. Downside: Using triangles just to scatter some few pointers just seems silly. Potential bottleneck on old hardware too.
Method 3: Something more advanced. Downside: Works on maybe 10% of cards.
added on the 2009-08-27 12:22:52 by 216 216
Method 4: Fake it, no one will notice.
added on the 2009-08-27 12:25:10 by kusma kusma
Ah yeah, then there's e.g. weighted blending. That's of course even more advanced effect than just sorting :)
added on the 2009-08-27 12:28:34 by 216 216
Method 5: Use only additive or multiplicative particles and don't sort. :P
added on the 2009-08-27 12:29:53 by kb_ kb_
Yeah, there's been a shortage of additive flares in demos
added on the 2009-08-27 12:37:11 by 216 216
never ever seen multiplicative ones till now :(, but there must be atleast one demo ftw..
added on the 2009-08-27 12:39:08 by mad mad
for static particles (up to few millions), what smash said
added on the 2009-08-27 12:51:54 by iq iq
iq: BINARY OR IT DIDNT HAPPEN!
added on the 2009-08-27 13:07:02 by kusma kusma
what kb said.
added on the 2009-08-27 13:08:46 by supah supah
supah: What 216 said.
added on the 2009-08-27 13:09:09 by kusma kusma
binary would be nice :)
added on the 2009-08-27 13:09:20 by bdk bdk
this nvidia paper to the cuda example that Hyde mentioned also covers/references iq's approach.
added on the 2009-08-27 13:11:51 by arm1n arm1n
Method 6: Fuck it, after all it looks good enough without sorting. ;)
added on the 2009-08-27 13:14:48 by nystep nystep
thanks for all the info, surely a lot to consider. I want to do a mix of different things, so it has to be sorted. Otherwise kb, your're quite right and that's what I've done until now :)

But it would be cool to mix static and moving particles so I'll try to make use of several of these techniques. For the moving particles I think it's easiest to do a radix sort in a thread since the GPU will be loaded with rendering the scene anyway, might be a bit much to also do sorting (talking about maybe 1000-5000 particles multicore systems nowadays), and for the rest I'll try the volume sort you suggested, iq..

One thing about that technique though, when you rotate the camera, don't you get "jumps" when it changes the sorting set? Or maybe like linear-interpolate between 2 sets on the gpu..?
added on the 2009-08-27 13:18:27 by jaw jaw
btw. iq's method was already described in 1995/6 by Zappy (Pierre Terdiman) here..
added on the 2009-08-27 13:20:07 by arm1n arm1n
jaw: If particles are "intersecting", you're bound to get pops no matter what.
added on the 2009-08-27 13:22:52 by kusma kusma
kusma: that's true.
added on the 2009-08-27 13:24:03 by jaw jaw

login