Credit to my partner in crime Toby Gilbert who collaborated with me on this project
A link to the paper: Over the Hills and Far Away
Category: Collaborative Research Project
Terrain Generation Collaborative Research Project – Update 2: Thermal Erosion & Data Structures
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!
Terrain Generation Collaborative Research Project – Introduction & First update
Welcome to the first update featuring my collaborative research project for my third year of university. The project is made up of a two man team, myself and Toby Gilbert. Our goal to research into new techniques of procedurally generating terrain on the macro and meso levels and maintaining relatively real time rendering of the geometry created. The macro side of generation being the large scale geometry such as mountains, hills and caverns etc.. For this we want to create as physically accurate terrain as possible to enhance realism. The meso being the smaller detail such as trees, boulders and grass, also a very demanding area to draw large volumes of shrubbery while maintaining performance. To increase the progress of our research we have split the two areas of generation between ourselves, Toby being in charge of the meso side of the generation and I shall be looking at the macro.
Initial Research
Terrain generation, a field that has been vastly researched in today’s computer graphics as it can be used in anything from computer games to movies. Therefore having a large amount of research that we can build from. Very basic techniques include simply using height maps, a previously generated texture in which every pixel value represents the height of the surface at the location of the pixel. So height of surface at (x,y) = f(x,y), function f returning the colour value of pixel (x,y) in a texture. This makes for very easy procedural generation by using random noise functions such as Perlin noise to generate the initial texture to be sampled. This method is very quick to implement and complexity can be added by developing more advanced methods to generate your texture. You will find a very detailed exploration of this technique in Realtime Procedural Terrain Generation by Jacob Olsen which uses a combination voronoi diagrams and noise generated by mid-point displacement to create fractal terrain. It also explores simulating erosion techniques such as thermal and hydraulic to improve the physical accuracy of the terrain. The limitations of this method being the terrain will never be able to generate features such as caves or arches in the surface. To achieve this we must look into generating volumetric data which is explored in Arches: a Framework for Modeling Complex Terrains by A. Peytavie ,E. Galin ,J. Grosjean and S. Merillou. In this paper they generate 3-dimensional data set consisting of different materials such a bedrock and sand. They will then simulate how these materials interact with each other and settle under gravity. They finally generate the volumetric data using a technique known as marching cubes. This is an algorithm in which you sample a three dimensional field of voxels and determine what to draw based on how these voxels intersect with the function. For example in the image bellow if one point of our voxel lies inside the shape and the other 7 lie outside then our surface must lie in between and therefore we draw a triangle between these point.
Finally we look into the meso side of generation. The challenges of this is that we need a lot of geometry to create a high amount of detail which in turn increases the compute power we will need to render our terrain in real time. Now you can achieve this by instancing geometry which means storing one set of geometry in memory and just drawing it many times. Alternatively in the paper Real-time Realistic Rendering and Lighting of Forests by Eric Bruneton, Fabrice Neyret solves this by rendering these objects as selection of textures different perspectives of an object and blending between them as you move around for a smooth transition between textures. This mean we can draw a large amount of objects very cheaply as textures are extremely optimised on the GPU.
Current Progress
The first step in this project was to implement the generation of the generation of the terrain through marching cubes. To achieve this I have created a modified version of the source code written by Paul Bourke here such that we can generate terrain from height maps. Our first generation program simply uses Perlin noise to generate a height map.
My next step was to make our terrain look a little more natural by rendering the terrain in a slightly more creative manor. For which I have used the technique in A rule-base approach to 3D terrain generation via texture splatting by Jonathan Farraris and Christos Gatzidis. This implementation shades the geometry based on the heights and the normals of its points. For example lower points are mud and grass shaded with brown and green and as the height increases it becomes rocks and snow shaded with grey and white. To further greater this we use the normals to identify sheers cliffs and shade them as rock instead of grass or snow. We can do this by calculating the angle through inverting the y component of the normal and multiplying it by 90. Now we just set a user defined thresh hold of faces above a certain again to shade as cliffs. In our program I have implemented to version of this, one with just block colours and one that uses pre created textures of our different types of terrain.
Declan Russell 