TerraFlow Features

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.