Two of the most important concepts in terrain flow modeling are flow routing and flow accumulation. Intuitively, flow routing is the assignment of flow directions to every point in a terrain to globally model how water flows through it. Flow accumulation then quantifies how much water flows through each point of the terrain if poured uniformly onto it. Flow routing and flow accumulation are two basic layers used for computing other attributes such as drainage networks and watersheds.

Issues

Realistically modeling water flow by assigning flow directions to each cell or vertex/triangle in a grid or TIN DEM is a complex task.

In the most common grid DEM flow modeling methods, a flow direction is either assigned to each grid cell towards the steepest downslope neighbor or directions are assigned to all downslope neighbors; these methods are called single flow directions (SFD or D8) and multiple flow directions (MFD), respectively. In another popular method D∞, a direction of steepest decent is computed in each grid cell based on a local interpolation function, and then flow directions are assigned towards the two closest neighbors.

TIN DEM flow modeling is less developed than grid DEM flow modeling. However, one major class of flow modeling methods assign directions to triangles, similar to the way directions are assigned to grid cells in grid DEM flow modeling. In another class of methods, directions are assigned to vertices. Some combinations of the two models have also been proposed.

One major issue in both grid and TIN DEM flow modeling is flow routing on flat areas, that is, assignment of flow direction to cells, vertices or triangles without any strict downslope neighbors. Flat areas can either be naturally present in a DEM, or (as commonly is the case) could have been introduced by denoising or flooding. Intuitively, flow directions should be assigned to flat areas such that water can flow towards points on the boundary of the flat area with one or more downslope neighbors (spill points). Often directions are assigned to ensure that there is a path (along flow directions) from each cell/triangle/vertex to the nearest spill point. Note that flat areas without any spill-points (sinks) are dead-ends for flow.

Once flow routing has been performed (direction assigned) on a grid DEM, flow accumulation of a cell c is often estimated as the number of cells with flow paths to c. Note that if SFD is used, this corresponds to the amount of water flowing through each cell, assuming that each cell initially has one unit of water. On a TIN DEM a similar definition is used but where each vertex (or triangle) is initially assigned water proportional to the area of the vertices surrounding the vertex (or to the size of the triangle).

Our Approach

In the TerraFlow project we developed and implemented I/O-efficient algorithms for flow modeling on massive grid DEMs. The TerraFlow software supports both SFD and MFD flow routing on DEMs without sinks; if the terrain contains sinks, TerraFlow first removes these sinks using flooding. On flat areas directions are assigned to generate paths to the nearest spill point. Flow accumulation is computed by assigning each cell one unit of water and continuously distributing water in each cell according to flow directions (proportional to height difference); when all water has been drained off the terrain, the flow accumulation of a cell is then the total amount of water that has flown through it. TerraFlow has been included in the open-source GIS system GRASS and an extension with the TerraFlow functionality has been written for the commercial GIS system ArcGIS in version 8.3.

In our current work, we have reimplemented TerraFlow to increase efficiency (both I/O and CPU computation) and stability. We have also increased the functionality in a number of ways. For example, we have added support for TIN DEMs (where flow directions are assigned to vertices), just as we have added support for flow modeling on terrains with sinks (i.e., the DEM is not flooded before routing and accumulation). We have also implemented full support for the SFD and MFD routing methods and added support for further user-specified routing methods; we are currently implementing D∞ using this feature. Support for user-specified flat area routing has also been added and we are in the processes of implementing models other than the simple shortest spill-point path method. Similarly, in flow accumulation we have added support for user-defined initial flow and flow distribution; this e.g. allows for relatively simple implementation of accumulation related features such as LS-factor (erosion computation), which we are currently implementing.

Our Results

To test our new software, we ran our code on lidar data from the Neuse river basin in North Carolina. Starting with over 400 million lidar points, we constructed grids and TINs using new methods described on this site. The data cover an area of roughly 5700 mi² (14,800 km²). Results are summarized in the table to the right. In the flow routing phase, we processed over 8,500 nodes per second in each of the three test cases. In the flow accumulation phase, the node throughput was over 62,500 nodes per second.

Links

TerraFlow

Publications

P. K. Agarwal, L. Arge, A. Danner, H. Mitasova, T. Mølhave, and K. Yi. From LIDAR to Watershed Hierarchies. (In progress)

L. Arge, J. Chase, L. Toma, J. S. Vitter, R. Wickremesinghe, P. Halpin, and D. Urban. Efficient Flow Computation on Massive Grid Terrain Datasets. GeoInformatica 7(4):283-313, 2003.

References

J. Garbrecht and L.Martz. The assignment of drainage directions over flat surfaces in raster digital elevation models. Journal of Hydrology, 193:204--213, 1997.

JS. enson and J. Domingue. Extracting topographic structure from digital elevation data for geographic information system analysis. Photogrammetric Engineering and Remote Sensing, 54(11):1593--1600, 1988.

J. F. O'Callaghan and D. M. Mark. The extraction of drainage networks from digital elevation data Computer Vision, Graphics and Image Processing, 28, 1984.

P. Soille, J. Vogt, and R. Colombo. Carving and adaptive drainage enforcement of grid digital elevation models. Water Resources Research, 39(12):1366--1375, 2003.

D. Tarboton. A new method for the determination of flow directions and contributing areas in grid digital elevation models. Water Resources Research, 33:309--319, 1997.