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

Algorithm 3: Finding saddles and outlets

Input : Terrain cells $\mathcal{T}$ with elevation $z$ , set of depression basins $\mathcal{D}$
Output: Per-depression saddle and outlet

1 // Compute border cells and store the border altitude in  $z'$ 
2 foreach cell  $c \in \mathcal{T}$  in parallel do
3   if  $bid_c \neq bid_n$  of any 4-neighbour  $n$  of  $c$  ( $n \in \mathcal{N}_c$ ) then
4     tag  $c$  as a border cell
5      $znb \leftarrow \min(z_n \text{ for } n \in \mathcal{N}_c \text{ such that } bid_c \neq bid_n)$ 
6      $z'_c \leftarrow \max(z_c, znb)$ 
7   end
8 end

9 // Saddles and outlets (with atomic lexicographic argmin)
10 foreach basin  $d \in \mathcal{D}$  in parallel do
11   saddle of  $d \leftarrow \text{argmin}((z'_c, bid_n)$  for each border cell  $c$ 
12   and  $n \in \mathcal{N}_c$  such that  $bid_c = d$  and  $bid_n \neq d$ )
13   outlet of  $d \leftarrow \text{argmin}(z_n$  for each neighbor  $n$  of the
14   saddle such that  $bid_n \neq d$ )
15 end

16 // Remove cycles
17 foreach basin  $d \in \mathcal{D}$  in parallel do
18    $d' \leftarrow$  basin of outlet of  $d$ 
19   if  $bid$  of outlet of  $d' = bid$  of saddle of  $d$  then
20     if  $bid$  of outlet of  $d < bid$  of saddle of  $d$  then
21       Delete the saddle and outlet of  $d$ 
22     end
23   end
24 end

our two-layer structure, with an implicit depression graph and explicit flow routing, this needs to be interpreted differently. Instead, we merge stream trees by adding and re-routing recipient links, using one of two strategies (Figure 5 (b)).

The first strategy, depression jumping, involves adding a recipient link directly from the depression's local minima to the newly established outlet cell. This is straightforward and efficient but leads to a jump discontinuity in the flow path, which, depending on the application, may be undesirable.

The second strategy, depression carving [Rie98], mimics the course of water channeling down from the saddle. We first compute the flow path that connects a saddle and outlet to the associated local minimum and then reverse the direction of all recipient links. In this way, we allow water to flow upstream from the local minimum to the outlet. The pseudo-code for these two strategies is presented in Algorithm 4.

A single iteration of basin identification, saddle edge selection, and re-routing of recipients ends up being insufficient. It will not necessarily connect all depressions to the set of outflow basins. However, on any given iteration this process removes at least half of the remaining depressions, meaning that a total of $\log(L)$ iterations are required, where $L$ is the number of local minima (Algorithm 5).