Tesselation of Cuboids with Steiner Points.

Nancy Hitschfeld, Gonzalo Navarro and Rodrigo Far&itacute;as

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 [Hitschfeld 1997], and then gives a recommendation on 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 always be 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 a 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.