Day / night on the planet, part 1

Problem: vertices with normals pointing into sun's direction
are lit even when the sun is on the other side of planet.

If you looked at our Screenshots section you probably noticed something strange about these screenshots - most of them are really dark and have some small areas randomly lit. There is a reason for this kind of behavior and I'm going to reveal it now - our world is actually a true planet! Before we just had a regular flat terrain and our sun was set somewhere in the sky above and it lit the terrain correctly. Once we switched to planet, we ended with one part of it being lit properly, and another being mostly dark. Because of nature of the planet, we just couldn't have all terrain lit anymore. What we needed was a day/night cycle.

Now, a few words about planet - we decided to go that way because we thought it will add a nice realistic touch to how players experience the world - for example, they can actually go around and arrive at the same place from which they departed. There are a lot of other cool things about having a planet, but it also introduces new problems. One of them is how diffuse sunlight works.

First problem was easily solved - our sun was static and didn't really move. It turned out that all the code for moving was already written by Milcho, but Update() function for the planet wasn't called. Once I fixed it we got a day/night cycle with sun circling around the planet (its of course not how it happens in real world, but moving planet around the sun would be much harder and not really worth the effort, so we use usual simplistic model), but one major problem remained - because some vertex normals pointed downwards towards the planet core, they were lit by the sun while it was on the other side of the planet! This is the reason of strangely lit holes on our screenshot page.

After a quick brain storm we found some solution that had a slight chance of success - we needed a "horizon" of some kind. Because we no longer had a flat terrain, we couldn't just hardcode horizon to be, for example along XZ plane. For each vertex on the planet's surface, horizon will be different. This is what we came up with:

Problem: vertex is lit even at night because its normal
points towards the sun

Solution: adding a "fake" horizon that determines
area where the sun is "active" for a given vertex

Our horizon is a plane that goes through vertex position and is perpendicular to vertex up vector. We compute dot product of up vector (U) and vertex to sun vector (VS). If the result of dot product is negative, it means sun is outside of our horizon (night), if its positive or zero - its in the horizon (day).

Pseudo-code in GLSL vertex shader looks like this:


    upVector = normalize(vertexPosition - corePosition)

    vertexToSun = normalize(sunPosition - vertexPosition)

    sunInHorizon = dot(upVector, vertexToSun)

    sunIntensity = 1.0

    sunFade = 0.2      // sunlight will fade when the dot product is less or equal 0.2

    if (sunInHorizon < 0)

    {

        // no diffuse light

    sunIntensity = 0.0 

    }

    else

    {

        // we fade sunlight

        if (sunInHorizon <= sunFade)

        {

          sunIntensity = sunInHorizon / sunFade

        }

    }

    diffuse = sunIntensity * diffuseLight

This way we solved problem of lighting vertices that have normals pointing into sun direction while sun is on wrong side of the planet and achieved a nice day/night transition over the whole planet. Timelapse of this effect can be seen on this video:

Its probably still far from perfect, but works ok for now. In next part of day/night series I'd like to optimize and correct some things presented today and also add day/night effects to our skydome, which right now remains white despite time of day change.

Bottlenecks and smooth noise functions

Over the past few days, we've been trying to improve the current bottlenecks that slow down the engine.

The first bottleneck was simply a graphics one - how many polygons can be drawn on screen. The standard solution is frustum culling. In our case, this was a fairly easy task, since all our visual data is separated into 'visual blocks'. Each one is simply a cube, 12m on each side, which holds all visual data. Frustum culling for that simply meant checking whether each corner is visible, and if none of them are, drawing it was skipped.

Another improvement to graphics was reducing the sheer number of draw calls. As you can imagine, with one visual block being a 12x12x12m cube, in order to get good visual distance between them, we have quite a few of them. One way to decrease the number of draw calls is to simply add only full ones to a list when rebuilding, and draw only that list. The downside is that in order to accurately maintain that list, when the user moves, a rather large number of them have to be rechecked. This is an acceptable trade off, for the most part at least.

But another bottleneck, even worse is the sheer number of data that can be covered. In fact, 21*21*21 = 9261 visual blocks give us a little over 120m view distance on each side of the player - and cover a huge volume of 16 million cubic meters! - which means we need 16 million data samples to construct that volume!!!

This presents a generation bottleneck - the terrain generation function must be fast enough to generate that much data in a reasonable time. Of course one generated the data is stored to disk, and can be read from there.
For generating data, we were able to obtain a decent looking terrain at approx. 16 datablock generations per second. This means a point generation rate of 27,000 data points per second, while when loading datablocks, we were able to load of speeds ranging beteween 100 and 200 datablocks/second  - which is an average of 259,000 datapoints per second.

