Discretization of Discrete 3D Surfaces

The discretization of discretely described surfaces is a relatively recent topic with not many published works. Basically, the discretization may be performed either directly in the real space or indirectly using the parametric space. The indirect discretization requires the construction of a mapping function [85,86], which is non-trivial for highly curved surfaces or even impossible for non-manifold surfaces. The more the surface deviates from a flat shaped surface, the more the mapping becomes non-linear, which makes the anisotropic meshing of the parametric space (formed by the original mesh mapped to the parametric plane) more difficult. Thus complex surfaces can be discretized only piecewise with the mesh compatibility on the interfaces between different parameterizations being still an open issue. Therefore, majority of approaches prefer to work directly on the surface in the real space where the major challenges are related to the smoothness (in terms of continuity) of the final mesh.

The approach introduced in [78,88] creates a new mesh by successive modifications applied to the control grid using a set of geometrical and topological operators (insert/remove node, swap/collapse/split edge) according to the element density specification prescribed on the original control grid. The continuity of the final mesh is ensured by interpolating nodal normals, calculated from the quadric patches built at each node using the least-squares fit of adjacent mesh nodes. The advantage of this approach, except its simplicity, efficiency, and robustness, consists also in the fact that a valid mesh is maintained throughout the whole meshing process.

The technique described in [77] is based on the refinement of a stereolithography (STL) mesh produced by CAD systems using a bisection algorithm. The newly inserted nodes are projected to the surface with the help of interpolated nodal normals defined by the initial STL mesh. The regularity of the refined mesh is improved by edge swapping to comply with the Delaunay property in a ``weak'' form, based on the minimum empty circumsphere criterion. The swapping of edges corresponding to model features is prevented.

The method presented in [80] also works with surfaces described by the STL format. Initially, the consistency and validity of the STL mesh are checked. Then geometric features of the underlying model are recovered. The actual mesh generation is performed by the AFT working directly on the surface. The nodes of the generated mesh are initially positioned on linear facets of the original STL mesh to increase the efficiency and robustness of the algorithm. However, the nodes are later projected to the surface using a second order correction algorithm to fulfill the surface constraint.

Also the strategy described in [84] generates the new mesh directly in the real space using the AFT. However, the surface, over which the actual meshing takes place and which controls the smoothness of the final mesh, is reconstructed from the control grid using an interpolating subdivision technique [72]. This technique is based on the hierarchical recursive refinement of triangular simplices forming the control grid using a special averaging scheme that works with unstructured control grid of arbitrary topology and which ensures the continuity of the final limit surface (after the infinite number of refinements). The drawbacks of this approach consist in relatively large computational demands related especially to the projection algorithm and in significant sensitivity to poor quality elements in the initial control grid.

*Daniel Rypl
2005-12-07*