DIAMOND-SQUARE

Virtual reality has always been a particular fascination of mine. It astounds the mind that we have come so far in our ability to generate virtual worlds that mimic reality so closely, that the line between the two starts to blur.

Previously, I have worked on a somewhat-related topic in the same field: the realistic synthesis of images through ray-tracing. However, in this project we are less concerned about the appearance of the scene and more about the scene itself. More specifically: we are going to generate realistic-looking terrain.

Table of contents

Heightmaps

Before we can generate any terrain, we need to define exactly what it is we consider as terrain, and how we represent it. We view a patch of terrain as a function \(H\) that maps a point \((x, y)\) on the euclidean plane to a value \(z\), representing the height of the terrain at that point:

$$ H: \mathbb{R}^2 \rightarrow \mathbb{R} $$

To simplify things, we regard our terrain patch as discrete and bounded. That is, we define \(H\) to be valued only at integer coordinates:

$$ \{(x, y) \vert x,y \in \{0, 1, 2, \ldots n \} \} $$

..up to some limit \(n\). Basically, we are talking about a grid whose vertices each bear the terrain's height value, \(z\), at their position.

Algorithm description

The generation procedure used is titled the diamond-square algorithm. It generates a square patch of terrain with size \(2^n + 1\). The algorithm begins with an 'empty' patch, where all \(z\)-values are undefined:

The first step is to initialize the corner vertices with some seeding values:

Next comes the diamond-step, where each square defined in the previous step computes its midpoint value by averaging its four corners, plus a random value \(r_{xy}\):

After the diamond-step comes the square-step, where each diamond defined in the previous step computes its midpoint value by averaging its four corners, plus a random value \(r_{xy}\):

We repeat the diamond- and square- steps until all values have been defined:

That's it! Now we have a complete definition of a height map for a patch of terrain. Below is a visualization of such a map as a grayscale texture, and beside it how it looks when converted to a mesh in three dimensions:

One last note: The way in which the random offsets \(r_{xy}\) are chosen for each vertex \((x, y)\) is important. In order to achieve smooth-looking terrain, it is necessary for the variance of the distribution from which they are drawn to be reduced after each iteration of the algorithm. This means that offsets drawn in earlier iterations will determine the global shape of the terrain, while values drawn later will determine its local details.

Source code

You can view the source code and documentation on GitHub. Some more samples of generated heightmaps are available under the demo/img directory of the repository.

See also