Introduction

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, etc.

An important class of discretely described 3D surfaces is the group of surfaces described by the stereolithography (STL) file format. The STL file format has become the standard data transmission format for rapid prototyping industry. This format approximates 3D surfaces of a solid model with oriented triangles (facets) of different size and shape (aspect ratio) in order to achieve smooth enough representation suitable for industrial processing of 3D parts using stereolithography machines. Producing a pre-production STL prototype of a part can greatly enhance the design of a product including its geometric visualization. While originally the STL files were introduced as a native file format of the STL CAD software created by 3D Systems company, almost all of today's CAD systems are capable of producing an STL file. This makes the STL format of 3D surface representation very attractive for practical use in general geometry preprocessing and design.

The aim of this paper is to extend a recently developed algorithm for discretization of discrete 3D surfaces [1] to class of surfaces geometry of which is described by discrete data in the STL format. The actual discretization consists of several phases. Initially, a boundary representation of the entire model is constructed from the STL file using feature recognition based on appropriate topological and geometrical operations. In this way, distinct model entities (vertices, curves, and surfaces) of topological nature (topological features) or with important geometrical aspects (sharp features) are established. In the current implementation, the geometrical operations are based on dihedral and turning angle, and on the aspect ratio of two neighbouring facets. Note that the current implementation makes no attempt to detect the volumes. In the next phase, a smooth (limit) surface is recovered over the original STL grid. This is accomplished using the interpolating subdivision based on the modified Butterfly scheme which yields surfaces (even in the topologically irregular setting). Similarly, the limit boundary curves are recovered using one-dimensional interpolating subdivision producing curves. Note that prior the actual subdivision process, the original STL grid is enhanced (in terms of both geometry and topology) to prevent some undesirable effects during the recovery process applied to surfaces with curvature in one direction only. In the last phase, the reconstructed limit surface is subjected to the triangulation accomplished using the advancing front technique operating directly on the limit surface. This avoids difficulties with construction of smooth parameterization of the whole surface.

The paper is organized as follows. In Section 2, the STL file format is described. Section 3 outlines the extraction of the boundary representation of the model. The reconstruction of a smooth 3D surface from the discrete STL data using the subdivision technique is recalled in Section 4. Section 5 briefly describes the actual mesh generation. The capabilities of the algorithm are presented on few examples in Section 6 and the paper ends with concluding remarks in Section 7.

*Daniel Rypl
2005-11-05*