3.5 Surface Mesh

The generation of a suitable surface mesh is not simple. The difficulty is that the surface description of a CAD model and surface meshing are two different tasks. The purpose of the first is purely the definition of the structure. The latter will require the first, but it will also depend on the generation type of the volume mesh.

An input model can be described in very different ways. Constructive solid geometry CSG uses boolean operations on solids to define a structure [99]. Alternatively, the same structure can be defined by a boundary representation BREP. The enclosing surface, in two dimensions the contour, is given through splines, bezier curves, non-uniform rational B-spline (NURBS) patches, or edges and polygons.

Figure 3.16: Splitting an edge to ensure a well connected surface topology. Correctly splitting a polygon requires an expensive calculation of all intersections.

The transition from a mere structure description to an actual surface mesh involves several preprocessing steps. A first conversion into a meshable surface description, as already mentioned earlier, is not trivial and depends on the type of solid modeling [97]. Figure 3.16 shows an example of a structure description which makes intersection calculations necessary to derive the boundary representation. After extracting the well connected surface topology, it must be adjusted to work with the generation type of the volume mesh.

A method based on graph theory and network flow techniques for bidirected flow problems has been developed by [111]. A boundary given by curved polygons is refined into quadrilaterals (four point mesh elements for surfaces in three dimensions) so that the resulting surface mesh is suitable for numerical analysis. The theoretical approach avoids typical standard traps where patches stay unresolved because the number of remaining points and edges does not allow a tessellation into quadrilaterals with the available templates.

Many tetrahedral mesh generators, e.g. most advancing front and Delaunay methods, require a surface triangulation. Furthermore, providing a refined, coarsened, or smoothened surface triangulation will prove efficient prior to the generation of the volume mesh. In some cases the elements of the surface mesh are required to fulfill certain mesh criteria as for example Crit. 3.1. Such special surface triangulations can be generated through complex refinement procedures. A new technique will be described in detail in Section 6.3. It will also be useful if the volume meshing method is capable to adapt the surface mesh a posteriori. Other methods, e.g. some cartesian and octree techniques, generate the surface mesh indirectly by calculating the intersections of the surface representation with the elements of the volume mesh. Again, a surface which is represented by a triangulation may simplify this process.

Where in computational fluid dynamics and related fields the triangulation of NURBS patches is important [2,120], quite different solid modeling techniques are employed in semiconductor process and device simulation [188]. The structures might be defined through layout data [101]. Or they might be rasterized and composed of a large number of equally sized small cells (cellular data). Such an output, e.g. from topography simulation, contains too many cells to be directly used for the surface or the volume mesh. Simple cartesian solid modelers produce staircase-like surfaces where the normal vector of each facet is parallel to a coordinate axis (Fig. 3.17).

Figure 3.17: Staircase effects approximate slopes and result in unnecessary large meshes.

These cases unnecessarily complicate the meshing process, and can be avoided with a preceding data reduction and/or smoothing step. Such techniques also gain importance for level set methods. An iso surface of a continous volumetric data set forms the structure description. Extracting a surface mesh from such an iso surface may not be straightforward because the data set is itself discretized on a mesh. Coarse mesh elements and interpolation can cause an extremely rough and unsuitable surface mesh.