Download the full procedural methods project here. Read about the turtle graphics and L-systems here. I'll talk about the post-processing in a later post.
An interesting side-effect of this process is that you must have a high-resolution mesh to begin with. Each flat face will be represented using many triangles. This may be desirable for lighting or collision purposes with the final terrain, but I wanted to try generating a mesh with the bare minimum number of triangles needed to represent the overall shape. So what if we instead start with a mesh containing just two triangles, then create new vertices and triangles as required with each successive fault?
Faulting by adding triangles to a mesh
For a low number of faults the additive algorithm produces a terrain with far fewer vertices than the traditional faulting algorithm. For a high number of faults it produces finer detail than could be achieved with a fixed resolution grid, while representing the terrain with the minimal number of vertices possible, at least ideally. In truth the current version of this algorithm ends up producing more triangles than is necessary due to the fact that each triangle is split individually without taking into account adjacent triangles with common edges. This results in more and more, smaller and smaller triangles being added to a section as more faults pass through it. Eventually this artifacts itself as holes in the mesh in areas of cross-section for many faults, as the triangles are now small enough that the vertices are considered the same (floating point rounding errors) and so are removed as duplicates. I'll discuss possible solutions to this problem later on.
In the first version of the algorithm the vertical quads were added to the set of triangles which are split using the Delaunay triangulation. This led to the vertical surfaces also having far more triangles than necessary, but this was a much easier problem to fix. When a horizontal surface is faulted it becomes two arbitrarily-shaped polygons, but when a vertical quad is split it simply becomes two smaller quads. This is why the vertical quads and horizontal triangles are dealt with separately during the faulting process.
The terrain is stored as a collection of triangles and a collection of quads. These triangles and quads are what the faulting algorithm operates on. Only after the faulting process is finished is the vertex buffer for the mesh generated.
In this application a Delaunay triangulation is always being formed from a set of 5 points, 3 of which form a triangle upon whose edges the other 2 points lie. The algorithm for forming a Delaunay triangulation is as follows:
Color banding to produce ‘biomes’
Problems and improvements
This could be fixed using duplication checks when building the vertex and index buffers. Another possible fix would be to change the storage method used by the algorithm and operate on a single set of edges, rather than separate sets of triangles and quads.
Since the cutting plane is formed by connecting two random points on different edges, it is sometimes extremely short, or very closely follows one of the outer edges. These faults don’t tend to add much to the terrain other than additional triangles, so some sort of vetting process for the cutting plane could be implemented to force it to keep picking new points until some desired criteria are met.