In the presented implementation, the mesh generation is constrained
directly to the surface. A widely known advancing front
algorithm [8,9] with
some modifications allowing for surface curvature is employed. Firstly
the initial front consisting of edges constituting the
boundary^{2} of the surface (including inner
loops) is established. Once the initial front has been set up the mesh
generation continues on the bases of the edge removal algorithm
according to the following steps until the front becomes empty:

- The first available edge is pulled from the front. The edge
is oriented from to and the triangle is assumed to be
generated on the left side of it when viewing against the outer normal of
the surface (Fig. 1).
- The position of ``ideal'' point (Fig. 1), forming the new triangle,
is calculated as
(1)

where

(2)

(3)

(4)

The stands for the position vector, means the surface outer normal and denotes the element size (as extracted from the octree). Index refers to a particular point in 3D.

- The projection of point to the surface is
accomplished using the normal
, gradients
and
and
parametric coordinates and of any nearby point
(typically an already existing node).
The projection is performed in an iterative manner.
The point is firstly projected to the tangential plane given by
the normal
. The increments of parameters and ,
calculated using the surface gradients at point , are then used to
get better approximation of point . Consequently surface normal and
gradients are calculated at this point and the whole process is
repeated until the desired accuracy in the approximation of point
is achieved (Fig. 1).
Note that only one iteration is used for projection on planar
well parameterized surface.
- The new position of ``ideal'' point is evaluated
taking into account local surface curvature (this point is now
referred as )
(5)

where

(6)

The is reflecting the local mesh size variation and is given as

(7)

- Projection of point to the surface and the
corresponding mesh size are calculated.
- 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 triangle . 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-axe parallel to
the pulled edge by a half (Fig. 2).
The selection of point is
driven by the following rules. Point is
- identical with point if there is no point inside the sphere , no point inside the ellipsoid directly connected with the pulled edge and there is no point inside the sphere circumscribed to the .
- an already existing node inside the sphere circumscribed to the forming the largest angle if there is no point inside the sphere and no point inside the ellipsoid directly connected with the pulled edge .
- taken as node if it falls inside the sphere and there is no other node inside the sphere circumscribed to the .
- an already existing node inside the sphere circumscribed to the forming the largest angle . The point is an already existing node inside the sphere (Fig. 2).
- taken as node if the already existing edge or forms sufficiently small angle with the pulled edge and no point is inside the sphere circumscribed to the .
- an already existing node inside the sphere circumscribed to the forming the largest angle , where point is the end point of already existing edge or being at sufficiently small angle to the pulled edge .
- taken as node if it falls inside the ellipsoid and there is no other node inside the sphere circumscribed to the . Point is the end point of already existing edge or .
- an already existing node inside the sphere circumscribed to the forming the largest angle , where node falls inside the ellipsoid and is directly connected with the pulled edge .

Acceptance of node in cases (vii) and (viii) improves mesh quality in the mesh size transition zones and eliminates creation of chunks of edges when front close-ups.

To speed up the neighbourhood searching only the half-space given by point and vector is considered. - The intersection check is carried out to avoid overlapping of
the created triangle with an already existing one in the
neighbourhood.
Again using the parametric space the intersection check can be
performed quite efficiently. Moreover, if the edge or is the
already existing one the check can be entirely omitted. This will
reduce the number of intersection investigations to about a half.
- The front is updated to account for newly formed triangle . The node , if chosen according to the rule (i), is registered into the octree.

- ...
boundary
^{2} - The boundary edges are obtained as the result of the boundary curve discretization and their size must reflect the required element size stored in the octree.

*Daniel Rypl
2005-12-03*