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

Algorithms for evaluating water flow over terrains are a staple of geo-analysis, with applications in computer graphics and beyond. Consequently, any improvement in their run-time performance is worth serious consideration. In this paper, we provide improved algorithms for solving both flow and depression routing problems, with, respectively, $O(\backslash log\; n)$ and $O(\backslash log^2\; n)$ complexity for a terrain with $n$ nodes. This is an improvement on previous methods, which usually require as many iterations as the length of the longest river ($\backslash sim\; \backslash sqrt\{n\}$). Most importantly, we are the first to propose a GPU solution for both flow and depression routing.

In comparative terms, our GPU implementation for depression routing outperforms an optimized parallel CPU algorithm by $34\backslash times$ to $52\backslash times$ on a $1024^2$ resolution terrain, depending on the strategy for recipient correction. We also improve on previous GPU methods for flow routing [Bar19, SPF⁺23] by a factor of $5\backslash times$.

In terms of raw performance, our GPU implementation executes in under 55ms on terrains up to $4096^2$ sample resolution. This opens up new opportunities and research avenues for the future use of flow and depression routing in an interactive context. Further work on our algorithm is also required to reach more general applications, for instance by allowing for multiple recipients (Multiple Flow Directions).