State Sorting Tutorial
In terms of gaining maximum performance from your rendering code, there are two fundamental techniques - culling and state sorting. Culling removes non-visible geometry, while state sorting reorganises the ordering that calls are made to the rendering API in order to reduce how much of the state changes for each new primitive.
State sorting is quite a bit of a black art. Doing a web search leads to many questions about it, but very few concrete suggestions on going about implementing in it your application. This tutorial aims to give as good an introduction as possible, without getting into the specifics of a particular higher-level scene graph structure. Just in case you are wondering, the code examples are taken from the Aviatrix3D project.
What is state sorting?
State sorting is about minimising the number of state changes that go down the OpenGL pipeline by grouping collections of similar objects together. Some state changes are more expensive than others. For example, turning on and off depth buffer writing is far less expensive than turning on or off a light. What you need to do then, is to work out what State is more expensive than another and then sort your objects accordingly.
Of course, that leaves the question of "well how do I sort?". Sorting
requires that you have something to sort. Since this is an object-oriented
language, sorting collections of objects is a good idea. (well, duh...). How
you decide to sort them is a long and involved process. Every one that I've
seen done in Java ends up using a wrapper object that implements the
The next thing to look at is - what does that object contain that it needs to compare so that it can give this answer of negative, zero or positive? The simple answer is: whatever you need to compare to get the order correct. Heh, good answer that one (and one of the most frustrating to find a decent answer on the internet or in books). That object must hold all of the state that is of importance to your sorting order, so that means things like textures, lights, material, buffer state handling etc etc.
At about this point, you've moved into the world of a scene graph. It may not look like it at first, but step back and you'll see that you need collections of objects that hold info about the current texture (and all it's parameters), material state, light state etc. These are all classic objects of a scene graph architecture. There's not much of a jump going from this up to the next level of creating grouping nodes, switches, viewpoints etc. So then, the question arises - do you really want to implement your own scene graph, or would one of the pre-rolled ones like Xith3D or Aviatrix3D save you a lot of time and effort?
Assuming you've decided to plow ahead with your own solution, in each of these objects you will now need to implement a comparison between the two states. The good thing about the requirements is that it is very liberal so long as we keep to those basic ternary output talked about above. The goal here is to sort things to minimise state change, and that's all. It's not about priority sorting (though that could be done too), so your decisions about what is "less than" or "greater than" another object's state can be entirely arbitrary - so long as you are always consistent.
To illustrate how this work, let's take an example of a Light that we want
to state sort. There are 3 different different light types provided by OpenGL
- point, spot and directional light. Let's say our two objects that we want to
sort represent a light. Our first decision point is based on whether we even
have the same type of light. Changing from a spotlight to a spotlight is a
small state change compared to a directional light, for example. So, at the
start of our
If the objects are the same reference then obviously they're the same. Next,
cast the incoming object to be the same as us. It's ok if you toss a
From this point on, it's just more of the same - for every state that your object keeps, you need to do a comparison. Keep doing comparisons until you find something that doesn't match, or until there is nothing left to compare, and thus return zero. For example, here's the rest of that method:
See how at each comparison point all we do is look for inequality and then assign some random value if they aren't.One thing that you do want to do is order your equality checks in a way that is the most efficient. Do the big checks first, such as the type of light, as this will get the biggest results fastest. Then, order the checks as you go down for things that are more and more likely to be the same. Determining that is going to take a lot of just basic knowledge about 3D graphics and your particular application. Remember that this is an insertion sort algorithm that uses a tree-style structure where multiple comparisons are made time and again with O(n log n) time cost and thus the faster you can make a decision about the difference between two objects, the quicker you can sort.
Of course, that's the simple part, now you have to deal with the more complex
issue of multiple-states within an object. Think of your terrain - you not only
have a texture object, but material information, lights and the geometry itself
(though geometry is not typically state sorted). If
all you did was toss the individual lights, materials and textures into a single
array and then tell
For example, here's the comparison function out of the TextureUnit object in Aviatrix3D:
See how at this high level all you care about is whether the two objects being compared even have the same objects set, and if they don't, to do a comparison on them. This can be repeated right down the chain of object types that you're working with.
Now you've got the basics of a state sorting system going. There's plenty more to add, but this should be enough to get you up and running. Anything after this starts getting fairly implementation specific.