RE: [Algorithms] Understanding VIPM's

[Chris B. <Chr...@ma...>]

Tom, thankyou very, very much for the detialed response. The flanges idea is something I've never have considered, I guess I'm too used to conserving polygons.

The mail format problem is I suspect attributable to our corperate implementation as all my local client settings are set to plain text. In any case I won't post again to the list until they resolve the problem.



-----Original Message-----
From: Tom Forsyth [mailto:to...@mu...]
Sent: Tuesday, 15 August 2000 6:47 PM
To: gda...@li...
Subject: RE: [Algorithms] Understanding VIPM's


Hi Chris - plain text posting please. Ta.


Your first question seems to be a general VIPM question. Basically, you find
the error associated with collapsing all possible edges in your mesh, then
pick the one with the lower error, and collapse it. To collapse an edge, you
simply move one vertex on the edge to the other, and remove degenerate tris.
To expand, you do the opposite. Then recalculate all edge error values that
have changed (since the collapse will have changed some of them), and again
collapse the lowest-error edge. Repeat until there are no triangles left!
This is not locked to a regular grid, or indeed any particular topology -
except that most implementations don't deal with edges that have more than
two triangles using them (though they do handle fewer than two).



I assume you're talking about VIPM rendering of a terrain, rather than just
discrete objects. Be aware that things are not cut and dried for this
subject - as Charles says, there are a number of possible ways to VIPM
terrain.

Because VIPM is best when it takes a fixed "chunk" of something, then
processes it (which is what makes it idea for discrete objects), it needs a
certain adaptation to a continuous thing like a landscape.

The method I favour is to start with a regular heightfield grid. In fact,
any tesselation of your landscape data is just fine (including
non-heightfield data) - the concepts are the same, it's just simpler to talk
about the regular heightfield-type grid. Start with as high a resoloution as
you want (i.e. the maximum detail that anyone will see).

Then split this grid into chunks of a certain size (8x8 seems like a "good"
number, but it all depends on your app). Add "flanges" - small polygonal
edges that extend the chunk, sloping downwards underneath the neighbouring
chunk (and so not normally visible - they get Z-buffered away), and VIPM
each chunk.

The flanges make sure you can have adjacent chunks at different levels of
detail and still ensure there are no cracks between them. Remember - we're
talking about cracks of only a few pixels wide, if that, so it may be
kludgy, but the flange system will do just fine. And the really nice thing
about the flange system, as opposed to the other possibilites that Charles
mentions is that there is no need to communicate any information at all
between chunks at runtime, which reduces CPU time even further. The extra
overdraw you suffer is pretty minimal.


The variation of this scheme is to "mipmap" or "quadtree" your levels of
detail. If you have a view distance that is collossal, then whatever size
chunk you pick, it will always be wrong in some cases. Either the chunks are
too large (physically) and the VIPM is too coarse to reduce detail well at
different distances. Or they are too small physically, and when you draw to
the distance, you are collapsing them down to the maximum - two tris - but
then drawing tens of thousands of them.

The quadtree variation is similar to the quadtree texturing that some people
use, and indeed they do very similar things, and can easily be tied
together. You have fairly small chunks with flanges and you VIPM them as
above. Then you take groups of chunks (classically you take 4 chunks
together, but you could make it coarser and take 16 chunks together or
more), combine them into one mesh (bin the flanges between them, but still
have flanges at the new edges, and VIPM it as a single mesh.

Do this hierarchially, and according to distance, switch to whichever
quadtree level you want. There is also a good argument for controlling the
VIPM collapse order of each level so that the transition between drawing a
level, and drawing its four "child" levels is done when each uses the same
mesh, so that the transition is seamless.

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

-----Original Message-----
From: Chris Brodie [mailto:Chr...@ma...]
Sent: 15 August 2000 00:34
To: 'gda...@li...'
Subject: [Algorithms] Understanding VIPM's


I was going to send this e-mail directly to Mr Bloom for help but thought
that other lurkers here might be able to benefit from the answer I receive. 

I've been reading Charles Bloom's website documentation of VIPM's and am
starting to get a little more excited about them now that I realise how much
it can simplify the rendering pipeline amongst other things...

I have some question's though: 

-From what I've read I believe that the VIPM mesh would resemble something
along the lines of a Triangulated Irregular Network that is locked to a
grid. I don't however understand the edge collapsing and vertex insertion
routines. I understand the error array that would come with each
patch(chunk) but just not what to do with it.

-The other thing I don't understand is the edge matching for terrain chunks.
Under something like a triangle or quad ROAM implementation the edge mapping
is easy to visualise but I cant quite grasp how the edges get formed.  Does
the chunk start at minimum resolution, ie a square then get built up as the
error is implemented and the surface subdivided. If this is so at what point
is an edge broken. 

If anyone is interested in helping me understand this I'm happy to write up
a pretty graphical document that'll explain all this to other people new to
the technique (partly so you guys don't have to answer the question again,
partly so I know I understand the technique properly).
Many thanks 


Chris Brodie 

_______________________________________________
GDAlgorithms-list mailing list
GDA...@li...
http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list