Material sorting

unless you have a HUGE number of material changes, that wont affect much at all... :)

The typical way of doing this is to break your geometry down into sub-meshes, where each sub-mesh corresponds to a specific material. In this way, when a new sector's geometry becomes visible, you just add the geometry's sub-meshes into their correct groups and render it when needed.

So a typical frame would look like this (extreme pseudocode warning)



This scheme doesn't natively handle translucent materials. But this can easily be handled by treating alpha-sorted materials as a single group and then sorting within the group by distance and rendering this group after all opaque groups.

I hope that answered your question...

Thank you both! Well, the amount of material switches isn't that big. But years ago, I once made a quad terrain and for each quad the material was applied again. Stupid of course, but since then I learned to sort it. But maybe sorting inside the sub-meshes is enough indeed.

@FreY, you used a technique I'm using as well. When new stuff becomes visible(or invisible), the geometry is added/removed from a material group. I used it in a case that this 'group update' wouldn't happen much. But in this case, its more common that meshes needs to be added/removed from a list. So it's got to be fast. What kind of listing approach do you guys advice? I used pointer lists for that to minimize looping through the whole list in order to find an item for removal and avoid re-allocating memory.

The transparent materials are called later, first all opaque polygons, then the transparent ones.

Thanks for helping!
Rick

Quote:

Stupid of course, but since then I learned to sort it. But maybe sorting inside the sub-meshes is enough indeed.

We all start off with naieve implementations :)

Quote:

What kind of listing approach do you guys advice

I use a custom non-allocating doubly-linked list. A linked list is ideal in this case because:
(1) you never index anything within the list
(2) you only traverse the list in order.
(3) the list is not persistent from frame to frame. In order to clear the list, it is sufficient to set the linked list head node to NULL.

Insertion and removal from my list is O(1) and a very small O(1) at that. Since there is no physical allocation, my implementation is very fast for these operations. I suppose I could post my linked list code (or a link to it) if you're interested :)

a array of stacks of pointers with fixed size should do the job and you access the pointers in sequence which makes it quite fast

plus resetting is only one single operation to be performed O(1) = 1 per group

i use a std:vector< std:vector > groups;
groups.reserve(numberofmaximumpossiblegroups);
and for each group allocate as much memory as needed

and add some counter variables since you are only updating the pointers no insertions no removal

I would be interested in a list like that definitely, since I´m currently planning a 2D action-adventure with 3D-engine behind it and I´m currently thinking about a feasible approach for sorting the stuff I need to render in an effective manner... currently I´ve come to this (purely theoretical) construct:

I´d use a list of "groups", which are identified through the material (supplied by a ResourceManager class) they use for rendering themselves. If the renderer is told to render some geometry with a material, it checks whether there is a group for that material. If there is such a group, the geometry is added to the group´s geometry. If there´s no such group a new group is added to the list.
I´d also dispose this list of groups every frame and build a completely new one.
The only problem I see is this adding of geometry to an already existing group:
Of course I would also like to render as much of that geometry of a group in one draw-call as possible. Therefore I would have to join the geometry´s vertex array (and index array) with the one in the group, so I could just render the whole vertex and index array in one call (ideally).

So I in fact have two problems:
a) the list of groups should be fast for searching and insertion, removal isn´t important...
b) joining of two arrays in an efficient manner

I guess solving these two problems would also solve spek´s problem, since he would only have to join the geometry from the newly visible sector with the geometry of the already existing group and would get rid of those abundant material changes.

no don t merge them there s an ideal number of triangles to be rendered at once with VBOs and merging required reallocation and copying which entirely kills you performance


store a group for each material
and each group contains a list of meshes to be rendered with the groups material or shader
i sort by shader and shaderclass instead of materials since shader and materials are nearly 1:1 related

theres no need to sort during runtime
at startup build a list of possible materials in the correct order (in my game this is typicaly 100-200)
during each render phase iterate over these 200 materials setting the state and drawing the meshes if applicable
iterating of 200 things takes no time

Sorry, I wasn't logged in when I made the above post.

what zedzeek told you works for static scenes without spatial partition

with sp. partitions you keep presorted lists in the leafs of your partition tree
and need to merge these at runtime

however you need to take lights into consideration which makes it a hole lot more complex

Quote:

The actual iteration shouldn't take long time, but what about actually switching the material? I'd never imagine you'd be able to switch shader programs 200 times per frame, and keep a good framerate. Maybe you could explain in a bit more detail?

you only set the material shader/textures etc if theres something oonscreen that uses it ie
if ( material[X].num_meshIDs )
{
set material
draw meshes
}

Quote:

I was also under the impression that in most systems, especially when using some form of spatial hierarchy for frustum culling, you would build a new list of visible objects every frame. Intuitively, I'd say this requires some sorting during runtime.

yes u build list of visual meshes each frame (which u can sort, i sort transparent from back to front and normal stuff from front to back but thats optional).

afterwards u see what material each mesh uses and add that meshs ID to that materials list of onscreen IDs
and then u do what i described above.
i hope thats clear