• Advertisement
Sign in to follow this  

fast sorting algorithm for depth sorting

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

hello, i am currently using quicksort to depth sort objects in my scene. unfortunately this algorithm is O(n log n) if i am not mistaken and is eating up about half of the framerate in a worst-case scenario. so what sorting algorithms are usually used for depth sorting. thanks!

Share this post


Link to post
Share on other sites
Advertisement
You need to exploit frame coherency. The list of objects from one frame to the next is usually not very different, and the number of things within that list that change Z order is not going to be large either. You can probably get away with only quicksorting when a large number of items are added/changed, and doing much simpler search-moves to handle smaller, individual changes.

Share this post


Link to post
Share on other sites
GPU Gems 2 contains a chapter on GPU sorting using bitonic merge sort, which is shown to be as good if not better in all situations as quicksort or STL sort.

Share this post


Link to post
Share on other sites
Quote:
Original post by ViLiO
I personally got pretty decent results using a Radix Sort [smile]

Regards,
ViLiO


Seconded. Check out this for some good tips on implementing it.

Share this post


Link to post
Share on other sites
thank you,
i will try radix sort, although i have yet no idea on how to use it with linked lists, since at the beginning an array of the size of elements is allocated and i cant do that with lists.

Share this post


Link to post
Share on other sites
Quote:
Original post by superpig
You need to exploit frame coherency. The list of objects from one frame to the next is usually not very different, and the number of things within that list that change Z order is not going to be large either. You can probably get away with only quicksorting when a large number of items are added/changed, and doing much simpler search-moves to handle smaller, individual changes.


I think that is a great idea. Do you mean AVL or BST tries for instance? We could have a heap (as a BST or AVL tree) and then most of operations like Insert, Delete, Find are O(lgn) so it is much faster than even the Radix Sort! However is is much harder to implements such Data Structure...

Share this post


Link to post
Share on other sites
Quote:
Original post by Fen
Quote:
Original post by superpig
You need to exploit frame coherency. The list of objects from one frame to the next is usually not very different, and the number of things within that list that change Z order is not going to be large either. You can probably get away with only quicksorting when a large number of items are added/changed, and doing much simpler search-moves to handle smaller, individual changes.


I think that is a great idea. Do you mean AVL or BST tries for instance? We could have a heap (as a BST or AVL tree) and then most of operations like Insert, Delete, Find are O(lgn) so it is much faster than even the Radix Sort! However is is much harder to implements such Data Structure...


All I meant was that if you reuse the list from frame to frame, then it's almost always going to be mostly sorted, and you should look to take advantage of that. For example, if you implement quicksort, you should pick your pivot points to be in the middle of each section because it is highly likely that the parts on either side will be of equal size, giving you the best case time.

Share this post


Link to post
Share on other sites
Quote:
Original post by ehmdjii
... eating up about half of the framerate in a worst-case scenario.


The suggestions above are very good however I'm not sure this is your problem. I think that if sorting is eating half of your framerate there is some other major flaw. How many items are you trying to sort per frame? Are you sorting them more than once per frame? Are you copying data or just changing pointers?

Share this post


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

  • Advertisement