UNiGiNE Valley Benchmark

Although it's been a quiet few months as I've not been able to devote much time to my voxel worlds, I thought I'd share a link I found interesting.

The guys over at UNiGiNE have created a new benchmark/demo "Valley" showing a very nice real-time terrain:

They've been a little heavy handed with the depth of field for my liking; something I've noticed on many demos trying to show off this feature but that's just my personal taste.  It doesn't really detract from what is still a very impressive demo.

I would like to know where the heightfield data was sourced from - whether it was a DEM set or created procedurally in an offline tool for example - I doubt it's created real-time as that's not really the point here.  They do a good job of making it look nice though.

Here's their website link: UNiGiNE Valley Benchmark

Procedural Castle

I've been taking a break from trying to synthesise natural terrain features and instead been working on a system to create buildings in a procedural manner.  I've looked a little at this before in my previous Osiris project (see Building Placement Revisited) but didn't take it much further than producing some roughly textured boxes:

Simple skyscraper buildings produced procedurally

I thought it was about time I pushed it a bit further to produce structures to make my new voxel worlds a bit more interesting.  I've taken the basic system I was developing before but reworked and extended it to make it more powerful and capable of producing more varied output:

Voxel castle produced by the new procedural building system

It's not exactly going to win any modelling awards but I'm hoping the mechanism behind it's production will give me the power to create all manner of man made structures and buildings reasonably simply.

