Boundaries and interfaces of geometries must be
adequately represented by the grids which cover the
geometry
. For two-dimensional
triangular grids this implies that the boundary and interface polygons
must be subsets of the union of all grid edges.
The same requirement stated differently is that the triangular grids
must tessellate the segments of the geometry.
As the input geometry and input grid for VORONOI are potentially specified independently from each other, conformity between them can not be expected. A constrained Delaunay triangulation that will yield a geometry-conforming triangular tessellation of the input segments is achieved by introducing a boundary refinement step before the actual triangulation is performed.
Figure 6.13: The Delaunay triangulation of this
configuration of boundary points A, B, C, and grid point
P yields a
non-geometry-conforming grid.
Without this preprocessing step, a direct triangulation of all grid and geometry points will not yield the desired geometry-conforming grid (see Figure 6.13). Especially layered geometries and non-planar structures which occur frequently in VLSI devices may easily cause non-geometry-conforming triangulations as depicted in Figure 6.14. The combination of tensor product grids with non-orthogonal geometries (as shown in Figure 6.15) also inevitably causes non-geometry-conforming triangulations when no additional boundary grid points are inserted.
Figure 6.14: A simple example of a layered geometry which,
without boundary refinement,
causes a non-geometry-conforming triangulation
Figure 6.15: Non-geometry-conforming triangulation of a
tensor product grid
The boundary refinement step iteratively applies a refinement criterion (described next) to every edge of the boundaries and interfaces which determines if a given edge needs to be refined. When applicable, the refinement is done by inserting an additional boundary grid point, thereby splitting the old boundary edge into two new boundary edges. At the end, all final boundary edges are ``guaranteed Delaunay edges'', hence they will be reproduced in the subsequent triangulation step.