3.4.3

This technique uses a very simple algorithm to find the element surrounding a given point. The algorithm is structured into two parts. The first part selects a start tetrahedron. The second part is an iterative search. Beginning with the start tetrahedron, the algorithm chooses neighboring tetrahedrons such that the distance to the search point is reduced. To choose among the neighboring tetrahedrons, the dot products of the normal vectors of the bounding triangles and the vector from the search to the in-sphere point of the start tetrahedron are computed. The algorithm is then repeated until either the tetrahedron containing the search point was found, or a boundary face was reached in which case the algorithm has to start at another starting tetrahedron. Fig. 3.15 depicts the principle of this algorithm.

The big advantage of this algorithm is its vanishing pre-processing
time. The imposed memory overhead is also considerably smaller compared to the
*oct-tree*. The only requirement to the data structures holding the grid elements is
that information about neighboring elements needs to be computed and held in
memory. In the following we compare *oct-tree* and *jump-and-walk* on the basis of the above
example (management of
elements). If, for the sake of
simplicity, the implementation of the algorithm does not distinguish between
boundary and inner triangles, each triangle holds two handles to tetrahedrons
and three point handles. We estimate the number of triangles to be
, so that the total amount of memory overhead computes to
megabytes which is considerably more as with the *oct-tree*.

The average performance of the *point location* can not be estimated
easily since it strongly depends on the selection of the starting
element. Several algorithms to select such an element were proposed. One
possible strategy is to randomly choose several points (of elements) and use an
element that references the point with the smallest Euclidean distance. Another
strategy accounts for locations that are (possibly) geometrically related to
each other. The algorithm remembers the result of the last location and takes
this as starting condition for the next. In literature the "theoretical
performance" for *jump-and-walk* on a Delaunay triangulation is given as being
proportional to (in dimension ) when the points are randomly
distributed [50].

The performance also strongly depends on the shape of the geometry. If we look at the structure depicted in Fig. 3.16,

the thin region between the two thicker ones is unfavorable for a

The likelihood of picking a starting element within the thicker regions is proportional to the ratio of the number of points in the two regions and thus, can be very high if the algorithm randomly chooses points and computes Euclidean distances to the query point.

Two algorithms to select a starting tetrahedron were implemented.
The first algorithm uses a configurable number of randomly chosen points and
picks the one with the smallest Euclidean distance to the search point. From the
set of tetrahedrons that reference this point the first is chosen as the start
tetrahedron. The second selection algorithm uses a *point bucket oct-tree* to store all points
of the mesh. A point that is close to the search point is chosen. The algorithm
to find a close point takes advantage of the leaf structure of the *point bucket oct-tree* in
the following manner. First the deepest node or leaf that contains at least one
point is searched. If a leaf was found and the search point lies within the
coordinates of this leaf then the point stored on the leaf is taken as start
point. Otherwise the neighbors of the node (or leaf) are searched. This
algorithm is guaranteed to return a point if the *point bucket oct-tree* is not empty. A
tetrahedron is then chosen from the close point in the same way as with the
first algorithm.

After the selection of the start tetrahedron the actual walk algorithm is started. The algorithm remembers all tetrahedrons that were already met to avoid endless loops. If the algorithm encounters the surface of the mesh, another starting tetrahedron is chosen.

The implementation of *jump-and-walk* is a general templatized code that
supports *point location* for two-dimensional and three-dimensional grids respectively.

2003-03-27