Pedagogical Aid for Procedural Map and Terrain Generation

Developed by:

Problem Statement:

For a long time, one of the more interesting problem in Computer Graphics has been that of generating realistic looking terrain. Procedural terrain generation is widely used in Video games, film making and simulations. By using realistic terrain models, naturally occurring phenomena such as tectonic plate shifts, erosion and earthquakes can be simulated and studied. The objective behind creating this tool was to implement a simple way to generate terrain using the Delaunay triangulation. The idea behind using Delaunay triangulation of random points as opposed to a grid is to create terrain that simulates natural erosion. The tool allows you to change the variables and generates randomized terrain based on them. During and after the terrain creation process users can move around the world using the controls given on the tool page.

Click here for the tool

Check out the code at :
TOOL
DCEL

References:

Algorithm:

For generating the mesh, I have used the algorithm from Razafindrazaka et. al with some changes. The algorithm starts by generating a set of random points which will be used as vertices of the mesh. The algorithm starts by creating a triangle face that will include every generated vertex. This is the first face of the triangulation. When we add a point to a face, we split the face into three triangles where each triangle has the new point as one vertex and two points from the original triangle as the other vertices. The new faces are inserted as children of the old parent face. After the creation of the three new faces, we must ensure that the edges of a face are valid by ensuring that any fourth vertex does not lie in or on the circumcircle of a face. If an edge is not valid then the edge is flipped with the two other vertices of the two triangles and the new faces are recursively validated. Once the validation is finished, we will have the Delaunay triangulated mesh for the points. One by one all the points are added to create the entire mesh. Once the mesh has been obtained, random points are selected for valleys and mountains whose number is provided by the user. Each point is given a random height between the maximum height and it's half. These heights and points are used to create a two dimensional Gaussian function. Each point is assigned the value of the Gaussian function of the mountain or hill closest to it. This gives the terrain steep slopes which is generally expected from any mountain. Once the height map is applied to all the vertices, the actual filled faces of the mesh can be generated. Each vertex is assigned a color based on it's height and then each triangle face interpolates between the colors of it's three vertices. Once the terrain is created the user can turn the mesh on or off.

Data Structure:

For the algorithm to work efficiently, it is essential that each face, edge and vertex be aware of every edge ,vertex and face surrounding it. For this purpose we use a Data structure known as Doubly Connected Edge List. My implementation of this data structure is a bit more complicated than the traditional. The data structure keeps track of each vertex, face and half edge(which is a one directional edge from one vertex to other) using maps. Each vertex is also aware of all the edges leaving from it. Each half edge is aware of the face that it belongs to, it's twin which contributes to the adjacent face, it's next edge, it's previous edge in the face and it's vertices. Each face is aware of just one edge which contributes to it, using which it can track all the other vertices and edges. Using this data structure, adding a vertex can be done in O(log n) time where n is the number of faces. Flipping an edge can be done is O(1) time.

Pseudocode:

Here is the pseudocode for adding a vertex to the triangulation:

Method: addVertex(vertex):

1. face = dcel.root;
2. while(face.isOld):
3. foreach child of face:
4. if child contains vertex:
5. face = child;
6. break;
7. Create 6 new halfedges from new vertex to each vertex of face.
8. Create 3 new faces from the three old and one new vertex.
9. Assign each old and new halfedge the correct halfedges and its new face.
10. Add the new faces,halfedges and vertices to the maps.
11. Mark the old face as old and set it's children to the new faces.
12. Verify the old edges to ensure that the faces surrounding the new faces are valid.

Here is the pseudocode for flipping the edges after determining if the faces are invalid or not

Method:flipEdges(oldFace,invalidFacePoint):

1. Get the shared edge between invalid face and oldFace.
2. Create the objects for two new halfedges and faces.
3. Assign the old edges to the new faces and the new edges.
4. Assign the new faces to the old edges.
4. Mark the old faces as old and set its children to the new faces.
5. Recursively verify if the faces surrounding the old edges are valid.