Constant-time navigation in four-dimensional nested simplicial meshes


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.

Shape Modeling Applications, 2004. Proceedings