[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: firstname.lastname@example.org Organization: Lawrence Livermore National Laboratory To: email@example.com 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 -- firstname.lastname@example.org