Ideal STL container for Renderque
Im trying to find a container which is ideal for a Renderque. At first sight, set seems ideal since it maintains all it's contents in a sorted manner.
However i wish to sort in many levels. I'll use an example to illustrate:
Lets say we have our stuff to render as this
Obj1->mesh(dog)-> texture(x)
Obj2->mesh(dog)-> texture(y)
Obj3->mesh(cat)-> texture(x)
Obj4->mesh(cat)-> texture(y)
Obj5->mesh(dog)-> texture(x)
Now i would want to sort by texture in my first level
Obj1->mesh(dog)-> texture(x)
Obj3->mesh(cat)-> texture(x)
Obj5->mesh(dog)-> texture(x)________________________This is the divide btwn diff textures
Obj2->mesh(dog)-> texture(y)
Obj4->mesh(cat)-> texture(y)
Now i want to sort by mesh within the divide without affecting the texture sort to get this:
Obj1->mesh(dog)-> texture(x)
Obj5->mesh(dog)-> texture(x)____________________Divide btwn diff meshes
Obj3->mesh(cat)-> texture(x)
________________________This is the divide btwn diff textures
Obj2->mesh(dog)-> texture(y)
Obj4->mesh(cat)-> texture(y)
Any help on what STL member functions/containers are best suited? I think i should use std::sort with std::set. But im not sure how i can do more than 1 level of sorting.
std::set allows you to specify your own sorting criterion. It is then up to you to provide a comparison operation that works on several attributes.
e.g.
Assuming that your mesh and texture already have meaningful comparison operators.
You may want to have a look at the std::pair template and its comparison operators...
Now, whether std::set is the ideal container or whether you're better off maintaining a sorted std::vector (or std::deque), I do not know. Experiment.
e.g.
bool renderqueue_less(const object& lhs, const object& rhs){ if(lhs.mesh->texture != rhs.mesh->texture) return lsh.mesh->texture < rhs.mesh->texture; return lhs.mesh < rhs.mesh;}
Assuming that your mesh and texture already have meaningful comparison operators.
You may want to have a look at the std::pair template and its comparison operators...
Now, whether std::set is the ideal container or whether you're better off maintaining a sorted std::vector (or std::deque), I do not know. Experiment.
std::set<> uses, on all STL implementations known to me, a red-black tree to store its data and requires memory allocations, so its not a good idea for containers which quickly change content.
If you can, either use an std::deque<>, which is fast for insertions and removals at the beginning and end of the list, or use an std::vector<>, which amortizes its performance drain after a few frames because it only ever grows and never actually shrinks its allocated memory again.
To sort with any number of sorting criteria, you have to create a custom comparison functor, for example, like this:
As a side note, you might want to reverse all that and sort by texture instead. I remember reading something about vertex buffer switches being faster then texture switches from Direct3D 8.0 upwards.
-Markus-
If you can, either use an std::deque<>, which is fast for insertions and removals at the beginning and end of the list, or use an std::vector<>, which amortizes its performance drain after a few frames because it only ever grows and never actually shrinks its allocated memory again.
To sort with any number of sorting criteria, you have to create a custom comparison functor, for example, like this:
struct LessMeshTexture : public std::binary_function<Obj, Obj, bool> { bool operator()(const Obj &Left, const Obj &Right) { // If left mesh is smaller, return true // (since we're a smaller-than comparison function) if(Left->mesh < Right->mesh) return true; // If right mesh is smaller, the the result is false else if(Right->mesh < Left->mesh) return false; // Otherwise, left and right must be using the same mesh else return Left->mesh->texture < Right->mesh->texture; }};// Example: Sort by mesh, then by texturestd::sort(objects.begin(), objects.end(), LessMeshTexture());
As a side note, you might want to reverse all that and sort by texture instead. I remember reading something about vertex buffer switches being faster then texture switches from Direct3D 8.0 upwards.
-Markus-
Quote:
Now, whether std::set is the ideal container or whether you're better off maintaining a sorted std::vector (or std::deque), I do not know. Experiment.
A sorted vector basically means an ordinary vector which is sorted by using std::sort?
Quote:Original post by GamerSg
A sorted vector basically means an ordinary vector which is sorted by using std::sort?
Originally, yes. Then, when you add a new element, you find out where it should go (e.g. with std::lower_bound()) and directly insert it there. You don't have to re-sort the whole container each time. The tradeoff of insertion vs. access speed is one you have to explore. Find what works best for your application.
Thanks for your help Fruny.
One new question, by overloading the operator <, i'm stuck to sorting in a predefined manner.
For some scenes, it might be more necessary to sort from front-back then texture, in some scenes it might be better to sort by shader,etc.. So is there a way to change the way objects are sorted on the fly?
One new question, by overloading the operator <, i'm stuck to sorting in a predefined manner.
For some scenes, it might be more necessary to sort from front-back then texture, in some scenes it might be better to sort by shader,etc.. So is there a way to change the way objects are sorted on the fly?
std::sort can take a comparator as argument aswell as the input iterators.
See these documents:
std::sort
Strict Weak Ordering
See these documents:
std::sort
Strict Weak Ordering
Quote:Original post by GamerSg
So is there a way to change the way objects are sorted on the fly?
yeah, you can make the comparison structure take some values in a constructor. Set some member variables and use those in the comparison operator, eg:
struct compare{ int sortBy; compare( int sb ) : sortBy(sb) {} bool operator () ( const Obj& a, const Obj& b ) { if( sortBy == 0 ) // implies shader { return sort by shader conditions } if( sortBy == 1 ) // implies texture { return sort by texture conditions } }};// somewhere else in code:std::sort( renderqueue.begin(), renderqueue.end(), compare(1) );
Quote:Original post by GamerSg
So is there a way to change the way objects are sorted on the fly?
Either maintain multiple containers, each sorted according to a given criterion, or re-sort the container when you need to change the sorting order. Alternatively, you can look at boost's multi-index containers.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement