Random Landscapes
[OpenGL home]


Introduction
  Building random landscapes or random worlds is something that has always appealed me. Since my first steps into programming I've did things like that. First purely in the form of descriptive-text synthetic worlds and then, as my programming skills improved and computers became more powerful, including more and more visual effects.

  One of the last versions was Paysage3D. whose landscapes I used to find good-looking. They look so dull now, compared to what is possible with OpenGL. After all, I had not really improved the algorithm since I first wrote it in Basic on my Commodore 16. I was just able to get smoother landscapes because of the increased speed of the computer, and more colours. It took then a whole night of computation to get a depth 5 (32 x 32) landscape in blue an green. Now, in a few seconds I get depth 8 (256 x 256), with lights, textures and erosion, and I can move throughout it in real time!

  OpenGL really allowed me to break all the barriers I had encountered so far, mainly because it gave me a lot more speed, relieved me from basic 3D-geometry tasks, which left me with more time to devote to higher level topics like erosion and land-cover modelling. Also, the possibility to drape textures on the terrain makes for more realistic appearance.

  You will find three demos on this page. They are all based on my component library ahGLrandomHDS that allows to generate and navigate through fractal random landscapes.
 


 


Landscape with QBasic and old computer


Paysage-3D: random landscape before OpenGL
(coded in Delphi 3)

Algorithm


  I'm not going to explain all the details here. Look at the code for that. But I'm going to explose the principles.

Definitions

  First, a few definitions (they show how I use these concepts. I'm not sure these are the exact definitions):
  • Landscape: A piece of land defined by its topography (height field) and land-cover (type of terrain occuring in each pixel or landel=landscape element). The topography is used to render the 3D-shape, the lighting effects and landel visibility. The landcover is used to render the colour and texture of each landel.
  • Fractal: This is scale self-similarity. That means that, whatever the scale at which you zoom in on the landscape you always see the same kind of structures. This also defines the way the landscape is built: recursion of a same process at finer and finer resolution. Note that the notion of fractionnary dimension is not explicitly used. Those landscapes have a dimension between 2 and 3 because they fill more or less the 3D space. But as we are interested in realistic-looking landscapes, only a small range of them are useful. Note also that this is a random fractal algorithm, meaning that some noise is introduced in the system.

Random fractal algorithm

  This algorithm seems to have several names: mid-point displacement, diamond-square, plasma. I prefer the "mid-point displacement" name as it is the most descriptive.

  It is based on the following process: 

1. Start with a segment where you know the heigth of both extremities.
2. Find the middle point and draw a perpendicular through it.
3. Draw a random point on this perpendicular.
4. Connect this new vertex to the two ends of the first segment.
5. Repeat these steps for each new segment recursively.
  Each recursion double the number of segments. These levels of recursion are commonly called depth. The deeper the depth, the higher the number of vertices and the finer the resolution. There are two parameters to this algorithm: the length of the first perpendicular segment or amplitude and the factor by which this length is multiplied at each recursion level or roughness. With a high roughness, the line will be very zigzagging. With a low roughness, the line become smoother after each recursion. Realistic-looking values are between 0.3 and 0.5.

  This is a 2D algorithm. In 3D, we don't use segments but squares. For each square we compute a a medium point, draw a perpendicular, etc.. Exactly the same. However, there are two possible situations: 1° the new point lies in the middle of  a square: we use the four corners of the square to interpolate its starting height. 2° the new point lies on the middle of an existing segment: we use the points computes in 1° to interpolate its starting height. This draw "squares" and "diamonds" (=oblic squares) on the grid, hence the strange name sometimes given to this algorithm.

Topography modifiers

  With a depth of 6 or above, this algorithm already give pretty realistic landscapes. However, these landscapes are "symmetric" in respect to the vertical axis (they are not symmetric in the mathematical meaning of the word, but you can put them upside down without seeing any difference). Real landscapes are submitted to gravity and therefore are not symmetric. Particles tend to fall from the high grounds and accumulate in the low parts. This can be simulated starting from the fractal landscape to get better results. In my component this can be done in several ways:
  • Sea: Just drawing a sea - i.e. levelling up all altitudes below "sea level" - hides the undesired symmetry.
  • Rain erosion: this simulate the fall of rain on the landscape. Wherever a rain drop falls, it flows down, following the steepest slope. Wherever it passes, it takes up with it some material (lowers the altitude). When it arrives in a pit, it deposits what it has collected along the way. By raining one water drop on each landel and letting it run, you will get canyons, rivers and alluvial plains, depending on how you tweak the parameters (erosion and deposit rates). The best results are obtained with depth larger than 6.
  • Sea erosion: This simulate the effect of the sea eroding the shores of a continent. This flattens the landels into a beach while cutting a cliff behind it. By repeating the process several times with different "sea level", you can sculpt plateau and cliffs.
  • Life erosion: this is not a symmetry-breaking modifier but it helps to smooth the sharp angles the other erosion processes generate.

Land-cover

  Finally, we can the landscape will look more realistic if we drape a texture on it, reproducing topography dependent features of the terrain. For example, steep terrain will rendered with cliff textur, high elevation will be covered with snow, etc.. In my component, this part is mainly left to the creativity of the programmer. For eaver landel he gets its coordinates, its height and the vector perpendicular to the terrain at this location (the normal). The normal allows him to compute slope and aspect of a given landel. The FractalLandscape and FractalArchipelago demos show how this can be used. This is a first and very simple way of use the above informations. I'm confident that other developpers will find smarter ideas to use them to get better results.

Light

  Light are a mean to get more crispy image with a better feel of 3D by emphasising the topography. Two kinds of light effects are implemented in my component: 1° light shade reproduces the fact that colours tend to be brightest where the surface is facing the light source. 2° Shadows reproduce how a hill intercepts light and casts a shadow on the landscape behind it.

GLScene related components


  You should first read the tutorial written by Phil Scadden explaining how using these components. Here are further information:

  The code around TerrainRenderer (TR) and HeightDataSource (HDS) is very clever. It has a lot of generality and may be used
for numerous purposes. perhaps because of this, it makes finding one's way along the object hierarchy a little bit difficult. Here are
a few signposts that, hopefully, will accelerate your learning curve. 

The tTerrainRenderer 

  Think of it as a buffer between the crude elevation data and the rendering. Actually, you don't really need to understand how it
works. In the code, you will find a comment telling this is a "brute-force" rendering algorithm, but it's actually quite incorrect. The
TR does a lot of clever level of details and memory management, and raycast intersection computation. Basically: 
  • It looks where is the camera and what has to be drawn. If it's far, the mesh is simplified according to a ROAM algorithm (I didn't look how it works exactly). If it's close, the mesh is rendered "brute-force", i.e. triangle by triangle. Note that there is no light computation. 
  • As the camera moves, new parts of the landscape come in view and others disappear. The new parts are loaded from the HDS and, if the "pool" is full, the unused parts are freed. 
  • The whole landscape is modelled in a set of tiles. Beware, here: there is a confusion in the terminology. The tiles are the smallest unit managed by the TR. They are visible or not. Usually their size is between 16 and 32 cells. OK, we need some definitions here: 

  • Box 1: Some definitions

      The height data source contains elevation information stored in a square array (size=power of two). These are the cells. They are finest resolution you can get. If you want more precision, you need to interpolate between them with the InterpolatedHeight function. The cells may come from various sources : Bitmaps, HT files, mathematical function, perlin or fractal algorithm. In each case you may have a superior level of orgnisation depending on the size of the file, of the bitmap, of the algorithm particularities. There is no commonly accepted name for this level but I shall call it patch. In your case, a patch would be a bitmap. Note that a patch don't really need to have a size=power of two, althoug it simplifies greatly your task. 

      The cells are displayed in blocks by the TR. These blocks (squares) are the tiles. The tiles' size is a power of two and is smaller than or equal to the patch size.



     
  • The TR manages the tiles. They are visible of not, high or low quality, loaded or missing or "dirty" (the HDS as been modified). A tile can be draped by a texture. This the finest control you have for this. You cannot play with the cells colours, except by predefining your own textures. 
  • The tiles are the communication pipeline between the HDS and the TR. A tile is a tHeightData and they are built in the HDS event handler "OnStartPreparingData". The pool of tiles is stored into the tList HeightDatas. 

