Project Hedra is a game I wrote from scratch using OpenGL which I develop in my spare time.

What I think is the most interesting aspect about it are the worlds. They are completely procedurally generated at runtime and the only data saved for them is the original seed.

World structure

Since the world is theoretically infinite it's impossible to load it all at once. Instead, a 32x32 grid of "chunks" (very similar to chunks in Minecraft) is loaded around the player. New chunks are created when the player moves and the old ones discarded.

Chunks are pieces of the world that hold an offset and information about 32x32x128 voxels. These are stored in a hash table and can be quickly queried by their offset.

Storing voxel information in memory

A voxel is the smallest unit of world information inside the engine, it's needed to build the meshes for the world and calculate the placements of structures.

Each voxel needs to hold information about its density and its type. The density of a voxel represents "how filled" that specific spot is. A density < 0 represents an empty or air voxel while a density of 1 is a filled voxel. The type represents the material and properties of that voxel.

A naive approach would be making the voxel struct contain a float for its density and a byte for this type. This would result in 5 bytes (8 when we add padding) per voxel. Although this looks good when having many voxels like in our case, it expands to 1GB [1] of memory just for storing voxel information.

A better approach would be to use a Half precision floating point which occupies 2 bytes and reduces our voxel size to 4 bytes when we add padding. Even though we just cut the memory needed in half I think we can do better.

The approach I choose was to shorten the density information to the range [-2, 2] and store all this in an unsigned short with the following format:

BlockType    Sign      Significant
0000         0         0000000000

Where

• BlockType stores the voxel type.
• Sign stores the sign of the density.
• Significant stores up to 3 significant numbers in the density in integer format. This gives us enough precision to create a smooth-looking world.

This results in just 2 bytes per voxel, needing only 256MB of memory for storing the voxel information.

Generating the structure

A typical approach to generating these density values I talked about previously is using 3D Perlin Noise. Perlin noise is a very commonly used noise for generating procedural worlds. With enough layering, you can make realistic-looking surfaces just from this simple function.

Hedra takes a similar approach but instead uses Simplex Noise because of the lower computational overhead. This noise is generated using SIMD to improve its performance during runtime.

A bunch of layers of noise are generated both in 2D and 3D some of these are generated in a lower resolution and then upscaled using trilinear interpolation. Finally, these are all mixed to create a single density value.

Paths, rivers, and environment

After the base terrain is generated the environment, path and rivers need to be placed. In the case of rivers and path layers of noise with very big amplitude are generated. These are then clamped to a range as to form "rings". Many of these noise rings with different seeds are layered together forming a network of paths and rivers.

The environment consists of stuff like trees, rocks, grass, reeds, etc. These are placed either randomly using the chunk's offset as a seed for the RNG or in the case of grass and trees using layers of perlin noise in order to form patches of grass and trees.

Meshing the terrain

Finally, the last step is to combine all the data generated and create the mesh. Because of the smooth looks of the game, this step is usually very different from other voxel engines.

First, the voxel information is polygonized into a mesh using Marching Cubes. This process is run for all the voxels in each chunk, grabbing the neighbor information and marching a cube through it to determine the correct surface. At the same step neighbor information and some noise is used to determine the color of the generated surface.

A similar thing is done for the water mesh. Then this information is combined with the hand-made meshes we placed earlier. This mesh is then optimized and simplified depending on the chunk LOD (using the awesome meshoptimizer), stitching together borders with other chunks to avoid holes in the terrain.

As the last step, the chunk mesh which is divided into 3 different buffers (water, static, and instance) is uploaded into the corresponding GPU. The separation is needed because they use different shaders and rendering techniques.

Next

Some ideas for other blog entries:

• Rendering engine in Project Hedra
• Placing human-generated content in an algorithmically-generated world

[1] 32x32 chunk grid of 32x32x128 voxels each = 32x32x128x32x32x8 = 1073741824 bytes.