<H2>DESCRIPTION</H2>

<p><EM>r.terraflow</EM> takes as input a raster digital elevation

model (DEM) and computes the flow direction raster and the flow

accumulation raster, as well as the flooded elevation raster,

sink-watershed raster (partition into watersheds around sinks) and tci

(topographic convergence index) raster.

<p><EM>r.terraflow</EM> computes these rasters using well-known

approaches, with the difference that its emphasis is on the

computational complexity of the algorithms, rather than on modeling

realistic flow.  <EM>r.terraflow</EM> emerged from the necessity of

having scalable software able to process efficiently very large

terrains.  It is based on theoretically optimal algorithms developed

in the framework of I/O-efficient algorithms.  <EM>r.terraflow</EM>

was designed and optimized especially for massive grids and is able to

process terrains which were impractical with similar functions

existing in other GIS systems.

<p>Flow directions are computed using either the MFD (Multiple Flow

Direction) model or the SFD (Single Flow Direction, or D8) model,

illustrated below. Both methods compute downslope flow directions by

inspecting the 3-by-3 window around the current cell. The SFD method

assigns a unique flow direction towards the steepest downslope

neighbor. The MFD method assigns multiple flow directions towards all

downslope neighbors.

<p>

<table width=80%>

<tr>

<th><img src="rterraflow_dir2.png" alt="[SFD]" border=0></td>

<th><img src="rterraflow_dir3.png" alt="[MFD]" border=0></td>

<tr>

<th>SFD: flow to steepest<br> downslope neighbor.</th>

<th>MFD: flow to all<br> downslope neighbors.</th>

</table>

<p>

<table width=80%>

<tr>

<th><img src="rterraflow_codes.png" alt="[CODES]" border=0></td>

<th><img src="rterraflow_codes_mfd.png" alt="[CODES_MFD]" border=0></td>

<th><img src="rterraflow_codes_sfd.png" alt="[CODES_MFD]" border=0></td>

<tr>

<th>Possible flow direction<br> values.</th>

<th>Example flow direction<br> value for MFD.</th>

<th>Example flow direction<br> value for SFD.</th>

</table>

<p>

In case of SFD, the flow direction can take one value from 1, 2, 4, 8, 16, 32,

64, 128. In case of MFD, the flow direction value is a sum of all the possible

flow directions. A flow direction value 0 means ... , -1 means ... , null means

 ... (???).

<p>The SFD and the MFD method cannot compute flow directions for

cells which have the same height as all their neighbors (flat areas)

or cells which do not have downslope neighbors (one-cell pits).

<ul>

  <li>On plateaus (flat areas that spill out) <EM>r.terraflow</EM>

routes flow so that globally the flow goes towards the spill cells of

the plateaus.

  <li>On sinks (flat areas that do not spill out, including one-cell

pits) <EM>r.terraflow</EM> assigns flow by flooding the terrain until

all the sinks are filled and assigning flow directions on the filled

terrain.

</ul>

<p>In order to flood the terrain, <EM>r.terraflow</EM> identifies all

sinks and partitions the terrain into sink-watersheds (a

sink-watershed contains all the cells that flow into that sink),

builds a graph representing the adjacency information of the

sink-watersheds, and uses this sink-watershed graph to merge

watersheds into each other along their lowest common boundary until

all watersheds have a flow path outside the terrain. Flooding produces

a sink-less terrain in which every cell has a downslope flow path

leading outside the terrain and therefore every cell in the terrain

can be assigned SFD/MFD flow directions as above.

<p>Once flow directions are computed for every cell in the terrain,

<EM>r.terraflow</EM> computes flow accumulation by routing water using

the flow directions and keeping track of how much water flows through

each cell.

<EM>r.terraflow</EM> also computes the tci raster (topographic convergence

index, defined as the logarithm of the ratio of flow accumulation and

local slope).

For more details on the algorithms see [1,2,3].

<H2>NOTES</H2>

<p>One of the techniques used by <EM>r.terraflow</EM> is the

space-time trade-off. In particular, in order to avoid searches, which

are I/O-expensive, <EM>r.terraflow</EM> computes and works with an

augmented elevation raster in which each cell stores relevant

information about its 8 neighbors, in total up to 80B per cell.  As a

result <EM>r.terraflow</EM> works with intermediate temporary files

that may be up to 80N bytes, where N is the number of cells (rows x

columns) in the elevation raster (more precisely, 80K bytes, where K

is the number of valid (not nodata) cells in the input elevation

raster).

All this intermediate temporary files are stored in the path specified

by <em>STREAM_DIR</em>. Note: <em>STREAM_DIR</em> must contain enough free

disk space in order to store up to 2 x 80N bytes.

<p>The internal type used by <EM>r.terraflow</EM> to store elevations

can be defined at compile-time.  By default, <EM>r.terraflow</EM> is

compiled to store elevations internally as floats.

A version which is compiled to store elevations internally as

shorts is available as <EM>r.terraflow.short</EM>. Other versions can

be created by the user if needed. 

<p><EM>r.terraflow.short</EM> uses less space (up to 60B per cell, up

to 60N intermediate file) and therefore is more space and time

efficient.  <EM>r.terraflow</EM> is intended for use with floating

point raster data (FCELL), and <EM>r.terraflow.short</EM> with integer

raster data (CELL) in which the maximum elevation does not exceed the

value of a short SHRT_MAX=32767 (this is not a constraint for any

terrain data of the Earth, if elevation is stored in meters).

