Re: [Algorithms] Terrain LOD algos & HW friendliness

[<lin...@cc...>]

[snip]

> > Lindstrom-Koller does not exhibit this behavior.  That algorithm will
> > never instantiate a vertex unless the actual projection of the error
> value,
> > from the exact position of the vertex, exceeds the error threshold.

This is true, with the exception that a vertex may be included because
it depends on some other vertex, even though its error is smaller than
the threshold.

> > They
> > do pay a CPU cost for this -- it's what their whole region of
> uncertainty
> > thing is all about.  If you think of a Lindstrom block as being
> analogous
> > to a ROAM wedge, then you will see that where Lindstrom-Koller has a
> > mechanism for the uncertainty region (and delta-max and delta-min),
> > ROAM just assumes that any wedge exceeding delta-min must be
> subdivided.
> 
> ROAM is optimal and correct.  It is possible to spend extra work to get
> less over-conservative, but this isn't what Lindstrom et al do for
> their final bottom-up pass as far as I recall...but my recollections
> on that paper are fuzzy now (Peter?).

As are mine... :-)  Seriously, our algorithm is conservative only when
choosing what resolution block to use for a region, which is then
coarsened.  Conceptually, however, it works exactly as though each
vertex were visited bottom-up (from the very highest resolution height
field) and tested for inclusion.  Thus it always produces the "optimal"
triangulation with respect to the error metric, and is never
over-conservative.

________________________________________________________________________
Peter Lindstrom              Graphics, Visualization, & Usability Center
PhD Student                              Georgia Institute of Technology
lin...@cc...                http://www.cc.gatech.edu/~lindstro