Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

Hippokrates

Have to sort really fast

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

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?

Share this post


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

Share this post


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

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
if your problem is due to transparency, then you could also disable depth buffer writes when drawing a (possibly) transparent object.

Share this post


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

Share this post


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

}
}

Share this post


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

Share this post


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

Share this post


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


void qsort( void *base, size_t num, size_t width, int (__cdecl *compare )(const void *elem1, const void *elem2 ) );

Remarks

The qsort function implements a quick-sort algorithm to sort
an array of num elements, each of width bytes. The argument
base 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 routine
that compares two array elements and returns a value
specifying their relationship. qsort calls the compare routine
one or more times during the sort, passing pointers to two
array 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]

Share this post


Link to post
Share on other sites

  • 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!