Spatial Modeling using Triangular, Tetrahedral, and Pentatopic Decompositions

Abstract

Techniques are described for facilitating operations for spatial modeling using triangular, tetrahedral, and pentatopic decompositions of the underlying domain. In the case of terrain data, techniques are presented for navigating between adjacent triangles of a hierarchical triangle mesh where the triangles are obtained by a recursive quadtree-like subdivision of the underlying space into four equilateral triangles. We describe a labeling technique for the triangles which is useful in implementing the quadtree triangle mesh as a linear quadtree (i.e., a pointer-less quadtree). The navigation can then take place in this linear quadtree. This results in algorithms that have a worst-case constant time complexity, as they make use of a fixed number of bit manipulation operations. In the case of volumetric data, we consider a multi-resolution representation based on a decomposition of a field domain into nested tetrahedral cells generated by recursive tetrahedron bisection, that we call a Hierarchy of Tetrahedra (HT). We describe our implementation of an HT, and discuss how to extract conforming meshes from an HT so as to avoid discontinuities in the approximation of the associated scalar field. This is accomplished by using worst-case constant time neighbor finding algorithms. We also present experimental results in connection with a set of basic queries for performing analysis of volume data sets at different levels of detail. In the case of four-dimensional data which can include time as the fourth dimension, we present a multi-resolution representation of a four-dimensional scalar field based on a recursive decomposition of a hypercubic domain into a hierarchy of nested four-dimensional simplexes, that we call a Hierarchy of Pentatopes (HP). This structure allows us to generate conforming meshes that avoid discontinuities in the corresponding approximation of the associated scalar field. Neighbor finding is an important part of this process and using our structure, it is possible to find neighbors in worst-case constant time by using bit manipulation operations, thereby avoiding traversing the hierarchy.