In the preceding section, we have seen that the major obstacle for reusing grid-related software is direct access to low-level representation details, together with to inavoidable high variability of such details in the field of geometric data structures.
In order to decouple implementations of algorithms (or other data structures) from these details, we will develop in the following a uniform, abstract interface layer for grids.
How can one obtain such an interface? Let us look again at the simple algorithm for surface calculation:
What kind of functionality does this algorithm need?
Items * and * can be summarized as iteration or combinatorial functionality. Item * obeys to the general pattern of storing data on (or associating data to) grid elements. And item * attaches geometric meaning to the combinatorial entitiy "facet".
Thus, in this case, functionality needed by the algorithm falls into three classes. This, however, is no accident due to the simplicity of the algorithm, but a pattern found also when investigating more complex algorithms. To sum up, we distinguish the following three fundamental layers of functionality:
The combinatorial layer views a grid simply as a lattice, or, more generally, a poset, given by the incidence relationship. The entities involved are of a purely discrete nature; there is not notion of coordinates of vertices or the like. The notion of dimension used here is a combinatorial or intrinsic dimension.
The grid function layer adds the possibility to associate data with the discrete grid elements, for example to put marks on vertices, or to store solution values on cells. Mathematically, it captures the notion of a function from the discrete set of grid elements of any fixed dimension to entities of some given type, for example reals or integers.
The geometrical layer provides an embedding into a concrete geometrical space of an (external) dimension which is at least the intrinsic dimension. For example, a grid of (intrinsic) dimension 2 could be embedded in 3-space, like the surface of a torus. It corresponds to the notion of a geometric realization of a combinatorial complex.
We will discuss these layers in an informal way in the introductory sections on the combinatorial, grid function and geometrical layers, respectively.
A more formal description of the concepts involved starts in the concept section.. Here C++ syntax is prescribed, in a way analogous to the STL documentation. We will refer to them with a trailing (C). This part is of cours crucial for actually implementing generic components; it is not so important for understanding the bib picture (because it contains inevitably many arbitrary decisions).
In a short lookahead, here is the generic version of the algorithm presented before:
grid_function<Cell,double> surface(Grid);
for(CellIterator c(Grid); !c.IsDone(); ++c)
surface[*c] = 0.0;
for(FacetOnCellIterator fc(c); !fc.IsDone(); ++fc)
surface[*c] += Geometry.volume(*fc);
In the third part of the documentation, concrete components are described, sorted by functionality (algorithms, grid ranges, iterators and so on). These components separate into two layers, depending on whether they are leaf components (for example basic grid implementations), or generic extensions, that is, classes which provide additional functionality for each grid component that is a model of a certain concept. In fact, most components belong to this second layer, which evidently greatly enhances reuse.
In the present framework, a mathematical grid is not represented by a single entity (e.g. a class), rather, different classes cooperate to this aim. This is already visible by the dissection into the three fundamental categories, namely combinatorics, data association and geometry.
Moreover, each of these categories introduces many sub-categories and refined concepts, especially the combinatorial one. In order to understand how grids are represented by these concepts, it is important to understand their mutual relationship.
For each concrete grid type, there is one class implementing the abstract grid concept. (In the STL parlance, it is models of the concepts.) To actually use this grid type, one has to access a number of different classes accounting for a representation of this mental "The Grid" thing one may have in mind. Thus, there are seperate classes for grid elements (vertices, edges, cells), iterators, and grid functions. The concrete grid types act as a sort of central entry point giving access to these associated types, which one can think of as forming a sort of `halo' around the central grid type.
The number of supported types will not be the same for all grids. The basic Grid concepts requires any types at all -- everything useful comes in through refinements of this concept. A grid even does not need to define all possible element types -- there are grid types used only for I/O (see IstreamComplex2DFmt) which do with a quite minimalistic set of associated types. Most profoundly, grids differ in the amount of incidence iteration they can support -- a trade-off between storage consumption and functionality.
At first reading, one can consider this type association as fixed. But in principle, it is possible to use different `halo' types with one and the same grid type. This technique allows a fine control of grid functionality which is not attainable with a monolithic approach.
An important technical question is now how to access `halo types' in a consistent and uniform manner.
The way chosen here is to collect all non-generic grid-related types into a dedicated entity called grid_types, associated to a concrete grid type. (With `non-generic', we mean types that have to be specialized for each concrete grid type.) In practice, this is just a class template that has to be specialized for concrete grids.
This mechanism provides algorithms with a single entry point to type information (and perhaps other) related to a grid parameter. It also offers a clean possibility to pass a different `halo', that is, a customized set of types which behave differently. For example, one could use special iterators for doing limited algorithm animation in an automatic way. Currently, only few algorithms are actually parameterized by grid types, an example is the CGT parameter of CalculateNeighborCells.
We may contrast this with the corresponding mechanisms for STL containers: These, too, are associated with some service types, namely the iterator type(s), which are accessed by means of nested typedefs:
Container C;
typedef Container::iterator iter_type;
iter_type i = C.begin();
MyGrid g;
typedef grid_types<MyGrid> gt; // default set of related types
gt::VertexIterator vi = g.FirstVertex();
An important qualitative difference is the parameterization of algorithms. STL algorithms are never parameterized by containers but always by iterators forming a logical range [begin, end). This captures well the only aspect of containers the algorithms are interested in, namely that they represent linear sequences. In contrast, algorithms for grids are parameterized by grids, and often also by grid functions or grid geometries, which correspond in some sense to the STL containers. This is due to the fact that grids in this case act as placeholders for the underlying mathematical structures on top of which the algorithm performs its tasks.
The set of types used by these algorithms is rich, corresponding to the richer structures of the domain. Moreover, these types are not independent, by closely relate to each other. Therefore, the responsibility for bundling the right types together has to be concentrated somewhere. This is in essence what the grid_types mechanism does: It maps grid types to a set of related types. If one want to control the way algorithms access grid-related types, one has to parameterize them with such mappings, in addition to their regular parameters.