Sorting Billboards
Author
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
I'm using my simple implementation of bubble sort, certinly matching up to my needs:
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).
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).
Author
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
If you do this for a lot of particles every frame, it will be VERY slow
Author
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 ;)
"... 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 ;)
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,...
Enokh: You might want to read up on other sorting algos like radix, quick,...
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.
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?
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?
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...
Author
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.
"and it will run fast enough..."
For what? Sorting 128x128x128 = 2097152 squared distances in realtime? Of course it's NOT fast enough.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
