2. Surface Modeling

Some modifications of the surface of the three-dimensional structure are required prior to the actual meshing procedure. The volume decomposition performed by the tetrahedrization module uses a modified advancing front algorithm. The adapted surface of the geometry provides the initial front. The Constrained Delaunay triangulation which would allow the embedding of an unaltered surface into the Delaunay tetrahedrization is not yet well defined in three dimensions and remains an open problem. In one way or the other it becomes necessary to transform the surface to be contained in a Conforming Delaunay tetrahedrization: A non-planar Delaunay surface triangulation of the geometry is generated which will be part of a geometry conform Delaunay mesh. It provides the core meshing algorithm with the initial front. A general polygonal description of the boundaries and interfaces is read as well as an optional set of grid nodes to be reused. The applied Delaunay criterion for a surface triangle is based on the following two properties (Fig. 2):

Property 1:

  Let D be a finite set of points in a sub-domain of the n-dimensional space . Two points and are connected by a Delaunay edge e if and only if there exists a point which is equally close to and and closer to than to any other .

Property 2:

Let D be a finite set of points in a sub-domain of the n-dimensional space . Three non-collinear points and form a Delaunay triangle t if and only if there exists a point which is equally close to and and closer to than to any other .

A fast point location method becomes crucial for the verification of this criterion. We implemented a point bucket octree to store all grid nodes at all times. The following steps are involved to adapt the given surface for use with the tetrahedrization algorithm and to derive a three-dimensional Delaunay surface triangulation.

• Triangulation of the possibly non-convex input polygons. At the moment a polygonal boundary description is required (Fig. 3). A volume oriented input description must be converted to a surface representation.

    
  Figure 3: MOS Transistor as polygonal input.
  

• Conversion and consistency checks - splitting of edges. This is not a trivial process, if the polygonal input is not well connected or overlapping polygons exist. See Fig. 4.

    
  Figure 4: Edge splitting can be a necessary conversion of the input data to yield a well connected surface triangulation.
  

• Management of different materials - respecting interfaces opposed to boundaries. Maintaining conformity at the interfaces and choosing the segments which have to be meshed.
• Using a feature edge parameter to determine structural edges. This parameter affects the degree as to how much the original geometry is allowed to be transformed. An example is shown in Fig. 5.

    
  Figure 5: Non-flippable feature edges are drawn in a red color. The green edge is an example of a local transformation.
  

• Applying local transformations to surface elements, like edge swapping between surface triangles that do not form a structural edge as defined by the feature edge parameter (Fig. 5). Refer to [3] for the more general usage of local transformations in Delaunay triangulations.
• Respecting edges which are formed by more than two triangles
  (e.g. triple lines, Fig. 6).

    
  Figure 6: An example of a ``triple line''.
  

• The surface triangulation of the domain may contain edges which are neither Delaunay nor can be swapped (structural edges). In such cases refinement of edges and triangles by point projection or bisection is necessary.

Note, that in the worst case these heuristics may fail to produce a surface representation compliant with the above stated properties. In such a case a few non-delaunay triangles exist which require a special handling during the tetrahedrization process (See robustness issues at the end of the next section.) The underlying goal of the surface modeling procedure is to automatically understand complex three-dimensional structures. The generated Delaunay surface representation (Fig. 7) is fed into the modified advancing front algorithm.