fast sorting algorithm for depth sorting
Author
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!
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.
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.
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.
Author
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.
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.
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...
Quote:Original post by FenQuote: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.
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?
I've used this merge sort for lists in commercial games. With no frame coherency stuff, and just rebuilding a render queue each frame and sorting it, the sort was using less than 0.1% of CPU time.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
