create terrain with some vertical cliffs, natural arcades, caves using octree

Question

I am about to start creating the first terrain. I would like to create a terrain with vertical cliffs, natural arcades and caves.

For instance in one point the terrain might look like this.

I want to discuss about how to store this information about the terrain.

I think quadtree will not do the trick. From my understainding with quadtree perfectly vertical terrain is bound to be low quality in the vertical part, as you cannot subdivide it.

So I thounght that octree should be the right tool. But I have a conceptual problem with octree. I cannot understand how to store the triangle data in a octree structure.

Understanding how to store data in a quadtree is easy: you subdivide the region in a lot of squares and you give a coordinate value to each vertex of the squares, then you just connect all the verticies with triangles.

But what can you do when it comes to octtree? Which information should you store conceptually in the octree tree?

I cannot guess the logic and the algorithm that lays behind a octtree terrain.

Thank you

Answer 1

Note: This topic is way too large to be answered appropriately in a StackExchange answer. You will have to do your own further research / googling.

Voxel Grids

Fundamentally, you're trying to figure out a representation of a voxel grid. The simplest possible way to represent a 3D grid is a simple array, like map = new Voxel[width, height, depth], where Voxel is some kind of small structure that represents the material at a particular point, e.g. air, ground, water, etc. However, this wastes a lot of space on possibly empty or uniformly solid areas. The storage required is roughly O(N³). Finding a way to cut that down leads us to.....

Space Partitioning Structures

To overcome the storage shortcomings of a dense voxel array, you would look into a space-partitioning structure (such as a quadtree, octree, spatial hash, etc.) The primary advantages that all these structures satisfy are:

• Sub-linear retrieval time of the volume data at a particular coordinate. (The trees will have O(log N) and the hashmap should have O(1)). There will be some differences between the structures, such as the trees are scale-invariant and so are suitable for large-scale LOD operations.

• No space wasted on large empty (or possibly uniform) areas.

Typically for performance reasons, the leaf nodes of this structure will be chunks of voxels that represent, for example, an 16x16x16 volume.

One misconception in the question is that a quadtree would not be able to handle overhangs. This is not necessarily true. Even in a hash-table, a hash collision does not actually lose data. There are multiple ways of handling overlap. For example, Minecraft uses a quadtree, since its vertical-axis is limited to 256 units, which is small enough that its chunks are simply 16x16x256 columns.

Isosurface Extraction

We now have a data structure where, generally speaking, we can query for data like

Voxel v = myGridStructure.GetVoxelAt(100,100,0);

How do we translate this into a triangular mesh that the graphics card can render? The simplest way, (i.e. the Minecraft method), is to generate a square at every boundary between "air" and "not-air". This yields a blocky look that a lot of current "voxel games" use. There are many other algorithms out there that attempt to generate a smoother surface. The classic algorithm is called Marching Cubes, but there are also other algorithms such as surface nets(almost a smoothed naive algorithm) or dual contouring (requires a gradient vector, but gives nice sharp edges). This page is one of the first Google matches for isosurface extraction and links to some papers on the topic.

Answer 2

There are techniques based around traditional heightmaps, but instead of using a purely vertical height value, the textures contain a full 3D vector, indicating the displacement to apply to the vertex.

This allows you to stretch around and reallocate areas of the terrain, creating overhangs and jutting parts of the terrain. Complemented with carefully placed meshes, you can create pretty much anything.

A prime example of this is in Halo Wars, which had a video/slide presentation at GDC now available in the GDC Vault for free, which covers this in great detail.

Answer 3

Store the existence of terrain in your data structure. That would be a boolean value where true means solid and false means air. You could also extend this and store a material as integer, where 0 means air, 1 means dirt, 2 means stone, 3 means wood, and so on.

To generate a mesh from that data, use marching cubes or a similar algorithm. It calculates a polygon mesh out of voxel data.

By the way, I suggest octree if you want a tree data structure. It is the 3d equivalent of quadtree and therefore it fits your world better. Although I would go with a simple 3d array for now. Later on, for larger worlds, you can decide whether to use octrees or divide the world in chunks.

To save space, you can use run-length encoding.

There is a very good article on the blog 0 FPS discussing different data structure for such terrains, including array, array chunks, octree and a combination of interval tree and hash table which shows up to be the fastest structure.

Answer 4

http://vterrain.org/Elevation/Caves/ has a collection of papers on modelling caves/terrain with caves.

Generally speaking, there are three methods used:

• The caves are modelled as a snake/chain of vectors, with a property which defines the thickness of the cave around the vector.
• Voxels
• The terrain is handled like a triangle mesh, with caves being modelled as part of the mesh (this can also be combined with heightfields if a portion of the heightfield is cut out near the tunnel/cave entrance)

Aside from that, there's also vector heightfields, which have already been mentionedin another answer.