RE: [Algorithms] VIPM With T&L - what about roam

[Tom F. <to...@mu...>]

> From: Mark Duchaineau [mailto:duc...@ll...]
> 
> 
> Tom Forsyth wrote:
> 
> > No. The whole point of VIPM is that you calculate the 
> strips/list/whatever
> > offline. You then make a low number (e.g. five) 
> modifications to that data
> > each frame, according to whether an edge collapses or 
> expands. If an edge
> > doesn't change, then (a) the strip/list information for it 
> doesn't get
> > touched by the CPU, and (b) the edge isn't even considered 
> by the CPU.
> >
> > Basically, there is a list of collapses/expands (which it 
> is depends which
> > way you traverse it). The object has a "current position" 
> pointer. And each
> > frame, the CPU decides how far & in which direction it 
> needs to move the
> > pointer. When moving the pointer, the collapse/expand 
> entries simply say
> > which indices need to be changed, and to what value, so it 
> is a simple
> > memory-copying operation on indices to move the "current 
> position". No
> > thinking required byt he CPU, apart from deciding how many 
> tris it wants to
> > draw for the VIPM chunk - just memory bandwidth really.
> >
> > If you're using indexed lists, the tris are also stored in 
> collapse order,
> > so collapsed tris just get dropped off the end of the list. 
> If using strips,
> > then tris are collapsed out of the middle of strips just by 
> making them
> > degenerate (which hardware bins very quickly, since it 
> spots that two of the
> > three indices are the same).
> 
> Okay--I hadn't known about the tris index order.  Very Cool!  
> I hope this
> really works on current drivers/hardware though...  Since you 
> are shifting
> the index range around, a dumb driver would not understand that it
> doesn't need to do anything.

Not quite sure what you mean. Almost all drivers these days don't even look
at the indices you're sending (annoying Win2k validation aside) - they just
dump them to the card and let the hardware do the de-indexing for you.

And yes, it does indeed work on current hardware - the drivers just point
the hardware DMA streams at the index and vertex lists and say "do it".

> But this is really slick--it solves the
> issue of how to smoothly slide between to "chunk" detail levels
> at essentially no cost.  The degenerate strips is an 
> issue--in fact I can't
> picture a strip surviving after one of its vertices goes away--don't
> you have to change the indexing?  The only way I see this working is
> if you don't strip but just send three indices per tri in 
> your index arrays.

As well as no longer T&Lling the vertex (you don't actually do anything to
the vertex, it just falls off the end of the transformed list, because you
tell the API not to transform as many), you also change the indices that
refer to that vertex. You change them to refer to the vertex that
conceptually the edge collapsed to.

So if you have a strip 1,2,3,4,5,6:

2---4---6
|\  |\  |
| \ | \ |
|* \|  \|
1---3---5

And the edge 1-3 collapses, so that vertex 3 collapses to vertex 1, you
modify index 3 to point to the same vertex as index 1, and then you get:

 2---4---6
||  / \  |
|| /   \ |
||/     \|
 1-------5

The double vertical lines are just to show that the triangle marked (*) has
now become degenerate, since two of its vertices refer to vertex 1. The
hardware will bin that very quickly - it's not a significant overhead to
have it lying around unless the number of degenerates grows large (e.g.
twice as many degen as non-degen or something like that).

Note that vertex 3 will not actually be the third vertex in the list - it
will of course be the last, so it can fall off the end when the collapse
happens.

> Getting the vertex ordering done "right" sounds like an interesting
> issue for VIPM.  I'll be curious to see what ideas come of that.

Ah, well that's the trick. But at least it's all done offline. Algorithms
like Quadric Error Metrics (Garland & Heckbert:
http://graphics.cs.uiuc.edu/~garland/papers/quadrics.pdf) (and the
derivative by Hoppe) seem to work extremely well - I've been very pleased
with the results.

> --Mark D.

Tom Forsyth - Muckyfoot bloke.
Whizzing and pasting and pooting through the day.