The computer aided design (CAD), engineering (CAE), and manufacturing (CAM) became state of the art of engineering practice in many fields influencing the design process of products from both qualitative and quantitative points of view. CAD, CAE, and CAM applications matured in very sophisticated systems accommodating various phases of the product design, starting from the modeling, continuing with the analysis and optimization, and ending by the manufacturing of the final product. It is well recognized that numerical methods based on a spatial discretization (as the finite element method, the boundary element method, the finite volume method, and others) play an important role in CAD, CAE, and CAM systems. Namely, the finite element method (FEM) is probably the most widespread analysis technique in the engineering community. This technique is capable of solving field problems governed by partial differential equations for very complex geometries. However, successful and efficient use of FEM still requires significant expertise, time, and cost. Many researchers are investigating ways to automate FEM, thus allowing improved productivity, more accurate solutions, and use by less trained personnel. Often the most time consuming and experience requiring task faced by an analyst is the discretization of a general geometric definition of the problem into valid and well conditioned finite element mesh. The accuracy and cost of the analysis directly depends on the size, shape, and number of elements in the mesh. Automatic generation of consistent, reproducible, high quality meshes without user intervention makes the power of the finite element analysis accessible to those not expert in the mesh generation area. Therefore tools for an automated and efficient mesh generation, including the discretization of 3D surfaces, are important prerequisites for the complete integration of the finite element method with design processes in CAD, CAE, and CAM systems.

The 3D surface mesh generation, having a special position between 2D and 3D mesh generation, has been under an intensive development in recent years. It is not only the starting point of some discretization techniques for solids, (e.g. techniques based on the triangulation of boundary surfaces at first as the advancing front technique (AFT) [15,43,56] or the Delaunay triangulation (DT) [17,44,52,65]), but it plays an important role, for instance, in shell analysis or BEM. The special status of the 3D surface triangulation arises especially from the complex description of 3D surfaces. While there are available sophisticated data structures for the description of arbitrary topology [2,8,16], the range of geometries which can be handled by existing algorithms is rather limited. Particularly, the 3D surface meshing is restricted by the complexity associated with the mathematical description of surface geometry.

The 3D surface discretization algorithms may be generally classified as direct and indirect. The direct methods work directly on the surface in the physical space and have to account for the surface curvature. The indirect methods, which are currently most common, utilize the bijective mapping between the surface and a planar parametric space. The parametric space is triangulated using a suitable planar mesh generator and the generated grid is then mapped back onto the original surface. The direct methods seem computationally more demanding because the performed operations are truly three-dimensional. On the other hand, they possess better control over the elements being generated and eliminate the necessity to implement anisotropic meshing of the parametric space or to further transform the parametric space to make it look isotropic.

With respect to the geometrical shape of the elements, the 3D surface meshing techniques can produce triangular, quadrilateral, or mixed (even including other types of elements, e.g. pentagons) meshes. Originally, most of the research on the development of fully automatic unstructured 3D surface mesh generators has been concentrated on various triangulation schemes. Their advantage lies in the fact that simplicial elements are most suitable to discretize domains of arbitrary complexity, particularly when locally graded meshes are needed. In the past, a wide class of algorithms for generation of triangular surface meshes has been established, among which two basic strategies - the AFT and the DT - have proved particularly successful. Later, the activity was focused on the development of methods for the generation of quadrilateral surface meshes. This effort was driven, first of all, by the fact that quadrilateral elements are much more popular in the engineering community because of their favourable features from the computational point of view.

Nowadays, most of the algorithms can discretize parametric 3D surfaces (Ferguson, Coons, Bezier, B-spline surfaces) using usually the indirect approach. However many (and not only engineering) applications deal with the surfaces of discrete nature (e.g. deformed finite element meshes, triangulations of points scanned by computer tomography, digital terrain representations, etc). Therefore, the dominating activity in the 3D surface meshing area is currently focused on the discretization of discrete surfaces of various topology.

The presented work is motivated by current trends in the automatic unstructured 3D surface mesh generation. It describes the triangulation of parametric 3D surfaces by the AFT using both the direct and indirect approaches with special emphasis on the robustness and computational complexity of the employed methodology and on the quality of resulting meshes. The direct technique is further extended to the family of discrete surfaces described by unstructured triangular grids of arbitrary topology. Again, the main focus is laid on the computational complexity of the implemented algorithms. And finally, the same direct triangular kernel is used in a modified form for the generation of mixed (and consequently also all-quadrilateral) meshes. This time the main objective is to reuse an existing triangular mesh generator based on the AFT subjected to some minor modifications instead of developing a complex strategy for a new quadrilateral mesh generator.

*Daniel Rypl
2005-12-07*