Subsections

• 2.6.1 Hierarchical Refinement
  • 2.6.1.1 Red-Green-Refinement
  • 2.6.1.2 Bisection and Projection
  
  
• 2.6.2 Moving Boundaries
• 2.6.3 Cellular Data

2.6 Grid Refinement -- Adaptive Meshes

During the simulation process, often locally adapted grids are required. We can distinguish two types of adaptation:

• Due to calculation errors a grid refinement at local regions becomes necessary. This can be within time invariant simulations where a criterion indicates a large discretization error in some regions.
  Alternatively, within transient simulations and the areas of interest move inside the device, which is caused by the gradients of the distributions. During a diffusion simulation, for instance, initially narrow and steep dopant profiles become wider. In addition, the profile edge becomes weaker and propagates across the device. Such an one-dimensional diffusion profile is shown in Figure 2.12. The grid resolution in areas of high concentration curvatures and gradients must be high to achieve a good accuracy. Initial areas of high grid density become useless during simulation and the grid density can be reduced in these areas, while in regions where the dopant edge sweeps through the grid density must be increased. This enforces transient grid refinement and coarsening during the simulation. It has to be noted that full regridding is not practicable with regards to calculation time.

  Figure 2.12: One-dimensional diffusion, diffusion constant $D$, $d=1.5 k$, no out-diffusion across $z=0$. The initial concentration profile at $4 D t=0$ and simulated distributions at $4 D t=k^2$ and $4 D t=10 k^2$ are shown.

  $$\quad \frac{\partial^2 c}{\partial z^2}=\frac{1}{D} \frac{\partial c}{\partial t}$$

  $$\quad \frac{\partial c}{\partial z}(0,t)=0$$

  $$\quad c(z,0)=c_0 \left(\mathrm{e}^{\textstyle -\frac{(z-d)^2}{k^2}}+\mathrm{e}^{\textstyle -\frac{(z+d)^2}{k^2}}\right)$$

  $$\quad c(z,t)=c_0 \sqrt{\frac{k^2}{k^2+4 D t}}\left(\mathrm{e}^{\t... ...}{k^2+4 D t}}+\mathrm{e}^{\textstyle -\frac{(z+d)^2}{k^2+4 D t}}\right)$$

  
  

  

• By special kinds of simulations even boundaries may be deformed or new material segments can be created -- for example within oxidation -- or a material segment can be etched away. Concerning grid generation, these applications require a broad pool of grid adaptation techniques. Some of them are not trivially solvable. Local deformation can be solved relatively simply by local regridding or movement and stretching of grid elements, whereas the creation of new segments is not trivial. As several segments can merge during the simulation, one segment can also be split into several parts.

Usually additional knowledge of the simulation problem is required. A general refinement approach has not been found yet and grid refinement must be adapted to the given problem. The methods described in this section have not been realized in the scope of this work, but show an overview of investigations and developments which are still under construction.

2.6.1 Hierarchical Refinement

For frequently performed local grid refinement and coarsement, the complete regeneration of the grid of the simulation domain is not acceptable due to the enormous time consumption of each new regridding step. Local regridding will be a better solution, but most of the grid generators are not designed for local regridding. The grid generator must support functionality for the removal of grid elements and points, the insertion of new points, and regridding. Local regridding of an area often requires the removal of neighboring elements and an inclusion of these regions in the regridding process. Most grid generators do not supply these functionalities.

A commonly used method of local adaptation is based on hierarchical mesh refinement. A given (relatively crude) grid is refined by splitting some grid elements into smaller ones. In frequent refinement steps, these elements can be split themselves. If the hierarchical splitting information is stored, this method offers also the possibility of hierarchical coarsement of the meshes, but this functionality results in some additional hierarchical information, which must be stored in the data structures. Additionally, care has to be taken that certain grid criteria must be fulfilled also for the refined grids -- for instance the Delaunay criterion. Usually splitting a grid element into smaller ones may also cause splitting of neighboring grid elements and it must be guaranteed by the algorithm that this neighbor splitting is done only locally and terminates, and that refining of a region does not induce a global split of all the grid elements, resulting in a never terminating splitting process.

2.6.1.1 Red-Green-Refinement

One method to perform such a refinement, is called red-green-refinement. This refinement technique is a commonly used refinement method for two-dimensional applications, especially for Delaunay grids. A triangle to be refined is split into four smaller children -- so called red triangles, as shown in Figure 2.13. At the intersections of the triangle edges, new points are inserted. Thereby four triangles are generated, whose edges are connected to these points. A pleasant property of this method is that all new triangles are geometrically similar to the original one and thereby the element quality of the new triangles is the same as the quality of the original one. A positive aspect is that usually the condition of the resulting equation system will not become worse by the refinement -- but it is also not improved.

Figure 2.13: Red-refinement of a triangle.

Figure 2.14: A red-refined triangle with a red-refined neighbor.

