International Conference on Shape Modeling and Applications 2004 (SMI'04)
Constant-Time Navigation in Four-Dimensional Nested Simplicial Meshes
Genova, Italy
June 07-June 09
ISBN: 0-7695-2075-8
We consider a recursive decomposition of a four-dimensional hypercube into a hierarchy of nested 4-dimensional simplexes, that we call pentatopes. The paper presents an algorithm for finding the neighbors of a pentatope along its five tetrahedral faces in constant time. To this aim, we develop a labeling technique for nested pentatopes that enables their identification by using location codes. The constant-time behavior is achieved through bit manipulation operations, thus avoiding traversing the simplicial hierarchy via pointer following. We discuss an application of this representation to multi-resolution representations of four-dimensional scalar fields. Extracting adaptive continuous approximations of the scalar field from such a model requires generating conforming meshes, i.e., meshes in which the pentatopes match along their tetrahedral faces. Our neighbor finding algorithm enables computing face-adjacent pentatopes efficiently.
Citation:
Michael Lee, Leila De Floriani, Hanan Samet, "Constant-Time Navigation in Four-Dimensional Nested Simplicial Meshes," smi, pp.221-230, International Conference on Shape Modeling and Applications 2004 (SMI'04), 2004