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

Nowadays finite element modelling involves discretization of very complex objects in terms of both geometry and topology. 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 presented paper addresses triangulation of 3D surfaces, geometry of which is described by discrete data.

The surface to be discretized is represented by a triangular control grid of arbitrary topology. The boundary edges of the grid form the boundary curves of the surface. The end nodes of each curve represent vertices. The limit surface is reconstructed using a subdivision technique. In the presented approach, the interpolating subdivision based on modified Butterfly scheme [1] which yields surfaces (even in the topologically irregular setting) has been employed. Similarly, the limit boundary curves are recovered using one-dimensional interpolating subdivision [2] producing curves.

The properties of the limit surfaces and curves (the derivative masks for normal (tangent) evaluation on the surface (curve)) have been derived by standard examination of the eigenstructure of the local subdivision matrix. Note that other subdivision schemes, including approximating ones, can be adopted providing that appropriate masks for limit position and normal (tangent) evaluation are available.

The actual discretization is accomplished using the Advancing Front Technique operating directly on the surface [3]. This avoids difficulties with construction of smooth parameterization of the whole surface. The mesh gradation is controlled by the octree data structure, reflecting the required element spacing specified at the nodes of the surface control grid. Allowing only for one octree level difference of octants sharing an edge, too steep size gradation is eliminated and therefore no special strategy for choosing an edge to be removed is to be employed. This leads to the almost linear computational complexity of the implemented meshing algorithm.

The crucial aspect of the discretization is the projection algorithm. It must be reliable, efficient, and accurate. The adopted projection technique is based on local progressive refinement (subdivision) of the background grid. It avoids storage of huge amount of data required by global subdivision up to a sufficiently hight level dictated by the prescribed accuracy (element size). The reliability is achieved by backtracking. This algorithm, however, is computationally sensitive to the element size and therefore it is applied only in the final stage to constrain the location of mesh nodes to the limit surface. In other cases, it is replaced by an approximate projection based on projection to a (rational) Bezier triangle used to approximate the limit surface over individual elements of the control grid.

The capability of the proposed methodology is demonstrated on a set of examples including performance diagrams. Its benefits and drawbacks are discussed and some modifications further improving the performance 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/237170.237254

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

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.

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 £85 +P&P)