This leads to the major problem in this fiasco, and that is, the speed at which the density function operates. For our project, we currently use libnoise, and we use something like 7 independent one octave functions, and two 2 octave functions  Four of these (including one of the 2 octave) are combined together in different frequencies and amplitudes to generate terrain, while the other 3 are used for picking biomes and determining oceans and seas and mountain areas.

For those familiar with how Perlin noise works, this means a huge number of lookups and trilinear interpolations. Which makes it slow, slow, slow. ... Unfortunately, the slowness is greatly due to the sheer number of points generated, not only the speed of the noise. A quick switch to an implementation of Simplex Noise (also authored by Ken Perlin), showed no significant improvement in speed. (the measured speed is not only dependent on the generation but on number of other factors). While Simplex noise may be faster in higher dimensions we only use 3d noise anyway, and while straight forward tests of speed may show it faster in lesser dimensions, it is still comprable to Perlin noise when used in a real world application. Of course its speed isn't the only thing that it has improved over Perlin, but for now, it won't help our bottleneck.

The only way to help the generation bottleneck is to redesign the density function used to use less noise modules, and combine them in more ingenius ways.

The good thing is, that while this is a bottleneck as such, it is only applicable when the terrain is first generated. Often times players will move around generated terrain, which, as mentioned, is much faster. There's also the possibilty of pre-generating terrain while nothing else is pending - but this also has the drawback of starting to store excessive data, so it too must be balanced.

In other words, without more major overhaul, the speed of the density function is not likely to show significant improvement by just switching noise generators.

The importance of data and visuals separation

At the start of the project, some four months ago, the idea was only for procedural terrain, without editing. At that point, what we now call 'visual blocks' was the only data structure around.

Visual blocks are simply a collection of cubes with density values on each corner. These cubes naturally share corners, at most 8 cubes per corner. Visual blocks were generated on the fly,

extracting a surface from the density function using an implementation of the Marching Cubes Algorithm (now patent-free). This happened without storing any data to disk, as the terrain was not editable, thus the density function described it perfectly at all times.

As the other guy on the project joined, we decided to go for editable terrain. This meant that we had to store terrain data on the disk, since when edited the density function would no longer be an accurate representation. In the previous post, I mentioned how to store these discretely.

Now, the other problem when storing data is somewhat tricky. Neighboring visual blocks share

densities along the border. These densities can be considered as part of both visual blocks. So the question was, do we store this data as part of both visual blocks, or just one?

Storing it in just one visual block would require loading the whole next one to obtain this data, but even worse, would lead to recursive calls! The newly loaded visual block would require the next one, and so on and so on. There are ways of avoiding this, but not entirely too pretty.

Storing the densities as part of both visual blocks seems wasteful. If we consider that a visual block is in fact cubical, and all its sides border another, this would mean large amounts of densities to be duplicated.

And perhaps, most importantly, storing the data on per-visual block basis, ties the underlying data structure to the basic unit of display. If we wanted larger visual blocks (say for LoD), we couldn't do that.

The solution was to completely detach the underlying data from the visuals. In something called the Terrain Data Manager (which to some extent is described in the project wiki here), we manage both writing / reading form disk and the data currently in memory. The TDM stores datablocks - which are completely unrelated and independent from visual blocks. Datablocks are non-overlapping but adjacent, and are the basic atomic unit of data that can get loaded or generated.

The picture on the right illustrates how visual blocks can overlap several parts of datablocks.

Since the datablock was the smallest unit of data we would load, it made sense for it's size to be small, but due to costly time of reading/writing to disk, this size could not be too small. The current implementation holds datablock size at 20 voxels along each axis (or in other words, 20 m^3, since voxels are stored 1/m), while the visual blocks size is still being experimented upon. The separation of these two ideas gives large amounts of freedom

A visual block can be of any size and range, while the underlying data management remains untouched. The visual blocks don't even have to be of size that's multiple - or anywhere close to that of the datablock. This allows tweaking of both visual blocks size and datablock size independently, to optimize the time required for building and generating. It also eliminates the problem of storing any duplicates or causing recursive calls.

Further, the datablocks are the only data that actually gets generated - and stored. Visual blocks no longer concern themselves with where data comes from - the disk or is generated - they only request data from the TDM. The TDM hides all internals, and only returns certain things, like density at a specific point, or voxel-type (as in dirt, sand, etc) at a point.

