Tessellations of Cuboids with Steiner Points

Proceedings, 9th International Meshing Roundtable, Sandia National Laboratories, pp.275-282, October 2000

MESHING
RESEARCH
CORNER

Nancy Hitschfeld
Integrated Systems Laboratory, ETH-Zürich
Email: nancy@iis.ee.ethz.ch
Nancy Hitschfeld, G. Navarro and R. Faria
Department of Computer Sciences, University of Chile
Email: gnavarro@dcc.uchile.cl, rfarias@dcc.uchile.cl

Abstract
This paper presents a study of different 1-irregular cuboids (cuboids with at most one Steiner point on each edge) that can appear when meshes are generated using extensions of the modified octree approach [5], and then gives a recommendation how to handle them. The study is divided into two parts depending on the type of refinement used: First, for the bisection based approach (Steiner points are midpoints of the cuboid edges), the 1-irregular cuboids are classified into equivalence classes (each element of the class is partitioned in the same way) and the exact value of the number of equivalence classes is computed. As this value is not too big, all 1-irregular cuboids can be handled using a hash table, and then a tessellation can be always found in constant time. Second, for the intersection based approach (Steiner points can be located at any position along a cuboid edge), the total number of 1-irregular cuboids, and upper and lower bounds for the number of equivalence classes are computed. The lower bound is too big to handle all the equivalence classes in a hash table. In this case, a mixed approach, i.e., the use of an pattern-wise algorithm for 1-irregular elements with bisected edges and an algorithm that computes in real time the tessellation for the other 1-irregular cuboids, is recommended.

Download Full Paper (Postscript Format)