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 order to control the element size distribution, an octree is built around the surface (or domain) to be discretized. The size of individual octants corresponds approximately to the required element spacing specified by the user (for example on the control grid) while the nodes of the octants are storing the required spacing exactly. To ensure the gradual variation of the element size, the maximum one-level octree difference of octants sharing an edge is enforced. This will guarantee creation of well shaped triangles. During the actual mesh generation the, required element size is extracted from the octree for a given location using the interpolation of octree nodal values of the mesh size.

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 the ``ideal'' point (forming the new ) is calculated taking into account local curvature and mesh size variation,
- the projection of point to the surface is evaluated,
- the local neighbourhood of point is established (in terms of a set of octants),
- 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 the newly formed .

The generated mesh is then subjected to optimization in order to improve the quality of the final mesh. The Laplacian smoothing technique in combination with topological transformations (diagonal edge swapping) is adopted. This yields the optimized grid after only a few cycles of smoothing (typically up to six). Note that, contradictory to the smoothing carried out in 2D, the repositioning of a node is likely to shift the node out of the surface. Therefore, the point-to-surface projection has to be employed to satisfy the surface constraint.

*Daniel Rypl
2005-12-03*