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

TitleA dimension-independent simplicial data structure for non-manifold shapes
Publication TypeReports
Year of Publication2006
AuthorsHui A, De Floriani L
Date Published2006/04/07/
InstitutionDepartment of Computer Science, University of Maryland, College Park
KeywordsTechnical Report

We consider the problem of representing and manipulating non-manifoldmulti-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.