Shape Representations Based on Simplicial and Cell Complexes

Abstract

Simplicial and cell complexes are the most common way to discretize 3D shapes and two-, three and higherdimensional scalar fields. In this state-of-the-art report, we review, analyze and compare data structures for simplicial and cell complexes. We first classify such representations, based on the dimension of the complexes they can encode, into dimension-independent, and dimension-specific ones. We further classify the data structures in each group according to the basic types of topological entities they represent. We present a description of each data structure in terms of the entities and topological relations it encodes, and we evaluate it based on its expressive power, on its storage cost, on the efficiency in supporting navigation inside the complex (i.e., in retrieving topological relations not explicitly encoded in the data structure). We also discuss a decomposition approach to modeling non-manifold shapes, which has led to powerful and scalable representations.