###
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.