Sign in to follow this  
GamerSg

Ideal STL container for Renderque

Recommended Posts

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.

Share this post


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

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.

Share this post


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


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 texture
std::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-

Share this post


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

Share this post


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

Share this post


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

Share this post


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


Share this post


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

Share this post


Link to post
Share on other sites
Alternatives are; some container that supports random accessible iterators e.g. deque/vector and use the standard library heap operations.

Or use std::priority_queue which is a container adaptor, it adapts another container that is a model of a Sequence with a restricted interface it essentially does the same thing as the first method i described but all packaged up although the first method is more flexible.

Quote:
Original post by Fruny
Alternatively, you can look at boost's multi-index containers.


You read my mind, thats exactly what jumps up at me [smile]

[Edited by - snk_kid on March 29, 2005 12:38:06 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Fruny
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.


Looks exactly like what i need, ill take a look. Thanks.

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