# Carve river beds into existing 3d procedural generated terrain

I'd like to know if exists an algorithm to apply to an existing vertex structure which models it by adding rivers beds like cuts through the slope of a mountain for instance.

This approach should:

• not work on heightmaps, since my terrain is not generated with heightmaps
• modify the surface with randomness
• according to the heights (river sources should be higher and the flow should descend)
• be as realistic as possible (like not too many circular paths)

I have no needs for speedy algorithms. would be enought to have a separated algorithm to modify the surface so that I am not forced to do all the work during the creation of the terrain.

I tagged this question with c# because this project is written in c# using xna4.0 and in the case that someone knows any algorithms in different languages, c# is preferred (ye, this is optimism)

By the way, I'm looking forward to see if someone knows anything that could fit these needs

• I read that question, @byte56 but it either speaks about 2d techniques or assumes to create rivers and lakes during the world generation process. And sorry, I forgot to say that I'm working on 3d procedural generated terrain – Leggy7 Feb 7 '14 at 18:58
• So, why droplet principle is not working for you? Place a "droplet" at random vertex, then move it along edges towards nearest lower vertex, smoothing and lowering vertices around traversed path. Repeat million times. If terrain is more complex than heightfield, then you need to take into account droplets falling from height and use actual geometry carving instead of simply moving vertices down. – Shadows In Rain Feb 8 '14 at 22:10
• I think the most realistic solution would be if you would simulate rain and erosion. Erosion will naturally converge to rivers. To verify your results. The average of riverLength/riverLengthBeeline is π – Arne Feb 9 '14 at 15:10
• I think the question is too broad to answer. 1. We know what your terrain isn't (height-map) but not what it is. 2. We do not know exactly what you want the result to be but we have some clue as to what you don't want it to be (e.g. with too many circular paths). I think it would be best if you include pictures demonstrating the input and output you wish to achieve. If it is not absolutely clear what you wish to do than any answers will be very high level and imho uninformative. – wolfdawn Feb 28 '14 at 9:09
• Why do you not want to do this during the creation of the terrain? More to the point, why do you believe that this isn't fundamentally part of the creation of your terrain? – Steven Stadnicki Feb 28 '14 at 21:08

Your question is quite broad and underspecified, so in this answer I'll focus on finding river flows.

Within the field of computational geometry there is quite a bit of research on the topic of drainage networks on a terrain. An overview can be found in section 3.5 of this article: Digital Elevation Models: overview and selected algorithms.

A useful starting point about drainage networks on triangulated irregular networks (TINs) - which sound like your existing vertex structure - is Yu et al., Drainage queries in TINs: from local to global and back again.

I should note that the methods used in that article only provide you with realistic drainage or waterflow networks. Subsequent effects of erosion of the terrain is not covered.

May I suggest that any reasonable 3d terrain can have a (set of) 2d heightfields draped over it. This was required for my project to form NPC path maps, unfortunately, I have found no references to the procedure - possibly because it amounts to

• identify all top surfaces
• group them into continuous meshes
• store connectivity between them.

For the additional part of erosion by rain, every cliff edge must be mapped to the location where it falls (in a different sheet of the surface).

Then one can run the 2d algorithms on the heightmaps so produced. The art lies in linking them together so sheet borders do not produce artifacts, and adding impact erosion at the base of each temporary waterfall.

As for the perceived requirement to be "during world generation", that is a multi-step process which most games do not want the player to see happening (unless one is doing a SimEarth style), your use of a pre-gen 3d terrain instead of a generated 2.5d heightmap adds only the complication of allowing underfolds.

• but what if my terrain is not generated starting from heightmaps? Sorry I forgot to specify. – Leggy7 Feb 28 '14 at 7:38
• My first point is that any 3d terrain can be approximated by a set of heightfields, regardless of how it was originally generated. And so I explain one way to extract these heightmaps from a real 3d data set. – Canis Artorus Feb 28 '14 at 19:58

Here is an algorithm off the top of my head. It requires a graph structure for the terrain mesh vertices that allows speedy access to the neighbors of a given vertex, i.e. all vertices in the same triangle as a given vertex. You should be able to create such a structure easily from the mesh data itself.

Then, 1) Find an appropriate starting vertex. You could pick this one randomly, but it probably needs to fulfill some restriction, being above water level and/or within a mountain range. Depending on what you know about your terrain, you can make a better guess.

2) Find all neighboring vertices connected to the current one. From the set of neighbors, choose the one with lowest elevation. Save the "steepest descent vector" from the current vertex to this one.

3) Apply a valley modification function to the positions of the nearest neighbors such that the current vertex is the one being shifted downwards most strongly, whereas vertices left and right to the current one are shifted less and those ahead and behind are not affected. Can be done by some vector projections / dot and cross products.

4) Pick the next vertex for the algorithm based on a mix of the steepest descent vector (this will make the valley follow the gradient of the terrain) and the previous descent vector (I'm calling this flow vector now). This introduces a bit of inertia since it means the river will have a tendency to stick to it's flow direction. The amount of mixing will control the curvature of the resulting river.

Now proceed with 2) - 4) again until some stopping criteria is met (having reached the ocean or something similar).

I would recommend considering a technique inspired by seam carving. Look for the least expansive path through the terrain from any side to the opposite side (for instance north to south). The way you'll calculate price in this case is by the y value of the vertices you pass through (their height). Once you have a list of these vertices, lower them slightly deeper by N units. Pick a W that will be the width of your new river in units and now find all vertices that are less than W/2 units away from the path you found. Now using their distance d from the path, lower each of these vertices by:

N * sqrt((W - d) / W)


You can use any foo you like instead of sqrt. You may want to use the original y - W as a base value to calculate the height of the vertices in the river. In that case it would be:

base = y - N; //Done for each vertex on the path.
//Nearby vertices will use the weighted average
// of the two closes vertices on the path.
vertex.y = base + N * (1 - sqrt((W - d) / W));