The generation of unstructured meshes on free-form surfaces has been
addressed e.g. by Peraire * et al.*[2], Kreiner and
Kröplin[1] and
Samareh-Abolhassani[3] and
Stewart[4]. The main differences between the
presented paper and the related work above are in two areas: (i) The
mapping of the physical surface into the parametric space, and (ii) the
triangulation in the parametric space proper.

Peraire * et al.* use topologically regular patches which are fitted to
the actual surfaces. The parametric space is then a trimmed rectangle.
While this can avoid the need to deal with badly parameterized surfaces, it
also involves extensive computations, as the close-fit surfaces must be
computed, and also the trimming must be applied. They then work in the
transformed parametric space, i.e. they apply an inverse mapping which makes
the anisotropic (distorted) parametric space look isotropic. The
triangulation is then the usual advancing front technique for isotropic
meshes. However, a distinct disadvantage is the need to transform between
coordinate systems for a large number of points.

Kreiner and Kröplin use the same triangulation of the parametric space as
Peraire * et al.*. On the other hand, they work directly with the CAD
surfaces, taking into account the need to maintain compatibility between
the surface patches. The need to triangulate very badly parameterized
surfaces has not been addressed by these authors, however.

Samareh-Abolhassani and Stewart[4] have explored the possibilities of generation of structured meshes directly in the parametric space. This technique is directly applicable to unstructured meshes, therefore it is considered relevant here. They subdivide the task into three steps: (1) curve and surface parameterization, (2) grid generation, and (3) backward mapping from the parametric space into the physical domain. They use different non-uniform parametric spaces, i.e. they switch from the intrinsic parameterization of the surface to another one which gives the inverse distortion in the parametric space, so that the grid is of ideal shape after being mapped back on the physical surface. They note that the backward mapping is very non-linear and consequently computationally intensive and not fully robust.

Many CAD systems and geometric modelers work on basis of tensor product
polynomial surfaces, which enables their mapping onto planar parametric
space [2]. One of such surfaces, based on Bernstein 4th order
polynomials, is Bezier bicubic surface, which has been adopted by the
authors^{1}.

Unfortunately, most surfaces cannot be represented or even approximated by a single Bezier bicubic patch. Thus there is a need to split a given surface into a set of patches which represents a valid approximation of original surface. This entails the problem of mesh compatibility along edge shared by two (or more in the case of 3D solid modeling) adjacent patches. However, more serious difficulties are introduced by the fact that the bijective mapping between the Bezier bicubic surface and parametric space is generally not affine, what consequently leads to generation of poorly-shaped elements caused due to distortion and anisotropic stretch induced by the mapping. This effectively eliminates the possibility to use isotropic triangulation of the parametric space without any amendment. Therefore implementation of such a mesh generation technique is required that enables creation of directionally pre-stretched elements in the parametric space to obtain well shaped elements (near to equilaterals) after being mapped onto the original surface. Thus the mesh generator must be provided with a special mesh control function describing the stretch and distortion of elements in the parametric space. Both the above mentioned problems can be successfully resolved by employing advancing front technique for the mesh generation in the parametric space. However, some additional measures had to be taken to avoid difficulties in determination of mesh control values (stretch, distortion) at multiple control points (singularity points), which are typical for degenerated Bezier surfaces.

To verify the robustness of the proposed algorithm, a set of tests have been run, each one with different configuration in terms of shape of the surface and the required mesh density and gradation. Most of them have provided a very satisfactory solution, which proves the vitality of the suggested approach.

The paper is organized as follows. The second section deals with the extraction of mesh control function from a Bezier bicubic patch. The problem of singularities and the way they have been (at least partially) resolved are discussed in the third section. The fourth section concentrates on the proper mesh generation in the parametric space and the associated difficulties. Section five addresses some aspects of mesh optimization. Section six presents some of the examples and the paper is closed with the summary in section seven.

- ...
authors
^{1} - The Bezier bicubic patch was selected only to demonstrate the technique but the approach itself is generally applicable to all tensor product polynomial surfaces of arbitrary degree.

*Daniel Rypl
2005-12-03*