SPEAKER: Riccardo Fellegara

TITLE: A spatio-topological approach to the representation of simplicial complexes

ABSTRACT: The efficient representation of simplicial complexes is an active research topic in several fields, including geometric modeling, computer graphics, scientific visualization, and geographic data processing. Managing complexes in three dimensions and higher is not a simple task since the data structures proposed for three dimensions are quite large and are even larger when considering complexes in four dimensions and higher. Furthermore, current implementations cannot always keep large complexes entirely in system memory (in-core) and some out-of-core approaches, for example using a spatial data base, are intrinsically slow. There are two fundamental categories of queries proposed in the literature for interacting with simplicial complexes: those based on spatial locality and those based on topological connectivity. Spatial locality information can be retrieved through spatial queries, such as point location queries, box queries and ray intersection queries, which are needed to understand the relation between the cells of the complex and arbitrary regions in space, and are thus based on geometric information. Topological connectivity information can be retrieved through topological queries and are useful for understanding the way in which the simplexes in the complex are connected to each other. They are typically used to support applications that involve navigation on the complex (e.g., isosurface extraction or path computation). In general, topological data structures tend to be inefficient for spatial queries and spatial indexes exhibit a high overload when executing topological queries. The aim of this thesis is to propose and investigate new data structures for simplicial complexes in three dimensions and higher, based on spatial indexes and on multi-resolution models. The main idea is to introduce a framework which can generalize to arbitrary dimensions and can represent different type of complexes over manifold and non-manifold domains. In this presentation we show the two main contributions obtained during the first year of my phd. The first contribution is the design and implementation of a framework for efficiently managing spatial indexes for tetrahedral meshes. The second contribution is a framework based on topological spatial indexes, which could efficiently compute topological relations, and can efficiently execute different tasks, such as mesh simplification, with respect to existing topological data structures.