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

Jain, Aryamaan and Kerbl, Bernhard and Gain, James and Finley, Brandon and Cordonnier, Guillaume (2024) FastFlow: GPU Acceleration of Flow and Depression Routing for Landscape Simulation, Computer Graphics Forum, 43.

Text (PDF) Computer Graphics Forum - 2024 - Jain - FastFlow GPU Acceleration of Flow and Depression Routing for Landscape Simulation.pdf - Published Version Download (4MB)

Abstract

Terrain analysis plays an important role in computer graphics, hydrology and geomorphology. In particular, analyzing the path of material flow over a terrain with consideration of local depressions is a precursor to many further tasks in erosion, river formation, and plant ecosystem simulation. For example, fluvial erosion simulation used in terrain modeling computes water discharge to repeatedly locate erosion channels for soil removal and transport. Despite its significance, traditional methods face performance constraints, limiting their broader applicability. In this paper, we propose a novel GPU flow routing algorithm that computes the water discharge in O(log n) iterations for a terrain with n vertices (assuming n processors). We also provide a depression routing algorithm to route the water out of local minima formed by depressions in the terrain, which converges in O(log 2 n) iterations. Our implementation of these algorithms leads to a 5× speedup for flow routing and 34 × to 52 × speedup for depression routing compared to previous work on a 10242 terrain, enabling interactive control of terrain simulation.

Item Type:	Journal article (paginated)
Uncontrolled Keywords:	CCS Concepts, • Computing methodologies → Shape modeling, Massively parallel algorithms
Subjects:	Computing methodologies Computing methodologies > Computer graphics > Shape modeling
Date Deposited:	20 Oct 2025 08:38
Last Modified:	20 Oct 2025 08:38
URI:	https://pubs.cs.uct.ac.za/id/eprint/1774

Actions (login required)

View Item