[Algorithms] Streaming Transforms

[J. W. R. <jra...@in...>]

With the Nv40 coming out there are soon going to be cards that will let
you render massive numbers of instanced objects without constantly
stalling out.

For quite some time we have been told to perform as few state changes as
possible.  However, when a transform is considered a 'state change' this
has prevented developers from doing massive (on the order or tens of
thousands) of dynamic objects at high framerate; even if the sum total
of those objects did not actually come near the triangle throughput of
the card.

I'm currently exploring how to render the theoretical maximum number of
instanced objects possible at high frame rate on the Nv40.

Once you start dealing with massive numbers of low polygon instanced
objects; very quickly you realize that just the transform data itself
can add up to a lot of memory.  

I am curious if you guys can think of more efficient ways to send
transform data in massive quantities.  For example, representing all of
your transforms as a quaternion and a translation would take less than
half as much bandwidth as a full 4x4 matrix (assuming of course your
objects have no scale.)

There is also the challenge of trying to manage this many entities
without iterating through them in various portions of your pipeline.

Thoughts?