Sorting objects and parallelism
Author
I've been thinking about sorting objects back-to-front to perform correct alpha-blending. It is clear, that for about 1k objects there shouldn't be problems to sort them (http://linux.wku.edu/~lamonml/algor/sort/sort.html). But what if I need to sort about 100k of objects? I think that doing sorting not all the time but, for example, per one second could be a good solution. But if sorting needs, let's say, 0.5 second, then after every 1 second of rendering I get my application stuck for this 0.5 second to do the sorting. How to fight this? Maybe using an additional thread could help?
One common approach is iterative sorting. Every frame, do just a few passes of bubble sort. Assuming that Z orders don't usually change dramatically over a short period of time, this keeps things completely sorted most of the time, and mostly sorted all of the time.
Author
Quote:
Every frame, do just a few passes of bubble sort
Seems to be quite simple :). Suppose I can do similar thing with some faster sorting algorithms? For 100k of objects I would need much more than 1 second to do the sorting... :)
Quote:
Assuming that Z orders don't usually change dramatically over a short period of time
Mhm, we MUST make such assumption in this situation :)
Quote:Original post by MaxestThere's this "bubble sort EEEVIL" idea which totally ignores temporal coherence. For a mostly-sorted array (measured by summed displacement), bubble sort and its ilk are hands down the fastest possible sorting algorithm. In contrast, quicksort (in its classical implementation) on a mostly sorted array is very slow.
Seems to be quite simple :). Suppose I can do similar thing with some faster sorting algorithms? For 100k of objects I would need much more than 1 second to do the sorting... :)
Quote:Quote:
Assuming that Z orders don't usually change dramatically over a short period of time
Mhm, we MUST make such assumption in this situation :)
There are other sorting algorithms which may improve things here... I know some people use cocktail-sort for this. But if you want everything sorted perfectly and you're not willing to leverage temporal coherence, your options are limited. Also, remember to profile! Sorting 100k objects takes much less than 0.5 seconds on my computer.
Author
I tried code from aformentioned website. For 10k random elements algos like heapsort or quicksort do the sorting in less than 1 ms (AMD Turion 2x1.8Ghz). Bubblesort did the same in 0.5 second.
However, after first sorting, and moving the camera later on, the sorting will only be affecting few elements (depending on camera speed of course...). So as you say, profiling is most important here. Geez... and that's all for some stupid grass :D
However, after first sorting, and moving the camera later on, the sorting will only be affecting few elements (depending on camera speed of course...). So as you say, profiling is most important here. Geez... and that's all for some stupid grass :D
Quote:Original post by MaxestNow sort the already-sorted array again, using (a) quicksort, and (b) this slightly modified bubble-sort:
I tried code from aformentioned website. For 10k random elements algos like heapsort or quicksort do the sorting in less than 1 ms (AMD Turion 2x1.8Ghz). Bubblesort did the same in 0.5 second.
void bubbleSort(int numbers[], int array_size){ int i, j, temp; for (i = (array_size - 1); i >= 0; i--) { bool mod = false; for (j = 1; j <= i; j++) { if (numbers[j-1] > numbers[j]) { temp = numbers[j-1]; numbers[j-1] = numbers[j]; numbers[j] = temp; mod = true; } } if(!mod) break; }}
You may want to use a fast sorting algorithm at the start of a scene, or after a transport, just whenever temporal coherence has gone out the window. Then use something like a bubble sort or a natural merge sort when temporal coherence is high and the objects are nearly sorted.
Author
Quote:
Now sort the already-sorted array again, using (a) quicksort, and (b) this slightly modified bubble-sort:
Quick-sort crashes when numbers are already sorted ;). So I used heap-sort instead. Heap-sort for already sorted list of 100k elements gives 50 ms (<1ms for 10k elements) and your version of bubble gives <1ms in the case of 100k elements.
I see that nowadays sorting the objects in realtime does not cost as much as I thought. Grass will rise :)
Quote:Original post by MaxestAn algorithm doesn't crash, your implementation might. Classically Quicksort exhibits its worst case of O(n2) when the sequence is already sorted.
Quick-sort crashes when numbers are already sorted ;).
Quote:Original post by dmatter
Classically Quicksort exhibits its worst case of O(n2) when the sequence is already sorted.
Shhh, don't give away the ending. [grin]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
