The use of 3D shapes in different domains such as in engineering; entertainment; cultural heritage or medicine; is essential for representing 3D physical reality. Regardless of whether the 3D shapes are representing physically or digitally born objects; meshes are a versatile and common representation for the 3D reality. Nonetheless; the mesh generation process does not always produce qualitative results; thus incomplete; non-orientable or non-manifold meshes frequently are the input for the domain application. The domain application itself also demands special requirements; e.g. an engineering simulation requires a volumetric mesh either tetrahedral or hexahedral; while a cultural heritage color enhancement uses a triangular or quadrangular mesh; or in both cases even hybrid meshes. Moreover; the processes applied on the meshes (e.g. modeling; simulation; visualization) need to support some operations; such as querying neighboring information or enabling dynamic changes of geometry and topology. These operations need to be robust; hence the neighboring information can be consistently updated; during the dynamic changes. Dealing with this mesh diversity usually requires dedicated data structures for performing in the given domain application. This paper compiles the considerations toward designing a data structure for dynamic meshes in a generic and robust manner; despite the type and the quality of the input mesh. These aspects enable a flexible representation of 3D shapes toward general purpose geometry processing for dynamic meshes in 2D and 3D.
[ABGA04] ALLEGRE R.; BARBIER A.; GALIN E.; AKKOUCHE S.: A hybrid shape representation for free-form modelling. In Proceedings of the Shape Modeling International 2004 (Washington; DC; USA; 2004); IEEE Computer Society; pp. 7–18. 2
[AGFF09] ATTENE M.; GIORGI D.; FERRI M.; FALCIDIENO B.: On converting sets of tetrahedra to combinatorial and pl manifolds. Computer Aided Geometric Design 26; 8 (November 2009); 850–864. 3
[AJ05] ALUMBAUGH T. J.; JIAO X.: Compact array-based mesh data structures. In Proceedings of the 14th International Meshing Roundtable (September 2005); Springer-Verlag; pp. 485–504. 2
[Bau72] BAUMGART B. G.: Winged edge polyhedron representation.Tech. rep.; Stanford University; Stanford; CA; USA; October 1972. 2
[Bau75] BAUMGART B. G.: A polyhedron representation forcomputer vision. In Proceedings of the May 19-22; 1975; National Computer Conference and Exposition (New York; NY; USA; 1975); AFIPS ’75; ACM; pp. 589–596. 2
[BBCK03] BLANDFORD D. K.; BLELLOCH G. E.; CARDOZE D. E.; KADOW C.: Compact representations of simplicial meshes in two and three dimensions. In Proceedings of the 12th International Meshing Roundtable (September 2003); pp. 135– 146. 2
[BBCK05] BLANDFORD D. K.; BLELLOCH G. E.; CARDOZE D. E.; KADOW C.: Compact representations of simplicial meshes in two and three dimensions. International Journal of Computational Geometry and Applications 15; 1 (2005); 3–24. 2
[BKP10] BOTSCH M.; KOBBELT L.; PAULY M.; ALLIEZ P.; LEVY B.: Polygon Mesh Processing. AK Peters; 2010. 2
[BSBK02] BOTSCH M.; STEINBERG S.; BISCHOFF S.; KOBBELT L.: Openmesh - a generic and efficient polygon mesh data structure. OpenSG Symposium; 2002. 2
[CA03] CHEN J.; AKLEMAN E.: Topologically Robust Mesh Modeling: Concepts; Data Structures and Operations. Tech. rep.; Texas A&M University; 2003. 3
[CGG04] CIGNONI P.; GANOVELLI F.; GOBBETTI E.; MARTON F.; PONCHIO F.; SCOPIGNO R.: Adaptive tetrapuzzles: efficient out-of-core construction and visualization of gigantic multiresolution polygonal models. ACM Transactions on Graphics 23; 3 (August 2004); 796–803. 2
[CKS98] CAMPAGNA S.; KOBBELT L.; SEIDEL H.-P.: Directed edges - a scalable representation for triangle meshes. Journal of Graphics Tools 3; 4 (December 1998); 1–11. 2
[DDF02] DANOVARO E.; DE FLORIANI L.: Half-edge multitessellation: A compact representation for multi-resolution tetrahedral meshes. In Proceedings of the First International Symposium on 3D Data Processing Visualization and Transmission (Washington; DC; USA; 2002); 3DPVT ’02; IEEE Computer Society; pp. 494–499. 3
[DDFM05] DANOVARO E.; DE FLORIANI L.; MAGILLO P.; PUPPO E.; SOBRERO D.; SOKOLOVSKY N.: The half-edge tree: A compact data structure for level-of-detail tetrahedral meshes. In Proceedings of the International Conference on Shape Modeling and Applications (Washington; DC; USA; 2005); SMI Š05; IEEE Computer Society; pp. 332–337. 3
[DFGH04] DE FLORIANI L.; GREENFIELDBOYCE D.; HUI A.: A data structure for non-manifold simplicial d-complexes. In Proceedings of the 2004 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing (New York; NY; USA; 2004); SGP ’04; ACM; pp. 83–92. 2
[DFH03] DE FLORIANI L.; HUI A.: A scalable data structure for three-dimensional non-manifold objects. In Proceedings of the 2003 Eurographics/ACM SIGGRAPH Symposium on Geometry Processing (Aire-la-Ville; Switzerland; Switzerland; 2003); SGP ’03; Eurographics Association; pp. 72–82. 2
[DFH04] DE FLORIANI L.; HUI A.: Update operations on 3d simplicial decompositions of non-manifold objects. In Proceedings of the ninth ACM Symposium on Solid Modeling and Applications (Aire-la-Ville; Switzerland; Switzerland; 2004); SM ’04; Eurographics Association; pp. 169–180. 3
[DFH05] DE FLORIANI L.; HUI A.: Data structures for simplicial complexes: an analysis and a comparison. In Proceedings of the third Eurographics Symposium on Geometry Processing (Aire-la-Ville; Switzerland; Switzerland; 2005); SGP ’05; Eurographics Association; pp. 119–128. 2
[DFKP05] DE FLORIANI L.; KOBBELT L.; PUPPO E.: A survey on data structures for level-of-detail models. Advances in Multiresolution for Geometric Modelling 1 (2005); 57–82. 2
[DFMPS02] DE FLORIANI L.; MAGILLO P.; PUPPO E.; SOBRERO D.: A multi-resolution topological representation for non-manifold meshes. In Proceedings of the seventh ACM Symposium on Solid Modeling and Applications (New York; NY; USA; 2002); SMA ’02; ACM; pp. 159–170. 3
[DFMPS04] DE FLORIANI L.; MAGILLO P.; PUPPO E.; SOBRERO D.: A multi-resolution topological representation for non-manifold meshes. Computer-Aided Design 36; 2 (2004); 141–159. 3
[DT07] DECORO C.; TATARCHUK N.: Real-time mesh simplificationusing the gpu. In Proceedings of the 2007 symposium on Interactive 3D graphics and games (New York; NY; USA; 2007); I3D ’07; ACM; pp. 161–166. 3
[FG00] FREY P. J.; GEORGE P.-L.: Mesh Generation: Applicationto Finite Elements. HERMES Science; 2000. 2
[GLLR11a] GURUNG T.; LANEY D.; LINDSTROM P.;ROSSIGNAC J.: Squad: Compact representation for triangle meshes. Computer Graphics Forum 30; 2 (2011); 355–364. 3
[GLLR11b] GURUNG T.; LUFFEL M.; LINDSTROM P.;ROSSIGNAC J.: Lr: compact connectivity representation for triangle meshes. ACM Trans. Graph. 30; 4 (July 2011); 67. 3
[GR09] GURUNG T.; ROSSIGNAC J.: Sot: compact representation for tetrahedral meshes. In Proceedings of the 2009 SIAM/ACM Joint Conference on Geometric and Physical Modeling (New York; NY; USA; 2009); SPM ’09; ACM; pp. 79–88. 3
[GR10] GURUNG T.; ROSSIGNAC J.: SOT: compact representationfor tetrahedral meshes. Technical Report GT-IC-10-01; Georgia Institute of Technology; 2010. 3
[HSH09] HU L.; SANDER P. V.; HOPPE H.: Parallel viewdependent refinement of progressive meshes. In Proceedings of the 2009 symposium on Interactive 3D graphics and games (New York; NY; USA; 2009); I3D ’09; ACM; pp. 169–176. 3
[HVDF06] HUI A.; VACZLAVIK L.; DE FLORIANI L.: A decomposition-based representation for 3d simplicial complexes. In Proceedings of the fourth Eurographics Symposium on Geometry Processing (Aire-la-Ville; Switzerland; Switzerland; 2006); SGP ’06; Eurographics Association; pp. 101–110. 3
[Ket98] KETTNER L.: Designing a data structure for polyhedral surfaces. In Proceedings of the Fourteenth Annual Symposiumm on Computational Geometry (New York; NY; USA; 1998); SCG ’98; ACM; pp. 146–154. 2
[Ket99] KETTNER L.: Using generic programming for designing a data structure for polyhedral surfaces. Computational Geometry: Theory and Applications 13; 1 (May 1999); 65–90. 2
[KT02] KALLMANN M.; THALMANN D.: Star-vertices: a compact representation for planar meshes with adjacency information. Journal of Graphics Tools 6; 1 (January 2002); 7–18. 2
[LCCC01] LÉVY B.; CAUMON G.; CONREAUX S.; CAVIN X.: Circular incident edge lists: a data structure for rendering complex unstructured grids. In Proceedings of the Conference on Visualization ’01 (Washington; DC; USA; 2001); VIS ’01; IEEE Computer Society; pp. 191–198. 2
[Lee99] LEE K.: Principles of CAD / CAM / CAE Systems. Addison-Wesley; 1999. 1
[LH06] LEFEBVRE S.; HOPPE H.: Perfect spatial hashing. ACM Trans. Graph. 25; 3 (July 2006); 579–588. 3
[LLLV05] LAGE M.; LEWINER T.; LOPES H.; VELHO L.: Chf: A scalable topological data structure for tetrahedral meshes. In Proceedings of the XVIII Brazilian Symposium on Computer Graphics and Image Processing (Washington; DC; USA; 2005); IEEE Computer Society; pp. 349–356. 3
[LSK 06] LEFOHN A. E.; SENGUPTA S.; KNISS J.; STRZODKA R.; OWENS J. D.: Glift: Generic; efficient; random-access gpu data structures. ACM Trans. Graph. 25; 1 (January 2006); 60–99. 3
[MB91] MUUSS M. J.; BUTLER L. A.: Combinatorial solid geometry; boundary representations; and non-manifold geometry. State of the Art in Computer Graphics: Visualization and Modeling 1 (June 1991); 185–223. 2
[PSSSM09] PENA SERNA S.; SILVA J.; STORK A.; MARCOS A.: Neighboring-based linear system for dynamic meshes. In
Proceedings of the 6th Workshop in Virtual Reality Interactions and Physical Simulations (Aire-la-Ville; Switzerland; Switzerland; 2009); VRIPHYS ’09; Eurographics Association; pp. 95– 103. 2
[SB11] SIEGER D.; BOTSCH M.: Design; implementation; and evaluation of the surface_mesh data structure. In Proceedings of the 20th International Meshing Roundtable (2011); IMR; pp. 533–550. 3
[SNCH08] SANDER P. V.; NEHAB D.; CHLAMTAC E.; HOPPE H.: Efficient traversal of mesh edges using adjacency primitives. ACM Trans. Graph. 27; 5 (December 2008); 144:1–144:9. 3
[TM06] TOBLER R. F.; MAIERHOFER S.: A mesh data structure for rendering and subdivision. In Proceedings of WSCG: International Conference in Central Europe on Computer Graphics; Visualization and Computer Vision (2006); pp. 157–162. 3
[Wei85] WEILER K.: Edge-based data structures for solid modeling in curved-surface environments. IEEE Computer Graphics and Applications 5; 1 (January 1985); 21–40. 3
[WMKE04] WEILER M.; MALLON P. N.; KRAUS M.; ERTL T.: Texture-encoded tetrahedral strips. In Proceedings of the 2004 IEEE Symposium on Volume Visualization and Graphics (Washington; DC; USA; 2004); VV ’04; IEEE Computer Society; pp. 71–78. 2
