Adjacency and incidence framework: a data structure for efficient and fast management of multiresolution meshes

ABSTRACT

This paper introduces a concise and responsiveness data structure, called AIF (Adjacency and Incidence Framework), for multiresolution meshes, as well as a new simplification algorithm based on the planarity of neighboring faces. It is an optimal data structure for polygonal meshes, manifold and non-manifold, which means that a minimal number of direct and indirect accesses are required to retrieve adjacency and incidence information from it. These querying tools are necessary for dynamic multiresolution meshing algorithms (e.g. refinement and simplification operations). AIF is an orientable, but not oriented, data structure, i.e. an orientation can be topologically induced as needed in many computer graphics and geometric modelling applications. On the other hand, the simplification algorithm proposed in this paper is "memoryless" in the sense that only the current approximation counts to compute the next one; no information about the original shape or previous approximations is considered.

REFERENCES

• 1: ASPERT, N., SANTA-CRUZ, D., AND EBRAHIMI, T. 2002. Mesh: Measuring errors between surfaces using the hausdorff distance. In Proc. of the IEEE International Conference in Multimedia and Expo (ICME), vol. 1, 705-708.
• 2: Bruce G. Baumgart, Winged edge polyhedron representation., Stanford University, Stanford, CA, 1972
• 3: BRISSON, E. 1993. Representing geometric strutures in d dimension: topology and order. Discrete & Computational Geometry 9, 4, 387-426.
• 4: Swen Campagna , Leif Kobbelt , Hans-Peter Seidel, Directed edges—A scalable representation for triangle meshes, Journal of Graphics Tools, v.3 n.4, p.1-11, Dec. 1998
• 5: CAREY, R., BELL, G., AND MARRIN, C. 1997. The reality modeling language iso/iec 14772-1. Tech. rep., The VRML Consortium Incorporated.
• 6: Paolo Cignoni , Claudio Rocchini , Roberto Scopigno, Metro: measuring error on simplified surfaces, Centre National de la Recherche Scientifique, Paris, France, 1996
• 7: CIGNONI, P., MONTANI, C., AND SCOPIGNO, R. 1997. A comparison of mesh simplification algorithms. Computers and Graphics 22, 1, 37-54.
• 8: 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]
• 9: 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]
• 10: 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]
• 11: GARLAND, M. 1999. Multiresolution modeling: Survey & future opportunities. In Eurographics '99 - State of the Art Reports, 111-131.
• 12: GUÉZIEC, A. 1995. Surface simplification with variable tolerance. In Second Annual Intl. Symp. on Medical Robotics and Computer Assisted Surgery (MRCAS '95), 132-139.
• 13: HECKBERT, P. S., AND GARLAND, M. 1997. Survey of polygonal surface simplification algorithms. In Siggraph'97 Course Notes 25.
• 14: Hugues Hoppe , Tony DeRose , Tom Duchamp , John McDonald , Werner Stuetzle, Mesh optimization, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.19-26, September 1993 [doi>10.1145/166117.166119]
• 15: 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]
• 16: HOPPE, H. 1998. View-dependent refinement of progressive meshes. Tech. rep., MSR-TR-98-02, Microsoft Research.
• 17: HUBELI, A., AND GROSS, M. 2000. A survey of surface representations for geometric modeling. Tech. rep., #335, Swiss Federal Institute of Technology Zurich.
• 18: Junho Kim , Seungyong Lee, Truly selective refinement of progressive meshes, No description on Graphics interface 2001, p.101-110, June 07-09, 2001, Ottawa, Ontario, Canada
• 19: Reinhard Klein , Gunther Liebich , Wolfgang Straßer, Mesh reduction with error control, Proceedings of the 7th conference on Visualization '96, p.311-318, October 28-29, 1996, San Francisco, California, United States
• 20: KOBBELT, L., CAMPAGNA, S., AND SEIDEL, H.-P. 1998. A general framework for mesh decimation. In Graphics Interface, 43-50.
• 21: Aaron W. F. Lee , David Dobkin , Wim Sweldens , Peter Schröder, Multiresolution mesh morphing, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.343-350, July 1999 [doi>10.1145/311535.311586]
• 22: Peter Lindstrom , Greg Turk, Fast and memory efficient polygonal simplification, Proceedings of the conference on Visualization '98, p.279-286, October 18-23, 1998, Research Triangle Park, North Carolina, United States
• 23: LOOP, C. 2000. Managing adjacency in triangular meshes. Tech. rep., No. MSR-TR-2000-24, Microsoft Research.
• 24: Michael Lounsbery , Tony D. DeRose , Joe Warren, Multiresolution analysis for surfaces of arbitrary topological type, ACM Transactions on Graphics (TOG), v.16 n.1, p.34-73, Jan. 1997 [doi>10.1145/237748.237750]
• 25: M. Mantyla, Introduction to Solid Modeling, W. H. Freeman & Co., New York, NY, 1988
• 26: Xiujun Ni , M. Susan Bloor, Performance Evaluation of Boundary Data Structures, IEEE Computer Graphics and Applications, v.14 n.6, p.66-77, November 1994 [doi>10.1109/38.329098]
• 27: Renato Pajarola, FastMesh: Efficient View-Dependent Meshing, Proceedings of the 9th Pacific Conference on Computer Graphics and Applications, p.22, October 16-18, 2001
• 28: 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]
• 29: ROY, M., NICOLIER, F., FOUFOU, S., TRUCHETET, F., KOSCHAN, A., AND ABIDI, M. 2002. Assessment of mesh simplification algorithm quality. In Proceedings of SPIE Electronic Imaging, vol. 4661, 128-137.
• 30: 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
• 31: Gabriel Taubin , Jarek Rossignac, Geometric compression through topological surgery, ACM Transactions on Graphics (TOG), v.17 n.2, p.84-115, April 1998 [doi>10.1145/274363.274365]
• 32: TOUMA, C., AND GOTSMAN, C. 1998. Triangle mesh compression. In Proceedings of Graphics Interface'98, Morgan Haufmann Publishers, K. B. W. Davis and A. Fournier, Eds., 26-34.
• 33: Greg Turk, Re-tiling polygonal surfaces, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.55-64, July 1992
• 34: WAVEFRONT TECHNOLOGIES, I. 1998. Wavefront file formats. Tech. rep., Version 4.0 RG-10-004 (1ł ed.), Santa Barbara, California, USA.
• 35: WEILER, K. 1985. Edge-based data structure for solid modelling in curved-surface environments. IEEE Computer Graphics and Applications 5, 1, 21-40.
• 36: WEILER, K. 1998. The radial edge struture: a topological representation for non-manifold geometric boundary modelling. Geometric Modelling for CAD applications.
• 37: Steve Zelinka , Michael Garland, Permission grids: practical, error-bounded simplification, ACM Transactions on Graphics (TOG), v.21 n.2, p.207-229, April 2002 [doi>10.1145/508357.508363]
• 38: 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
          Subjects: Curve, surface, solid, and object representations

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.6 Methodology and Techniques
          Subjects: Graphics data structures and data types

Keywords:
boundary representation, mesh simplification, multiresolution algorithms, polygonal meshes