    Next: 4.1.2 H-RLE Data Structure Up: 4.1 Initialization Previous: 4.1 Initialization

## 4.1.1 Closest Point Transformation

As mentioned in Section 3.1.3 the LS function is usually initialized as a signed distance function. In case of the sparse field LS method it is better to use the smallest (signed) Manhattan distance (4.1)

rather than the smallest Euclidean distance, for the initialization. With the latter, the first time step of the sparse field LS method gives wrong results for the position of a (non-axis-parallel) plane moving with constant speed. However, if initialized with the Manhattan distance, trilinear interpolation of the LS function correctly describes the position of the plane after the first time step. The reason for this behavior is the update scheme (3.29) which also corresponds to a Manhattan distance calculation.

It is not necessary to calculate the initial LS values for the entire grid. Only grid points close to the boundary have to be considered. In particular, the sparse field method requires the determination of all active grid points together with their LS values only at the beginning. If the sign of the LS function is known for all other grid points, the additional layers can be determined using (3.28). The required LS values can then be computed using (3.29). The knowledge of the sign for the LS values at all points of the grid is also a prerequisite for the setup of the H-RLE data structure.

The signs of the LS values are unambiguously defined, if the set of all grid points with an opposite signed neighbor is known. This set of grid points clearly separates the positive and the negative grid points from each other. To satisfy all the requirements for the initialization of the sparse field method and the H-RLE data structure, the LS framework determines all grid points for which the LS value is in the range .

This set of grid points contains all the required information, because due to (4.1) all grid points are included, which have an opposite signed neighbor. Before setting up the H-RLE data structure, the LS framework collects all these grid points together with their LS values and stores them in a list. In the following sections an efficient technique is described to obtain this list in linear time.

Since the Manhattan distance is only needed for grid points close to the boundary, the distance computation can be simplified. For these points the Manhattan distance can be approximated by the smallest distance to the boundary along any paraxial direction. In other words, the smallest unsigned distance of a grid point is approximated by (4.2)

Here denotes the unit vector pointing in the -direction ( ).

In practice the distance transform is carried out by an iteration over all segments of the discretized boundary representation. For each segment all intersecting grid lines are determined. The number of possible grid lines can be confined using the bounding box of the segment. In the two-dimensional case the test whether a grid line intersects a line segment or not is trivial. In the three-dimensional case the intersection test with a triangle is more difficult and is described in Appendix A. For each intersecting grid line the intersection point is calculated and all grid points on that grid line are considered for which (4.3)

Here it is assumed that the grid line is parallel to the -th axis direction, hence parallel to . is a small positive constant ( ), introduced for numerical reasons, which ensures the calculation of the initial LS values for all grid points directly neighbored to the boundary. Thus, must be larger than the maximum numerical error for the calculation of the distance . In this work is used.

The signed distance of a grid point to the current segment is given by (4.4)

The sign of the -th component of the normal vector can be obtained by considering the orientation of the surface segment with respect to . In two dimensions the distance is positive, if the vertex is on the left-hand side. In case of three dimensions the sign is positive, if the vertices , , and are seen counterclockwise. If for each grid point the distance with the smallest absolute value is kept, at least all grid points with LS values in the range will be properly initialized after iterating over all segments of the boundary mesh. However, this procedure can lead to problems as depicted in Figure 4.2a, where the wrong sign could be assigned to the LS value of both grid points, since both segments are equally distanced. To resolve this ambiguity without additional consideration of neighbor segments, another distance is measured using (4.5)

in order to determine the closest segment for a certain grid point . Here denotes the unit vector pointing from to the centroid of the segment with (4.6) is again a small positive constant ( ). However, the distance which is finally assigned to is still calculated using (4.4). is used for all LS initializations in this work.

The initialization procedure is now as follows: For each segment and for all intersecting grid lines all grid points fulfilling (4.3) are determined. The indices of these grid points are appended to a list along with their corresponding distances and , defined in (4.4) and (4.5), respectively. Finally the list is lexicographically sorted with respect to the grid point indices. If there are more entries with the same , (which is not very often the case,) of that entry with the smallest corresponding is used for the initial LS value .

The entire initialization algorithm has a complexity of , where is the final number of defined grid grid points in the H-RLE data structure. is the total number of segments of the boundary mesh. The logarithmic term is due to the sorting algorithm which cannot be avoided, since the setup of the H-RLE data structure requires a sorted list as well. This initialization algorithm can produce inefficient sets of active grid points as exemplified in Figure 4.2b, which can be avoided by appending a pruning procedure, as mentioned earlier (see Section 3.4.2).    Next: 4.1.2 H-RLE Data Structure Up: 4.1 Initialization Previous: 4.1 Initialization

Otmar Ertl: Numerical Methods for Topography Simulation