[ROAM Algorithm Homepage] [ROAM Algorithm Version 2 work in progress]
Subject:
Re: [Algorithms] Lindstrom / ROAM / CLOD and tristrips
Date:
Fri, 15 Feb 2002 15:52:39 -0800
From:
Mark Duchaineau Internal
Organization:
Lawrence Livermore National Laboratory
To:
gdalgorithms-list@lists.sourceforge.net
References:
1 , 2 , 3
Charles Bloom wrote:
>
> This seems based on a lack of understanding of how VIPM works. VIPM
> has *never* touched the buffers, and the new versions like "sliding window"
> and "stripping" give you better management of the index list.
>
> I'm thoroughly convinced that you could make a renderer with VIPM that
> consistently renders 100k triangles per frame, with those triangles
> being "nearly" the most important triangles in a many-million-triangle
> database (instancing required).
This is great, but how can the complexity of the whole system
be reduced without hurting ourselves? A good first step might be to use
triangle bintrees (ROAM splits) internal to a progressive vertex array
(PVA) instead of general PMs. Makes for a quick implementation,
relatively speaking, especially considering the bigger issue of how to
get the chunks continuous under split/merge. With chunk splits/merges
there is no limit at all to the database size, just assume each
chunk slides from say 128-256 tris and then has to split into
little chunks which also slide from 128-256. Limiting the
slide factor to 2X helps reduce the penalty you get from
enforcing a truely static slider in the PVA (pardon me if I say PVA
instead of VIPM--the term "PVA" captures everything needed
about the slick static slider idea whereas "VIPM" misses that).
>
> I'd also like to take this spot to remind people of a point that I
> think has been missed. Thatcher's chunk-morph technique could actually
> be used with VIPM to very good effect; in fact, it's probably best to
> not consider it an LOD scheme on its own, but rather as an enhancement
> to any existing LOD scheme.
>
I've been advocating this for a long time--except use ROAM split/merge
queues and triangle bintree chunks as the marco-level approach.
This is ideal since you want to make the best choice every frame
of which handful of PVA chunks you want to split/merge into
smaller/bigger chunks, given a time budget, and you need to deal
with continuity at the chunk boundaries. Just a lot simpler this
way. Also if some geometry is runtime modified, then you can
"dechunkify" seamlessly in those locales and "rechunkify"
when the geometry stabilizes again, and the unchunked-chunked
boundaries are easy to make continuous (relative to
PM-in-quadtree).
BTW, this is all largely reinventing the Lindstrom96 CLOD paper,
which did incremental updates to quadtree chunking and
fine-grained LOD within a chunk. In a sense the main new things
to do are: (a) optimize the the selection of the limited number
of chunk split/merges you can budget per frame, and (b) use the
PVA slider idea to replace the (only slightly) view-dependent
progression within a chunk with a truely view-independent
progression. In fact, if the eyepoint moves to a different side
of the chunk, so that the progression really should be different,
then you can recompute the progression every once in a long while
(long in number of frames anyway) to match the new chunk-eye
relationship.
At the end of the day, you would like to get a near perfect set of
100,000+ triangles in a frame for each view, but do only a tiny
bit of CPU work. This is all heading in the right direction,
but keep *both* goals in mind. I think we are on the same page
here.
As for morphing, I've seen some really cool demos, but I'd generally
rather have all those "lost" triangles back to make a more
accurate surface... With the PVA slider stuff per chunk, then
everything will be changing very smoothly (little scattered
changes that are hard to percieve). This is a huge improvement
over popping a big chunk all at once when the slider is missing.
One of the reasons fine-grained VD optimizers look so much
better than the old flight simulator block LOD schemes is
exactly because the CLOD changes are small in area and scattered
(uncorrelated) in their location and timing. Also note that
a lot of mesh CLOD popping artifacts are caused by the naive
use of hardware lighting on the vertices--this is a bad thing
to do. Use pixel shaders exclusively with geometry LOD.
-- Mark Duchaineau
Updated 2003-02-20 -- duchaine@llnl.gov