State sorting

I have a rendering class, this class takes a struct which holds

  • the mesh to be rendered
  • the world transform matrix to use when rendering
  • and another struct which defines how the mesh is to be rendered (various flags and values-> textured, lit, light props, blended, blend funcs, etc)

With this information stored in an STL deque the class can draw these meshes later in any order it wishes. The problem when it comes to sorting these meshes is that it gets extremely complicated. I’m using a radix sort, which can’t beat it for sorting on multiple keys.

Basically I need help in coming with a way to sort these meshes. The way I have right now is a pain in the ass. Maybe a deque isn’t the best structure, maybe a radix sort isn’t the greatest. If anyone has any suggestions or pointers I’d greatly appreciate it.

This is indeed a cumbersome problem and I will describe my sollution to it (which probably is not the best one :wink:

Basically I made a presorted structure of “shader components”. That is my engine is a multipass/multitexture engine that renders polygons with shaders. These shaders are made up of shader components that represent one rendering pass.

This structure is sorted at load time so there is no sorting whatsoever when the rendering goes on.

My meshes then add theirselves to the passes they need to get rendered correctly and all meshes that has the same passes gets rendered at the same time.

This approach could probably be completed with some kind of delta states so you don’t switch render states between similar (but not exactly the same) shader components. However this can be hard if you have a big world and do not utilize all the shader components loaded each time you render. The sollution would be to set the delta states anyway (and have a lot of unnecceccary delta changes) or compute the delta states on the fly (which probably could be optimized to work well). However I have not tried this.

Hope this helps some!



That’s interesting, but each mesh object I have is not necessarily rendered every frame so I can’t pre-sort them at load time.

What I did consider was taking the render state struct and ordering it from least important vars to most important, then passing that entire struct as one single sort key to the radix sort. It would then be sorted correctly, but changing the sort order would require a recompile.

The other idea was maybe adding the meshes to a tree, which might save time as opposed to sorting a huge collection of meshes at the end of the frame.

[This message has been edited by outRider (edited 08-02-2002).]


I was also thinking about it. I would have a shader class. Each property (texture used, vertex program, blending modes, …) will be one component. Each component has a number associated which describes it cost to change its state, and one Id (e.g. texture ID, vertex program id, blending mode)So at first you sort all shaders(with the corresponding mesh) after the first component. You arrange all objects with a same component value(tex id ,…) in order. After that you sort all objects where the first component it equal after the second component. You repeat until all objects with equal first component are sorted. Then you proceed with the 3rd components… To archieve multipass you can make a component whith a high cost and value describing it render order.To perform culling you just have a component with an even higher cost and it value describing its visibility. You then render only those who arer visible. Transparency can also be accomplished by assigning a component with avalue indicating the render order

I hope you can follow


To clarify a bit:

I don’t sort the meshes just the shader components. I also have meshes that isn’t rendered every frame.

Using radixsort can be troublesome in this case… maybe if you define a couple of functions that compute the key from your struct and pass one these functions to your sorter (preferably via objects). This however adds one level of indirection and could impose some performance issues.

Often meshes are added to a tree (a scene graph) to sort objects spatially. Very good for collision detection/culling but I have not found it very good for render state sorting.

In my engine I kind of have both a scene graph and a “tree” (actually its a bunch of vectors) for the rendering. This way I can cull objects and cluster them when i render.

Hope this explains some.