Introduction

The computer aided design (CAD) and engineering (CAE) became state of the art of engineering practice in many (not only industrial) fields influencing the design cycle of products from both qualitative and quantitative points of view. CAD and CAE applications matured in very sophisticated systems accommodating various phases of the product design, starting from the modelling, continuing with the simulation and optimization, and ending by the manufacturing of the final product. It is well recognized that numerical methods based on spatial discretization (as finite element method (FEM), boundary element method (BEM), and others) play an important role in CAD and CAE. Therefore tools for automated and efficient mesh generation, including the discretization of 3D surfaces, are also of high importance.

The 3D surface mesh generation, having a special position between 2D and 3D mesh generation, has been under intensive development in recent years. It is not only the starting point of discretization techniques for solids, based on triangulation of boundary surfaces at first, but it plays an important role for instance in shell analysis or BEM. The special status of 3D surface triangulation arises especially from the complex description of the surface. While there are available sophisticated data structures for description of arbitrary topology, the range of geometries which can be handled by existing algorithms is rather limited. Particularly, 3D surface meshing is restricted by the complexity associated with the mathematical description of the surface geometry.

The 3D surface discretization algorithms may be generally classified as direct or indirect. The direct methods [5] work directly on the surface in the physical space. The indirect methods [6], 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 anisotropic mesh generator and the generated grid is then mapped back onto the original surface.

Nowadays, most of the algorithms can handle parametric 3D surfaces (Ferguson, Coons, Bezier, B-spline surfaces) using usually the indirect approach, however many 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). The aim of this paper is therefore to extend an existing algorithm for discretization of parametric 3D surfaces to the family of discrete surfaces represented by a triangular grid of arbitrary topology. To avoid difficulties with the parameterization of these surfaces and their anisotropic triangulation in the parametric space, the direct discretization approach is adopted.

The paper is organized as follows. In Section 2, the reconstruction of a smooth 3D surface from the discrete data using the subdivision technique is explained. Section 3 briefly describes the actual mesh generation. Some implementation aspects, including a robust algorithm for point-to-surface projection, are outlined in Section 4. The performance of the algorithm is presented on several examples in Section 5 and the paper ends with concluding remarks in Section 6.

*Daniel Rypl
2005-12-03*