From: Mark Duchaineau <duchaine@ll...>  20021125 19:20:34

Hi John, Great question. Lot's of pointers here. I have some old code showing ROAM on surfaces with subdivisionsurface 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 signeddistance fields with surface contouring. A couple of pointers would be: 1) Luebke's original siggraph paper on viewdependent 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 subdivisionsurface 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 splitmerge ROAM but not with subdivision surfaces: http://www.cognigraph.com/ROAM_homepage/Roamsteps  Win32 and Linux There is also a source/demo of chunkbased 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 ViewDependent LevelofDetail 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 finegrained 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 fourpoint floating tet gets added as well) Cheers, Mark John Cannon wrote: > > I'm considering using chunked, crackfree ROAM to adaptively simplify only > the distant views of a massive dynamic terrain represented as a quadbased > subdivision surface. > > Can you use ROAMbintree simplifications for arbitrary topology terrains (or > at least nonheightfield) ? > Does it require vertex regularity and hence only suitable for semiregular > meshes (I imagine it can still work around extraordinary vertices) ? > ROAM seems suited to quadbased subdivision (eg, CatmullClark) due to > rightangle triangle requirement, but can it work for trianglebased > 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 > edgecollapse (one that doesn't retain 2manifold) or something other than > ROAM is required for that ? > > I should probably work these out for myself but any thoughts/comments are > appreciated. > > John. 