Complexity of software in the domains mentioned before is often determined by the interaction of (grid) data structures and algorithms operating on them. Examples for algorithms include cell neighbor search, iso-surface extraction, rendering of geometric structures, intersections of geometric structures, grid generation and refinement, numerical discretizations like finite elements (FEM) or finite volumes (FV), or point localization in a grid.
Due to the similarity of the underlying mathematical concepts, algorithms are in principle independent of a particular data structure. Yet, in practice their implementations rely heavily on the details of the latter. Consequently, such an implementation can be used only with the concrete data structure it was designed for. Given the multitude of grid representations in use, this is a real problem.
It would therefore be a considerable gain in reusability if grid algorithms could be implemented in a way that is independent of the data representation, without compromising efficiency substantially. For the comparatively simple case of linear sequences, this has been achieved by the C++ Standard Template Library (STL). We propose an approach similar in spirit for the more involved case of grids.
The paper is organized as follows: First (section 2), we give a very short overview over the mathematical aspects of grids and the requirements of grid algorithms. In section 3, we introduce set of core functionality (a micro-kernel) for grid data-structures. Section 4 deals with a few selected generic components, followed by a detailed case study for grid functions in section 5. Efficiency is considered in section 6. In section 7, we discuss some difficulties that arise in generic programming. Finally, we compare our work to related efforts, and discuss some of its implications.
This work is part of the author's doctoral thesis (4), where the approach is evaluated in the context of the sequential and distributed numerical solution of PDEs.