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

Input : Terrain cells $\backslash mathcal\{T\}$, non-outflow local minima $\backslash mathcal\{L\}$
Output: Per-cell basin identifiers bid

1 for $i\; \backslash leftarrow\; 0$ to $|\backslash mathcal\{L\}|\; -\; 1$ in parallel do
2   $bid$ of $\backslash mathcal\{L\}[i]\; \backslash leftarrow\; i$
3 end
4 for $i\; \backslash leftarrow\; 1$ to $\backslash log\_2(|\backslash mathcal\{T\}|)$ do
5   foreach cell $c\; \backslash in\; \backslash mathcal\{T\}$ in parallel do
6     $bid$ of $c\; \backslash leftarrow\; bid$ of recipient of $c$
7     recipient of $c\; \backslash leftarrow$ recipient of recipient of $c$
8   end
9 end

graph to progressively detect the path of water and update recipients. The algorithm proceeds through the stages of basin identification, saddle edge selection, and donor-recipient re-routing.

Basin identification. Our algorithm begins by segmenting out each stream tree and associating with its cells a unique basin identifier (hereafter referred to as a basin-id, or bid in the pseudo-code of Algorithm 2). To this end, we assign to each non-outflow local minima a unique identifier – leaving a common outflow identifier for all outflow basins – and use pointer jumping to copy this identifier in parallel to all upstream nodes of its stream tree (Algorithm 2).

Saddle edge selection. We use the per-cell basin annotation to isolate cells lying along the border with neighboring basins. To do so, we tag as a border cell, any cell in the current basin with at least one adjacent cell belonging to another basin. Ultimately, one of these border cells is chosen as a saddle edge in the depression graph. We do not need to construct these edges explicitly as Boruvka's algorithm only requires the edge with the lowest weight.

For each border cell, this weight is set as the lowest elevation that will permit an overflow from it into an adjacent basin. Specifically, this is the maximum of the border cell's altitude and the lowest altitude among its neighboring cells. Then we choose the border cell with minimum weight per basin.

Although we could compute the minimum altitude using a variant of rake-compress in $\backslash mathcal\{O\}(\backslash log\; n)$, we found it more efficient to instead compute it in a single step with atomic operations. We also store the saddle, which is the source cell in the current basin with minimum weight, and the outlet, which is its lowest neighbouring cell across the basin border (see Figure 4).

Close-coupled loops can occur when two basins have saddle edges pointing at each other. We resolve this by simply deleting the edge with the higher saddle basin-id. We also apply a similar strategy to choose among saddles of identical elevation, which could lead to larger cycles. This is prevented by selecting saddles in lexicographic order (elevation concatenated with the basin-id of the outlet). This algorithm is summarized in Algorithm 3.

Re-routing recipients. Ordinarily, the next step in Boruvka's algorithm would be to collapse the newly incorporated edges. Due to