13.1.1 String Based Methods

An early approach to describing the time evolution of boundaries were the string methods. The string algorithm was proposed in [57] and is based on the straightforward idea to approximate the boundary considered by line segments forming a string in two spacial dimensions and by a triangular surface mesh in three dimensions. In the following the idea is discussed in the two-dimensional case. Depending on the local speed the points are moved along the bisectors of the angles between two neighboring line segments.

During the movement of the surface, the density of the points has to kept roughly uniform by inserting points where the surface expands and by deleting them where the surface shrinks. The formation of superfluous loops and self-intersections, however, causes problems especially when the speed of the movement of the boundary strongly varies [143]. This problem is inherent to the string algorithm. The loops are small in the beginning, but they expand as the simulation continues and can even intersect one another.

In order to overcome this problem the loops have to be straightened out as soon as possible and hence a ``de-looping'' operation must be done every few time steps [143]. Of course the de-looping operation is based on finding intersections between surface segments, which is not prohibitively computationally expensive in two dimensions, but poses higher demands in three dimensions.

Although the three-dimensional case is analogous in a certain sense, devising a robust algorithm is non-trivial and the de-looping operations become computationally very expensive. Additionally numerical problems of the intersection operations have to be considered. Several efforts to derive robust and efficient de-looping algorithms were undertaken [83,85,86]. It is claimed that the string algorithm now works stably in two and three dimensions [143,107,46,104,142], but the only two three-dimensional implementations can be found in [9,106]. It is used for tracking surface evolution, e.g., in the process simulator DIOS [56] and in the SAMPLE simulator [106]. Additional two-dimensional implementations can be found in [78,150].

Finally for the purpose of etching and deposition simulations certain geometric operations like joining surfaces and detecting voids are non-trivial to implement, especially if efficiency is required.