Using Recursive Subdivision
for Triangulation of 3D Surfaces

Daniel Rypl, Zdeněk Bittnar

Department of Mechanics
Faculty of Civil Engineering
Czech Technical University in Prague
Thákurova 7, 166 29 Prague, Czech Republic


The present paper deals with the generation of computational meshes over 3D surfaces described by discrete data in the form of a triangular grid of arbitrary topology. This may be a deformed finite element mesh from the previous step of an analysis, grid obtained from computer tomography, digital representation of terrain, grid representing a surface in stereolithography (STL) format etc. The new computational mesh is generated over a smooth surface that is topologically and geometrically similar to the underlying piecewise planar control grid. The recovery of the smooth surface is performed using a recursive subdivision technique based on hierarchical refinement of triangular simplices forming the control grid. In the present approach, the interpolating subdivision based on the modified Butterfly scheme, yielding C1 continuous surface even in the topologically irregular setting of the control grid, is adopted. With respect to the application to STL meshes, the modified Butterfly scheme was subjected to slight amendments in order to make the recovered surface more regular in situations where the original strategy seemed to be not enough flexible. The actual discretization is accomplished using the advancing front technique operating directly on the surface. This avoids difficulties with construction of smooth parameterization of the whole surface. The crucial aspect of the discretization is the projection algorithm, required to comply with the surface constraint, which must be reliable, efficient, and accurate. The adopted projection technique is based on local progressive refinement (subdivision) of the control grid. To overcome its high computational demands, an approximate but computationally more efficient projection, based on projection to a parametric triangular patch used to approximate the recovered smooth surface over individual elements of the control grid, is applied during the some stages of the mesh generation process. The capability of the proposed methodology is demonstrated on a few examples.