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

To match the expected natural behaviour, water needs to be routed out of local depressions. Our strategy is to create new donor-recipient connections and reroute others to ensure an uninterrupted, minimum-cost path from any node to one of the designated outflows. In this context, we define the minimum cost to be the smallest increase in altitude needed to move water out of a depression.

Broadly speaking, this involves connecting depression basins with outflow basins through saddle points and then re-orienting a path of edges within each depression to flow uphill and link to the corresponding outlet. The challenge lies in preventing the formation of cycles as this will lead to highly unnatural flow behavior. Once all stream trees have been corrected, we only need to run flow routing once to calculate discharge volumes.

Figure 4: A saddle between basins: With respect to a source basin (in light red) and its neighbor (light green), the saddle and outlet together form the lowest elevation bridge.

Depression routing consists of building a depression graph, in which the depression and outflow basins represent nodes, and edges are formed by the adjacent cells between different basins. It is likely that there will be multiple potential candidates between any two basin nodes formed by cells paired along their common border. We choose the one with the lowest maximum altitude and call this the saddle (see Figure 4). The saddle altitude is the weight assigned to the new edge in the depression graph. From a physical perspective, choosing the path with the lowest altitude ensures that the potential energy cost of water routed out of the basin is kept to a minimum.

Following Cordonnier et al. [CBB19], the minimum cost route out of depressions can now be cast as a minimum spanning tree problem. Among the several MST algorithms (e.g., Prim's, Kruskal's), Boruvka's [Bor26] is perhaps the most amenable to parallelization [VHPN09]. Boruvka's Algorithm constructs a minimum spanning tree by iteratively identifying and merging the minimum-weight edges of each component in parallel until only one component remains. We note that the optimal theoretical complexity for parallel MST algorithms is $\backslash mathcal\{O\}(\backslash log\; n)$ [CHL01], but the specific algorithmic improvements needed to achieve this are not portable to the GPU, as they involve complex branching and scheduling operations. Therefore, we build our algorithm upon the more usual $\backslash mathcal\{O\}(\backslash log^2\; n)$ variant.

Figure 5: (a) Two iterations of depression routing. The grey basin on the left does not have an outgoing edge, likely because it would have created a loop with a basin of a higher id. In the next iteration, basins are recolored based on their new local minima, and only one edge remains. (b) From the initial configuration of the recipients (top), we apply either depression carving, which reverses the path of water until it reaches the outlet, or depression jumping, which directly connects the local minimum with the outlet.

Boruvka's algorithm consists of greedily forming sub-trees by treating each as a single collapsed node. It begins by treating all nodes in the initial graph as separate sub-trees. Then, each of these is grown by incorporating the incident edge of minimal weight (and its attached sub-tree). The two sub-trees are joined, their shared edge is collapsed, and the algorithm repeats until a single tree results. The parallel variant of Boruvka's algorithm [VHPN09] applies edge selection in parallel and replaces the edge collapse with a structure that maintains the connected components of the tree under construction. This requires at most $\backslash log\_2(V)$ iterations, where $V$ is the number of vertices in the graph (depressions in our case) (Figure 5 (a)). Each of these iterations parses the structure for connected components, adding an extra $\backslash log\_2(V)$ iterations at worst, and resulting in an overall complexity of $\backslash mathcal\{O\}(\backslash log^2(V))$.

While we could build an explicit depression graph, compute a minimum spanning tree, and parse the tree to update recipients, such a construction would be costly as it involves the detection of pairs of adjacent depressions. Furthermore, while Boruvka's algorithm outputs an undirected tree, we require directed edges to orient water towards outflow basins. Instead, we introduce a hybrid structure where terrain data is used in conjunction with the depression