We implemented the TerraFlow flow routing and flow accumulation algorithms as described in Algorithm Outline.

- FILL, the TerraFlow flow routing
program, reads the elevation grid into a TPIE stream,
implements all subsequent steps and produces as output a flow
direction grid and a filled elevation grid. The output flow
direction
grid can be MFD or SFD (default MFD). FILL can
also create a special
file called the
*flowStream*which contains all the information required by FLOW (filled elevations, flow directions) but in the internal format of TerraFlow. - FLOW, the TerraFlow flow accumulation program, uses the flowStream produced by FILL and computes the flow accumulation grid. By default, FLOW pushes flow downslope using MFD and the directions computed by FILL.

Both FILL and FLOW can run in either SFD or MFD mode. This has the followin meaning:

For FILL

- MFD means that the flow direction of a cell points to:
- on slopes: to all downslope neighbors
- on flat areas: to all the neighbor cells which discover it in the same time in the course of a BFS starting from the spill cells of the plateau.

- SFD means that the flow direction of a
cell points to:
- on slopes: to the steepest downslope neighbor (biggest tan_beta).
- on flat areas: choose one neighbor (among the neighbor cells which discover it in the same time in the course of a BFS starting from the spill cells of the plateau) using some heuristic.

For FLOW

- MFD means that every cell distributes its incoming flow
to:
- on slopes: to all downslope neighbors
- on flat areas: to all neighbors pointed to by the cell's flow direction.

- SFD means that every cell distributes its incoming flow
to a dominant direction. This dominant direction is computed as
follows:
- on slopes: the steepest downslope neighbor (biggest tan_beta).
- on flat areas: choose one neighbor (among the neighbor cells which discover it in the same time in the course of a BFS starting from the spill cells of the plateau) using some heuristic.

The combination of the SFD/MFD options for FILL and FLOW have the following effects:

- (FILL=MFD, FLOW=MFD)
For every cell which has downslope neighbors its direction points
to all of them. On plateaus, the direction of the cell points to all
cells which discover it in the course of the BFS starting from the
spill-cells of the plateau. FLOW uses all the directions of the cell
to distribute flow.
- (FILL=MFD, FLOW=SFD)
Same as above for flow routing. FLOW computes the dominant
direction for each cell and uses only this direction to distribute
flow. On slopes the dominant direction is to the neighbor cell with
biggest
*tan beta*. On plateaus FILL picks the first one. - (FILL=SFD, FLOW=SFD)
FILL computes only the dominant direction: on slopes, it selects
the neighbor cell with biggest
*tan beta*; on plateaus it uses an heuristic to select a ``middle'' direction (Note that it has more information than FILL and can make a better choice). - (FILL=SFD, FLOW=MFD) FILL computes dominant directions as above. FLOW uses SFD on plateaus, and extends SFD to MFD on slopes by including all downslope neighbors. Note that (MFD, SFD) and (SFD, SFD) will give identical results on slopes, while on plateaus the second one can make a better choice.

**Additional feature:** FLOW can switch from MFD to SFD at
user-defined threshold.
By default, FLOW pushes flow downslope using MFD. If the user
specifies a threshold value *c* then, if the flow value of a cell
exceeds *c*, FLOW computes and uses a dominant direction (among
the possibly multiple directions computed by FILL); otherwise, if the
flow value is below *c* it uses the flow directions computed by
FILL . Using this option the user can experiment with different
thresholds in order to get more realistic flow accumulation grids.
The intended usage is to run FILL to compute MFD flow directions and
then run FLOW with the desired threshold. If the threshold *c*
is set to 0 the flow accumulation algorithm simulates a D8-type
algorithm, as it was initially proposed by O'Callaghan and Mark.

Our implementation of TerraFlow is based on the TPIE (Transparent Parallel I/O
Environment) system. TPIE is a collection of templated functions and
classes designed to facilitate easy and portable implementation of
external memory algorithms. The basic data structure in TPIE is a
*stream*, representing a list of objects of the same type. The
system contains I/O-efficient implementations of algorithms for
scanning, merging, distributing and sorting streams and data
structures like I/O-efficient priority queue. TPIE facilitated the
implementation of the algorithms, as it contains many of the building
blocks required.

<laura@cs.duke.edu> Last modified: Wed Apr 18 22:50:22 2001 by laura.