Direct Discretization of 3D Surfaces

The direct methods for the discretization of 3D surfaces work directly on the surface in the real space. They avoid the anisotropic meshing of the parametric space as well as the demanding calculations related to the reparameterization or the inverse mapping. They can be also applied to non-parametric 3D surfaces if sufficient tools for surface manipulation (including a projection to the surface) are available. However, these methods suffer from enlarged computational expenses due to the full 3D calculations (including the projection to the surface and the intersection check). And this is mainly the reason why they are not as popular as the indirect methods.

The octree based methods [6,22,29] produce a surface mesh usually as a byproduct of a solid meshing which is a 3D extension of the quadtree technique described in Subsection Generation of Triangular Meshes. The surface to be meshed is placed in the root octant, usually a cube, that is then recursively subdivided into eight child octants until all octants are at the desired level. To ensure a gradual variation of the element density, the one-level difference rule is applied. Then a computationally demanding phase, evaluating the intersection of the surface with each octant, is performed. This intersection, represented in the form of a polygon, is then subjected to a triangulation typically based on the element removal concept. Note that additional nodes optionally inserted inside the polygon to simplify the polygon triangulation have to satisfy the surface constraint.

The approach introduced in [57] applies the AFT to a surface represented by a fine grid of curves. At each node of the grid, its coordinates and the surface normal are available. This surface data are intensively used for the surface projection to satisfy the constraint to the surface body. The actual AFT is an extension of the conventional AFT allowing to reflect the surface curvature. The optimization of the surface is performed only on the topological level using the edge swapping without moving the nodes on the surface.

A similar technique, employed to tensor product polynomial surfaces, was presented in [60]. The standard AFT, appropriately modified to account for the surface curvature, as well as the Laplacian smoothing are applied directly in the real space of the surface. The parametric space is used to efficiently implement the projection to the surface and to resolve some intersection checks. Further modifications are introduced to the spatial localization and front management to alleviate the inherent logarithmic computational complexity of the conventional AFT and to approach the linear one.

*Daniel Rypl
2005-12-07*