[Algorithms] VIPM Strips

[Charles B. <cb...@cb...>]

I just read the paper "Skip Strips" by El-Sana et.al.
which seems to be a much-overlooked work on VDPM.  I
found it as part of the course notes in the simplification
course on the Siggraph 2k CD.

It's an interesting read, though quite archaic.
They make some clever data structures to speed up the
inherently slow algorithm of VDPM.

Anyway, it gave me ideas about how to strip VIPM.  In
fact, it's so easy, it's ridiculous.  Generate your
vertices in collapse order.  Create an optimal Indexed
Triangle Strip over those vertices, using duplicated
vertex indices to make it one single strip over the
entire mesh.  When you do a collapse, do it just like
normal VIPM, except that rather than changing indices
in a list of indexed triangles, you're changing them
in a list of indexed strips; it's just the same operation: 
	IndexList[ vsplit->changeIndex ] = newVertIndex;
You also can't reduce the number of triangles by two,
because the two collapsed triangles may not be at the
end of the list, and their verts are needed to continue
the strip on either side.

After you collapse some number of verts, you switch down
to a new strip which is optimized on that number of
verts.  This takes a cue from Tom Forsyth, and something
like power-of-2 sets of triangle strips are recommended.
For example, a mesh with 5000 triangles at full LOD might
have strip lists for {5000,3000,2000,1000,500,250,125}
triangles.

Now note that the memory usage of this scheme is almost
identical to that of normal VIPM (!!).  If you use power-
of-2 triangle strip list changes, then you only duplicate
the number of indices stored, and by using strips instead
of lists, you roughly half the storage needed.

The disadvantage of this scheme is obvious : your triangle
count stays the same until you swap down to a shorter strip.
In that sence, it's a lot like discrete LOD.  The difference
is that you're still doing collapses one by one, and reducing the
vertex count one by one, and virtually eliminating popping.

Finally, what's the advantage?  I'm not sure.  This method
is surely faster than conventional VIPM.  On the other hand,
I'm not sure it compares terribly well to Tom's idea of
stripped prefixes and tri-list suffixes.

-------------------------------------------------------
Charles Bloom    cb...@cb...    http://www.cbloom.com