Design, Analysis and Comparison of Spatial Indexes for Tetrahedral Meshes

TitleDesign, Analysis and Comparison of Spatial Indexes for Tetrahedral Meshes
Publication TypeReports
Year of Publication2010
AuthorsDe Floriani L, Fellegara R, Magillo P
Date Published2010///
InstitutionDepartment of Computer Science and Information Science, University of Genoa
Abstract

We address the problem of performing spatial queries on tetrahedral meshes. These latterarise in several application domains including 3D GIS, scientific visualization, finite element
analysis. We have defined and implemented a family of spatial indexes, that we call tetrahedral
trees. Tetrahedral trees are based on a subdivision of a cubic domain containing the mesh
defined either by an octree or a 3D kd-tree. For each of them, we have four variants of
the spatial index, depending on four different subdivision criteria. Here, we present such
indexes, we discuss how to construct them and perform classical spatial queries such as point
location and window queries. We compare the various tetrahedral trees based in memory
usage, performances in spatial queries and computation times for constructing them.