The presented work deals with the discretization techniques applicable to 3D surfaces that are recognized to be an important issue in the automated generation of high quality meshes in the framework of CAD, CAE, and CAM. The work is divided into several parts with respect to different methodologies.

The first part provides a global overview of the most common techniques related to the generation and optimization of two-dimensional meshes and to the discretization of 3D surfaces.

In the second part, an indirect approach for the triangulation of 3D parametric surfaces is introduced. This approach is based on the existence of a bijective mapping between the surface and a planar parametric space. Initially, the planar anisotropic mesh of the parametric space is generated using the extended AFT capable to produce stretched elements. The control space defining the magnitude and orientation of the stretching over the parametric space in terms of the ellipses of stretches is derived from the surface metric tensor using its spectral decomposition. The 2D mesh of the parametric space is then mapped onto the original 3D surface where it is subjected to additional optimization in terms of the Laplacian smoothing. A special attention is paid to the treatment of singularities arising in case of degenerated surfaces. The indirect approach is then presented on a set of examples demonstrating the vitality of the approach for the generation of uniform and graded meshes of reasonable quality.

The third part deals with the direct approach of the discretization of 3D parametric surfaces. This approach avoids the anisotropic meshing of the parametric space by constraining the triangulation directly to the surface body in the real space. The actual mesh generation is again performed using the modified AFT capable to handle the curvature of the surface. An octree data structure is used as the control space for the extraction of the desired mesh density as well as for the spatial localization. This leads together with a special front management to the almost linear computational complexity of the algorithm, which makes the direct AFT very competitive in practical applications. The excellent quality of the generated uniform and graded meshes is demonstrated on several examples illustrating the robustness and efficiency of the proposed approach.

In the next part, the direct approach for the triangulation of 3D parametric surfaces is extended to the family of discrete 3D surfaces represented by manifold triangulations of arbitrary nodal topology. The limit surface, over which the actual meshing is accomplished, is reconstructed from the control triangular grid using the modified butterfly scheme which is an interpolating subdivision technique yielding a continuous surface. The recovered limit surface is discretized directly in the physical space by the AFT, thereby parameterization of the surface is not required. Considering the discrete nature of the surface, a special attention is paid to the proper implementation of the surface projection in order to achieve robustness and reasonable efficiency of the algorithm. The performance of the proposed strategy is then presented on a few examples that reveal relatively high computational demands of the method.

The last part is dedicated to the generation of mixed quad-dominant and all-quadrilateral meshes. The main emphasis is laid on reusing an existing triangular mesh generator based on the AFT subjected to some minor amendments instead of developing a complex strategy for a new quadrilateral mesh generator. The actual discretization algorithm is split into several phases. In the first phase, a mixed mesh is created using the augmented triangular kernel described in the third part. The quadrilateral elements are formed by merging two adjacent and consecutively created triangles. In the second phase, the initial mesh, generally containing a large amount of triangular elements, is subjected to an optimization in terms of the Laplacian smoothing and topological cleanup resulting in only a very low percentage of the triangular elements in the mesh. These remaining triangles may be optionally eliminated by a one-level refinement applied in the third phase leading to an all-quadrilateral mesh. The proposed strategy is capable to produce uniform and graded mixed and all-quadrilateral meshes of high quality, which is demonstrated on a set of examples.

*Daniel Rypl
2005-12-07*