Rain falling on a landscape flows downstream and progressively accumulates into streams and rivers. The volume of water flowing through a river cross-section per unit of time is called the discharge. Equivalently, the discharge is the upstream integral of the precipitation map. Flow routing involves the computation of this discharge for each cell of the terrain grid.
3.1. Flow routing
The direction of the water flow is discretized on the basis of a per-cell recipient, , which is chosen among the neighboring cells of the terrain and obeys the condition . This allows several mechanisms for the choice of neighbour. While the different choices have their place and are compatible with our algorithm, we prefer a random selection, with a probability based on the elevation difference between the source and potential recipient [TGSC24].
Let us consider the cells of a terrain as nodes in a graph, and interpret the connection between a cell and its recipient as a directed edge. The strict monotonically decreasing elevation of recipients guarantees that the graph does not contain any cycles. Since each cell has a single recipient (equivalently, a single edge leaves each node), this graph represents a set of trees (an algorithmic forest).
We use the term stream tree for each connected subgraph, since it represents a set of water channels. This allows flow routing to be recast as an accumulation (or scan). For a given stream tree, the scan proceeds from its leaves (ridges of the terrain) to a single root (an outflow cell). We propose employing rake and compress [SAF05] algorithms to perform this task in parallel (Section 4).
We handle the user-defined outflow mask by excluding recipient edges for its cells so that they become root nodes in the stream forest. However, other cells may also lack recipients if none of their neighbours meet the condition, i.e., local minima and flat areas. In reality, instead of interrupting flow, these areas would fill and overflow. This necessitates a solution for depression routing.