The discretization is carried out in a hierarchical manner. Firstly, the model vertices are discretized. Then the curves are segmented using the mass curve of the required element density along that curve. And finally, the individual surfaces are triangulated.

In the presented implementation, the surfaces are discretized by the advancing front technique constrained directly to the surface and modified to allow for surface curvature [4]. Firstly, the initial front consisting of edges constituting the boundary curves of the surface (including inner loops) is established. Once the initial front has been set up the mesh generation continues on the basis of an edge removal algorithm according to the following steps until the front becomes empty:

- the first available edge is pulled from the front,
- the position of ``ideal'' point (forming the new )
is calculated

taking into account local surface curvature and mesh size variation, - the projection of point to the surface is evaluated,
- the local neighbourhood of point is established,
- the neighbourhood is searched for the most suitable candidate

to form a new , - the intersection check is carried out to avoid overlapping of
the created

triangle with an already existing one in the neighbourhood, - the front is updated to account for newly formed .

Although large effort is devoted to the creation of well shaped elements already in the phase of the advancing front procedure some badly shaped triangles are comprised in the grid. Therefore, the Laplacian smoothing technique is used to optimize the shape of elements. Contradictory to the smoothing carried out in 2D, the repositioning of a node (to the weighted average of positions of nodes connected to it) is likely to shift the node out of the surface. Therefore, the projection (the same one as used for ideal point to surface projection) is employed to satisfy the surface constraint. The optimized grid is usually obtained after only a few cycles of smoothing (typically up to five).

*Daniel Rypl
2005-12-03*