13.4 Surface Extraction and Void Detection

Figure 13.3: This figure illustrates how the boundary curve is extracted in the example of these four grid points.

Although in the numeric representation the level set function is eventually calculated on a grid, the resolution achieved is in fact much higher than the resolution of the grid, and hence higher than the resolution achieved using a cellular format on a grid of the same size. This is because in the last step, the surface extraction step, the zero level set is approximated by lines or triangles using linear interpolation. This goes hand in hand with the requirement that the level set function essentially remains the signed distance function which is locally a linear function near the zero level set.

The two-dimensional surface extraction algorithm takes a level set grid as input and yields a list of points. It starts at the left hand side of the simulation domain and first finds a vertical edge whose points have different sign. Then it marches through the grid along the zero level set remembering the current edge and the current direction. The next edge which is intersected by the zero level set is found by considering the sign of the neighboring edges. After identifying an intersecting edge, the current edge and current direction are updated and a point on the edge found by linear interpolation using the values of the level set function at the two grid points is added to the list of points finally returned. The algorithm terminates when the boundary of the simulation domain is reached. In the example in Figure 13.3 we assume that the current edge is $AC$ going right. The zero of the linear interpolating function at the edge $AC$ is its midpoints. Considering the edges $AB$, $BD$, and $CD$, the edge $BD$ must be intersected by the zero level set and thus we find the next intersection point, which lies closer to $D$ than to $B$.

Voids are detected by finding an edge with points of different sign in the simulation domain first. This edge must not have been extracted previously. The surface extraction algorithm then proceeds in the same manner. The precise shape and location of voids is important for the electrical properties of films deposited (cf. Chapter 12).