A dimension-independent simplicial data structure for non-manifold shapes

Abstract

We consider the problem of representing and manipulating non-manifold multi-dimensional shapes, discretized as $d$-dimensional simplicial Euclidean complexes, for modeling finite element meshes derived from CAD models. We propose a dimension-independent data structure for simplicial complexes, that we call the {\em Incidence Simplicial (IS)} data structure. The IS data structure is scalable to manifold complexes, and supports efficient traversal and update algorithms for performing topological modifications, such as hole removal or dimension reduction. It has the same expressive power and performances as the incidence graph, commonly used for dimension-independent representation of simplicial and cell complexes, but it is much more compact. We present efficient algorithms for traversing, generating and updating a simplicial complex described as an IS data structure. We compare the IS data structure with dimension-independent and dimension-specific representations for simplicial complexes. Finally, we briefly discuss two applications that the IS data structure supports, namely decomposition of non-manifold objects for effective geometric reasoning, and multi-resolution modeling of non-manifold multi-dimensional shapes.