Have to sort really fast
Author
What would be the fastest method to sort a linked list?
I have a list of 3D Objects that have to be sorted by z order because the might contain transparency. So how can I possibly sort them at a speed that allows me to do this per-frame?
Have them allways be sorted 
as you update and objects position if it changes in the z direction compare it to it''s neibours. If it exceed or is less the one of them, you know it''s time for them to swap positions.
When you add a new object to the list, make sure you add it to the right place in the list so that it perserves the sort order.
as you update and objects position if it changes in the z direction compare it to it''s neibours. If it exceed or is less the one of them, you know it''s time for them to swap positions.When you add a new object to the list, make sure you add it to the right place in the list so that it perserves the sort order.
herm.. you could use a std::set, which automatically sorts items as they''re placed in the set.
There''s no random access tho, so you''d actually have to traverse the whole set, just like a list, to find a particular element.
There''s no random access tho, so you''d actually have to traverse the whole set, just like a list, to find a particular element.
if your problem is due to transparency, then you could also disable depth buffer writes when drawing a (possibly) transparent object.
A fast way to do it is to do a bubble sort and amortize the sort over time. You do one pass on the list per frame. Not a full sort, just one pass. Over a small period of time your list will sort. This works well for lists that have good time coherency, ie. don''t change much over time.
If you''ve put yourself in a situation where you need to sort a large very-unsorted list every frame you should rethink your design. Sorting that much every frame means you''ve made some bad design choices...
If you''ve put yourself in a situation where you need to sort a large very-unsorted list every frame you should rethink your design. Sorting that much every frame means you''ve made some bad design choices...
If you use std::list, it has a sort member function which uses this frightening code (VS.NET):
void sort() { // order sequence, using operator< if (2 <= size()) { // worth sorting, do it const size_t _MAXBINS = 25; _Myt _Templist(this->_Alval), _Binlist[_MAXBINS + 1]; size_t _Maxbin = 0; while (!empty()) { // sort another element, using bins _Templist.splice(_Templist.begin(), *this, begin()); size_t _Bin; for (_Bin = 0; _Bin < _Maxbin && !_Binlist[_Bin].empty(); ++_Bin) { // merge into ever larger bins _Binlist[_Bin].merge(_Templist); _Binlist[_Bin].swap(_Templist); } if (_Bin == _MAXBINS) _Binlist[_Bin - 1].merge(_Templist); else { // spill to new bin, while they last _Binlist[_Bin].swap(_Templist); if (_Bin == _Maxbin) ++_Maxbin; } } for (size_t _Bin = 1; _Bin < _Maxbin; ++_Bin) _Binlist[_Bin].merge(_Binlist[_Bin - 1]); // merge up swap(_Binlist[_Maxbin - 1]); // replace from last bin } }
Author
Well, I use this lists for my so called sprites (so called, because they are in a way normal 3D objects except that they are always quads).
So I can`t know how many sprites I have got but I don`t think it will become thousands. More like something below 100 because I can reload them per map. It could even be less.
So I can`t know how many sprites I have got but I don`t think it will become thousands. More like something below 100 because I can reload them per map. It could even be less.
About that bubble sort, he actually didn''t say to do a full bubble sort each time, just one pass through it each frame. As long as the positions don''t change too radically, it should keep everything close enough and still be fast. Interesting idea, and worth a try, I think.
Karg
Karg
from memory there is a qsort() function or something like that around the shop...
look at that just found it in msdn. its used on arrays and is very generic:
last I knew nobody can come up with an algorithm which was better an O(n*log(n)) which I *believe* quicksort is.
just another suggestion
Toby
Gobsmacked - by Toby Murray
[edited by - tobymurray on August 16, 2002 1:40:36 PM]
look at that just found it in msdn. its used on arrays and is very generic:
void qsort( void *base, size_t num, size_t width, int (__cdecl *compare )(const void *elem1, const void *elem2 ) );RemarksThe qsort function implements a quick-sort algorithm to sort an array of num elements, each of width bytes. The argumentbase is a pointer to the base of the array to be sorted. qsort overwrites this array with the sorted elements. The argument compare is a pointer to a user-supplied routinethat compares two array elements and returns a valuespecifying their relationship. qsort calls the compare routineone or more times during the sort, passing pointers to twoarray elements on each call:compare( (void *) elem1, (void *) elem2 );The routine must compare the elements, then return one of the following values:Return Value Description <0 elem1 less than elem2 0 elem1 equivalent to elem2 >0 elem1 greater than elem2 last I knew nobody can come up with an algorithm which was better an O(n*log(n)) which I *believe* quicksort is.
just another suggestion
Toby
Gobsmacked - by Toby Murray
[edited by - tobymurray on August 16, 2002 1:40:36 PM]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
