Keywords: 3D surface, discrete surface, stereolithography format, interpolating subdivision, advancing front technique.

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. The presented paper addresses triangulation of 3D surfaces geometry of which is described by discrete data in stereolithography (STL) format.

The STL file format has become the rapid prototyping industry's standard data transmission format and is the format required to interact with stereolithography machines. This format approximates the 3D surfaces of a solid model with oriented triangles of different size and shape (aspect ratio) in order to achieve smooth enough representation suitable for industrial processing. While 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 actual discretization of the 3D surface described by the STL file consists of several phases. Initially, a boundary representation 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 character (topological feature) or geometrical character (sharp feature) 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. Small amendments to the original subdivision scheme were suggested in order to improve the performance when the interpolating subdivision is applied to STL meshes. Moreover, prior the actual subdivision process, the original STL mesh is slightly modified (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 recovered 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 capabilities of the proposed methodology are demonstrated on few examples. The benefits and drawbacks of the proposed approach are discussed and the directions for further research are suggested.

1

D. Zorin, P. Schröder, W. Sweldens: "Interpolating Subdivision for Meshes with Arbitrary Topology", In: Computer Graphics Proceedings (SIGGRAPH '96), 189-192, 1996. doi:10.1145/276884.276893

2

N. Dyn, J.A. Gregory, A. Levin: "A Four-Point Interpolatory Subdivision Scheme for Curve Design", Computer Aided Geometric Design, Vol. 4, 257-268, 1987. doi:10.1016/0167-8396(87)90001-X

3

M. Halstead, M. Kass, T. DeRose: "Efficient, Fair Interpolation using Catmull-Clark Surfaces", In: Computer Graphics Proceedings (SIGGRAPH '93), 35-44, 1993. doi:10.1145/166117.166121

4

E.J. Stollnitz, T.D. DeRose, D.H. Salesin: "Wavelets for Computer Graphics: Theory and Applications", Morgan Kaufmann Publishers, Inc., 1996.

5

Z. Bittnar, D. Rypl: "Direct Triangulation of 3D Surfaces Using the Advancing Front Technique", In: Numerical Methods in Engineering '96 (ECCOMAS '96), Wiley & Sons, 86-99, 1996.

6

D. Rypl, Z. Bittnar: "Triangulation of 3D Surfaces: From Parametric to Discrete Surfaces", In: CD-ROM Proceedings of the Sixth International Conference on Engineering Computational Technology, Civil-Comp Press, 2002. doi:10.4203/ccp.76.12

purchase the full-text of this paper (price £20)

go to the previous paper
go to the next paper
return to the table of contents
return to the book description
purchase this book (price £95 +P&P)