[ROAM Algorithm Homepage] [ROAM Algorithm Version 2 work in progress]
Subject:
Re: [Algorithms] ROAM for arbitrary topology...
Date:
Mon, 25 Nov 2002 11:20:23 -0800
From:
Mark Duchaineau
Reply-To:
gdalgorithms-list@lists.sourceforge.net
Organization:
Lawrence Livermore National Laboratory
To:
gdalgorithms-list@lists.sourceforge.net
References:
1
Hi John,
Great question. Lot's of pointers here.
I have some old code showing ROAM on surfaces with subdivision-surface
connectivity (think of a subdivision surface with displacements). This
should handle things like arches, cliffs, simple caves, etc. For really
detailed topology, the holes, handles, components etc would need to
be simplified as well, and ROAM (nor progressive meshes) can deal with
that as is. Methods that allow topology simplification are based on vertex
clustering, or use implicit 3D density or signed-distance
fields with surface contouring. A couple of pointers would be:
1) Luebke's original siggraph paper on view-dependent display with
vertex clustering hierarchies
http://www.cs.virginia.edu/~luebke -- Luebke's current homepage
http://www.cs.virginia.edu/~luebke/publications/sig97.html -- main paper
2) my old demo code showing the data structures etc for ROAM with
subdivision-surface connectivity
http://www.cognigraph.com/ROAM_homepage -- see the introductory source
code and notes (Linux)
Note that the image on the top, the hollow tet thing, was generated
with this code.
More recent intro code shows a complete split-merge ROAM but not
with subdivision surfaces:
http://www.cognigraph.com/ROAM_homepage/Roamsteps -- Win32 and Linux
There is also a source/demo of chunk-based ROAM:
http://www.cognigraph.com/ROAM_homepage/LibGenROAM20020716.tar.gz --
Linux
3) new 3D ROAM paper (contouring a density field using a 3D ROAM mesh)
http://graphics.cs.ucdavis.edu/~gregorsk/ -- see IEEE Vis 2002 paper
There are upsides and downsides to all these methods. One thing
that is a little different and more in the spirit of recent work
discussed on this list is chunked ROAM. The idea is to do ROAM
on triangle bintrees, but draw each triangle as a patch of triangles
from AGP memory. More on continuity of the chunk edges later.
The important idea here is that you can put arbitrary meshes inside each
chunk, including interesting topology like an arch, hole, separate
components, etc. The main trick is that all topology changes must
occur on the interior of a patch diamond during split/merge. Since
diamonds alternate where there interiors are every other level
of detail, you can put topology changes most anywhere *except* at
the chunk corner vertices that already exist. In other words,
if topology must change right on a vertex in the base mesh, then put
the final (fine res) topology there to start with in that neighborhood.
You can always move your base mesh a little (just slide it around
a bit) to avoid this altogether (Simplification of Simplicity, anyone?).
You keep continuity by ensuring that the base edge
or each triangle patch has the same edges as each of its two potential
neighbors (the base neighbor can be from the same LOD or one coarser
level). You can make this constraint hold through a simple scheme
such as Josh Levenberg uses, by picking some uniform refinement
for the edge (each patch edge becomes four, eight or sixteen small
edges). There are fancier schemes to allow adaptive patch edge
refinements, such as Alex Pomeranz's work. The papers on these ideas
are here:
http://www.technomagi.com/josh/ -- see
"Fast View-Dependent Level-of-Detail Rendering Using Cached Geometry
http://www.cognigraph.com/ROAM_homepage -- see
"ROAM Using Surface Triangle Clusters (RUSTiC)"
So this doesn't answer in detail the very interesting question at the
heart of this: can you modify the split/merge operations to allow
topology changes? I heven't worked out the details on doing this
for fine-grained split/merges, only for chunks. It shouldn't
be too difficult to come up with a minial set of changes. Something
like:
1) normal split/merge of a diamond (two triangles become four with
one new vertex).
2) a handle gets added (two verts instead of one)
3) a component gets added (usual split but a four-point floating tet
gets added as well)
Cheers,
--Mark
John Cannon wrote:
>
> I'm considering using chunked, crack-free ROAM to adaptively simplify only
> the distant views of a massive dynamic terrain represented as a quad-based
> subdivision surface.
>
> Can you use ROAM-bintree simplifications for arbitrary topology terrains (or
> at least non-heightfield) ?
> Does it require vertex regularity and hence only suitable for semi-regular
> meshes (I imagine it can still work around extraordinary vertices) ?
> ROAM seems suited to quad-based subdivision (eg, Catmull-Clark) due to
> right-angle triangle requirement, but can it work for triangle-based
> subdivision (eg, Loop) ?
> Topology simplication would be nice (eg, small archway in distant view can
> be flattened out to pave the way for better simplification), but I think
> edge-collapse (one that doesn't retain 2-manifold) or something other than
> ROAM is required for that ?
>
> I should probably work these out for myself but any thoughts/comments are
> appreciated.
>
> John.
-- Mark Duchaineau
Updated 2003-02-20 -- duchaine@llnl.gov