26 Jun 2017

Note: the /x/ series of posts on my site are mostly unpolished mini posts. The polished version of this will come later, maybe in a few months.

In my polygon map generator from 2010 I built the mountains based on the coastline, then made rivers flow down from the mountaintops. Two weeks ago I grew rivers up from the coastlines; last week I marked mountains and valleys from the river basin data. My goal this week was to build mountains that matched the generated rivers.


Last week I made a quick & dirty 3d renderer to see what the (bogus) elevation data looked like. It looked ok but the renderer had some major flaws.

The way I’m generating rivers, I assign an elevation to each blue point. To render them, I drew the triangles using the red points. I made the red points the average values of the blue points. But this isn’t the structure I really want. I want the red points to be above the blue points, like this (side view):

By setting red points to be the average of the blue points, I was missing the peaks and valleys.

And by only drawing the red points I was losing even more detail:

And if it wasn’t bad enough, the normals for each of these triangles was almost always facing the same direction (up), which meant that the lighting didn’t help illuminate the terrain much at all, except for large features.

And to top it off, I was using per-vertex normals, which average out the per-face normals, reducing detail even further.

I hadn’t really been thinking about the rendering properly last week. I thought “hey, there’s not enough detail … let me increase the number of triangles!” I pushed the number of triangles up from 12.5k to 1.25M to get some detail. Although some of the terrain looked cool, it was at the same time too bland and smooth. With 1M pixels and 1.25M triangles I was wasting my triangles. I should be able to get a lot more detail with far fewer triangles.

Time to think this through…

What I need to do is draw triangles with both the red and blue points. And that means I need to subdivide these big triangles into smaller ones (top view):

How should I divide them? Instead of focusing on how to divide the black-edged triangles, I focused on the quadrilateral formed by the crossing of the black and white edges:

There are two ways to divide this space into triangles. Either I can fold the quad down on the black edge (keep in mind the blue points are lower than the red points):

Or I can fold the quad up on the the white edge:

Some of you may have run into this problem before when trying to decide how to draw quads. Which way should I fold? For this problem, I actually want both! I want to use the black edge when it’s a mountain ridge and the white edge when it’s a river valley. Either way, I need to generate two triangles for each full edge in the original dual mesh, which means one triangle per half edge. If I later add support for cliffs, I will need to generate four triangles for any cliffs that have waterfalls flowing over them.

TODO: render in differnet ways, for the same terrain. This would mean I need to implement multiple mesh to triangle functions. 1. Use vertex normals from library, and render only black triangles; 2. Use face normals, black triangles; 3. Use subdivided faces; 4. Use normal interpolation; 5. Use normal interpolation with valleys vs hills vs mountains. (4 and 5 should be later on the page)


Ok, now that I can actually see the generated terrain, I can start exploring different elevation generation functions. I need to figure out:

  1. how to assign the elevations to blue points given the river drainage system
  2. how to ensure elevations on both sides of a mountain range are consistent
  3. how to assign elevations to red points given the blue points
TODO: separate the generation of the noise bias from the calculation of the river and elevations so that I can reuse the same noise function multiple times TODO: https://hal.inria.fr/hal-01262376/file/2016_cordonnier.pdf