7.1.3 Generic Interpolation



next up previous contents
Next: 7.1.4 The KIRKPATRICK Point Up: 7.1 GRS Previous: 7.1.2 Unstructured Grid Reading

7.1.3 Generic Interpolation

 

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.



next up previous contents
Next: 7.1.4 The KIRKPATRICK Point Up: 7.1 GRS Previous: 7.1.2 Unstructured Grid Reading



Martin Stiftinger
Tue Nov 29 19:41:50 MET 1994