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

Floriani, Leila De; Hui, Annie

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

Files

072-082.pdf (256.12 KB)

Date

2003

Authors

Floriani, Leila De
Hui, Annie

Publisher

The Eurographics Association

Abstract

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.

        @inproceedings{:10.2312/SGP/SGP03/072-082
,
booktitle = {Eurographics Symposium on Geometry Processing
},
editor = {Leif Kobbelt and Peter Schroeder and Hugues Hoppe
},
title = {{A scalable data structure for three-dimensional non-manifold objects
}},
author = {Floriani, Leila De and 
Hui, Annie
},
year = {2003
},
publisher = {The Eurographics Association
},
ISSN = {1727-8384
},
ISBN = {3-905673-06-1
},
DOI = {/10.2312/SGP/SGP03/072-082
}
}