A scalable data structure for three-dimensional non-manifold objects

TitleA scalable data structure for three-dimensional non-manifold objects
Publication TypeConference Papers
Year of Publication2003
AuthorsDe Floriani L, Hui A
Conference NameProceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing
Date Published2003///
PublisherEurographics Association
Conference LocationAire-la-Ville, Switzerland, Switzerland
ISBN Number1-58113-687-0

In this paper, we address the problem of representing and manipulating non-manifold, mixed-dimensional objects described by three-dimensional simplicial complexes embedded in the 3D Euclidean space. We describe the design and the implementation of a new data structure, that we call the non-manifold indexed data structure with adjacencies (NMIA), which can represent any three-dimensional Euclidean simplicial complex compactly, since it encodes only the vertices and the top simplexes of the complex plus a restricted subset of topological relations among simplexes. The NMIA structure supports efficient traversal algorithms which retrieve topological relations in optimal time, and it scales very well to the manifold case. Here, we sketch traversal algorithms, and we compare the NMIA structure with data structures for manifold and regular 3D simplicial complexes.