The tHeightDataSource 

  This is very versatile object. Its role is to prepare the elevation date, organise them into tiles and transmit them to the TR. If you
are lucky, you don't need to plunge into the code and just need to code an OnStartPreparingData devoted to your needs. But if
you want more versatility, you need to go deeper, and it becomes the jungle! Not that the code is bad or desorganised; actually, if
it wasn't so well written, it would be impossible to find its way through it. But simply, there is a lot of intertwined functions and data
structures. Here is a try to explain what happens: 
  • The TR want to render some part of the terrain. It calls the HDS through a GetData function. 
  • The GetData check if the tile has already been packaged and if yes, it just send it back. 
  • If not, the data are "preloaded". Here there is some play with Hash data I didn't investigate, but it will finally come down to fire an OnStartPreparingData event. 
  • In the event handler you - or the descendant of the tCustomHDS you are using - is going to collect the data, possibly to link them to a texture and to fill the tile data structure (tHeightData). There can be only one texture by tile (but you can use multitexturing). Note that the tHeightData structure is not a simple array. Actually it is an intelligent object able to juggle with three data types (byte, smallint and single), to interpolate heights between cells and to compute normals. As you can see, the OnStartPreparingData is were the job is done. It is the only part where you need to write code, but it is quite touchy. Be careful with this event handle or you are going into troubles (access violations). 
  • Once the tile is fully computed, its state is set to "hdsReady", meaning that the TR can render it. If, for some reason, it is not possible to compute a tile, just set the state to "hdsNone". The TR will draw nothing here. 
  • The tile is stored in the the tList HeightDatas and sent back to the TR. 
  • The HDS keep also a log of what tiles are used and how frequently. When more tiles need to be computed, it will flush out those tiles that have been the less used lately. 
  Wooof! I'm not sure that what I've written here is very clear. It's just beginning to settle down in my mind and there are still some
blind spots here and there. But at least, I hope this will help you in your task. 

Fractal Landscapes


  This demo allows you to generate randomly realistic landscapes by a lot of parameters:
  • Amplitude and roughness of the terrain
  • Erosion by rain (rivers and pools), by sea (cliffs and beaches) and by "biology" (smoothing angles)
  • Sea level and transparency
  • Sun position, affecting shading and casting shadows
  • Land-cover defined by altitude, slope and aspect (e.g., at low altitude flat terrain is beach and steep slopes are brown cliffs, higher you'll find meadows, forests and rock cliffs, and still higher you might find snow)
  • Textures
  • Camera effects: depth of view, focal length
  • Fog
  • Etc.
  Once the landscape has been built, you can explore it in 3D.

FractalLandscape executable
 

Santa-Barbara-like landscape

Switzerland-like landscape
Dune Fighter

  This simple demo shows how such a landscape could be used in a game. You control a character moving across a random dune environment. The warrior and mushrooms are figures well-known to GLScenians.

DuneFighter executable
 

Fractal Archipelago
  The first demo created a local landscape. Although you could fly without encountering boundaries, the landscape was always the same. This demo is different in this aspect: it generates on the fly random islands, thus creating an infinite archipelago where all islands are different. Moreover, you have now dynamics swell and waves.

Fractal Archipelago executable
 

 Random landscape library

  You can download here the source code of all three demos, the ahGLRandomLandscape unit and a very short tutorial program showing how to set up GLScene to make use of these components.

RandomLandscape Source package
 

Links

http://www.vterrain.org/Elevation/artificial.html
http://www.javaworld.com/javaworld/jw-08-1998/jw-08-step.html
Landscaper: Texture maker
AI-Planet: Not really a random landscape but nice stuff!