Vexal

Procedural Terrain Generation

Procedutral Terrain Generation - Description

This project is still in progress

Overview

This project is a component of my Direct3D11 Game Engine. The goal of this project is to eventually be able to procedurally generate a planet from the scale of a first-person shooter viewpoint up to the scale of a ship in space in real-time for use in a game.

Since this project is still in development, this page will post updates when new features are completed or broken.



Current Development

Terrain Screenshot

Procedural Terrain Procedural Terrain
Procedural Terrain Procedural Terrain



Multithreaded Terrain Cell Generation - August 2013

Each terrain cell can now be generated on a separate thread. As many threads as needed can be used, greatly speeding up terrain generation, and allowing the simulation to run normally while the terrain is generated. Parameters exist to control how many cells can be generated simultaneously, and to control the time between each cell being created.


Simplex Noise Terrain - July 2013

Procedural Terrain

The generation function now uses Simplex Noise instead of Perlin Noise.

Shown in the picture to the left is an example world definition file used to create the parameters for the Simplex Noise, and the parameters used for the first video above. Inside each { } is the definition for a single simplex noise function. The function runs for each x,z input coordinate, and outputs a 'y' height value. Functions nested inside functions imply that whether the nested function is applied at a particular coordinate is dependent on the output of the parent function at that coordinate. This nesting is how biomes are created. For more information on how dependencies and biome nesting works, see the next section of this page, Selective Application of Noise Function Application.

Functions inside [ ] are function systems. They signify that multiple simplex noise functions are applied at each input coordinate, with the output value being all functions combined. The amplitude and frequency of these function systems are multiplied or divided for each successive octave.

The parameter names mean:

  • Frequency: The frequency of the simplex noise function. Higher values produce bumpier terrain. The input coordinates are multiplied by the frequency before computing the function output.
  • Ampltitude: The peak value of the simplex noise output. The output height of the simplex noise function is multiplied by the amplitude.
  • Contribute Value: Whether this function contributes to the output height value of the system -- non-contributing functions are used for dependencies.
  • Octave Count: For function systems, the octave count is the number of successive simplex noise functions applied on top of each other at a particular input coordinate.
  • Octave Start: The offset for the octave count.
  • Persistence: In a function system, for each octave, the frequency of the function increases by a power of two, whereas the amplitude of the function is equal to pow(persistence, octaveIndex)
  • Frequency Multiplier: Multiplied to the frequency of each function in a function system.
  • Scale: The amplitude of a function system for each function is multiplied by the scale, and the frequency is divided by it.
  • Falloff Power: The output of the simplex noise at a particular coordinate is divided by some scalar to this power.
  • Dependency Type: For nested functions, dependency type determines how the child function is compared to the output of the parent function.
  • Dependency Fail Action: For nested functions, dependency fail action determines how to compute values in the failure range of the parent function.
  • Dependency Value: Dependency value 1 is the cutoff failure output for the child function to fail against the parent function's output. For interpolated functions, dependency value 2 is the interval outside the passing comparison of the parent function output for which the output of the child function goes to zero.


Selective Noise Function Application (biomes; varying landscapes) - June 2013

The screen shots of my terrain generation previously all demonstrated mountainous landscapes. If the goal is a huge mountain range, then this is perfect. However, if the goal is to make a useful game world, then having only mountain ranges can be problematic.

The first intuitive solution to this issue which comes to mind is to make the frequency of the mountains lower, so that the high mountain peaks are more spread out. This solves the issue of there being no flat land, but it leaves another problem: In order for the mountains to look good, additional high frequency, low amplitude height functions must be added on top of the low frequency, high amplitude mountain functions (to give the mountain a craggy, bumpy look, as opposed to a rolling, smooth look). This is fine for the mountains, but since the noise functions are applied uniformly across the entire map, then all the areas in between the mountain peaks will also become needlessly bumpy. It is not enough to simply lower the frequency of the tall mountain peaks.

The next solution is to selectively apply the high frequency height functions. One could check the height value generated by the low frequency height function at a particular coordinate, and only if the height value is above a certain threshold, then the height value from the high frequency function will be applied. This allows the areas in between mountain peaks to remain flat, and the high mountain peaks to remain craggy.

Other conditions can descriminate which functions to apply in which areas. For example, one could have a very low frequency height function which only returns 1, 2, or 3 at any coordinate. Coordinates where the function returns 1 could on top apply a set of noise functions producing a low frequency rolling hill; coordinates returning 2 could apply noise functions producing flat plains, etc.

Unfortunately, selective application of noise functions is not as straightforward as one wishes it be. As demonstrated by the following images:

The above images show that if a noise function is only applied to a specific area, there is a discontinuity at the coordinates at the edge of where the noise function is applied.

The solution to this issue is to interpolate the resulting height of the function at the coordinates where it is no longer applied so that the output of the function smoothly goes to zero.

selective noise function application with interpolation selective noise function application with interpolation

Terrain with selectively applied noise functions interpolated at edges.


