OpenVolumeMesh - A Versatile Index-Based Data Structure for 3D Polytopal Complexes

Michael Kremer 1 David Bommes 2 Leif Kobbelt 3
1 Computer Graphics Group
ACG - Computer Graphics Group
2 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : We present a data structure which is able to represent heterogeneous 3-dimensional polytopal cell complexes and is general enough to also represent non-manifolds without incurring undue overhead. Extending the idea of half-edge based data structures for two-manifold surface meshes, all faces, i.e. the two-dimensional entities of a mesh, are represented by a pair of oriented half-faces. The concept of using directed half-entities enables inducing an orientation to the meshes in an intuitive and easy to use manner. We pursue the idea of encoding connectivity by storing rst-order top-down incidence relations per entity, i.e. for each entity of dimension d, a list of links to the respective incident entities of dimension d1 is stored. For instance, each half-face as well as its orientation is uniquely determined by a tuple of links to its incident half-edges or each 3D cell by the set of incident half-faces. This representation allows for handling non-manifolds as well as mixed-dimensional mesh con gurations. No entity is duplicated according to its valence, instead, it is shared by all incident entities in order to reduce memory consumption. Furthermore, an array-based storage layout is used in combination with direct index-based access. This guarantees constant access time to the entities of a mesh. Although bottom-up incidence relations are implied by the top-down incidences, our data structure provides the option to explicitly generate and cache them in a transparent manner. This allows for accelerated navigation in the local neighborhood of an entity. We provide an open-source and platform-independent implementation of the proposed data structure written in C++ using dynamic typing paradigms. The library is equipped with a set of STL compliant iterators, a generic property system to dynamically attach properties to all entities at run-time, and a serializer/deserializer supporting a simple le format. Due to its similarity to the OpenMesh data structure, it is easy to use, in particular for those familiar with OpenMesh. Since the presented data structure is compact, intuitive, and e cient, it is suitable for a variety of applications, such as meshing, visualization, and numerical analysis. OpenVolumeMesh is open-source software licensed under the terms of the LGPL.
Type de document :
Communication dans un congrès
21st International Meshing Roundtable, Oct 2012, San Jose, United States. Springer, pp.531-548, 2012, Proceedings of the 21st International Meshing Roundtable. 〈10.1007/978-3-642-33573-0_31〉
Liste complète des métadonnées

Littérature citée [33 références]  Voir  Masquer  Télécharger


https://hal.inria.fr/hal-00762280
Contributeur : David Bommes <>
Soumis le : jeudi 6 décembre 2012 - 17:49:34
Dernière modification le : jeudi 8 février 2018 - 16:20:02
Document(s) archivé(s) le : samedi 17 décembre 2016 - 22:05:23

Fichiers

ovm.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Michael Kremer, David Bommes, Leif Kobbelt. OpenVolumeMesh - A Versatile Index-Based Data Structure for 3D Polytopal Complexes. 21st International Meshing Roundtable, Oct 2012, San Jose, United States. Springer, pp.531-548, 2012, Proceedings of the 21st International Meshing Roundtable. 〈10.1007/978-3-642-33573-0_31〉. 〈hal-00762280〉

Partager

Métriques

Consultations de la notice

415

Téléchargements de fichiers

403