We are now in a position to define what a depression means in our context. As a preliminary, we use the term basin for the set of terrain cells that share the same stream tree, effectively all belonging to the same catchment area and channeling water to a single root cell. If this root cell is an outflow, then the basin is classified as an outflow basin, otherwise, it constitutes a depression (Figure 2 (c)).
3.2. Depression routing
Depression routing is the task of finding reasonable water paths out of all depression basins. Unfortunately, this problem is non-local and therefore not amenable to trivial parallelization. For instance, an obvious first thought would be to connect a depression to an adjacent basin at the point of the lowest neighboring elevation, but this may give rise to a chain of connections that form a cycle, and therefore is unable to route the water toward outflow cells.
Two families of solutions have been proposed to tackle this issue. One option is to progressively flood the terrain from the outflow cells towards the interior, keeping track of cells to be processed through a priority queue [BLM14]. While this enables a simple and efficient single-threaded solution, it is not suited to parallelization on the GPU, because it imposes a sequential order, with each processed cell potentially changing the subsequent state of the queue. The other option is to build a depression graph by representing depressions as nodes and their adjacency relationships as edges. There are two subtleties. First, all outflow basins are grouped into a single node marked as the start. Second, edges are weighted according to the lowest altitude along their shared boundary. The path out of all depressions is then given by the Minimum Spanning Tree (MST) of the depression graph, which connects all depressions to the collection of outflow basins.
In Section 5, we detail our GPU implementation of depression routing and propose two strategies for correcting the flow path: either creating a jump connection between a local minimum in the current depression and a cell in the next basin or preserving the continuity by inverting flow for a subset of cells in the depression.