The generation of unstructured meshes on free-form surfaces has been addressed e.g. by Peraire et al., Kreiner and Kröplin and Samareh-Abolhassani and Stewart. 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 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 . One of such surfaces, based on Bernstein 4th order polynomials, is Bezier bicubic surface, which has been adopted by the authors1.
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.