Description of the geometric element type

 

The geometry of a single element is described using a polygon-oriented boundary representation of the parameter domain. As we support only (curved) polyhedral elements, an element can be described by the set of its vertices and a description of the boundary polygons. This applies only to the local coordinates of an element; its shape in world coordinates is determined by some transformation routine.

For a threedimensional polyhedron, we specify the number of boundary polygons (faces) and for each of these polygons the number of vertices, the local vertex indices and their order (thus giving an orientation to the polygon such that the surface normal is the outer normal to the polyhedron), and the local indices of the adjacent face across each of the edges of the polygon.

For each vertex, the coordinates in the local coordinate system of the element are given by the element description. Based on these values, the visualization routines may operate in the local coordinate space. The pointer to a function check_inside() is provided by the element description, which checks whether a point in local coordinates is inside the element or not.

The element description is completed by pointers to transformation routines from local coordinates to world coordinates and vice versa, and routines boundary() and neighbour() which give information about the neighbourship of elements. Additionally, the transformation routine from world to local coordinates checks whether a given point is inside the element or not.

typedef struct
{
 int       number_of_vertices;    /* number of vertices                  */
 int       number_of_polygons;    /* number of faces                     */
 int       *polygon_length;       /* vertex counts of the faces          */
 int       **polygon_vertex;      /* face to vertex adjacency            */
 int       **polygon_neighbour;   /* face to face adjacency              */

 int       dimension_of_coord;    /* dim. of local coordinate system     */
 double    **coord;               /* local coordinates of the vertices   */
 int       parametric_degree;     /* parametric element if > 1           */
 int       (*world_to_coord)(ELEMENT3D *, float *,  double *);
 void      (*coord_to_world)(ELEMENT3D *,  double *, float *);
 int       (*check_inside)(ELEMENT3D *,  double *);

 ELEMENT3D *(*neighbour)(ELEMENT3D *, int, int,  double *, float *);
 int       (*boundary)(ELEMENT3D *, int);
} ELEMENT3D_DESCRIPTION;

The arrays and procedures give following information:

polygon_length[j]

is the count of vertices of the j-th face ( ).

polygon_vertex[j][i]

is the (local) index (with range ) of the i-th vertex from the j-th face ( , polygon_length[ j ]).

polygon_neighbour[j][i]

is the index of the adjacent face to the j-th face across the edge from vertex polygon_vertex[j][i] to vertex polygon_vertex[j][i+1] ( number_of_polygons, polygon_length[j]).

coord[k][i]

is the i-th local coordinate of the k-th vertex from the polyhedron ( , ).

check_inside(element3d, coord)

returns INSIDE (-1) if the point with local coordinates coord is inside of the element's parameter range. Otherwise, at least one plane of a local face separates the element and the given point. In this case the local index of such a face is returned.

world_to_coord(element3d, xyz, coord)

transforms a point from given world coordinates xyz[3] to coord[dimension_of_coords] in the local coordinate system of element3d. The return value is identical to that from check_inside().

coord_to_world(element3d, coord, xyz)

transforms a point from local coordinates coord[dimension_of_coords] to world coordinates xyz[3].

neighbour(element3d, polygon, flag, coord, xyz)

returns a pointer to an adjacent element of element3d across face number polygon. Depending on flag, the routine returns the first neighbour or a next one (in case of non-conforming meshes the adjacency may be not one to one). If coord is not NIL, the routine transforms those coordinates from the old local coordinate system to the new one. In many cases this transformation can be supported by the optional parameter xyz, which provides world coordinates of the point if available, otherwise this parameter has to be NIL. The structure element3d may be overwritten by the routine.

boundary(element3d, polygon)

returns 0, if polygon is an inner face of the mesh, or a nonzero integer, if polygon is part of the mesh's boundary.

The number of such element descriptions and therefore the amount of storage for them is equal to the number of different element types in one mesh. There are no copies of this necessary for each element.

In the Figures, examples of vertex and face relationships for cubes, tetrahedra, and prisms are depicted. check_inside() is easily implemented using the local coordinates.

The user's data structures (from a numerical method, e.g.) may be completely different to the structures described above. In case of implicitly given Finite Difference meshes, the functions neighbour and boundary are implemented using simple index arithmetic.
Unstructured grids usually provide such information explicitly.