Compact combinatorial maps: A volume mesh data structure

We propose a compact data structure for volumetric meshes of arbitrary topology and bounded valence that offers cell–face, face–edge, and edge–vertex incidence queries in constant time. Our structure is simple to implement, easy to use, and allows for arbitrary, user-defined 3-cells such as prisms and hexahedra, while remaining very efficient in memory usage compared to previous work. Its time complexity for commonly-used incidence and adjacency queries such as vertex and dart one-rings is analyzed.

Figure optionsDownload as PowerPoint slideHighlights
► A concise local connectivity description of generic 3-cell (volume cell) types.
► An efficient way to store all the maps for darts in volume meshes.
► A straightforward way of associating attributes to k-cells.
► A constant time complexity access to adjacency information.