<p>Both <EM>r.terraflow</EM> and <EM>r.terraflow.short</EM> work with

input elevation rasters which can be either integer, floating point or

double (CELL, FCELL, DCELL). If the input raster contains a value that

exceeds the allowed internal range (short for

<EM>r.terraflow.short</EM>, float for <EM>r.terraflow</EM>), the

program exits with a warning message. Otherwise, if all values in the

input elevation raster are in range, they will be converted

(truncated) to the internal elevation type (short for

<EM>r.terraflow.short</EM>, float for <EM>r.terraflow</EM>). In this

case precision may be lost and artificial flat areas may be created.

<p>For instance, if <EM>r.terraflow.short</EM> is used with floating

point raster data (FCELL or DCELL), the values of the elevation will

be truncated as shorts. This may create artificial flat areas, and the

outpus of <EM>r.terraflow.short</EM> may be less realistic than those

of r.terraflow on floating point raster data.

<p>The outputs of <EM>r.terraflow.short</EM> and <EM>r.terraflow</EM> are

identical on integer raster data (CELL).

<p>The <em>memory</em> should be set to an underestimate of

the amount of available (free) main memory on the machine. <em>r.terraflow</em>

will use at all times at most this much memory, and the virtual memory system

will never be in use.

<H2>EXAMPLES</H2>

<div class="code"><pre>

r.terraflow elev=spearfish filled=spearfish-filled dir=spearfish-mfdir

swatershed=spearfish-watershed accumulation=spearfish-accu tci=spearfish-tci

r.terraflow elev=spearfish filled=spearfish-filled dir=spearfish-mfdir

swatershed=spearfish-watershed accumulation=spearfish-accu tci=spearfish-tci

d8cut=500 memory=800 STREAM-DIR=/var/tmp/ stats=spearfish-stats.txt 

</pre></div>

<H2>SEE ALSO</H2>

<ul>

  <li>The <a

href="http://www.cs.duke.edu/geo*/terraflow/">TerraFlow</a> project at Duke University

  <li> <a href=r.flow.html>r.flow</a>,

       <A HREF="r.basins.fill.html">r.basins.fill</A>,

       <A HREF="r.drain.html">r.drain</A>,

       <a href="r.topidx.html">r.topidx</a>,

       <a href="r.topmodel.html">r.topmodel</a>,

       <A HREF="r.water.outlet.html">r.water.outlet</A>,

       <A HREF="r.watershed.html">r.watershed</A>

</ul>

<H2>AUTHORS</H2>

<dl>

  <dt>Original version of program: The <a

           href="http://www.cs.duke.edu/geo*/terraflow/">TerraFlow</a> project,

        1999, Duke University.

        <dd><a href="http://www.cs.duke.edu/~large/">Lars Arge</a>,

                <a href="http://www.cs.duke.edu/~chase/">Jeff Chase</a>,

        <a href="http://www.env.duke.edu/faculty/bios/halpin.html">Pat Halpin</a>,

        <a href="http://www.cs.duke.edu/~laura/">Laura Toma</a>,

        <a href="http://www.env.duke.edu/faculty/bios/urban.html">Dean Urban</a>,

        <a href="http://www.cs.duke.edu/~jsv/">Jeff Vitter</a>,

        <a href="http://www.cs.duke.edu/~rajiv/">Rajiv Wickremesinghe</a>.

  <dt>Porting for GRASS, 2002:

    <dd> <a href="http://www.cs.duke.edu/~large/">Lars Arge</a>,

             <a href="http://skagit.meas.ncsu.edu/~helena/index.html">Helena Mitasova,</a>

                 <a href="http://www.cs.duke.edu/~laura/">Laura Toma</a>. 

        <dt>Contact: <a href="mailto:laura@cs.duke.edu"> Laura Toma</a></dt>

</dl>

<H2>REFERENCES</H2>

<ol>

  <li><A NAME="arge:drainage"

       HREF="http://www.cs.duke.edu/geo*/terraflow/papers/alenex00_drainage.ps.gz">

       I/O-efficient algorithms for problems on grid-based

       terrains</A>.  Lars Arge, Laura Toma, and Jeffrey S. Vitter. In

       <EM>Proc. Workshop on Algorithm Engineering and Experimentation</EM>,

2000. To appear in Journal of Experimental Algorithms.

  <li><A NAME="terraflow:acmgis01"

       HREF="http://www.cs.duke.edu/geo*/terraflow/papers/acmgis01_terraflow.pdf">

Flow computation on massive grids</A>.

       Lars Arge, Jeffrey S. Chase, Patrick N. Halpin, Laura Toma,

       Jeffrey S. Vitter, Dean Urban and Rajiv Wickremesinghe. In

       <EM>Proc. ACM Symposium on Advances in Geographic Information

       Systems</EM>, 2001.

  <li><A NAME="terraflow:geoinformatica"

       HREF="http://www.cs.duke.edu/geo*/terraflow/papers/journal_terraflow.pdf">

Flow computation on massive grid terrains</A>.

       Lars Arge, Jeffrey S. Chase, Patrick N. Halpin, Laura Toma,

       Jeffrey S. Vitter, Dean Urban and Rajiv Wickremesinghe.

       To appear in <EM>GeoInformatica, International Journal on

       Advances of Computer Science for Geographic Information

Systems.

</ol>

<p><i>Last changed: $Date: 2006/09/22 14:57:11 $</i>