Using this method, any neighboring triangles can be red-refined (Figure 2.14) and any of the red triangles can be red-refined itself. But red-refined triangles will produce extra points along an edge of neighboring triangles that are not refined to the same level. These triangles must be refined irregularly, which are labeled as green triangles and are of lower quality (shown in Figure 2.15). Green-refinement is only performed if a single point is inserted. If more points are inserted or higher refinement of this triangle is wanted, the green triangles are removed and the parent triangle is red-refined, too.

By continuation of these two strategies, a hierarchical mesh is produced. Red triangles can be surrounded by red triangles as well as green triangles, and red triangles can also be further red-refined, which may also induce the generation of surrounding green triangles. With a hierarchical memory representation, refinement and also coarsening of already refined triangles can be handled easily.

Figure 2.15: A red-refined triangle with green-refined neighbors.

With the development of three-dimensional grids this technique has also been adapted to three dimensions [31]. A tetrahedron is red-refined by inserting the intersection points of the tetrahedron edges. By the insertion of these six points, the parent tetrahedron is split into two kinds of elements; four tetrahedrons and one octahedron (see Figure 2.16). On the one hand the octahedron can be split into four tetrahedrons (Figure 2.17). There are three possibilities according to the diagonal along which the octahedron is divided. Unlike for two-dimensional applications, not all the tetrahedrons are of the same geometrical shape. The tetrahedrons, which are created by splitting the octahedron, are spikier than the parents and therefore, of lower quality. Best results are obtained if the octahedron is split along its shortest diagonal. Consecutive refinement splits the resulting tetrahedrons. On the other hand this effect can be handled with mixed elements. A subsequent red-refinement of the octahedron delivers six smaller octahedrons and eight tetrahedrons. The resulting elements are geometrically similar to their parents or grandparents. After final refinement, the remaining octahedrons are usually decomposed to tetrahedrons by the common method (Figure 2.17).

Figure 2.16: Red-refinement of a tetrahedron into children, 4 tetrahedrons and an octahedron.

$\parbox{6.4cm}{\includegraphics[width=\linewidth]{picsconveps/red3d1.eps}}$
Tetrahedron

    =

$\parbox{7.0cm}{\includegraphics[width=\linewidth]{picsconveps/red3d2.eps}}$
4 Tetrahedrons

    +     

$\parbox{5.1cm}{\includegraphics[width=\linewidth]{picsconveps/red3d3.eps}}$
Octahedron

Figure 2.17: Final decomposition of the octahedron into 4 tetrahedrons.

$\parbox{6.0cm}{\includegraphics[width=\linewidth]{picsconveps/oct3d5.eps}}$
Octahedron

    =     

$\parbox{6.6cm}{\includegraphics[width=\linewidth]{picsconveps/oct3d2.eps}}$
4 Tetrahedrons

Figure 2.18: Subsequent red-refinement of the octahedron into 6 parent-similar octahedrons and 8 grandparent-similar tetrahedrons.

$\parbox{6.2cm}{\includegraphics[width=\linewidth]{picsconveps/oct3d1.eps}}$
Octahedron

    =

$\parbox{6.6cm}{\includegraphics[width=\linewidth]{picsconveps/oct3d3.eps}}$
6 Octahedrons

    +     

$\parbox{6.0cm}{\includegraphics[width=\linewidth]{picsconveps/oct3d4.eps}}$
8 Tetrahedrons

Figure 2.19: Possible green neighbors of a red-refined triangle.

Furthermore, for the handling of the surrounding green tetrahedrons, more cases must be considered. Theoretically, up to five points can be inserted (neglecting six point insertion, where this tetrahedron also is a red-refined tetrahedron). Only the three cases shown in Figure 2.19 are usually accounted for. Otherwise, the tetrahedron also is red-refined [39].

2.6.1.2 Bisection and Projection

Other methods for grid refinement also involve the bisection of mesh edges. Different to red-refinement, the edges are not mandatorily split in the middle and only one edge of a tetrahedron is split. Each tetrahedron sharing this edge is decomposed into two tetrahedrons. Further refinement operates on the newly generated tetrahedrons.

Equally bisecting mesh edges prevents that the grid spacing changes too rapidly while the triangle angles can become more obtuse. Obtuse angles may be removed in later repairing steps by edge-flipping or similar. Special care must be taken, not to loose the hierarchical grid information potentially required for coarsement. Orthogonally projecting the split points from the opposite triangle vertex prevents the generation of obtuse triangles, but may change the grid spacing dramatically.

A new method for bisection was introduced by Rivara and Hitschfeld [21][50][51]. In the two-dimensional method, only the longest triangle edge is intersected. Assuming that the longest triangle edge is on the opposite side of the biggest triangle angle, also the biggest angle is split into nearly two equal parts. Doing so, a shrinking of small angles can be prevented. Within this algorithm, also surrounding triangles may split and care has to be taken that this cascading effect does not result in a never-ending bisecting process and a never terminating algorithm. Within three dimensions, this technique is extended by several refinement steps and the termination of this process is influenced by the order of the different refinement steps. A lot of research still has to be done for three-dimensional applications.

