• Advertisement
Sign in to follow this  

Depth sort particles stored as a linked list

This topic is 3823 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi all, this is my first post at Gamedev. I need to depth-sort around 5000 alpha-blended particles stored inside a linked list (not the std one); blending is not additive, glAlphaFunc() is not a option obviously and depth buffer tricks help a bit but don't work in many situations. I've spent hours looking on the web for informations about this topic but I couldn't find any clear explanation or tutorial about depth sorting techniques or what is the best technique to do this. Any help will be really appreciated. Thanks a lot, Michele

Share this post


Link to post
Share on other sites
Advertisement
If the particles don't often change their position, then it's quite possible that a stable sort that's efficient on near-sorted data (such as insertion sort) would achieve good performance. You could then sort the list by squared distance to the eye, for example, and achieve near-linear complexity.

Share this post


Link to post
Share on other sites
Would suggest taking your particles into an array (sorting in a linked list is a mess), then write your own radix sort for the sorting. You could even move the linked list to array conversion into the first pass of the radix sort.

This is what I am doing with 64K depth sorted "particles" per frame. Averages about 40 clock cycles per particle to sort.

For 5000 particles you could also probably just use the GPU to sort. Google for Bitonic Sort...


Share this post


Link to post
Share on other sites
Sorting a linked list is not that messy. Mergesort lends itself to a linked-list implementation quite easily. If you were using a std::list in C++, you could just call sort() on it.

Share this post


Link to post
Share on other sites
(I use an array instead of a list, but you probably can adapt to your case)

A combination of cocktail sort (Bidirectional bubble sort) + radixsort has been the sort of choice for my particle systems. As Toohrvyk mentioned, it is very important to have the sort perform very quickly when the list is already almost sorted, since that will best utilize the frame-to-frame coherency.

What I do is that I sort the array using radixsort whenever I add lots of particles to the list (i.e. when I know that cocktail sort will most probably fare poorly), but in the per-frame sorting I use cocktail sort, which in practice usually just finishes after scanning the array 1-4 times per frame. I put a maximum limit to 10 scans of the array (Cocktail sort has the nice feature that it can continue from whatever it left off at, without performance penalties), which I very rarely run to. While breaking at this limit technically produces visual artifacts, I couldn't notice a difference, since they only occur for a single frame's time. (There was an additional rule I tried, "if the array has been unsorted for longer than 10 frames, perform a radix sort on it", but this rule didn't get used at all.)

I used to do insertion sort instead of cocktail sort, but my profiling made me switch to cocktail sort.

My arrays are in the range of 2000-5000, which I could manage at an acceptable rate. In my performance scaling tests, I came to the conclusion that doing any more would require GPU simulation and sorting.

Share this post


Link to post
Share on other sites
Hi everyone, thanks a lot for the answers and suggestions.

After what you said, I'm thinking about creating an array of distances and pointers to particles, and sort the array using radix sort. I guess that would be faster than sorting a list, correct? Or are there any faster options?

This is the app I'm working on, if you want to take a look ...
www.motionblur.it/tmp/multiverse_20071101_1700.zip (Press H for a list of the available actions)

Yesterday I switched to additive blending and I noticed it doesn't look that bad as I first thought, but I'll be adding depth sorting anyway as I might be moving back to non - additive blending.

Thanks a lot,

Michele

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement