Tracing a terrain
Published on 7 March 2009
This is a basic terrain rendering filter for Pixel Bender based on the Quasi-Analytic Error-Bound (QAEB, or "kweeb") ray tracing algorithm.
QAEB tracing is a raymarching algorithm for rendering realistic looking terrains using procedural fractal functions first introduced by Ken Musgrave. After reading the chapter about it in the excellent book, "Texturing & Modeling: A Procedural Approach", I thought it might make an interesting challenge for an interactive Pixel Bender filter.
The process is fairly unsubtle; a ray vector for each pixel is fired into the scene and its offset, y, above a 2D height field, f(x, z), is calculated. The ray is repeatedly stepped, or marched, forward until it intersects the terrain. At this point the colour for the pixel is determined based on its calculated height and angle between the surface normal-vector and sun position. A secondary ray can be fired off from the intersection point towards the sun and if it intersects the terrain again we know that the original surface point must be in shadow.
A couple of optimisations can be used to speed up the rendering. Firstly the step interval can be increased proportionally with distance as the geometric details get smaller in screen space the deeper into the scene. The second optimisation requires the scene to be rendered from the bottom up (near to far). It uses the calculated scene depth of the pixel below the one we want to calculate as the starting point for its ray as we know that as we move up the image we go deeper into the scene. However, Pixel Bender calculates many pixels in parallel on the GPU and so you can't use the result of one pixel calculation as the starting point for another, which unfortunately means we can't take advantage of this second optimisation.
This filter uses a composition of sinusoidal functions at different frequencies to generate the height map. It's by no means perfect but at a low altitude gives a reasonable cartoon-like landscape where the repeating structure isn't obvious. I created a different version that used Perlin noise for the height field, which generated a much more realistic terrain but would cripple Pixel Bender causing a few hard reboots! I'm porting this version to Processing and will post about that soon.
Other features such as the water level are set by clipping the height field at a lower limit and building like structures can be generated using a combination of modulo functions. There is also an option to overlay contour lines on the terrain.
For more technical details on terrain rendering and other excellent computer graphics goodies see Inigo Quilez's site.
Last updated: 7 March 2009