The system is inspired primarily by the work of Müller, Wonka, Haegler, Ulmer and Van Gool in their paper Procedural Modeling of Buildings where they present a grammar based system for the specification of buildings (See Miguel Cepero's Procedural World blog for another interpretation of this work), this essentially enables a set of rules to be written which when interpreted by a parser results in geometry being created representing the building for rendering.

Language Choice

I wanted the system to be easy to play with so it was essential that the runtime be able to reload and parse these rules dynamically without having to recompile or even re-run the program so coding them statically into the C++ source was out, but rather than write my own parser I decided to make use of the Lua language and integrated that into my project instead.  This gives me an out of the box solution for runtime loading and parsing and provides a far more powerful language feature set than I could hope to achieve in any home grown system.

Lua also has the advantage of being a model of simplicity to integrate with C++, syntactically similar enough to be quick to learn and well supported with documentation and tutorials on the internet.  There are even various editing environments with support such as Notepad++ and Sublime providing out of the box syntax highlighting (there is also a Visual Studio extension to provide Lua syntax highlighting although at this time it appears to not support the 2012 edition I am using).

The Fundamentals

In essence, I am representing each type of building or structure with a Lua file, when a building of that type needs to be generated the Lua file is loaded and an entry point function called "Axiom" executed.  From here on the Lua environment has control making it's entire feature set available to richly describe the shape and construction of the building. The output of this process is a Signed Distance Field (SDF, i.e. a 3D array of signed distance values) that can then be plugged in to the sparse voxel octree builder to produce a data structure the GPU ray caster can process to render images such as the castle above.

I expose a number of C++ functions to the Lua environment (22 at this time) that the script can call to perform useful intermediate processing operations and to output the final primitives that the SDF is constructed from.

The fundamental concept the script operates on at any one time is a 3D bounding box called a Scope, when the Axiom function of the script is called there are globals called xPos, yPos, zPos and xSize, ySize, zSize pre-defined with the 3D position and size of the current scope respectively which can be used to either emit an output shape or create additional scopes for further processing.  Each additional scope created is given a name which is the name of the Lua function to call to produce it's contents.  When that function is called it will in turn have the position and size globals pre-set to represent it's own position and size thus allowing each function to act on it's own area of 3D space without having to worry about where it came from or what transforms it's parents have been through.

Learning by Example

If that sounds confusing, a simple example might help:

function Axiom()
    Scope(0, 4, 0, xSize,ySize-4,zSize, "Castle");
    Scope(0,0,0, xSize, 4, zSize, "Ground");
end

here the main Axiom function is taking the original scope it's been given (which encompasses the entire 3D bounds of the building to start with) and creating two further scopes for later processing.  The first is called "Castle" and is at position (0, 4, 0) with the same size as the global scope in the X and Z axis but four metres shorter than the global scope in the Y axis.

The second scope it creates is called "Ground" and is at the origin of the current global scope (the origin is in the minimum corner of the box in (x,y,z) space) with the global scope's size in X and Z but is four metres tall in Y (the height).  Essentially this is dividing the total space of the building into two horizontal slices, a 4m tall one at the base which will become the ground and a second sitting on top of that into which the building proper will be generated.  The global scope is automatically destroyed when the function exits as it's not needed any more.

As it stands this script won't actually output anything, we need to add more code so it knows what to do with those two new scopes:

function Castle()
    Box(5, 0, 5, xSize-10, ySize, zSize-10);
end

function Ground()
    Box();
end

note here how the name of the scope is simply the name of the Lua function to call - a great advantage of a dynamic language like Lua that would be impossible in C++.  In this simple example I've made the Castle function output a box 10m smaller than but centred within the scope in the X and Z axes and the full height of the scope in Y while the Ground function simple creates a box that fills the scope.

Note the handy shortcut for the ground's box - having a shape fill the current scope is a common requirement so overloadings of many functions such as Box are provided that assume the origin and scope size as defaults.

Running this simple script now produces this:

not perhaps the most convincing of castles but hopefully you can see how the script produces what you see here.  It's important to remember though that it's not geometry that's being generated - there are no vertices and triangles being created by that Box function; instead for each point in the 256x256x256 SDF grid I'm using in the viewer it's calculating how far that point is from the surface of the boxes and storing that.

The brick and stone texturing is a result of the default appearance set when scripts are run, appearances are essentially a pair of textures one of which is used for flat surfaces and another for vertical ones - surface in between receive a blend of the two textures depending on their slope.  It is possible to specify different appearances when creating shapes but I'll let these examples stick to the default for now.

A Slightly More Complex Example

I don't want to turn this post into a reference manual for the construction system as that would be quite verbose and probably not terribly interesting so I'll jump straight forward to a more advanced example, making a tower with a crenelated top:

and here is the code that produced it:

function Axiom()
    Scope(xSize/4, 4, zSize/4, xSize/2,ySize-4,zSize/2, "SquareTower");
    Scope(0,0,0, xSize, 4, zSize, "Ground");
end

-- Produces a square tower with a crenelated top
function SquareTower()
    Box(xSize, ySize-3, zSize); -- Body of square tower
    SquareBoundary(merlonDepth, ySize-3, 3, xSize, zSize, "WallRampart");
end

-- Produces four long thin scopes forming a square boundary edge
function SquareBoundary(thickness, yPos, height, xSize, zSize, scopeName)
    Size(thickness, height, zSize);
    Scope(0, yPos, 0, scopeName);

    RotateToY(180);
    Scope(xSize, yPos, zSize, scopeName);

    Size(thickness, height, xSize);
    RotateToY(90);
    Scope(xSize, yPos, 0, scopeName);

    RotateToY(270);
    Scope(0, yPos, zSize, scopeName);

    RotateToY(0);
end

-- Produces a low wall topped by crenelations
function WallRampart()
    Box(xSize, ySize*0.5, zSize);

    Size(xSize, ySize*0.5, zSize+crenelWidth);
    MoveTo(0, ySize*0.5, 0);
    Appearance("StoneWall");
    SubDivZ({ "rep", merlonWidth, "Merlon" });
end

-- Produces a single merlon
function Merlon()
    Box(xSize, ySize, merlonWidth-crenelWidth);
end

hopefully it's length doesn't scare you off, assuming you're still with me you can see that the basic structure is the same; functions are often creating new scopes at a given position relative to their parents and based on the parent scope's size.  Points that I think are worth noticing include:

• The SquareBoundary() function shows how other Lua functions can be called just like normal to do additional work and allow code re-use without having to create intermediate scopes
• The RotateToY() function demonstrates rotating scopes, all translation and rotations are inherited automatically to child scopes
• The Appearance() function is used here to change the appearance for subsequent shapes, in this case changing to an appearance that doesn't have the rock floor texture so we don't get rock on the flat top surfaces of the merlons.
• The SubDivZ() function illustrates a more powerful way of subdividing space, in this case creating as many instances of the Merlon scope with a given width as will fit along the Z axis of the current scope.

Constructive Solid Geometry

At the moment the system is only capable of generating two basic geometric solids from it's scopes, either the boxes you've already seen or cylinders along the X, Y or Z axes.  These basic shapes can be combined however to create far more interesting shapes using a technique called Constructive Solid Geometry (CSG) where the results are combined using one of a range of boolean operators.

There are three primary operators available:

Union is the default which merges the shapes together

function Axiom()
 Box(0, 0, zSize/4, xSize/2, ySize/2, zSize/2);
 CylinderZ(xSize/4, 0, 0, xSize/2, ySize, zSize);
end

Subtract removes the second shape from the first

function Axiom()
 Box(0, 0, zSize/4, xSize/2, ySize/2, zSize/2);
 CylinderZ(xSize/4, 0, 0, xSize/2, ySize, zSize, CSG_Subtract);
end

Intersect produces the portion of solid that is common to both

function Axiom()
 Box(0, 0, zSize/4, xSize/2, ySize/2, zSize/2);
 CylinderZ(xSize/4, 0, 0, xSize/2, ySize, zSize, CSG_Intersect);
end

CSG has been around for a long time and I've used it before on CPU based ray tracer projects where it's relatively straightforward to implement operating on the intersecting spans of rays, but it's a whole lot more complicated when operating on geometry as the finite numerical precision of floating point numbers often leads to problematic fragments and slivers of geometry, problems with non-sealed hulls and issues with coincident surfaces.

Dealing with SDFs however eliminates these problems as the sample space is regular with no problems of open or closed surfaces.  (See Iñigo Quilez's page on Modeling with Distance Functions if you are interested in this)

In addition to the regular boolean operators, working with SDFs provides some other interesting options:

Adding signed distances together to create a blend

function Axiom()
 Box(0, 0, zSize/4, xSize/2, ySize/2, zSize/2);
 CylinderZ(xSize/4, 0, 0, xSize/2, ySize, zSize, CSG_Add);
end

here a basic addition is being applied resulting in a blend between the box and the cylinder shapes, likewise subtraction and other arithmetic operations can be used.

Advanced Parameters

The flexibility of Lua also makes it simple to add additional optional parameters to function calls.  By allowing a table to be passed at scope and shape creation time context specific values can be given:

CylinderY(0, ySize-10, 0, xSize, 10, zSize, { topRadius=0; appearance="RoofTilesBrown" });

here the cylinder has been given a zero top radius factor to turn it into a cone and the appearance for the shape changed to a brown roof tile effect producing the top of the castle's turret:

Turret roof formed by a cylinder with zero top radius

Space Modifiers

Finally it's also perfectly possible to apply arbitrary functions to areas of the SDF in much the same way as the geometric primitives do, but instead of generating values we can modify the values already present to produce interesting or bizarre effects that would be difficult to achieve with geometry directly (or at least without massively tessellated geometry)

NoiseShape(-4, -4, -4, xSize+8, ySize+8, zSize+8, CSG_Add, { noiseScale=0.5, noiseAmplitude=1.5 } );

here a Noise modifier has been applied to an area of the scope to warp the values already generated for the keep:

Regular keep without the modifier applied

Same keep with the Noise() modifier applied just for fun

although this is something of a contrived example (unless you were planning on making a castle out of jelly) it shows the power of the effect, other effects such as twists, warps and even softening blurs are also possible.

Variations on a Theme


So far everything presented here has been undeniably procedural being based on rules and parameters but it has also been entirely deterministic.  If I feed one of these Lua scripts into the system five times I will get exactly the same building out each and every time which is going to make it somewhat tedious to produce the wide variety of buildings and structures with which I hope to populate my voxel worlds.

The real power of procedural systems though of course is their ability to produce endless variations of something by supplying different input parameters or seeds.  For my building system there are only two primary inputs that dictate how the final architecturee looks: the first is the bounding box for the building comprised of the size of the plot onto which the building must fit and the height it's allowed to reach.  These would be defined by the higher level town or city planning systems driven by factors such as population density, building type and the distance from the centre of the conurbation, the bounds are simply passed to the Axiom function as the size of the root scope.  By writing the Lua script properly it can be made to work with a wide variety of overall building sizes, functions such as SubDiv() are really useful here to enable repetition along unknown length regions without undue scaling or stretching.

The second factor that has a more significant impact on the form of the building is the seed value that is used to initialise the random number generator.  This is calculated from the position of the building on the planet so the same building in the same spot will always look the same but the same script file used to generate a building at a different location may look completely different.  The Rand() function is used in the script to make decisions that can change the architecture: deciding whether to put a square tower, a round turret or nothing at all on a corner of the castle for example or whether there is a gateway on a given wall.  Rand() can also be used to vary the size of scopes and shapes, so for example once the choice of tower or turret is made it's width and height can be further randomised within sensible limits leading to a wide variety of final apperances.


Wrap Up

Hopefully this has been an interesting glimpse into what I hope will be a powerful system for synthetic formations, I've certainly learnt a lot about Lua and it's integration with C++ along the way which has been rewarding in itself, but feeling like the system I've created is open and flexible enough to produce interesting, realistic(ish) or even fantastical structures is satisfying.

There is even scope here to release a stand alone version of the viewer tool these screenshots are from so you too could experiment with creating architecture from Lua - as long as people can accept it's limitations of course

Anyone interested?

Impossible Worlds

Although I was pretty happy with the DEM terrain mapping described in my last post, I was aware that it didn't exactly show off the incredible flexibility that moving to voxels provides over the more traditional height-field grid techniques I employed in some of my previous projects.  You pay a massive cost in complexity, computational cost and rendering performance moving to voxels so it seemed a bit poor to not show off their strengths a bit more.

To this end, and just to have a bit of fun, I've been playing about with the underlying distance field functions my planets are based upon.  All the images in the previous post used a simple spherical distance function to give a basically realistic planet shape, but there's absolutely no reason (discounting physics) not to use any arbitrary function to produce the underlying shape upon which the DEM mapping works.

Here are a few of the toy-worlds I came up with:

Why not have a cube world...
  (maybe the birthplace of the Borg?)

Or a torus?

A union of three cylinders with a bit of -ve blending at the intersection

...and my timely tribute to Halo 4...

Obviously the terrain system copes with varying degrees of success when applied to these unconventional shapes but considering that it was designed for spheres it's surprisingly decent.  A proper parametric mapping would work better for the shapes that have one but these experiments are just toys after all.

Blobby world based on a low frequency noise function

Although the plan is for planets in my universe to be in general constrained by the laws of physics and nothing like these, this generality of form opens the door for having blasted husks of planets with huge chunks missing, cracked open meteorite ravaged planetoids and maybe just the odd eccentric alien world...

The Birth of Voxel Planets

After getting some basic data sets up and rendering with my GPU based sparse voxel octree ray-caster I wanted to get stuck in to actually using it to render planets.  Now as I've discussed before planets are pretty big and dealing with them can throw up many numerical precision issues for algorithms.  Having dealt with these in past projects however it seemed daft to reinvent the wheel so I spent some time porting the general solar system simulation code from Osiris into Voxelus.  This was made more complicated and time consuming as I started a whole new C++ framework for Voxelus rather than use what was becoming a very old and messy utility library - it was time well spent though as I believe it's healthy to have a clean slate now and again.

Very first voxel planet (256^3 grid)

With that done though I could bring across the procedural nebula backdrop generator which with a couple of colour tweaks just for fun at least gave me a nice cubemap backdrop.  Above is my very first voxel planet, rendered using a 256^3 data set as source for the SVO with tri-planar texture mapping to give it some interest.  The distance field from which this is generated is really just "distance from surface of sphere" so it's neither particularly interesting nor showing the power of voxels, but it's a start.

Modelled as an earth side planet, the 256^3 data makes each voxel almost 50 Km on a side!

Now perfect spheres can only be so interesting, so adding some relief detail was my next job.  Although completely arbitrary shapes are possible with voxels I wanted to get started with some fairly traditional planet forms so the initial focus was on producing something reasonably realistic.  I've used a variety of fractal functions in the past to simulate terrain, ridged multi-fractals being a popular choice but such terrains tend to suffer from a large degree of homogeneity - they tend to have a large degree of self-similarity especially across large areas even when combining numerous frequencies.

In the spirit of trying new things, rather than tread that worn path again I wanted to try something different for Voxelus.  Rather than generate heightfields from fractals, I wanted to see if I could generate something suitable using real-world Digital Elevation Model (DEM) data.  A little searching turned up the Shuttle Radar Topography Mission (SRTM) data which is available in a variety of resolutions.  Downloading this and writing a little command line tool to load and cut out interesting sections of it enabled me to produce a library of DEM tiles that I could use.

Two examples of DEM patches my tool cut out of the massive SRTM 500m data set

I used a simple height histogram to choose areas where there was a lot of variety in elevation in an effort to make the final result more interesting - although the SRTM 500m data set is hundreds of MB in size, a surprising amount of the Earth's surface is in fact pretty damn flat!

Armed with my library of DEM tiles I needed a way to map them onto my planet.  Mapping 2D squares onto a sphere is however a classically impossible task (ask any cartographer) so rather than being able to make some perfect mapping I instead needed to quilt the surface with overlapping tiles, using as few as possible while ensuring that there were no gaps in between. I also wanted to be able to quilt at various resolutions so I could combine several "octaves" of DEM data in a traditional fractal-esque fashion.

To do this, I based my mapping on an Icosahedron, a regular polyhedron made up of 20 triangles.

Icosahedron (image from Wikipedia)

The key attraction of the icosahedron is that each side is an equilateral triangle producing an even distribution of surface area, and that each side can be recursively subdivided into four smaller equilateral triangles to produce higher and higher detail meshes with the same characteristic.  By normalising the position of the vertices introduced by these subdivisions an increasingly high quality approximation to a sphere is achieved.

To map my DEM tiles onto the sphere I treat each triangle of the icosahedron as representing one tile.  The centre of the tile lies on the centroid of the triangle and extends outwards to cover the triangle completely.  Each tile also has a random rotation around the centroid so to ensure that there are no gaps between the tiles from adjacent faces, the tile has to be twice the radius of the triangles circumscribed circle in size.  There will be considerable overlap around the edges between adjacent tiles but that's all the better to avoid seams.

First "octave" of DEm tiles at primary icosahedron vertices, there are 12 tiles here

One further level of subdivision produces 42 smaller tiles

Subdividing again produces 162 even smaller tiles

These three images are to visualise how the tiles are distributed on the sphere. These examples actually have the tiles at the vertices rather than the triangle centroids but I later switched to the centroids as I thought it gave a better result.  Centroidal tiles produce 20, 80 and 320 tiles at each level respectively.  The tiles here are artificially smaller than final size simply to improve the visualisation.

Expanding the tiles to their correct sizes and repositioning them at the triangle centroids rather than the vertices produces a more accurate result:

Here the individual tiles have been tinted to aid identification and the edges shaded green based upon the weight of their influence at that point.  As you can see the weight of each tile fades off towards it's edges to avoid hard seams and there is no space between them regardless of their orientation to ensure a complete mapping of the sphere.  I've added a simple directional light so the relief from the DEM data can be seen.

Normals from just the basic level #0 data

Here the voxel normals can be seen, note that this is using just the 20 tiles from the level #0 quilting but with a  mountain height of about 500 Km to make detail obvious from such a distance - by comparison Mt. Everest on Earth is just 8.8 Km tall.

Finally here is the same level #0 data with some basic elevation/slope based texturing applied.  Even with just one level of DEM data I am quite pleased with the appearance of the terrain, particularly with the variety of landscape forms in evidence which encourages me that this technique might just be viable.

The coarse 256^3 nature of the data can be quite clearly seen in this image even from this distance so I think starting work on the dynamic resolution subdivision system for closer views might be next on the list of things to tackle.