I have a sorted array of objects (sorted back to front*), and I want to reorder them (to reduce videocard state changes), but they have dependencies (I can't reorder one object to be infront of an object that is supposed to cover it).

*2D graphics, lots of alpha, no depth buffer.

After sorting back to front, the dependencies are met, but it's far from optimal - there is room to re-arrange the draw calls to reduce state changes further.

So instead I'd sort by:

bool ShouldDrawBefore(const Object &objectA, const Object &objectB)
{
    if(objectA.coveredBy(objectB))
        return true;

    return (objectA.renderState < objectB.renderState);
}

That'll ensure the dependencies are met, and also group similar renderstates. This is better, but not quite there.

Imagine that I'm drawing a bunch of rocks, then one rock is occluded by a tree. If the rock renderstate is "less than" the tree renderstate, that means it'd go:

rock rock rock rock rock

tree //occluding tree

rock rock rock

tree tree tree tree

Instead, I'd rather once it switches to 'tree' that it tries to draw every tree that it can, before it switches back to rock.

rock rock rock rock rock

tree tree tree tree tree

rock rock rock

I'm trying to figure out how I'd do that - I'm fine making more than one sorting pass.

(there's much more than just two render states, but two is enough to demonstrate the problem)

Conceptually, I want something like this

bool ShouldDrawBefore(const Object &objectA, const Object &objectB)
{
    if(objectA.coveredBy(objectB))
        return true;

    //If we can avoid changing states, do so.
    //'previousRenderState' would be a lambda capture or functor member-var.
    if(objectB.renderState == previousRenderState) 
        return false;

    return (objectA.renderState < objectB.renderState);
}

While conceptually that'd work, in practice, many sort algorithms visit the elements of array in a arbitrary order, so 'previousRenderState' wouldn't be accurate until after the sort is complete.

Any suggestions for how I should go about sorting these?

I might miss something, but if you subivide your sorted list to smaller lists of equal items:

listOfLists = {
{rock rock rock rock rock},
{tree}, //occluding tree
{rock rock rock},
{tree tree tree tree}
}

And then do:

for (i=0; i<listOfLists.size; i++)
for (j=i+1; i<listOfLists.size; i++)
if (i.itemType == j.itemType and all lists between i...j do not occlude i) add i to j, clear i and break

You would get

{rock rock rock rock rock},
{}
{rock rock rock},
{tree tree tree tree tree}

which is what you want.

Would it make sense to sort on object type as second (or higher) sort criterium? That is, keep the "isbefore" sort, but if that isn't decisive, sort on object type.

That should group the same kinds of objects unless not allowed.

Say you have N objects with M "sort values", where M0 is prioritized as required depth order, M1 is shader, M2 is texture, etc...

Start by sorting by M0, to yield X <= N subgroups with equal M0. Then sort X0 by [M1, M2, ...] to minimize state changes when drawing the objects at the back. Then sort X1 the same way, but re-order the shaders in M1 used for that sort so that the last one that was used in X0 is at the front, same with M2 etc.

Loop over all Xi to do the same, always with the internal sort-values in Mi modified to put the last used value in Xi-1 at the front.

If you care about more than M0 and M1, you would have to recurse for new subgroups Y <= NX after sorting Xi to minimize changing texture when the shader changes within Xi.

Should be possible to optimize reasonably, as every recursion would only have to find the matching subgroup of Mi+1 and move it to the front of its parent..

You could make it more advanced by saying that M1 is valued as three M2 for example so if you had to change texture four times to avoid changing shader once you would re-order the priority of M1 vs M2 .. but I can't quite picture the exact complexity of that.. probably significantly worse.

Couldn't you just using a bit based sorting key? i.e

enum EObjectType
{
  objType_Tree,
  objType_Rock
};

struct SortID
{
   union
   {
     struct
     {
        uint32 renderState;
        uint32 objectType;
      };
      uint64 value;
    };

};

then you would create a sort id from by :

    SortID rockID;
    rockID.renderState = //how ever you generate the render state(possibly shader/textures/materials)..etc
    rockID.objectType = objType_Rock

    SortID treeID;
    treeID.renderState = //same as prior
    treeID.objectType = objType_Tree,

then you could just sort by:

   int32 Sort(SortID lhs, SortID rhs)
  {
     return lhs.value < rhs.value;
  }  

   Sort(rockID, treeID);

Then, if you're sorting a list as {tree,rock,rock,tree,rock,tree,tree,rock,tree},

it will be sorted into {tree,tree,tree,tree,tree,rock,rock,rock,rock}, without having to have separate lists, if you want to then sort by render state instead of object type, then you will switch the anonymous struct to

struct 
{
    uint32 objectType;
    uint32 renderState;
};
  

Thank you for the ideas, gentlemen! I appreciate the help.

Couldn't you just using a bit based sorting key?

if you're sorting a list as {tree,rock,rock,tree,rock,tree,tree,rock,tree},
it will be sorted into {tree,tree,tree,tree,tree,rock,rock,rock,rock},

But I don't want it sorted {tree tree tree tree} (see below).

So, generally, this is just a sort with hierarchical sort criteria (which is pretty straightforward - just a single sorting pass comparing on multiple criteria).

It's a tad more complicated then that, unless I'm accidentally overcomplicating the problem.

Except that you have some need to group all trees together in one draw call. In that case, I would just make the trees a single object (from the point of view of the sorting algorithm), with a depth equal to the minimum depth of all trees.

No, the trees don't need to be a single draw call. Perhaps using trees and rocks was a poor example on my part.

I don't care if the trees get split into two or more drawcalls, I just want to reduce the number of drawcalls in general (whether they be trees, rocks, or anything else).

Take a look at this:


Some of the shrubs are infront of the tree trunks, some of the shrubs are behind the tree trunks, some of the shrubs are isolated and can basically be drawn at any time.

Basically, my complication is, I don't want it sorted by depth except where it's required to be. I might be thinking about this wrong, though.

One thing I've done elsewhere is, if something is "isolated" (or if a group of something is isolated), sort all the non-isolated stuff first, and just insert the isolated stuff in whatever drawcall is convenient.

I think Erik Rufelt and JoeJ have the right idea: Sort once, split into groups, reorder entire groups if the group can be safely reordered. I'll try that approach and see where it leads me.

Hmm... I think I understand what you want to do, but I don't understand why you are worried about "isolation" and "groups". You want to reduce state changes, state changes are a combination of shaders, vertex/index buffers, and textures. This would be the "renderstate" portion of my key, if you want to then sort by depth "when necessary", which I'm guessing is when the two have the same render states, then you reserve a portion of the "sort key" to depth bits, this would create a hierarchy of lists, without having to take the overly complicated route of sorting, then splitting into groups, and then reordering entire groups. You don't want to sort a list more than you need to, and having a single sort key, with bits allocated to the categories that you need, you would only require one sort. In your example, the shrub in the middle of the picture would be sorted so that it is next to objects with the same shader, and other render states that fit your criteria, it would then be rendered after the groups of shrubs in the foreground, because it's further away from the camera, all done without having to build separate lists and wasting cpu time determining which grouping requires reordering.

You want to reduce state changes, state changes are a combination of shaders, vertex/index buffers, and textures. This would be the "renderstate" portion of my key, if you want to then sort by depth "when necessary", which I'm guessing is when the two have the same render states, then you reserve a portion of the "sort key" to depth bits, this would create a hierarchy of lists,

I only care about depth when two polygons are overlapping (i.e. plant covering tree-trunk, tree-top covering tree-trunk, tree-trunk covering tree-shadow, tree-shadow covering different plant), regardless of their renderstate.


Maybe I could do it by forming chains (trees, really, since there can be more than one overlapper) of the touching objects, and then start interweaving the chains into the render groups from bottom-up, creating new render groups as needed, re-purposing existing ones when possible. I'll explore this along with JoeJ's/Erik's idea, when I get around to implementing it (I have a few other tasks on my TODO list first).

Ah, well okay then, more power to you if you want to merge depth buffer level detail with render state sorting. As an optimization tip, you could give each object, or maybe each "mesh chunk" if you want to get really detailed, an axis aligned box, and then project each aabb onto the screen. You could then create a heuristic to determine which objects are close enough to be considered a "render group", most likely based on distance from one another, and distance from camera. With this, you'd be able to skip the initial sort, and then only sort the render groups that would be created from this initial aabb projection pass. If the camera is placed so that object a is always in front of object b, then the construction of the render groups could be done offline, making the runtime render state sorting on par with the other methods speed wise.