Depth sort particles stored as a linked list
Author
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
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.
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...
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...
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.
(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.
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.
Author
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
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
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
