Direct Triangulation of 3D Surfaces
Using the Advancing Front Technique

Zdeněk Bittnar, Daniel Rypl

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


A robust and efficient algorithm for discretization of tensor product polynomial surfaces is presented. The advancing front technique operating directly on the surface in the physical space is employed. This avoids difficulties with the anisotropic triangulation of parametric space of these surfaces and also guarantees the creation of well shaped triangles even in case of degenerated or badly parameterized surfaces. However, the parametric space is still used to resolve some intersection checks associated with the edge removal. The mesh gradation is controlled by the octree data structure. 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 proposed algorithm.