I produced a nice template for a isometric pixel character last night.  It was nice and refreshing to make some pixel art again after having been programming solidly for so long.

A few days ago the “More OpenGL Game Programming” book was posted through my letter box.  This book is awesome, and I have so far loved reading it.  At some point there was a description of the “Fault Line” algorithm for terrain generation, which really managed to grab my attention, as I have been particularly interested in procedural generation recently.  However, I realized that I have read about this method before on the great Hugo Elias website, as part of an article which can be found here.  At first I dismissed the algorithm when described by Hugo since he presents it in the context of spherical landscapes, and in this case the algorythm seemed computationally horrible. This book applied presented the algorithm in 2D space at which point I kicked myself for not realizing that it can also be applied in 2D space.

The fault line algorithm is generally employed in the first stages of height map construction during terrain generation.  The algorithm is extremely simple and a mode complete explanation can be found here.  The basic idea, is to generate two points that form a line that lies across the texture with a random position and orientation.  Each pixel of the texture that lies on the positive side of this line can be incremented a tiny amount.  After hundreds of iterations nice cloudy fractal noise is produces, that in theory should be free from any pattern or statistical bias.  This of course is only true if care is taken while constructing various elements of the algorithm.

Looking at the example images and source provided by the book however I realized that the terrain generation was sub optimal because statistically the fault line start and end points are biased towards the corners of the texture map.  I fixed this using a method I described in a previous post, by discarding fault lines that lie outside of a circle encompassing the texture space.  The results are pretty great actually, and what you see below is the output from four consecutive runs of my generator program.  These noisy maps will serve as a great base for farther manipulation, resulting in a terrain generator.

I spent my morning programming a small ambient occlusion generator for height maps and the quality of the output is surprisingly nice.  In the picture below, 2048 random rays are cast from the center of each pixel out towards the hemisphere.  Each pixel represents the ratio between rays that hit other locations of the height maps and those rays that are clear of all other terrain.

Several methods were used to improve the quality.  Again at all stages, I use sub pixel accuracy, using bi-cubic interpolation in all calculations.  Random rays are generated that maintain a strong random distribution over the entire hemisphere.  This is accomplished by setting a rays x and y components to a random value, between -1.0f and 1.0f.  The z component is set to a random value between 0.0f and 1.0f, to ensure it rises out of the terrain.  The statistical trick here is to discard the ray if it has a magnitude > 1.0f, and try to generate another random ray.  Once a ray is found with a magnitude of < 1.0f it can be normalized and then used.  This method was described in “Texturing and Modeling: A procedural Aproach”.

I have spent most of today and yesterday trying to simulate a basic form of erosion due to the action of water washing away at the surface of a height map.  To generate convincing, earth like procedural terrains, I really believe this is a phenomenon that needs to be modeled.  I devised and implemented two approaches to model this, the first involving something similar to pressure maps or heat maps, however it was too unstable to be really useful.  The second method is much more simple at its core however unfortunately not as fast as my first method.

I store an array that holds 32768 (2048*16) particles, each initially placed at random across the surface of the height map.  Each particle has a location, a velocity, and also a mass parameter.  Each particle gains an acceleration that guides it down the height map.  This is achieved by sampling the gradient underneath each particle in a process exactly the same method as that which is used to generate normal maps from height maps.  Figure 1 shows the height map and Figure 2 shows the corresponding normal map that can been calculated from it.  I did in fact take things one stage farther and allow the position of each particle to have a sub pixel accuracy so that the gradient can be calculated at sub pixel accuracy too using bicubic interpolation.  As particles run down the height maps, it is inevitable that their motion will cease at some point as they come to rest.  I detect this when the magnitude of their velocity is close to zero, at which point they are given a random location, with a bias towards high areas of the height map providing a weak model of evaporation.  When a critical speed is reached for any particle then it will lift material from its position on the height map and add it to the particles mass parameter.  When a particle lifts material, the height map is written to, again using bicubic interpolation, to reflect the loss of this material.  Figure 3 shows a visualisation of the particle system during simulation.  Particles shown in red are currently moving fast enough to lift material from the height maps surface.  When a particle comes to rest and has been flagged to be moved by the evaporation process, all of the mass that it has accumulated is first deposited at its current resting point.  Since the gradients are recalculated for each particle during its update, these two processes that change the height map will influence particles that later may follow a similar path.  Thus commonly used paths will be eroded, reducing their height gradually.  In figure 4, we can see the process after around 20 seconds of simulation.  Notice that deep eroded paths can be found moving from areas of high elevation to areas of low elevation.  Also notice that initially there was a large black split running through the middle of the map, representing some canyon, or a large river.  The process of erosion has deposited material in this space, raising its height significantly.

The simulation time could be considered significant if this technique was to be embedded in a games level generator, but the results seem initially very encouraging.  There are many parameters to play with however, each giving different results, so much more experimentation in this regard needs to be done.  Another technique that needs to be explored to compliment this work is a method to detect which regions of the map should be submerged by water.  After all, this is not much use unless we can also have nicely animated water in the correct places.

Figure 1.

The height map used in the demonstration.

Figure 2.

A normal map generated from the above height map, demonstrating a method of determining the gradient by taking the vector cross product of tangent and binormal vectors.

Figure 3.

Visualization of the particles in action.  Particles shown in red are moving fast enough to lift material from the terrain.

Figure 4.

The resulting simulation of crude erosion of the height map after around 20 seconds in the simulator.  Notice the deposit of material that begins to fill up the lowest points in the map.

Figure 5.

Here the erosion model is applied to a smooth gradient to observe the effect of many random particles all moving together to create successively larger channels the deeper down the surface they run.

I spent most of yesterday developing and implementing a really unique voxel renderer.  I have so far only heard of ray casting methods for drawing voxel landscapes, but the approach I came up with is radically different.  The performance is really great however, and is comparable to any ray casting approach.  I don’t know whether to keep the algorythm under wraps just now, since I think it could have a lot of potential.

Currently the rendering is only isometric, but it should be possible to modify it for perspective rendering too if I sit down with the math.  There is no pre computation for this method so the height map and terrain texture can all be updated on the fly, opening up lots of amazing possibilities.  Zooming, rotation, and tilting are all free performance wise since they are fundamental parts of the algorithm.  The terrain resolution is also independent from the performance of the algorithm surprisingly, so there is no penalty for a very detailed landscape.

Over the next few days I really want to push this technique and see if I can squeeze more from it.  I have plans to implement ambient occlusion and dynamic hemispheric lighting.  Also dynamic light mapping could be integrated.  The possibilities are really inspiring.

Here is an extreme close up where you can see the individual voxels.

Since I am experimenting with my new ray casting code, I decided it might be worth trying to implement a 2D version of the instant radiosity algorithm.  The results are very pretty.

The strategy is really simple.  From the light source, you cast out rays in several directions, and store the intersection points.  In the above capture, there was 64 of these points, but its more reasonable to have less, since there is an big performance penalty the more you have.  The next step is to iterate over all the tiles on the map performing a ray cast from the center of the tile, to each of these initial sample points that we captured.  The percentage of hits we gather determines the brightness of the tile, the more unblocked ray casts then the brighter the tile.  Simple as that.

An unfortunate aspect of the vanilla algorithm is that it produces many noticeable blocky artifact which can be quite off putting to the overall effect.  A solution I propose to this problem is to add jitter into the algorithm.  For each of the ray casts from a tile to one of the irradiance samples we add noise to the position of the irradiance sample.  This noise actually improves the overall accuracy of the algorithm which is a strange phenomenon.  It also looks much more pleasing to the eye in my opinion.