In the image on the left, the terrain is flat except for two areas where several noise functions are applied to create the appearance of a crater or rock formation. The noise functions are set to apply at coordinates whose value of a separate random function is past a threshold. The amplitudes of the noise functions are interpolated towards zero at a specified rate for coordinates not meeting the criteria for applying the functions.

The image on the right shows bumpy noise functions that are only applied to areas where the height of the mountain noise function exceeds a specified threshold. The threshold for application is near the top of the peak, and the bumpiness of the mountains gradually decreases towards the bottom.

Other Details

The system I have set up is intended to be as generalized as possible. A function can be set to be dependent on the value of any number of other functions at that coordinate. The dependency conditions can be set as well as the dependency fail actions.

An example of using this system could be to have a low frequency function intended to determine what land type is at a coordinate (snow, plains, mountains, grassland, etc). A set of functions can be created intended to only be used for specific land types.


Real-Time Procedural Texture Generation - February 2013

Texture generation based on slope and height is now supported. Each cell has a texture map designating the percentage of each texture at each coordinate. This map is generated based on the normal at each coordinate, as well as based on any arbitrary function at each coordinate. The generation is done incrementally each frame. Depending on the complexity of calculating the normal at a given coordinate, and the specified number of distinct mapping coordinates, the generation can take more or less time. It is designed to adaptively change the gneration speed to keep framerate fixed. Generation finishes within a couple milliseconds.

Bump mapping and normal mappping on all textures is now supported.


Real-Time Infinite Terrain Generation - November 2012

Since algorithms like Perlin Noise give a consistent output no matter the circumstances a particular input is given, it is safe to generate terrain incrementally and in real-time. In this update, terrain cells are generated as objects go near the cells. If an object enters a cell, and no terrain currently has been generated at that cell, then a cell is generated for it. Generation is nearly instant and fast enough for real-time use.

Procedural Generation
Only the cells I have walked over have generated terrain. The rest of the world is black.

Level of Detail Optimization - October 2012

Upon generating a mesh from a height map, a single vertex buffer is generated and sent to the video card. This vertex buffer holds all original vertices of the mesh. Instead of generating a single index buffer for the mesh, multiple index buffers are generated, skipping varying amounts of vertices.

LOD
Example of a piece of terrain rendered from four index buffers of varying resolution.

In the first iteration of this feature, a high-resolution index buffer "followed" the movement of the camera. Outside the square of vertices in the high-resolution buffer were eight buffers with a factor of two fewer indices following the camera, and so on, creating a fractal. I decided to forgo this method completely.

Instead, the index buffer for a particular model being rendered is chosen based on the distance from the center of the bounding box surrounding the model to the position of the camera. This can be seen in the image below.

LOD with perlin noise
Wireframe demonstrating that terrain cells further from the camera are rendered with fewer polygons.


Perlin Noise Terrain - October 2012

Perlin Noise is an algorithm to use a combination of functions to generate a random value for a given input. A certain input will always result in the same output no matter how much times the function is called. In this context, the final result is the height at a particular x,z, and the input is the x and z.

Procedural perlin noise

Test of terrain generated using a simple noise function with four different frequency / amplitude combinations.

The simplest way to visualize how the Perlin Noise algorithm works is to use your imagination to imagine a sine function. Then, with your imagination, imagine that sine function has a high ampltitude but a low frequency. Think about what life would be like if for each point in the heightmap, the height is the value of the sine function at that point. It would be a very smooth world with high, rolling hills.

Now, think about a heightmap generated from a sine function with a very small amplitude but a very high frequency. This world will be very uniform but very bumpy.

If you add the heightmap from the smooth world with high hills to the heightmap of the bumpy world with no hills, you'll get a heightmap with high, bumpy hills.

Perlin Noise works by adding the resulting values from any number of custom noise functions with any number of frequency and amplitude combinations to get a desired randomized set of values. The noise functions take any number of integers as input, and return a real value between -1 and 1 as output. The input values are multiplied by the frequency and the output is multiplied by the amplitude.

A smoothing kernel is applied to the result of the noise function, and then an interpolation function is applied.

Perlin noise low frequency Perlin noise high frequency Perlin noise with both frequency combined

Simple demonstration of combining a smooth function with high peaks with a bumpy function with low peaks to produce a bumpy function with high peaks. The first picture shows the function output with a frequency of .0004 and an amplitude of 3000. The middle picture shows the function output with a frequency of .3 and an amplitude of 5. The third picture shows the result of adding the first two heightmaps together. Ignore the black areas -- only a portion of the terrain was generated for this example.

A useful feature of Perlin Noise is that no matter what, the same input will yield the same output. This makes it possible to generate different parts of the terrain at different times without consistency being an issue. It also allows for terrain generation without knowing where the bounds of the terrain will be.



Bitmap Heightmap Generation - October 2012

This allows a .bmp file to be specified to generate a heightmap. The .bmp file is treated as a list of height values, so lighter areas are higher.

Height map

Heightmap generated from the .bmp file -- lighter areas are higher.


Height map Testing

The first component of this project was to create a heightmap. These shots are of some experimentation I did. The heightmap is a 2D array of height values which can be taken by the renderer and turned into a polygon mesh. The heightmap can also be used by the simulation for gameplay.