*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
*h*_{uv} 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
*S*_{u} of watershed *u* can be computed as
the minimum weight of its incident edges.
A watershed *u* is flooded by finding its spill elevation
*S*_{u} and raising all cells in *u* with
elevation lower than *S*_{u} to
*S*_{u}. If *S*_{u} 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*(*W*^{2}) 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 =*
{*h*_{uv} | *(u,v) in E }*.The set of events
that are interesting during sweeping is
{*h*_{sweep} *= 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.

- None of
*u*or*v*is done: Collapse*u*and*v*and raise both to*h*. - Precisely one of
*u*or*v*is done: Collapse*u*and*v*. Height*h*_{uv}must be spill elevation for the watershed which is not done; raise that watershed to*h*and mark it as done. - Both
*u*and*v*are done: Height*h*cannot be the spill elevation for neither*u*nor*v*. Ignore.

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.