Introduction

During the last decades, the finite element method (FEM) has become the most powerful tool for structural analysis. 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 prerequisite for the complete integration of the FEM with design processes in computer aided design (CAD), engineering (CAE), and manufacturing (CAM) systems. Nowadays finite element modelling involves discretization of very complex objects in terms of both geometry and topology. While sophisticated data structures for the description of arbitrary topology are available, 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. Most of the algorithms can handle parametric 3D surfaces, however many applications deal with the surfaces of discrete nature as deformed finite element meshes, grid of points scanned by computer tomography, digital terrain representations, surfaces represented in stereolithography format, etc.

The aim of this paper is to suggest a methodology applicable to generation of computational meshes over class of surfaces, geometry of which is described by discrete data in the form of 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 operating directly on the 3D surface is adopted. The actual surface triangulation is carried out by the advancing front technique which is found to be most appropriate for the direct discretization of 3D curved surfaces. The actual discretization consists of two phases. Initially, a smooth, so called limit, surface is recovered over the original control grid. This is accomplished using the interpolating subdivision based on the modified Butterfly scheme which yields surfaces (even in the topologically irregular setting of the control grid). Similarly, the limit boundary curves are recovered using one-dimensional interpolating subdivision producing curves. Finally, the reconstructed limit surface is subjected to the new triangulation accomplished using the advancing front technique operating directly on the limit surface. This algorithm can be seen as the extension of an existing algorithm for discretization of parametric 3D surfaces but without the necessity to construct a smooth parameterization of the whole surface and with the need of a special projection technique. Note that when handling complex models, additional phase identifying the individual entities (vertices, curves, surfaces, regions) of the discrete model should be prepended to the above mentioned two main phases. Reconstruction of boundary representation of the discrete model, however, is not subject of this work.

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 a few examples in Section 5 and the paper ends with concluding remarks in Section 6.

*Daniel Rypl
2005-12-08*