A hierarchical spatial index for triangulated surfaces

TitleA hierarchical spatial index for triangulated surfaces
Publication TypeConference Papers
Year of Publication2008
AuthorsDe Floriani L, Facinoli M, Magillo P, Dimitri D
Conference NameInt. Conf. on Computer Graphics Theory and Applications (GRAPP)
Date Published2008///
Abstract

We present the PM2-Triangle quadtree (PM2T-quadtree), a new hierarchical spatial index for triangle mesheswhich has been designed for performing spatial queries on triangle-based terrain models. The PM2T-quadtree
is based on a recursive space decomposition into square blocks. Here, we propose a highly compact data
structure encoding a PM2T-quadtree, which decouples the spatial indexing structure from the combinatorial
description of the mesh. We compare the PM2T-quadtree against other spatial indexes by considering the
structure of the underlying domain subdivision, the storage costs of their data structures and the performance
in geometric queries.