Unstructured Grid Element Representation



next up previous contents
Next: 7.1.2 Unstructured Grid Reading Up: 7.1.1 Architecture Previous: The Point List

Unstructured Grid Element Representation

   

Not all applications can get along with sequential access to the individual grid elements of an unstructured grid. Therefore GRS maintains the grid elements in a dynamic array of object pointers, where each pointer points to a grid element object. Applications can therefore address a grid element directly by obtaining the element pointer from this array.

This direct access is needed by GRS itself also, when it traverses all elements containing a particular point of the grid. A corresponding array holds for each point of the grid an index array containing the indices of all elements adjacent to that point. The grid elements itself contain indices to the points (nodes) which make up their shape. The number of those point indices depends on the grid type, and is defined in the individual class of this grid element. Storing the element index has been preferred over storing a pointer to the element, because PIF also deals with indices, and a pointer would have prohibited or at least impeded the writing unstructured grids to PIF.

Each element is characterized by its name, topological dimension, number of nodes, and methods for decomposition, interpolation, point-in-element-test and point restriction. The name is usually a short mnemonic and used as the class name of this grid element, for example TRI3 (a triangle with three nodes) or QA4 (a quadrangle with four nodes). The topological dimension is two for ``flat'' elements stored in a faceList, and three for solid elements stored in a solidList.

Note that the topological dimension of a grid element may be different from its geometrical dimension, for example when describing the triangulation of a surface of a three-dimensional geometric object. Let be the number of element nodes and the topological dimension. Then a valid grid element has to have element nodes. The decomposition method decomposes a given element into primitive elements of the respective topological dimension, which always have exactly element nodes. For example, a QA4 element may be decomposed into two TRI3 elements. This decomposition is used in various applications throughout VISTA, the most prominent of which is the xpif2d visualizer, which always operates on two-dimensional primitives (i.e. triangles).

On interpolation, the requested point is located inside a particular element of the grid and the corresponding interpolation method of the respective grid element class is invoked. For the point location, the point-in-element-test method is needed, which returns a boolean value indicating if a given point lies inside or outside the element. The interpolation method returns an interpolated value given a point lying inside the element, the coordinates of its element nodes and the respective attribute values on the element nodes. This is usually achieved through transforming the node and point coordinates to a unity element and evaluating the form functions of this unity element.

The point restriction method is used in hierarchical grids to determine if a point location is possible on the grid. This is the case if all children of an inner node inside a hierarchical element tree see Section 7.1.4 cover the area of its parent totally. But if - for example after a grid adaption step - the points of the lowest level move slightly and the grid hierarchy is not rebuilt, there may be elements whose children do not fully cover the parent area. Then a point location on such an element may produce incorrect results, as would the interpolation using this malformed hierarchical grid. Fig. 7.8 shows the cases of a correct triangulation allowing point location, and an incorrect triangulation where point location may produce wrong results.

  
Figure: Correct and incorrect grid element hierarchies for point location. The left triangulation shows the result of a KIRKPATRICK grid hierarchy construction step by removing the center point M and retriangulating the resulting polygon. The newly generated triangles are shaded, and locating point P will successfully return the light shaded middle triangle. The right triangulation (as it may result from an oxidation simulation using a hierarchical triangular grid) however fails to locate point P, because despite the fact it is included in the thickly outlined parent triangle, its shaded children do not include point P.



next up previous contents
Next: 7.1.2 Unstructured Grid Reading Up: 7.1.1 Architecture Previous: The Point List



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