3.2.1 Requirements for Finite Volume Meshes

The box integration method was early introduced by Macneal [96]. The Scharfetter-Gummel scheme [58,119,146] which is crucial for semiconductor device simulation is applied in conjunction with the box integration method. The integration domain is partitioned into well defined boxes (control volumes) with positive cross-sections [158,64,52]. At present all major device simulators (DESSIS [91], MEDICI [181], MINIMOS [18,44]) require that these control volumes coincide with the Voronoi regions [117] of the points^3.1. An additional discretization error is avoided due to a specific advantage of the Voronoi box. A Voronoi facet (part of the boundary of a Voronoi box) orthogonally bisects the dual edge in the mesh by definition. (It intersects the edge perpendicular at the midpoint.) The suitability of gravity boxes defined by the centroids and edge midpoints as opposed to Voronoi boxes has been investigated for two-dimensional semiconductor device simulation in [165]. Further research will have to show whether or not such a modified discretization scheme based on gravity boxes can be applied successfully in three dimensions and if an additional discretization error is negligible.

Because of the duality between the Voronoi diagram and the Delaunay Triangulation, the mesh generator is required to perform a Delaunay partitioning of which the Voronoi boxes are easily extracted. At the boundary the control volumes must be closed [64]. Voronoi points, which are the circumcenters of the Delaunay tetrahedra, are not allowed to lie outside of the domain. A Voronoi point located outside defines a vertex of an incident Voronoi box which must intersect the boundary as a result. This ``cut'' box is associated to an interior point (not part of the boundary) and forms an open control volume (Fig. 3.4).

Figure 3.4: A Voronoi box which intersects the boundary and an outside Voronoi point $M$. The Voronoi regions for each point are shaded differently.

If the Voronoi boxes are indeed used as the control volumes, the requirements directly translate to the following criteria for the triangles of the surface mesh.

Criterion 3.1 (smallest sphere)   Let $P$ be a finite set of points in $n$-dimensional space $R^{n}$ and let $t$ be an $(n-1)$-dimensional boundary simplex. $t$ and its $n$ linear independent points $p_{t,i}$ define an infinite number of $n$-dimensional spheres $S_{t,r_{c}}$ where each sphere contains the points $p_{t,i}$ on its perimeter. All points $p_{k}$ in $P$ are associated with a Voronoi box $V_{k}$. The smallest sphere $S_{t,r_{\min}}$ contains no other points of $P$ if the Voronoi box $V_{m}$ does not intersect $t$ for all $m$ with $p_{m} \notin p_{t,i}$.

In two dimensions the smallest sphere criterion is also sufficient to guarantee closed control volumes. In three dimensions an empty smallest sphere (equatorial sphere of a boundary triangle) might not guarantee a closed control volume. It can be shown that an additionally applied smallest sphere criterion to the edges of a boundary triangle is in conjunction stronger and suffices.

Criterion 3.2 (smallest sphere, edges and triangle)   Let $P$ be a finite set of points in three-dimensional space $R^{3}$ and let $t$ be a boundary triangle defined by three boundary edges $e_{t,i}$. Each $e_{t,i}$ with its two linear independent points $p_{e,j}$ defines a smallest three-dimensional sphere $S_{e,r_{\min}}$ where each sphere passes through the points $p_{e,j}$. $t$ defines a fourth smallest sphere $S_{t,r_{\min}}$ (equatorial sphere) which passes through the points $p_{t,l}$ of the triangle. All points $p_{k}$ in $P$ are associated with a Voronoi box $V_{k}$. No Voronoi box $V_{m}$ intersects $t$ for all $m$ with $p_{m} \notin p_{t,l}$ if and only if the four spheres $S_{e,r_{\min}}, S_{t,r_{\min}}$ contain no other points of $P$.

The proof essentially boils down to showing that the volume covered by the four smallest spheres (one triangle and three edges) ``swallows'' any sphere $S_{x,R}$ defined by a center $x$ and radius $R$, where $x$ is located anywhere on the triangle and $R$ is such that the sphere $S_{x,R}$ does not contain any of the three vertices of the triangle.

As will be seen in Chapter 5 the smallest sphere criterion (Crit. 3.1) is stronger than the Delaunay criteria (Crit. 5.1 and Crit. 5.2). If no Voronoi box associated with an internal mesh point intersects the boundary, the simplices forming the boundary must be Delaunay simplices. In other words: If one chooses a Delaunay Triangulation to utilize its inherently given Voronoi boxes as control volumes, and if the discretization scheme relies on closed control volumes, the boundary elements must be adapted in one way or another to satisfy the stronger criteria independently of the application. It follows from the well known Thales circle that in two dimensions the angle opposite of a boundary edge must not be obtuse. Non-obtuse triangulations can be guaranteed in two dimensions [7]. For three dimensions such a guarantee remains an open problem. In practice the mesh generator is required to construct a Delaunay mesh and to ensure that the surface mesh elements are at least Delaunay.