Computer Generated Landscapes

Overview

Exploration of techniques to generate and render realistic looking terrain; an application of computational geometry. This is mainly an artistic project but terrain generation and rendering have many applications in game development and simulation.

Demo

Click the image below, or click here to open in a new window. The demo may take several seconds to load and requires a browser that supports WebGL.

Use WASD keys to move and use the mouse to look around.

Data Set

The data set is a height-map, basically a 2D array of floats that represents heights at even sampling across a terrain. This form is easy to work with for terrain generation but must be tessellated (converted to triangles) before it can be rendered. For this demo we were working with ~516k triangles after the heightmap was tessellated. To simplify the demo the data set is generated externally by a Python script and then embedded in the application.

Terrain Generation

There are many approaches to generate terrain. The most basic approach is simply to generate random values for all points in the heightmap; this however ends up not looking very good because there is no pattern to the terrain. Taking a fractal approach [2] is much more interesting; one such approach is the fault algorithm [1] which works by repeatedly dividing a heightmap with random lines and each time raising all points on one side and lowering all points on the other. After many iterations this leads to a heightmap with natural looking patterns that is interesting to explore.

Dynamic Level of Detail

In order to efficiently render large highly detailed data sets we need a way to downsample the data and to use the lower detail versions when we are looking at something that is far away, and the higher detail versions when we are looking at something that is closer. For this demo we implemented a simple dynamic level of detail algorithm to do this for the data set we generated.
First we need a way to create lower-resolution versions of the terrain data. To do this we dynamically tessellate the terrain using a detail level that is assigned based on the distance of the terrain from the camera. This starts at level 0 for full-resolution, and decreases in quality as the level number increases.

The other thing we need is a way to use a lower detail level for terrain that is further away; the approach taken here was to split the terrain up into a grid of "patches" where each patch was an equal sized part of the original heightmap data that could be tessellated independently of the others. Every time the camera moves we check if it is in a different patch; if it is then we check the distance to each patch and update their resolution levels accordingly.

Areas For Improvement

The main issue with this approach is that rendering patches next to each other with differing resolution levels can lead to gaps in the terrain where vertices would have lined up if the levels were the same. There are several ways to fix this; an interesting one is triangle binary trees [3] which is a data structure that would help us dynamically tessellate a patch so that the edges adapted to the neighboring patches; unfortunately we did not have time to implement this approach.

Other inefficiences are how the resolution level changes are handled; for a large number of patches checking every patch would not be very efficient; it would be better to check the nearest neighbors and stop after a certain distance, e.g. if the max level was 5 then any patches more than 5 away from the camera would necessarily be level 5.
Another area that could be improved is the downsampling algorithm when producing lower resolution levels; currently we skip vertices but this can lead to very noticeable "pops" in the terrain as detail levels change because the skipped vertices are local maxima/minima. A better approach for this might be doing some sort of averaging, or perhaps by using curves and tessellating those dynamically as well.

Presentations

• Project Summary (PPTX) (PDF)
• Project Update (PDF)
• Project Final (PDF)

Source Code

The code is available on Bitbucket here. See the README for instructions on how to package the application.

References

1. Lighthouse 3D - Terrain Tutorial. <http://www.lighthouse3d.com/opengl/terrain/index.php?fault>
2. Fractal Landscape. <https://en.wikipedia.org/wiki/Fractal_landscape>
3. Binary Triangle Trees for Terrain Tile Index Buffer Generation. <https://www.gamasutra.com/view/feature/130171/binary_triangle_trees_for_terrain_.php>

---

Up