FastFlow: GPU Acceleration of Flow and Depression Routing for Landscape Simulation

Our stated aim is to efficiently calculate the direction and volume of water flow over an input terrain with due consideration of local depressions. We choose to represent the terrain as a 2D regular

grid of elevations $z$, often referred to as a Digital Elevation Model (DEM). This is an implementation decision and adaptation of our algorithms to other heightfield structures, such as Triangular Irregular Networks [Ban07], is straightforward. Note, however, that $z$ is a unique mapping $h(x,\; y)\; =\; z$ over the $x,\; y$ plane and so we do not support true 3D terrains with caves and overhangs [GGP⁺ 19].

There are three layers of terrain input to our algorithms. The first is the elevation grid. We refer to each element of the grid as a terrain cell $c$, with $n$ being the total number of cells. We prefer to use the term “cell” as opposed to the more familiar “vertex” or “node” in this context because we want to make clear that this represents a rectangular area on the terrain surrounding the sample. The neighbors of $c$, denoted by $N\_c$, are the 4 cells directly adjacent to $c$ in the $x$ and $y$ directions (Figure 2 (b)). The second input layer is the amount of water (or any loose material) initially deposited on the terrain and subject to flow. This can be interpreted as rainfall or precipitation and is denoted as $p\_c$. The final layer is a user-defined boolean mask $b\_c\; \backslash mapsto\; \backslash \{0,\; 1\backslash \}$ indicating the presence (1) or absence (0) of outflow cells. These serve as boundary conditions and act to trap water flow. Typically, outflow cells would line the edges of the grid, but there are cases, such as groundwater sinks, estuaries, and sea shores where they would be placed within the domain.

We output two maps: one for the per-cell discharge, and another for per-cell recipients corrected by depression routing to yield uninterrupted water paths.

Given these preliminaries, we now provide an overview of the flow and depression routing algorithms.