Selectively refinable subdivision meshes

ABSTRACT

We introduce RGB triangulations, an extension of red-green triangulations that can support selective refinement over subdivision meshes generated through quadrisection of triangles. Our purpose is to define a mechanism based on local operators that act on subdivision meshes while supporting operations similar to those available in Continuous Level Of Detail models. Our mechanism permits to take an adaptive mesh at intermediate level of subdivision and process it through both refinement and coarsening operations, by remaining consistent with an underlying Loop subdivision scheme. Our method does not require any hierarchical data structure, being based just on color codes and level numbers assigned to elements of a mesh, which can be encoded in a standard topological data structure with a small overhead.

REFERENCES

• 1: {BSW83} Bank R., Sherman A., Weiser A.: Refinement algorithms and data structures for regular local mesh refinement. In Scientific Computing, Stepleman R., (Ed.). IMACS/North Holland, 1983, pp. 3--17.
• 2: Paolo Cignoni , Leila De Floriani , Paola Magillo , Enrico Puppo , Roberto Scopigno, Selective Refinement Queries for Volume Visualization of Unstructured Tetrahedral Meshes, IEEE Transactions on Visualization and Computer Graphics, v.10 n.1, p.29-45, January 2004 [doi>10.1109/TVCG.2004.1260756]
• 3: Nira Dyn , David Levine , John A. Gregory, A butterfly subdivision scheme for surface interpolation with tension control, ACM Transactions on Graphics (TOG), v.9 n.2, p.160-169, April 1990 [doi>10.1145/78956.78958]
• 4: Mark Duchaineau , Murray Wolinsky , David E. Sigeti , Mark C. Miller , Charles Aldrich , Mark B. Mineev-Weinstein, ROAMing terrain: real-time optimally adapting meshes, Proceedings of the 8th conference on Visualization '97, p.81-88, October 18-24, 1997, Phoenix, Arizona, United States
• 5: Hugues Hoppe, Progressive meshes, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.99-108, August 1996 [doi>10.1145/237170.237216]
• 6: Leif Kobbelt, √3-subdivision, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.103-112, July 2000 [doi>10.1145/344779.344835]
• 7: {Loo87} Loop C.: Smooth subdivision surfaces based on triangles. Master thesis, University of Utah, Dept. of Mathematics, 1987.
• 8: David Luebke , Benjamin Watson , Jonathan D. Cohen , Martin Reddy , Amitabh Varshney, Level of Detail for 3D Graphics, Elsevier Science Inc., New York, NY, 2002
• 9: E. Puppo, Variable resolution triangulations, Computational Geometry: Theory and Applications, v.11 n.3-4, p.219-238, Dec. 1998
• 10: {Sab04} Sabin M.: Recent progress in subdivision: a survey. In Advances in Multiresolution for Geometric Modelling, Dogdson N., Floater M., Sabin M., (Eds.). Springer-Verlag, 2004, pp. 203--230.
• 11: Stephan Seeger , Kai Hormann , Gerd Häusler , Günther Greiner, A Sub-Atomic Subdivision Approach, Proceedings of the Vision Modeling and Visualization Conference 2001, p.77-86, November 21-23, 2001
• 12: {VG00} Velho L., Gomes J.: Variable resolution 4-k meshes: Concepts and applications. Computer Graphics Forum 19, 4 (2000), 195--214.
• 13: {VZ01} Velho L., Zorin D.: 4-8 subdivision. Computer-Aided Geometric Design 18 (2001), 397--427.
• 14: Joe Warren , Henrik Weimer, Subdivision Methods for Geometric Design: A Constructive Approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2001
• 15: {ZS00} Zorin D., Schröder P. (Eds.): Subdivision for Modeling and Animation (SIGGRAPH 2000 Tutorial N.23-Course notes). ACM Press, 2000.
• 16: Denis Zorin , Peter Schröder , Wim Sweldens, Interpolating Subdivision for meshes with arbitrary topology, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.189-192, August 1996 [doi>10.1145/237170.237254]
• 17: Denis Zorin , Peter Schröder , Wim Sweldens, Interactive multiresolution mesh editing, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.259-268, August 1997 [doi>10.1145/258734.258863]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling