When thinking about generating terrain we must first think about how we are going to store our data to represent it. This is a very crucial aspect as depending on the method you use to represent this data will have a direct effect on what kind of terrain you can generate and how large your data structure will be. In a ideal world we want to be able to represent any kind of terrain using minimal memory. The technique we have been using so far is two dimensional height maps. This is a very small way of representing terrain data in which we use a two dimensional array of elements that store height values. This results with a spacial requirement of n^2 bytes, n being the size of our array. This technique has its limitations in what type of terrain you can represent. Being only able to represent height and location information this restricts us to only being able to represent one layer of a surface and cannot represent natural phenomena such as horizontal caves. On the other hand we can represent our terrain in voxel form. This could be represented in a tree dimensional array which allows us to represent a third dimension of data. Where this representation has its draw backs is the size the data structure will be. Unlike our height maps voxels will be the size n^3 bytes, turning terrain that would be megabytes in height maps into gigabytes in voxel data. Therefore we must compromise and combine the two techniques with the data structure proposed in the paper Layered Data Representation for Visual Simulation of Terrain Erosion by B. Benes and R. Forsback. This paper proposes a method of a two dimensional array of elements which contain information about the underlying layers.

E.g.

typedef struct{

PropertiesT data[MAX_LEVEL];

float height;

} ElmT; //one element of the array

PropertiesT is a structure that contains information about the material possibly such as height of the material layer, material type or even density. Unlike in the voxel representation this clumps together layers of the same material providing information about the block which saves large amounts of data. The overall size of the data structure is now more like n^2 * sizeof(ElmT) * bytes which means as long as sizeof(ElmT) is smaller than n our which it is highly likely to be out data structure will be much smaller than the voxel based approach.

This data structure also gives us the freedom to easily implement erosion techniques. The technique we have used is known as thermal erosion and is sited from the same paper. The thermal erosion algorithm is an attempt to represent long term thermal weathering. A material is dissolve because of changes in temperature which cause there terrain to break up and fall down. The eroded part will fall down in the direction of greatest gradient. To achieve this we use the following equation,

The result of which will give the amount of material to move to neighbouring location i. Delta S is equivalent to 1/2 the largest height difference between the element we wish to erode and its eight neighbours, this must be calculated to stop oscillations in the algorithm. ‘hi’ represents the height of the neighbour we wish to move our material to which is divided by the sum of all our elements neighbouring heights.

Anyway enough of the boring stuff here is pretty video of it all implemented!

Reblogged this on Coding, Unix & Other Hackeresque Things.

LikeLike