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

Natural landscapes have been a source of fascination for generations of artists and scientists. As a consequence, the effective digital representation of terrain and surface features is crucial in several domains. In computer graphics, realistic landscapes provide a backdrop for films and games. In earth and environmental sciences, it supports investigations of the natural forces that shape our planet. In geographic information systems (GIS), it serves as the backbone of digital twin technologies that, in turn, support various forms of decision-making based on geospatial analysis.

In such applications, the inclusion of material (such as water [CBC*16] or sediment [YBG*19]) flow is ubiquitous and its impact cannot be ignored. Water affects surface appearance directly through above-ground accumulation in rivers and lakes, and indirectly through below-ground infiltration and the consequent supply of water to plants through osmosis. Over geological timescales, fluvial erosion driven by water flow sculpts mountains and valleys. Furthermore, water transforming through evaporation and condensation between the land surface and atmosphere drives weather and climate. Consequently, modeling the flow of material is a critical task in many applications involving terrain (Figure 1). (We will refer, without loss of generality, to the specific instance of water flow in the remainder of the paper, as our techniques extend trivially to other materials.)

Instead of treating water explicitly (for instance by solving the

Figure 1: Our GPU flow and depression routing algorithms can be applied to accelerate multiple aspects of landscape simulation, including 1) fluvial erosion, 2) rivers, 3) lakes, 4) ecosystems, and 5) sediment deposition.

Shallow Water Equations [Ben07]), researchers in computer graphics [CBC*16], hydrology [GM97] and geomorphology [BW13] have proposed methods for computing water discharge (the volumetric flow rate of water). This is based on the observation that discharge is the upstream integral of precipitation. Typically, a single simulated blanket of rain is applied and runoff is then progressively accumulated from higher elevations downwards to minima along the bounding edges of the terrain. This is complicated due to the presence of local minima (or depressions) in the terrain interior, which trap the flow. This necessitates a global computation of routing through chains of depressions toward the outflow boundary.

For clarity, we define flow routing as the computation of the discharge – or any other material flux – over the terrain, and depression routing as the computation of the water flow path out of depressions.

While previous work has addressed both flow and depression routing, with optimal solutions for the CPU [CBB19], and a separate focus on distributed computing [Bar16], existing solutions for the GPU [Bar19, SPF⁺23] are inefficient for flow routing and typically do not consider depression routing at all.

In this paper, we present a GPU algorithm to solve both flow and depression routing within the same framework. In the former case, we express flow routing as an accumulation (or scan) across a tree. We use a rake-compress algorithm [SAF05], which combines pointer jumping and tree pruning, to perform this accumulation efficiently. In the latter case, we cast depression routing as an instance of searching for a minimum spanning tree and are thus able to adapt Boruvka's algorithm [Bor26, VHPN09]. Our algorithms for flow and depression routing over a terrain with $n$ nodes complete, respectively, in $\backslash mathcal\{O\}(\backslash log\; n)$ and $\backslash mathcal\{O\}(\backslash log^2\; n)$ iterations, assuming $n$ processors. Furthermore, we provide optimized implementations of our algorithms in PyTorch and TensorFlow with custom CUDA kernels, which are well-suited for integration into existing terrain modeling pipelines.

We demonstrate its practicality through three example applications: river generation, terrain erosion, and ecosystem simulation. These use cases illustrate that with minimal modification, our algorithms are applicable to terrain modeling, geospatial analysis, and simulation models in computer graphics, geomorphology, and ecology. In particular, we show how to adapt our GPU algorithm to an implicit time-stepping scheme for erosion simulation using the Stream Power Law. This reduces the number of required time steps and significantly enhances interactivity. We also present a new strategy to account for sediment deposition.

Finally, we benchmark our solution against CPU and distributed computing variants, as well as previous GPU solutions. Our GPU implementation for flow routing provides a $5\backslash times$ speed up on a $1024\; \backslash times\; 1024$ resolution terrain over competing GPU implementations, while depression routing gains $34\backslash times$ to $52\backslash times$ speedup compared to parallel CPU approaches, depending on the variant of our algorithm. This improvement in performance enables applications in natural phenomena including river and lake modeling, terrain erosion, and sediment deposition, to cross the threshold and achieve interactive response times, especially when flow and depression routing need to be recomputed over many iterations.

To summarize, our contributions are: 1) an efficient parallel algorithm for flow and depression routing, 2) an accompanying implementation on the GPU, and 3) demonstrations of its suitability for typical application areas.