Given a terrain, how to draw the stream flow path?

Question

Assuming I have a terrain, as usual the terrain has ridges, creeks and all the characteristics that you can find on a real life map. Water flows from the top of the mountain into lower area, the path that water flows is termed stream flow path.

The terrain is given in terms of triangular irregular network ( TIN), which each point $p(x,y)$ has a $z$ value. How to use this information to construct the stream flow path? What is the physics behind this?

Edit: Just wonder is there any papers on this?

Answer 1

1. Let us first ignore the technical issues concerning a triangulated irregular network and just discuss the idealized smooth problem where there is given a smooth height profile $z=\phi(x,y)$ of the terrain. One can locally introduce a stream function $\psi=\psi(x,y)$ such that the curves $$\psi(x,y)~=~{\rm constant}$$ represent the streamlines. (However, there are global obstructions; see item (4) below.) The gradients of $\psi$ and $\phi$ must be perpendicular, $$ \nabla\psi \cdot \nabla\phi~=~ \frac{\partial \psi}{\partial x}\frac{\partial \phi}{\partial x}+\frac{\partial \psi}{\partial y}\frac{\partial \phi}{\partial y} ~=~0. \tag 1 \label{eq:1}$$

   This is a 1st-order linear PDE in $\psi$ in two variables $(x,y)$. Its solution $\psi$ formally solves the smooth problem locally.

2. If, moreover, the horizontal fluid velocity field $(u,v)$ is divergence-free $$ \frac{\partial u}{\partial x}+ \frac{\partial v}{\partial y} ~=~0,$$
   one can demand that $$ u = \frac{\partial \psi}{\partial y}, \qquad v = -\frac{\partial \psi}{\partial x}. $$

3. If furthermore $(u,v)$ is also curl-free (=vortex-free), then the stream function $\psi$ becomes a harmonic function. See also flownets.

4. Global obstructions. The streamfunction $\psi$ is ill-defined in sources and sinks, i.e. in local extrema.

5. Now let us comment on the triangulated surface, with vertices, edges and faces. If one (instead of introducing a streamfunction $\psi$) just solves the problem one-streamline-at-the-time, one could end up with streamlines that un-physically cross each other because of numerical errors. Solving in terms of the streamfunction $\psi$ protects against such unphysical solutions locally.

6. Let $\phi$ and $\psi$ be defined on the vertices. The gradients $\nabla\psi$ and $\nabla\phi$ naturally live on the faces, i.e. the dual graph, so that the equation $\eqref{eq:1}$ can be made discrete.

Answer 2

I'll try to give some starting ideas.

A triangulated surface will not be smooth but it may be useful to understand how the problem would work on a smooth surface. From each point water could be assumed to flow in the steepest direction going down. This ignores momentum of the water which could affect the path and even provide water falls. If you want to model that your job is going to be harder.

If the height $z(x,y)$ is a function of two grid coordinates $x$ and $y$ and is a differentiable function then the direction of flow is given by the negative vector derivative $-grad(z)$ You can trace a curve over the surface starting from any point (a spring) by following the direction until you either flow of the edge of the grid or arrive at a local minimum. If you arrive at a minimum the water is going to form a lake there and fill up until it finds a point to exit. Such a point will always be a saddle point, i.e. a point where $grad(z)$ is zero but it is neither a minimum or a maximum. This is the kind of point that forms a mountain pass and rivers from lakes always exit at such points.

You have to come up with some strategy for deciding where to put the sources of your streams. This might be random or you might pick special points such as saddle points. If these are sometimes exit points of lakes they could make could locations for springs too. In general from a saddle point there are two opposite directions in which the stream can flow which can be found using the second derivatives. You could also start streams from summits choosing the directions in which the terrain curves away steepest for the initial direction.

In the actual problem the surface is not smooth, it is a triangulated grid. From each point a stream will flow away in the direction of steepest decent. Within a given triangle this will be a straight line. Its direction is easy to work out. Find the normal to the triangle by taking the cross product of two edge vectors. Then project the normal onto the $(x,y)$ plane. You will have to deal with the cases where the land is flat as a special case.

When the water reaches an edge of a triangle it will either flow onto the adjacent triangle and change direction or it will flow along the edge. You have to check the gradient of each possibility and take the steepest. It may also arrive at a point from where it can flow away on a triangle or an edge. Again you need to calculate each possibility and take the steepest.

To find starting points you can either take random points at high altitudes or look for saddle points and summits. To do this look at each edge joining on a vertex and determine whether they slope up or down from the point. Trace round the point and count how many times the slope changes sign. If it changes twice you are on a slope. If it never changes you are on a summit or minimum point. if it changes more than four times you are on a saddle point. More than four times is possible since the surface is not smooth. The summits and saddle points are good places to put springs with water flowing away in the steepest direction(s). Trace the path of the streams from there until you reach a minimum.

On a terrain that is like a realistic landscape you are likely to find that streams converge. Mostly they will converge along edges of triangles but they could also converge at a vertex if there is more than one direction of local steepest accent from the point. One strategy would be to start a spring at every vertex or triangle centre and count how many (weighted by the area of the triangle?) converge into each stream to find the biggest rivers.

Hope this is enough to help you work out the details and write the necessary software.