3.5.1 Surface Extraction From Cellular Data

For certain applications a cellular data representation^3.4enables the use of problem adapted and efficient algorithms. During the simulation of etching and deposition processes topological changes of the surface structure are handled without special surface trace algorithms or algorithms to avoid the formation of surface loops. At the cost of a higher memory consumption due to the sampling of the structure moving boundary situations are managed in a straightforward manner with image processing techniques. The polygonal surface description is later retrieved through the marching cubes algorithm [95]. The original method which generates fairly smooth iso surfaces for continous data is adapted in such a way that it constructs the interfaces between a discrete distribution of several materials as shown in Fig. 3.18 and Fig. 3.19. The value of the magnitude on the cell corners is thereby not arbitrary but rather an integer reflecting the material type. The cell edges are never split differently than through bisection which results in a less optimal representation with angles limited to a multiple of $45^{\circ}$. The selection of the templates depending on the material type at each cell corner is not always straightforward (Fig. 3.19). A detailed description of such an implementation can be found in [85]. During the sampling and retrieval process it will be desireable to preserve as much of the polygonal information as possible in areas where the boundary remains unchanged [110].

It is interesting to see that the original marching cubes algorithm which operates on continous data can be utilized to extract surfaces from level set computations on ortho-product grids. Often such level set methods are performed on tetrahedral meshes and a to the marching cubes analogous algorithm becomes necessary.

Figure 3.18: Marching cubes algorithm applied to discrete data which describes the distribution of a finite number of materials.

Figure 3.19: Pathological cases and alternative templates.