Re: [Algorithms] Fast renderstate sorting

[Mark W. <mwa...@to...>]

We don't sort anything but translucent objects. We *group* by texture using 
a  custom hash table, as generally speaking, the order doesn't matter.
Our rendering is performed in "layers" where each layer may have its own 
blend mode etc. 99% of the time, we render opaque, additive then translucent 
stuff. We have a callback mechanism after each layer for custom content 
effects.
The only real complication comes in the form of objects dynamically changing 
their blend mode, such as when an object fades with distance and becomes 
opaque after fading in. In this case, we simply dynamically move the 
geometries into the appropriate layer depending on its state.
If we need a layer for a special effect, and it can't be done easily with 
the post-layer callbacks, then it is added globally (not that many in 
practise). I must admit I've never really seen the need for totally 
arbitrary state sorting and the like.
To render, I simply iterate through the layers, only processing those with 
geometries. This does result in more of a frame-deferred (buffered) type of 
rendering (not to be confused with a so-called deferred renderer!) but 
greatly simplifies most things for us.

HTH,
Mark

----- Original Message ----- 
From: "Madoc Evans" <tm...@ti...>
To: <gda...@li...>
Sent: Sunday, January 27, 2008 9:03 AM
Subject: [Algorithms] Fast renderstate sorting


>
> I'm looking to optimise my state sorting as it's currently very
> expensive, basically O(n^2).
>
> My current method looks for the state
> vector with the lowest cost from the most recently added. I've done as
> much research into set theory as I can stomach and found nothing
> applicable. The complete lack of global ordering criteria seems to
> defeat most algorithms.
>
> An order could possibly be introduced. For
> example, each state could be given a value and states prioritised so
> that a higher priority state is always more significant than a lower
> priority state. This seems both very messy and and not optimal as one
> state change would be considered more costly than all others put
> together.
>
> State sorting is something almost any 3D engine does and it
> seems to be taken for granted as if it were trivial. Rapidly sorting by
> many items by mutliple state change cost doesn't seem trivial to me. Am
> I just being dense?
>
> If I'm not just dense and hence the problem is not
> trivial, then I'd like to investigate it a little. So far, I am only
> able to suggest approximations based on re-using results from previous
> iterations. I've got some code set up to measure the sort time and
> resulting overall state cost on some hypothetical data, if anyone has
> some suggestions I'll be happy to test them.
>
>
> -------------------------------------------------------------------------
> This SF.net email is sponsored by: Microsoft
> Defy all challenges. Microsoft(R) Visual Studio 2008.
> http://clk.atdmt.com/MRT/go/vse0120000070mrt/direct/01/
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list
>