The introduction of the TDM was one of the major steps in making the editable terrain behave correctly, and it allowed us a lot of freedoms in experimenting with visuals.

Density Function & Saving discrete densities

What is a density function? Well, basically it's a function that returns a value at any given x,y,z coordinate (that's a 3d, there's 2d versions as well, but we use 3d).
The values of that density function are then interpreted as either inside or outside terrain, the simples assumption being that if the value is negative, it's outside terrain, and if it's positive, it's inside terrain.
The simplest density function, that generates a flat ground is this:

DensityFunction(x,y,z)
{
  return -y;
}

Anywhere above y = 0, this function will return negative, and below that positive. This information can be used by something like the Marching Cube Algorithm to extract a surface. 
Now, the problem with this is that it returns an incredibly huge range of densities. Obviously we don't need them all, since whether a point is at -100 or at -10000, it is clearly outside of terrain.

Section of the voxel grid used to generate terrain.
Yellow cubes are sand voxels, transparent ones are air.

What we wanted is a way to store this density to disk, in a way that would make it editable. This disqualifies storing just density function parameters (although this also needs to be stored for future generation of terrain), since the density function is not editable. The easiest example, if i wanted to make a hole in terrain somewhere, I'd have to modify all surrounding space to have a negative density. It is possible to store this information and to force the function to check if it's near that hole, and modify it's output.

However, for storing an indefinitely large amount of holes this wouldn't work.

A better solution is to start storing the density function on a discrete grid, and modifying it at each grid point, storing these values back to the grid. This would allow modifying on a large scale, since no matter what, we'd only have a certain finite amount of grid points to store.

Now the problem is storage space. The original version of the density function used a double as its output. The size of a double is 8 bytes. This is pretty tiny, but if we consider storing just a 100x100x100 meter cube, we get:

100*100*100*8 = 8,000,000 bytes, or a little under 8mb. This is just for a relatively small block of 100m. If we wanted to store a 1km x 1km x 1km block, that would make the required storage space about 7.5Gb

Obviously, a 1km cube on each side is a lot of volume, but is still incredibly small compared to what a player can walk to. The double just wasn't going to cut it

So, what if we were to store a byte for density? That would essentially cut all storage by 8, and while still significant, it would give us more wiggle room. That's a fine idea, but how do you map the output of type double down to a byte? A byte can only hold 256 values, after all!

The idea for the solution was mentioned earlier - whether a density is -100, or -1000 it doesn't make much of a difference. The results we obtained are highly dependent on the frequency of the density function used. However, with our density function aimed to generated good amount of roughness at around every 1 meter, we found that we can take the output value of the density function and basically map it like this:

• If the value is less than -1, return -128 as a byte
• If the value is greater than 1, return 127 as a byte (due to 0, a signed byte's range is actually [-128,127])
• If the value is between -1 and 1, basically map it to the discrete range of [-128,127].

With this, we were able to store 1 byte per datapoint, and, using the marching cubes algorithm, still obtain smooth terrain.
The datapoints are stored on every 1m, making it convenient to just refer to them by integer locations. For our purposes, this became known as a Voxel, even though it wasn't quite what a traditional Voxel definition is.

The story so far...

In brief, this started as one guy working on some procedural terrain generation at the beginning of 2011. Some months later, he joined forces with another guy who had also been working on a similar project.

And now they're working together, as the title says, on a Procedural Editable Terrain - aiming to create a dynamic world, which is both realistic, and completely changeable by the user.

In short, the terrain is based on a density function and an implementation of the Marching Cubes Algorithm. The storage of variable densities used alongside the MCA, allows for smooth, good-quality editable terrain.

The project is being developed in C++, with OpenGL for graphics, and various supporting libraries

What's been done so far (more of this will be elaborated in later posts):

• Generation of density-based terrain from a combination of perlin noise functions
• Discrete storage and saving of the density based terrain in so-called 'voxels'
• Meaningful material assignment to voxels (such as dirt, snow, rock etc.)
• Triplanar texture mapping and blending between any two given textures
• Digging of terrain
• Basic 'tool' implementation, including several debugging tools
• De-coupling of the data and visuals
• Variable distance drawing based on data
• On-the-fly generation and storage of necessary data
• Basic biomes, supporting different terrain features and blending between said features
• Occlusion culling

This is a short list of the features that have been currently implemented. Some of these will be expanded upon in later posts - hopefully with screenshots of the things at work