The finite element method is currently the most widely used method for the structural analysis. As the computer performance steadily increases, the engineering applications cease to be limited to ``simple'' problems. The investigation of more and more complex 3D models, in terms of both geometry and topology, is becoming state of the art of engineering practice. Therefore tools for an automated and efficient mesh generation, including the discretization of 3D surfaces, are of high importance.

There are some practical requirements on surface meshing. Firstly, the algorithm should be able to deal with a wide collection of surfaces of different complexity without user intervention. Secondly, generation of well shaped triangles accurately representing the surface geometry is desirable. And finally, the algorithm must exhibit a favourable computational complexity, ideally the linear one.

While sophisticated data structures for 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.

The surface discretization algorithms may be generally classified as direct or indirect. The direct methods work directly on the surface in the physical space. The indirect methods, which are currently the most common ones, 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 presented paper addresses triangulation of 3D surfaces, geometry of which is described by discrete data. To avoid difficulties with the parameterization of these surfaces and their anisotropic triangulation in the parametric space, the direct approach is employed.

*Daniel Rypl
2005-12-03*