Modular data structures for meshes and simplicial complexes

Efficient mesh data structures play a fundamental role in a broad range of mesh processing applications, in computer graphics, geometric modeling, scientific visualization, geospatial data science and finite element analysis. Although simple problems can be easily modeled on small low dimensional meshes, phenomena of interest might occur only on much larger meshes and in higher dimensions, as for simplicial complexes describing the shape of high-dimensional point clouds. In our research, we have developed a new data model for meshes and simplicial complexes, that we call a Stellar decomposition, which combines the encoding of minimal mesh connectivity information with a clustering mechanism on the vertices and cells of the mesh. Unlike combinatorial data structures, which explicitly encode the connectivity among cells of the mesh, this general approach has been shown to support scalability with size and dimension, and efficient processing of fundamental connectivity queries in a distributed fashion. Based on this model, we have developed new efficient representations for tetrahedral meshes endowed with a scalar field for the analysis and visualization of 3D scalar fields, and for arbitrary simplicial complexes. We have also devised a new and highly efficient decimation approach based on a Stellar decomposition, which simplifies large simplicial complexes by their homological properties.