Spatial Modeling using Triangular, Tetrahedral, and Pentatopic Decompositions
Spatial Modeling using Triangular, Tetrahedral, and Pentatopic Decompositions
Loading...
Files
Publication or External Link
Date
2006-04-28
Authors
Lee, Michael Thomas
Advisor
Samet, Hanan
Citation
DRUM DOI
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.