The discretization of regions is also based on advancing front technique. Faces bounding the region under consideration and created during surface discretization are collected to form the initial front. The mesh generation then continues on the basis of the face removal using similar steps as in the case of surface discretization until there are no remaining faces in the front:

- The first available face in the front is made active. The
nodes , and are oriented in anticlockwise sense with
respect to normal pointing inside (not yet discretized part of)
the region (Fig. 6).
- The position of ``ideal'' point , forming the new
tetrahedron, is calculated as
where

The position of points , and on the sides of active face and associated mesh size is calculated according to the following formulas (analogous to those used in surface discretization)

- The new position of ``ideal'' point is evaluated
taking into account local mesh size gradation in the same way as in
the case of surface discretization (this point is now
referred as )
where

- The local neighbourhood of point in terms of a set of
octants is established.
- The neighbourhood is searched for the most suitable candidate
to form a new tetrahedron . Again, two auxiliary geometrical
loci are constructed around point to resolve the acceptance
of tentative node . Firstly, a sphere with center in
and radius of . And secondly an ellipsoid
derived from sphere by extension of its half-axis parallel to
the active face by a half. The similar set of rules as in the
case of surface discretization (Fig. 5) is used to select point .
Point is
- identical with point if there is no point inside the sphere , no point inside the ellipsoid forming a face directly connected with the active face and there is no point inside the sphere circumscribed to the tetrahedron .
- an already existing node inside the sphere circumscribed to the tetrahedron if there is no point inside sphere circumscribed to the tetrahedron , no point inside the sphere and no point inside the ellipsoid forming a face directly connected with the active face .
- taken as node if it falls inside the sphere and there is no other node inside the sphere circumscribed to the tetrahedron .
- an already existing node inside the sphere circumscribed to the tetrahedron if there is no point inside sphere circumscribed to the tetrahedron . Point is an already existing node inside the sphere .
- taken as node if the already existing face , or forms sufficiently small angle with the active face and no point is inside the sphere circumscribed to the tetrahedron .
- an already existing node inside the sphere circumscribed to the tetrahedron if there is no point inside sphere circumscribed to the tetrahedron . Point is the point of already existing face , or being at sufficiently small angle to the active face .
- taken as node if it falls inside the ellipsoid and there is no other node inside the sphere circumscribed to the tetrahedron . Point is the point of already existing face , or .
- an already existing node inside the sphere circumscribed to the tetrahedron if there is no point inside sphere circumscribed to the tetrahedron . Node falls inside the ellipsoid and forms a face directly connected with the active face .

- To avoid overlapping of
the created tetrahedron with existing edges, faces and tetrahedrons in the
neighbourhood the intersection check is performed. In this case,
however, the intersection check is computationally much more demanding
due to the following reasons. Firstly, it is done fully in 3D and
secondly, considerably larger number of mesh entities must be
considered as the neighbourhood becomes truly three dimensional.
Also the number of cases in which the intersection check may be
entirely omitted is significantly reduced. In the presented
implementation, the new edges and faces of created tetrahedron are tested against
intersection with edges and faces in neighbourhood. The intersection
check is further limited only to those edges and faces from the
neighbourhood which have at least one point in common with the sphere
circumscribed to the new tetrahedron. This criterion effectively
replaces the reduction of the number of mesh entities involved in the
intersection check based on the investigation of their bounding box.
In the case an intersection is detected, the selected point is
rejected and the search of the neighbourhood is repeated without
taking this point into account.
- The front is updated to account for newly formed tetrahedron . The node , if chosen according to the rule (i), is registered into the octree.

Contradictory to 2D (or surface) triangulation 3D
discretization suffers from higher percentage of poor quality
elements. This is, first of all, typical for 3D Delaunay triangulation
in which high quality triangles may form degenerated tetrahedral
elements with volume close (or even equal) to zero. Unfortunately,
these elements, called slivers, are likely to be created also in
advancing front technique. Since the Delaunay property is used as the
governing criterion for neighbourhood search in the presented approach
the probability of sliver occurrence is even higher. Therefore some
postprocessing has to be employed to improve the quality of the mesh.
In this case, however, the smoothing process alone is not effective
enough. The application of Laplacian smoothing technique improves the
mesh in average but quality of sliver elements is usually spoiled even
more. It is therefore essential to combine the smoothing with some
topologically based technique. In the presented approach, two different
topological transformations (Fig. 7) are
employed. The actual transformation is accomplished only if its
application improves the overall mesh quality. The postprocessing then
consists of several cycles of
Laplacian smoothing (optionally with weighting) alternating with topological transformation
process. This technique proves to be effective and yields relatively high quality
meshes in only a few cycles (typically about five).

*Daniel Rypl
2005-12-03*