Sign in to follow this  
staticVoid2

sorting triangles by more than one material

Recommended Posts

staticVoid2    381
hi there, I'm trying to find another way of rendering an array of triangles when each triangle references more than one material. The most elegant solution would be to do something like this:
struct Triangle
{
   Vertex v[3];
   Texture *tex0, *tex1;
};
and then rendering would be something like:
for(int i = 0; i < triangleCount; ++i)
{
   setTexture(tris[i].tex0, 0);
   setTexture(tris[i].tex1, 1);

   drawTriangle(tris[i].v);
}
but this would be too slow and take up too much memory. Another way I've been thinking about doing it would be to store n amount of lists of triangle lists where n equals the number of materials each triangle references. i.e.
struct Triangle { Vertex v[3]; };
struct TriangleList
{
   Texture* tex;
   std::vector<Triangle> tris;
}


struct Mesh
{
   std::vector<TriangleList> channels[MATERIAL_COUNT];
};
and then use blending to blend the results. e.g. if the first channel stored diffuse maps and the second channel stored bump maps then you could render the scene using the diffuse channel first then set multapicative blending and render the second channel. But I think this approach would also take up too much memory having to store a separate copy of the vertices for each channel. Is there any other ways to do this?

Share this post


Link to post
Share on other sites
zyrolasting    280
Hey C2182! See what I did there? [smile]

You're close, and you have the right kind questions in mind. The most general approach is split each and every set of triangles with different render properties into subsets identified with simple integers. This is the batching technique used by ID3DXMesh. I actually addressed this earlier today. Check my response to a similar thread here. Sorry if you don't actually use D3D9, but the information should still be helpful to you.

Cheers!
-Zyro

Share this post


Link to post
Share on other sites
staticVoid2    381
thanks for the reply :)

The problem is that I can have more than one attribute id per list of triangles. e.g. a lightmap, bumpmap diffuse map etc.

I suppose my question could be more generalized to: how do you sort an array of something where there is more than one sort value so that you have the least possible switches.

e.g.

struct A { int lightMapIndex, diffuseMapIndex; };

A array[] = {
{ 5, 3 },
{ 3, 3 },
{ 1, 2 },
{ 2, 3 }
};

if this was an array of triangles each indexing both a lightmap
and a diffuse map then there would be a total of 5 SetTexture calls

however if I ordered the array like so:

{ 5, 3 },
{ 3, 3 },
{ 2, 3 },
{ 1, 2 }

there would only be 4 SetTexture calls.

Share this post


Link to post
Share on other sites
OrangyTang    1298
Quote:
Original post by staticVoid2
I suppose my question could be more generalized to: how do you sort an array of something where there is more than one sort value so that you have the least possible switches.

One elegant approach is to sort multiple times with a stable sort. First sort by diffuse map, then sort by lightmap. Because a stable sort retains the sorting order of identical elements you'll end up with something very close to the optimal order.

However that involves sorting multiple times, which can get a little out of hand if you've got lots of materials. Instead you could use a radix sort which sorts by integer values - pack your diffuse texture id into the lower bits and the lightmap texture id into the upper bits and sort once and you should have what you're after. This means that as long as you can fit your state into a single integer sort value you only ever have to sort your data once.

Or you could just use a regular sort with a custom comparator that uses your material ids directly and prioritises first by lightmap texture and then by diffuse texture.

Share this post


Link to post
Share on other sites
sajad83    122
Hi SV2

you point to somethings and I think that you want to use multiply textures for each triangle and also wanna to sort them to decrease device.set() calls.

at first for use multiply textureing I suggest you to use texture atlas techniques. it means that you can collect and arrange some textures in one texture and then fixed up all u,v of vertices. so you jast call device.set() one time and each texture coordinates in vertices (u, v) pick thery colors from texture atlas. any other tech is that you collect all of your textures in one VolumeTexture and then change u,v of each vertex by u,v,w which w is texture depth. ( also you can create cube textures for less than 6 texture in each triangle ).
here are some links to texture atlasing:
http://developer.nvidia.com/object/texture_atlas_tools.html
http://http.download.nvidia.com/developer/NVTextureSuite/Atlas_Tools/Texture_Atlas_Whitepaper.pdf

in second you try to sort array of data by more than one sorting value.
let's suppose that you wanna sort an array of data by n(n>1) priority. for example at fisrt you want to sort data by shader, and then in second by texture and then by geometry(vertices&indices) and so on ...
you can implement an integer value (named index) for each component of array and sort array by any simple algorithm before start rendering loop. after you sort all of them set a unique index value for each of them.
now in rendering loop just sort packs of objects by their index.

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