Introduction

Representation of spatial or planar geometric structures is central to many application domains, such as computational geometry, geometric modeling, geographical information systems (GIS), and computational simulation by numerical solution of partial differential equations (PDEs). Spatial structures are typically represented by a subdivision into simpler entities like triangles or cubes, as in fig. 1. This subdivision is called grid, mesh, polyhedron, triangulation or cellular complex, depending on the application area.

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.

Figure: A grid representing the north-friesian coast

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.