Sign in to follow this  
Lyve

Sorting Billboards

Recommended Posts

Hello, I'm rendering a lot of billboards (128x128x128) that lie on a fixed grid. I want to render them back to front, but the sorting algorithm is too slow. A Distance per billboard in the quicksort callback is just too much for the amount of data. Some time ago I've read that there is a better way to sort particles that lie on a fixed grid, anyone knows how to do that? Regards, Lyve

Share this post


Link to post
Share on other sites
I'm using my simple implementation of bubble sort, certinly matching up to my needs:


void GraphicsSystem::Sort(std::list <Particle*> *List)
{
std::list<Particle*>::iterator Iterator;
std::list<Particle*>::iterator InnerIndex;

for (Iterator = List->begin() ; Iterator != List->end() ; ++Iterator)
{
for (InnerIndex = Iterator ; InnerIndex != List->end() ; ++InnerIndex)
{
if((**Iterator) > (**InnerIndex))
{
Swap(*Iterator, *InnerIndex);
break;
}
}
}
}



Iterator is an iterator, *Iterator is a pointer to a particle, and **Iterator is the particle instance itself. The particle class has the > operator overloaded (checks if it's Z is greater than the input particle).

Share this post


Link to post
Share on other sites
Uh oh, bubble sort is even slower than quicksort.

If you do this for a lot of particles every frame, it will be VERY slow

Share this post


Link to post
Share on other sites
I've found the solution again:

"... uses a cheap hack to avoid sorting the block. Because the cells are in a fixed 3D grid, it is easy to find the most distant corner (or corners), and then use the triple-nested for loop, simply going along each axis in an order determined by the most distant corners."


I think this is a very nice trick ;)

Share this post


Link to post
Share on other sites
Nice solution Lyve. I used simmilar to transverse octree in f2b order without sorting. If later you'll need to use sorting I sugest you use something that exploits temporal and spatial coherence.

Enokh: You might want to read up on other sorting algos like radix, quick,...

Share this post


Link to post
Share on other sites
Quote:
Original post by Lyve
I've found the solution again:

"... uses a cheap hack to avoid sorting the block. Because the cells are in a fixed 3D grid, it is easy to find the most distant corner (or corners), and then use the triple-nested for loop, simply going along each axis in an order determined by the most distant corners."


I think this is a very nice trick ;)


Which also means it can be precomputed as lists of pointers or indices since there are only 4 (rather 2D) or 8 (full 3D) corners. This might speed up things a bit if you have far less bilboards than grid cells. This also works if you don't have a grid.

Share this post


Link to post
Share on other sites
Note that bubble sort (though slower in general) may be faster than quick sort in this case.

Bubble sort is fast when sorting sequences that are already partially sorted. Because there may be very few changes between every sort, that could be the case here... Perhaps worth a try?

Share this post


Link to post
Share on other sites
You don't need distance per billboard - all you need is the squared distance per billboard - just leave out the sqrt() and it will run fast enough...

Share this post


Link to post
Share on other sites
Of course I'm already using only the squared distance.

"and it will run fast enough..."

For what? Sorting 128x128x128 = 2097152 squared distances in realtime? Of course it's NOT fast enough.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this