Topology-reducing surface simplification using a discrete solid representation

ABSTRACT

This paper presents a new approach for generating coarse-level approximations of topologically complex models. Dramatic topology reduction is achieved by converting a 3D model to and from a volumetric representation. Our approach produces valid, error-bounded models and supports the creation of approximations that do not interpenetrate the original model, either being completely contained in the input solid or bounding it. Several simple to implement versions of our approach are presented and discussed. We show that these methods perform significantly better than other surface-based approaches when simplifying topologically-rich models such as scene parts and complex mechanical assemblies.

REFERENCES

• 1: Andújar, C. 1998. Space efficient connectivity test for n-dimensional images. Comput. Graph. 22, 4 (Aug.), 557--558.
• 2: Andújar, C. 1999. Octree-based simplification of polyhedral solids. Ph.D. dissertation. Dept. LSI, Universitat Politècnica de Catalunya, Barcelona, Spain. www.lsi.upc.es/~andujar.
• 3: Andújar, C., Ayala, D., Brunet, P., Joan-Arinyo, R., and Solé, J. 1996. Automatic generation of multiresolution boundary representations. Comput. Graph. Forum 15, 3, 87--96.
• 4: Andújar, C., Saona-Vázquez, C., and Navazo, I. 2000. LOD visibility culling and occluder synthesis. Comput. Aided Des. 32, 13, 773--784.
• 5: Ayala, D., Andújar, C., and Brunet, P. 1995. Automatic simplification of orthogonal polyhedra. In Proceedings of the International Workshop on Modelling, Virtual Worlds and Distribuited Graphics (MVD'95), D. Fellner, Ed. Infix, 137--147.
• 6: D. Ayala , P. Brunet , R. Juan , I. Navazo, Object representation by means of nonminimal division quadtrees and octrees, ACM Transactions on Graphics (TOG), v.4 n.1, p.41-59, Jan. 1985 [doi>10.1145/3973.3975]
• 7: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 8: Pere Brunet , Isabel Navazo, Solid representation and operation using extended octrees, ACM Transactions on Graphics (TOG), v.9 n.2, p.170-197, April 1990 [doi>10.1145/78956.78959]
• 9: Ciampalini, A., Cignoni, P., Montani, C., and Scopigno, R. 1997. Multiresolution decimation based on global error. Vis. Comput. 13, 5.
• 10: Cignoni, P., Montani, C., and Scopigno, R. 1998. A comparison of mesh simplification algorithms. Comput. Graph. 22, 1 (Feb.), 37--54.
• 11: Jonathan Cohen , Amitabh Varshney , Dinesh Manocha , Greg Turk , Hans Weber , Pankaj Agarwal , Frederick Brooks , William Wright, Simplification envelopes, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.119-128, August 1996 [doi>10.1145/237170.237220]
• 12: Matthias Eck , Tony DeRose , Tom Duchamp , Hugues Hoppe , Michael Lounsbery , Werner Stuetzle, Multiresolution analysis of arbitrary meshes, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.173-182, September 1995 [doi>10.1145/218380.218440]
• 13: Jihad El-Sana , Amitabh Varshney, Controlled simplification of genus for polygonal models, Proceedings of the 8th conference on Visualization '97, p.403-ff., October 18-24, 1997, Phoenix, Arizona, United States
• 14: Jihad El-Sana , Amitabh Varshney, Topology Simplification for Polygonal Virtual Environments, IEEE Transactions on Visualization and Computer Graphics, v.4 n.2, p.133-144, April 1998 [doi>10.1109/2945.694955]
• 15: El-Sana, J. and Varshney, A. 1999. Generalized view-dependent simplification. Comput. Graph. Forum 18, 83--94.
• 16: Carl Erikson , Dinesh Manocha, Simplification Culling of Static and Dynamic Scene Graphs, University of North Carolina at Chapel Hill, Chapel Hill, NC, 1998
• 17: Carl Erikson , Dinesh Manocha, GAPS: general and automatic polygonal simplification, Proceedings of the 1999 symposium on Interactive 3D graphics, p.79-88, April 26-29, 1999, Atlanta, Georgia, United States [doi>10.1145/300523.300532]
• 18: Henry Fuchs , Marc Levoy , S. M. Pizer, Interactive Visualization of 3D Medical Data, Computer, v.22 n.8, p.46-51, August 1989 [doi>10.1109/2.35199]
• 19: Michael Garland , Paul S. Heckbert, Surface simplification using quadric error metrics, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.209-216, August 1997 [doi>10.1145/258734.258849]
• 20: Markus H. Gross , Oliver G. Staadt , Roger Gatti, Efficient Triangular Surface Approximations Using Wavelets and Quadtree Data Structures, IEEE Transactions on Visualization and Computer Graphics, v.2 n.2, p.130-143, June 1996 [doi>10.1109/2945.506225]
• 21: Gueziec, A. 1996. Surface simplification inside a tolerance volume. Tech. rep. Yorktown Heights, NY 10598. Mar. IBM Research Report RC 20440.
• 22: Bernd Hamann, A data reduction scheme for triangulated surfaces, Computer Aided Geometric Design, v.11 n.2, p.197-214, April 1994 [doi>10.1016/0167-8396(94)90032-9]
• 23: Taosong He , Lichan Hong , A. Kaufman , A. Varshney , S. Wang, Voxel based object simplification, Proceedings of the 6th conference on Visualization '95, p.296, October 29-November 03, 1995
• 24: Taosong He , Lichan Hong , Amitabh Varshney , Sidney W. Wang, Controlled Topology Simplification, IEEE Transactions on Visualization and Computer Graphics, v.2 n.2, p.171-184, June 1996 [doi>10.1109/2945.506228]
• 25: 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]
• 26: Hugues Hoppe, View-dependent refinement of progressive meshes, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.189-198, August 1997 [doi>10.1145/258734.258843]
• 27: Kalvin, A. D., Cetting, C. B., Haddad, B., and Noz, M. E. 1991. Constructing topologically connected surfaces for the comprehensive analysis of 3D medical structures. In Medical Imaging V: Image Processing. Vol. 1445. SPIE.
• 28: Alan D. Kalvin , Russell H. Taylor, Superfaces: Polygonal Mesh Simplification with Bounded Error, IEEE Computer Graphics and Applications, v.16 n.3, p.64-77, May 1996 [doi>10.1109/38.491187]
• 29: Peter Lindstrom , Greg Turk, Evaluation of Memoryless Simplification, IEEE Transactions on Visualization and Computer Graphics, v.5 n.2, p.98-115, April 1999 [doi>10.1109/2945.773803]
• 30: William E. Lorensen , Harvey E. Cline, Marching cubes: A high resolution 3D surface construction algorithm, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.163-169, July 1987
• 31: Kok-Lim Low , Tiow-Seng Tan, Model simplification using vertex-clustering, Proceedings of the 1997 symposium on Interactive 3D graphics, p.75-ff., April 27-30, 1997, Providence, Rhode Island, United States [doi>10.1145/253284.253310]
• 32: David Luebke , Carl Erikson, View-dependent simplification of arbitrary polygonal environments, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.199-208, August 1997 [doi>10.1145/258734.258847]
• 33: C. Montani , R. Scateni , R. Scopigno, Discretized marching cubes, Proceedings of the conference on Visualization '94, October 17-21, 1994, Washinton, D.C.
• 34: Montani, C. and Scopigno, R. 1991. Quadtree/Octree-to-Boundary Conversion. In Graphics Gems II, J. R. Arvo, Ed. Academic Press Professional, Boston, MA.
• 35: Ohtake, Y. and Belyaev, A. 2001. Mesh optimization for polygonized isosurfaces. Comput. Graph. Forum 20, 3.
• 36: Jovan Popović , Hugues Hoppe, Progressive simplicial complexes, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.217-224, August 1997 [doi>10.1145/258734.258852]
• 37: Paolo Cignoni , Claudio Rocchini , Roberto Scopigno, Metro: measuring error on simplified surfaces, Centre National de la Recherche Scientifique, Paris, France, 1996
• 38: Ronfard, R. P. and Rossicnac, J. 1996. Full-range approximation of triangulated polyhedra. Comput. Graph. Forum 15, 3 (Sept.), C67, C76, C462.
• 39: Rossignac, J. and Borrel, P. 1993. Multiresolution 3D aproximations for rendering complex scenes. In Modeling in Computer Graphics. Springer-Verlag.
• 40: Rushmeier, H. E., Patterson, C., and Veerasamy, A. 1993. Geometric simplification for indirect illumination calculations. In Proceedings of Graphics Interface'93. Canadian Inf. Proc. Soc., Toronto, Ontario, 227--236.
• 41: Hanan Samet, Applications of spatial data structures: Computer graphics, image processing, and GIS, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 42: Pedro V. Sander , Xianfeng Gu , Steven J. Gortler , Hugues Hoppe , John Snyder, Silhouette clipping, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.327-334, July 2000 [doi>10.1145/344779.344935]
• 43: William J. Schroeder, A topology modifying progressive decimation algorithm, Proceedings of the 8th conference on Visualization '97, p.205-ff., October 18-24, 1997, Phoenix, Arizona, United States
• 44: William J. Schroeder , Jonathan A. Zarge , William E. Lorensen, Decimation of triangle meshes, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, p.65-70, July 1992
• 45: Marc Soucy , Denis Laurendeau, Multiresolution surface modeling based on hierarchical triangulation, Computer Vision and Image Understanding, v.63 n.1, p.1-14, Jan. 1996 [doi>10.1006/cviu.1996.0002]
• 46: Varshney, A. 1997. A hierarchy of techniques for simplifying polygonal models. In Course notes of ACM SIGGRAPH'97. ACM Press.
• 47: Veltkamp, R. C. 1992. Closed object boundaries from scattered points. Ph.D. dissertation, Erasmus University Rotterdam.
• 48: Xiaolin Wu, A linear-time simple bounding volume algorithm, Graphics Gems III, Academic Press Professional, Inc., San Diego, CA, 1992

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
Geometry simplification, multiresolution models, surface reconstruction