not intersect, is generated. A single check on the quality of the elements does not provide relevant
information about the infinite loop, since the quality of the tetrahedra is still acceptable.
An efficient solution for convergence problems introduced by Lohner
8
and adopted by our
mesh generator consists of destroying those elements which impede the tetrahedron creation
process, or those elements which induce the problem. The proposed solution thus involves
avoiding problems, either by eliminating each problem encountered, or by doubling back. In all
cases, the ‘wise’ mesh generator must learn from its own errors, and avoid repeating them. Mo¨ ller
and Hansbo
19
also describe a similar technique in which the front can be modified.
Note that element destruction can be dictated not only by convergence needs, but also by
quality considerations. When a convergence problem arises inside a volume, the strategy involves
destroying unsatisfactory elements, and leaving the problem on the skin of the volume to the last.
Convergence strategy in fact depends on skin mesh quality alone. If the quality of an element on
the skin mesh is very bad, we describe in Section 5 a solution in which the criterion can be lowered
temporarily in order to find or create a candidate node.
It seems obvious that the order in which faces of the front are activated has a considerable
influence on the final result. The front is traditionally sorted by order of size in order to avoid the
larger elements perturbing creation of the smaller ones. Apart from the essential care required, the
emphasis is traditionally placed on the search for a candidate node. We have elaborated front
management strategies to improve the quality of the mesh and the convergence speed of the
algorithm.
In the advancing front technique, nodes and elements can be created simultaneou-
sly4, 5, 7, 8, 19, 20 or a set of nodes, created in a prior approach, can be triangulated.21 Jin and
Tanner
7
remark that the first method is believed to have a better control over the character of the
generated meshes.
Nevertheless, we have chosen the second approach. Nodes can be however created during the
triangulation in order to solve some difficult configurations.
The reasons for our choice are:
(1) We found in this approach a way to avoid the creation of infinite loop configurations. The
process is described in Section 6.2.
(2) Since an octree has been used as a background mesh, it seemed natural to create the nodes
with the octants.
(3) Finally, we found difficult to carry out the mesh process while satifying heavy constraints
on the shape and the size of the elements.
However, we are aware that a post-treatment must be applied to the mesh in order to satisfy the
requirements of the user.
4. NODAL GENERATION BY AN OCTREE METHOD
A conventional octree approach
11
is used for node generation. Division starts with a hexahedron
root enclosing the object. The octree is built by successive insertion of weighted points inside the
initial hexahedron root. Octants are divided recursively up to a solution level at which the ratio
between the size of the octant containing the point to be inserted and the element size at the point
does not exceed a value specified by the system (division parameter). After recursive division,
some octants are sub-divided to limit the level difference between adjacent octants to a factor of
GENERATION AND OPTIMIZATION OF TETRAHEDRAL MESHES 655
( 1998 John Wiley & Sons, Ltd. Int. J. Numer. Meth. Engng., 41, 651—674 (1998)