Flooding the terrain

Flooding removes the sinks in the terrain by simulating flooding the terrain with an infinite amount of uniform rainfall. Flooding causes the level of water to gradually increase in each of the sinks and pockets of the terrain, causing them to overflow and spill into each other repeatedly, until each cell finds a flow path downhill. Once steady state is reached, the level of water remains constant and all water drains off the edge (the outside of the grid). Flooding determines the final level of the water for each cell of the terrain, and if it is higher than the elevation of that cell (ie. if the cell is under water), it raises it to the water level. This produces a new DEM with the property that each cell has a flow path (going through cells with non-increasing elevations) off the edge of the terrain; there will be no sinks, and it is easy to assign flow directions to every cell.

Flooding can be elegantly expressed in terms of sweeping and cycle-collapsing on the watershed graph. Let G=(V,E) be the watershed graph and let huv be the weight of edge (u,v), i.e. the smallest elevation on the boundary between watersheds u and v. The elevation of the lowest cell on the boundary of an watershed is called the spill elevation of that watershed. The spill elevation Su of watershed u can be computed as the minimum weight of its incident edges. A watershed u is flooded by finding its spill elevation Su and raising all cells in u with elevation lower than Su to Su. If Su is on the border with watershed v, this corresponds to flooding watershed u until it spills into and merges with watershed v. The flooding process collapses the two watersheds into one, readjusts the watershed graph, finds the spill elevation of the new watershed, and repeats until all watersheds collapse into the outside watershed. The expensive part in this process is the readjustment of the watershed graph after a collapse and the computation of the spill elevation of new watershed. A straightforward implementation of these ideas leads to an O(W2) algorithm, where W is the number of watersheds (number of nodes in the watershed graph).

The main idea in TerraFlow's new flooding algorithm is to avoid recomputing the spill elevation every time two watersheds collapse. We do this by viewing the flooding process as a bottom-up (in spill elevation) sweep through the graph with a horizontal plane. Denote the set of all weights of the watershed graph as Spill = {huv | (u,v) in E }.The set of events that are interesting during sweeping is {hsweep = h| h in Spill}. When a watershed collapses with the outside watershed we say that the watershed is done. As the sweep plane hits height h corresponding to the edge (u,v) between watersheds u and v it can be one out of the three cases.

We use a union-find structure to handle the watershed collapses, and, if necessary, a tiling step to reduce the number of watersheds. Flooding can be done in Sort(N) I/Os.


<laura@cs.duke.edu>
Last modified: Wed Apr 18 21:07:31 2001 by laura.