Jump to content
  • Advertisement
Sign in to follow this  
maxest

Sorting objects and parallelism

This topic is 3507 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

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?

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
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 :)

Share this post


Link to post
Share on other sites
Quote:
Original post by Maxest
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... :)
There'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.

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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
Quote:
Original post by Maxest
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.
Now sort the already-sorted array again, using (a) quicksort, and (b) this slightly modified bubble-sort:


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;
}
}

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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 :)

Share this post


Link to post
Share on other sites
Quote:
Original post by Maxest
Quick-sort crashes when numbers are already sorted ;).
An algorithm doesn't crash, your implementation might. Classically Quicksort exhibits its worst case of O(n2) when the sequence is already sorted.

Share this post


Link to post
Share on other sites
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]

Share this post


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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!