Particles - Frame based Sorting??

Thanks for the reply.

I was wandering though, would the STL Sort() function work?

As it uses the same principles of a bubble sort [<].

Cheers.

I believe quicksort also works faster if the data is almost sorted. It''s also quicker than bubble sort.

First off, with only 100 items, you may not see too much of a difference in different sorting methods. If, however, you can live with "almost" sorted order, you can only run a few passes of bubble sort each frame.

So you don''t run 100 passes on the particles, assuring that a particle that was at the furthest distance and moved in one frame to the nearest distance will be detected. Instead you run 10 passes (or 3 or 20, try out for speed vs accuracy) and get the vast majority in order. I did this for a particle engine and needed far less passes to keep things in order.

karg

Radix sort works quite well too

~Graham


----
while (your_engine >= my_engine)
my_engine++;

Bubble sort works well, but insertion sort might work better for things that are nearly sorted. As a matter of fact, I recently had a similar problem as you, so I designed an algo for this purpose.

void sort(Object *list, int i){
    if(i < numObjects-1){
        if(list[i+1].y < list[i].y){
            swap(list[i+1], list[i]);
	    sort(list, (i > 0) ? i-1 : i));
        }
        sort(list, i+1);
    }
}

Worst-case time is O(n^2), and best-case should be O(n)... I haven't done the math to verify this though but I'm pretty sure that's accurate. What it does is sort an object by its Y axis, you can adapt it for your own needs. It's short and sweet, although it might be rough when you're dealing with tons of elements due to the recursion. If you need to, you should be able to implement a stack without too much trouble or devise a non-recursive solution (although it loses its elegance).
For my purposes though (with about a dozen objects onscreen), it worked in DirectDraw perfectly without any slowdown even on an old p2.

I recently made a topic on this, check it out here.

[edited by - Odoacer on January 31, 2004 11:32:35 PM]

I''d really suggest that you use std::sort if you still have other code to be writing. Really. Generally, it''s introsort, which works like quicksort, but which doesn''t have n^2 worst case behavior. And it switches over to insertion sort once the sub-lists are small enough (14 items, I think), so after a couple iterations, all of your sub-lists will be that big, and then it''ll turn into insertion sort anyway. It''ll be slightly slower on average than just using insertion (or god forbid, bubble), but you don''t have to worry about some awful degenerate case where the camera teleports to the other side of the particle cloud - insertion becomes n^2, while std::sort() is still going to be no worse than n log n.