Re: On state and sorting.

[Steve Baker <sjbaker1@airmail.net>]

"Adam D. Moss" wrote:

> So, I'd like an algorithm that would know that this is
> a good and finished state:
> 33333111111222
> whereas an actual sorting algorithm would spend extra
> effort re-arranging this already-good ordering to:
> 11111122233333

What I have done at work (but not yet at home for games)
is to have all the OpenGL states stored as a data file
that the program loads up-front.

I do this for many reasons - but one nice spin-off is
that it's possible to write an off-line (or at least
on-program-startup) tool to sort those states into
order of 'sameness'.  You can't do a perfect job of
that because it's one of those problems that's a varient
of the travelling salesman problem that mathematicians
know can only be solved exhaustively.

However, you can get pretty close to perfection.

You can write a program that runs the code you use to
transition between states and measure the time it takes
to switch from any state to any other state.

Now you can re-order your list (using one of the well
documented travelling salesman heuristic algorithms) to
minimise the total transition time.

Now, unless you run this every frame after you've figured
out what's in the field of view, it's not going to yield
a perfect ordering every frame because some states will
have no polygons associated with them.  How well a static
ordering works depends on what ratio of total-states you
have in your game level versus the number of states that
are in the field of view on any given frame.  If most
states are visible most of the time then a static ordering
will be good.  If only a small percentage of your states
are visible on any given frame then it may be worth considering
doing a re-sort of just the visible states every frame. Having
a pre-computed list of the state change costs is worth-while
in any case.  At work, we only have to consider one graphics
card - so that table can be generated offline - but in a
game, you have to compute it for whatever hardware is being
used - so you may want to try to do that on startup.

Now, you have all the states in a big table - and it's
fairly simple to bucket-sort your polygons into the
'bucket' associated with each state.  You can also
fit the sorting of translucent 'states' to the end of
the list.

What complicates the issues for me are things like
matrix push/pop's.  If you have ten objects, each
of which is moving around and each of which has
two states needed to render it - then do you do
twenty matrix push/pops and only two state setups
or do you do ten matrix push/pops and twenty
state changes?

You can easily construct other difficulties of that
sort (eg Sorting alpha polygons by range).

----------------------------- Steve Baker -------------------------------
Mail : <sjbaker1@airmail.net>   WorkMail: <sjbaker@link.com>
URLs : http://www.sjbaker.org
       http://plib.sf.net http://tuxaqfh.sf.net http://tuxkart.sf.net
       http://prettypoly.sf.net http://freeglut.sf.net
       http://toobular.sf.net   http://lodestone.sf.net