As stated in Section 2.1.2 and [Hala94], interpolation of attributes between different grids is one of the most important tasks inside a TCAD framework. This task has to be as accurate, reliable, and as fast as possible. Depending on the grid the attribute is defined on, GRS makes provisions for three possible cases:
For tensor product grids, linear and higher-order (using the AKIMA
method [Hyma83][Akim70]) interpolation is implemented on the tensor product
grid class. In the case of higher-order interpolation, the spatial derivatives
of the attribute under consideration have to be calculated prior to
interpolation. This is done in the corresponding grid preparation method of
this class. Additionally, the grid axis ticks have to be sorted into ascending
order in order to allow an 
time point location. The respective
attribute values have to be shuffled accordingly, which is also done in the
grid preparation method.
Searching in point cloud grids is possible through using a search structure
like an N-ary tree [Same90], which allows an point
location on the point cloud. However, the interpolation function for point
cloud grids is currently not implemented in GRS, but rather exists as a
stand-alone prototype using a modified SHEPARD's method
[Alfe89][Agis91].
When interpolation on an unstructured grid is to be performed, a search
structure has to be used also, which enables locating the element in which a
given point lies. Besides the N-ary tree, several other geometric search
structures can be applied which allow an effort point location
[Prep85], like the slab method, the chain method, the
triangulation refinement method and the trapezoid method.
Among those methods, the triangulation refinement method (in the following referred to as the KIRKPATRICK point location method [Kirk83]) was chosen for the point location in unstructured grids, since it uses triangles (in two-dimensional space) and relations between them as data structures, and a triangle represents already the primitive geometric grid element in two dimensions. Furthermore, this method uses a hierarchical tree of those triangles, and this tree structure is equally well suited to represent hierarchical unstructured grids too. Therefore two goals (point location and hierarchical grid representation) can be met with a single data structure, which is an important conceptual advantage in the application of this method to unstructured grids.
This tree structure is called a search-directed acyclic graph (SDAG),
and has to be built prior to interpolation on unstructured grids. With this
search structure, the grid element in which a given point lies and therefore is
to be used for the interpolation can be located in time. The KIRKPATRICK method in general, and the construction of the SDAG in
particular are discussed in the following section.