On state and sorting.

["Adam D. Moss" <adam@gimp.org>]

Well, I've been diddling with my 3D engine (who
hasn't?) in past weeks and I've come to the point
where I have to start sorting my surface-groups
by state.

Basically, OpenGL state changes are expensive.
Everyone knows this, and I know this, but until I
really sat down and did some tweak-measure cycles
I didn't realize /how/ expensive.  In Mesa (probably
other implementations also), even *redundant* changes
are very expensive, like binding the same texture twice
in a row or glEnable()ing GL_TEXTURE_2D when it's
already enabled.  Ugh.

I'd assumed that texture state changes were expensive
mostly because of texture-memory-thrashing issues,
but, uh, no.  I suppose that since Mesa itself isn't
spotting redundant changes, they get all the way
down to the hardware and require a flush of the
rendering pipeline.  Ugh ugh.

So, here I am.  I have a scene full of faces (each
one typically requiring two or three texture passes,
and I'm on single-TMU hardware).  At least one of
these textures in the texture passes is shared between
many faces, but many decal textures are object-unique
with a few shared between a number of faces.

Longwindedly, I get to here: it's an interesting problem
with many facets thanks to the multi-pass (and rough
Z-sorting ideally needed for semi-transparent faces),
but I'm after an algorithm for sorting my faces by
'state', say texture primarily.  I could clearly use
something like quicksort or bucket-sort, but it occurs
to me that it's not 'sorting' I'm after, but 'grouping'
which could obviously be done faster.

Grouping algorithms, anyone?

--Adam