Figure 2.20: Two-dimensional grid refinement by line splitting.

A two-dimensional example of a grid refined by line splitting can be seen in Figure 2.20. This version of the algorithm introduced in [29] is based on recursive bisectioning of the longest edges of triangles and is capable of refinement and coarsening of previously refined areas upon to the base grid, too. The refinement is started on a relatively coarse basegrid. Fragments of the basegrid can be seen in the regions which surround the circular region. This grid is refined in areas of interest. These areas are marked by a criterion that is adapted to this problem. In the above example the refinement criterion is tailored for the simulation of electromigration [7].

2.6.2 Moving Boundaries

The deformation of mesh elements and moving mesh points occurs for instance during oxidation simulation. Often only local movement of the boundaries is expected while other portions of the mesh remain unchanged. Therefore, it is not feasible to start a new mesh generation every time a small portion of the grid moves slightly. During particular transient simulation steps of an oxidation simulation, the grid movement might be only small. However, difficulties are to be expected when the boundaries change qualitatively. If boundaries start to overlap a fusion of segment portions will arise.

When the mesh distortion is only local, the grid points can be moved and the involved grid elements are deformed. To avoid a too strong deformation, annealing techniques can be performed on the grid or a full regridding must be started. Within these methods, it is expensive to perform a collision detection of the growing grid elements. Further development of efficient methods will be necessary.

Other methods try to solve this problem by using diffuse boundaries. Thereby the grid points have an additional parameter that decides how much this point is part of the segment or the surrounding segment. With linear interpolation inside the tetrahedrons the exact boundary can be evaluated. These methods are known as levelset algorithms. After finishing the whole simulation, a global regridding for following simulations, which eliminates this fuzziness, must be performed. But within this method, the influence of the diffuse boundary must be accounted for within the differential equations to be solved. For two-dimensional problems, some approaches are available. For three dimensions, however, some difficulties still exist [1][8][32][47].

2.6.3 Cellular Data

For the simulation of etching and deposition processes, efficient algorithms have been developed which work with cellular data representations [38]. In contrast to a representation via meshes, the structure is discretized into small portions of matter. These are pixels within two dimensions and voxels in three dimensions (usually cubes). The device structures can easily be modified by adding and removing volume parts of these cubes, which makes this method of discretization perfectly suitable for performing process simulation which changes the topology. These topological modifications are managed in a straightforward manner by image processing algorithms. The major advantage is that topological changes of the structure can be handled without intensive surface tracing algorithms which avoid the formation of surface loops.

Unfortunately, for a good resolution of the structure, these voxels must be very small in size and the amount of stored data increases enormously. However, usually there is not much overhead in the amount of stored data as compared to more flexible grid representations. Within the commonly used device structures, normally some material layers are of such small thickness that the grid representation also requires a large number of grid elements to resolve the structures.

In order to transform the cellular representation to a polygonal surface description usually marching cube algorithms are applied [34]. The cube data only delivers a rippled (manhattan type) surface representation. Their description can be improved by handling the material type as integer values of the cube points so that a fairly smooth surface representation can be generated (see Figure 2.21(a) and Figure 2.21(b)) [30]. By allowing only bisectional splitting of the cube edges, the number of pathological cases can be limited; an excerpt of the remaining cases is shown in Figure 2.21(c).

Figure 2.21: Overview of the marching cubes algorithm [30].

$\parbox{9cm}{\begin{center}\includegraphics[width=8cm]{picsconveps/cube.eps}\end{center}}$
Marching cubes -- The surface is approximated by planes which result from edge bisectioning of the cubes.

$\parbox{9cm}{\begin{center}\includegraphics[width=5cm]{picsconveps/marg2.eps}\end{center}}$
Approximation of the surface, the black point lies outside of the segment

$\parbox{9cm}{\begin{center}\includegraphics[width=7cm]{picsconveps/mcalt2.eps}\end{center}}$
Some elementary cases which can result for cut cubes, the black points are cut away.

1.0 While a similarity of this method to the levelset algorithm can be observed, algorithms for extracting the surfaces have been developed that are more general and which work in a manner similar to levelset algorithms on ortho grids.

Considering that the extracted surface triangles are of the same size as the sampling cubes, the extracted surface data often consists of a large number of very small triangles. Therefore data reduction is necessary. While triangles lying in the same plane can be removed easily, the removal of ripples and staircases is more critical because structural corners and edges should be preserved. Certain surface coarsening and smoothing algorithms can be applied [30][58]. They may be based only on the surface representations or may be applied to solid modeled data of the already regridded representation. Special care must be taken of collision detection. An overlap of thin material layers must be prevented by the algorithm. Several techniques are known, their amount of smoothening and data reduction varies and strongly depends on the structures and methods. A suitable way must be found individually for each application [23][58].