Spatial Modeling using Triangular, Tetrahedral, and Pentatopic Decompositions

Simple item page
dc.contributor.advisorSamet, Hananen_US
dc.contributor.authorLee, Michael Thomasen_US
dc.contributor.departmentComputer Scienceen_US
dc.contributor.publisherDigital Repository at the University of Marylanden_US
dc.contributor.publisherUniversity of Maryland (College Park, Md.)en_US
dc.date.accessioned2006-06-14T05:57:50Z
dc.date.available2006-06-14T05:57:50Z
dc.date.issued2006-04-28en_US
dc.description.abstractTechniques 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.en_US
dc.format.extent1140255 bytes
dc.format.mimetypeapplication/pdf
dc.identifier.urihttp://hdl.handle.net/1903/3534
dc.language.isoen_US
dc.subject.pqcontrolledComputer Scienceen_US
dc.subject.pquncontrolledspatial modelingen_US
dc.subject.pquncontrolledfinite element analysisen_US
dc.subject.pquncontrolledneighbor findingen_US
dc.subject.pquncontrolleddata structuresen_US
dc.subject.pquncontrolledhierarchical methodsen_US
dc.subject.pquncontrolledselective refinementen_US
dc.titleSpatial Modeling using Triangular, Tetrahedral, and Pentatopic Decompositionsen_US
dc.typeDissertationen_US

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
umi-umd-3367.pdf
Size:
1.09 MB
Format:
Adobe Portable Document Format
Download

Collections

UMD Theses and Dissertations
Computer Science Theses and Dissertations