L3DT documentation
Large 3D terrain generator

The design/inflate algorithm

Introduction

The design/inflate algorithm begins with a low-resolution design map in which the basic shape of the final heightfield is laid out, including land altitudes, the position of volcanos, etcetera1). This map is called a design map because it allows the user to design the heightfield prior to calculation (see demonstration, below).

To generate the heightfield, the design map is 'inflated' using a diamond-square fractal algorithm. Heightfield overlays are applied at each stage of the inflation process, including peak roughening, erosion, cliffs & terraces, and various 'special' terrain types like mountain peaks, plateaux, volcanos, etc. Smooth effects such as peak overlays are done earlier, at low map resolution. Highly detailed overlays such as terraces, volcanos, etc are done later, at high map resolution. Most of the overlay operations, therefore, work on the heightfield when the map area is only 1/4th, 1/16th, 1/64th (etc) of the final map size. Diamond-square subdivision is significantly faster per-pixel than most of the overlay routines, so this scheme greatly reduces the total calculation time. The speed bonus for this approach was a bit over 10x between L3DT v1.0 (no inflation) and v1.5 (inflation).

Algorithm outline

The heightfield is generated from the design map in the following way:

  1. The heightfield is created at the same resolution as the design map and is seeded with the altitude values from that map.
  2. The heightfield is 'inflated' by a factor of 8× using a diamond-square routine to fill-in values by fractal interpolation.
  3. Smoothed peaks are overlaid on the heightfield to make rolling hills. The size / number of peaks is determined by the 'Peak' values in the design map.
  4. The heightfield is inflated 4×.
  5. Low-res 'special' overlays are applied (inc. mountain peaks, volcanos).
  6. The heightfield is inflated 2× (for the last time).
  7. High-res 'special' overlays are applied (inc. plateaux).
  8. Terracing is applied.
  9. File overlays are applied.

At several stages of this procedure, the heightfield is eroded by the thermal, fluvial and/or channelling erosion routines. The number, type and sequence of erosion passes is still a matter of some volatility within L3DT and thus they were omitted from the above list.

The inflation/overlay algorithm was first implemented in mid-2003 (in L3DT v1.5), but remains a continually mutating and evolving beast.

Demonstration

Below I present a rather artificial looking design map that I painted to illustrate the operation of the design/inflate algorithm. I have divided this map into 4 quadrants. In the centre of each quadrant I have made small mounds and placed volcanos atop them. The top left quadrant has no roughening, the top right has only peak-roughening (green), the bottom left has only fractal roughening (red), and the bottom right has both fractal and peak roughening (red + green = yellow). In the centre of the map I have painted some cliffs (blue). The little Vo 0 tags indicate the position of type-zero volcanos (smallish ones).

A bizarre design map.

The heightfield was then generated by the inflation/overlay algorithm. You can see from the light map below the effect of the peak and fractal roughening, as well as the cliffs in the middle.

The light map.

What does it look like in 3D?

techshot2.jpg
Screenshot from L3DT Viewer, looking from the west towards the east.
Note terracing at the intersection of the quadrants.

Of course, you can use this flexibility to design maps much more interesting than this. Island chains, sea cliffs, mountain ranges (etc, etc) are all a few mouse clicks away thanks to the easy-to-use design interface. Please refer to the making a fjord tutorial for a more elaborate demonstration.

1) The design map is itself generated by a pseudo-fractal algorithm, the details of which are unimportant.
 
l3dt/algorithms/hf/design_inflate.txt · Last modified: 2013/08/21 17:20 (external edit)
 
Except where otherwise noted, content on this wiki is licensed under the following license:CC Attribution-Share Alike 3.0 Unported
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki