Saturday 20 August 2011

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.

No comments:

Post a Comment