algorithm for fast animating subdivision surfaces
5-09-00
by Charles Bloom
-----------------------------------------------------

The goal here is to animate the base mesh of an SS (subdivision
surface) without having to rebuild the damn SS every frame
(for smooth-skinned character animation, for example).  Here's
my idea:

at startup time, you have a VertArray (VA) and a TriangleList (TL)
indexing into the VA.  Take the VA and TL and build a winged edge
structure (or whatever) and do N steps of subdivision.  The result
is a New VA (NVA) and a New TL (NTL) which indexes into NVA.

Now each vert in the NVA is some linear combition of the verts in VA,
as determined by the catmull-clark or butterfly or whatever scheme.
So, for each vert in the NVA I simply store a little linear algebra :
a set of coefficients and multipliers into the original VA :

NVA[i] = Sum[t] C(it) * VA[ I(it) ]

So, in my SS object, I just store all the C's (floats) and I's (ints).

Each frame, the render call takes a new VA as a parameter (presumably
generated by some other vert animation).  Then I run through all the
sums to compute the NVA vert positions, and then just kick a render
with NVA and NTL (btw NTL never changes).

This should be much faster than redoing the subdivision each frame.
The amount of math is roughly equal (maybe a few more different
constants need to be f-loaded), but the number of memory touches is
drastically reduced, and the whole edge-face-neighbor data structure
can be tossed out.

Oh, BTW I also just realized that you can do a really great View-
Independent Progressive-Mesh (VIPM) back-end on this type of SS
(Subdivision Surface).  Here it is :

At startup time, you have your NTL and NVA (see previous message).
You build a VIPM collapse list for the NTL, using the verts in the NVA
to measure errors and such.  This also reorders the NVA into collapse-
order, so that to do VIPM you have the NTL and a set of collapse/refine
infos to modify the NTL with, and you have an NVA, and you simply use
some prefix of the NVA as the set of active verts.

So, each frame, you can do SS + VIPM very simply.  You simply ask the VIPM
how many verts we'll need to hit the desired error or vert target for this
frame, and you do the corresponding collapses or refines to change the NTL
as desired.  Then, you simply do the sums to make the NVA from the VA, only
doing the first bunch of verts that are active in the VIPM.

The result is like a non-uniform subdivision scheme, but it's blazing fast.