# How do I simplify terrain with tunnels or overhangs?

I'm attempting to store vertex data in a quadtree with C++, such that far-away vertices can be combined to simplify the object and speed up rendering.

This works well with a reasonably flat mesh, but what about terrain with overhangs or tunnels? How should I represent such a mesh in a quadtree?

After the initial generation, each mesh is roughly 130,000 polygons and about 300 of these meshes are lined up to create the surface of a planetary body. A fully generated planet is upwards of 10,000,000 polygons before applying any culling to the individual meshes. Therefore, this second optimization is vital for the project.

The rest of my confusion focuses around my inexperience with vertex data: How do I properly loop through the vertex data to group them into specific quads? How do I conclude from vertex data what a quad's maximum size should be? How many quads should the quadtree include?

• I should have mentioned I'm using C++11 Apr 27, 2014 at 20:00

It might not feel like good advice at first, but the arguments are that the performance gains you get for making this kind of structure is totally overshadowed by the potential performance gain you would get by simply chopping your model into cubes at coarse resolution and doing basic culling. The reason is that modern GPUs are so efficient that they will render amazing amounts of geometry in the same time the CPU would use to be smart about it. To feed the GPU from an advanced structure vs. a simple flat format will incur all sorts of penalties in extra memory usage, memory fragmentation, cache misses etc.

1. Define a deterministic density function like this: float densityFunction(vec3 &point); that returns the density at the given point in space. It should be fairly fast. There exist many such functions that you can use out there, and they can often be combined for interesting results. TIP: Make sure they are continuous, that means that they don’t have any abrupt changes in the density. The "deterministic" and "fast" parts ensure that you can calculate this a lot on the fly, which is the key here.

2. Generate an isosurface based on this density function based on some triangulation algorithm such as marching cubes. You should be able to pass your density function as input, and also you need to be able to specify the corners of a bounding box, and a resolution which basically states how many levels of subdivision you want to trangulate per axis. void generateIsoSurfaces( func &densityFunction, std::vector<float> &vertices, std::vector<int> &indices, vec3 &low, vec3 &high, int resolution);

3. Keep track of your "camera" during rendering, and divide the world into cubic chunks of a set size that makes sense. For each visible cube, pass its bounding box and resolution to the triangulation function. The resulting vertices/indices can then be rendered with your favourite graphics subsystem such as OpenGL (or some engine on top of that).

4. To avoid regenerating everything over and over which will be expensive, make sure to keep each chunk of vertices in memory in a pool. Whenever a chunk is outside the view for a predetermined amount of time (or memory gets low) you free the data. If you get really fancy like I did, you can persist the result on disk. Just make sure reading/writing to disk is faster than regenerating it first.

This way to do things is rather elegant, and has many upsides:

• The density functions can be made as interesting and complex as you like and the engine will cope with them like any other density function.
• The rendering is fast because you are in effect just making polygon soups in a native format for the graphics subsystem
• Tweaking performance is really easy. Just change the resolution, bounding box size, chunk pool size etc to balance rendering between CPU and GPU. In my system I also made an adaptive LOD system so that when the chunks went far away from the camera, a new "less complex" version of the chunk was generated. I operated with resolutions in powers of two so that the poly-count will quadruple between levels. This might generate artifacts such as popping and mismatches at the boundaries between chunks of different levels of detail. In my application this was not important.
• The density function can be used by other parts of the game, such as physics, and it can be much simpler to use than having to work with the polygons. You can simply use newtons method to probe for where a vector hits the "surface" of the density function, and calculate the normal on that surface by simply doing this 3 times in close proximity.
• You can use the density function for procedurally generating shader or textures for the surface.
• Using this landscape engine for multiplayer games is feasible even when you want to use lock-step or similar algorithm for synchronizing game state since it can be made to be portably deterministic (two computers will get the exact same result when calculating the same density function).
• Generation of cubes is very scalable so you can easily leverage multiple cores in a modern computer. I did this by keeping around one thread per core that I feed with work.

There you go. Hope this was helpful!

Well you always have voxel based terrains (look into Marching Cube and Marching Tetrahedron methods). This allows you to put data on the range of only a single byte into each voxel then the algorithm will reconstruct itself. Going from data to mesh is very, very easy once you understand the algorithm. Going from mesh to voxels is a bit more difficult but possible. To do overhangs you need octrees or some other 3d data type ... you just do.

Also if you are doing stuff in patches you need to make an algorithm for patching your terrains together if you want to operate on them independently.

So something like

class Patch
{
//If Z is equal to 1 or 0 you evaluate it like a piece of a quadtree
//else evaluate it as a octree
private:
int dimX, dimY, dimZ;
float scale; //Scale of each unit of the dataset so we can map
//to real world coordinates.
int sizeXY; //getting Z slice is dimZ*sizeXY;
byte* values; //Assuming you use marching cube algorithm
public:
//Getters / Setters
};

//Convient thing about marching cube is it guarantees
//alignment of your patches if aligned patches have same resolution!
//general flow but it probably won't be the exact same.
class MarchingCubeConverter
{
//Map of byte value to vertex coords. You can get this
//From white-papers
public:
//Converts a given mesh specified by some coordinates to a voxel
//format with a given resolution and scale.
static void BuildPatch(Mesh* mesh,vec3 limits,dim3 resolution);
//Converts voxel data to a 3d mesh
static void BuildMesh(Patch* patch,Mesh* mesh);
};


Other option is if you don't want to do marching cube is to create your own quadtree structure that can be an octree if the data needs the 3rd dimension. Look at the patch class above and just when moving across the structure test for the Z dim to decide what you do with it. If you don't do marching cube though you would be saving overhands and stuff into a single unit of your quadtree. You only need that 3rd dimension if you plan on splitting the mesh along that 3rd dimension.

Psuedo-code for patching your terrain assuming you only care about 2 dimensional break-up. Should be straightforward to implement to the third dimensions.

void PatchTerrainMesh(QuadTreeNode<Patch>* node,Mesh* mesh,
int VertexPatchLimit)
{
//Test if the x-y dimensions are within your xy extents
//return the number of vertices that are within that limit.
int Vertices = FindContainedVertices(mesh,(*node)->extents);
if(Vertices > VertexPatchLimit)
{
node->subdivide(); //We now have 4 patches with appropriately divided extents

PatchTerrainMesh((*node)[0],mesh,VertexPatchLimit);
PatchTerrainMesh((*node)[1],mesh,VertexPatchLimit);
PatchTerrainMesh((*node)[2],mesh,VertexPatchLimit);
PatchTerrainMesh((*node)[3],mesh,VertexPatchLimit);
}
else
{
ExtractPatchFromMesh(node,mesh);
}
}

{
//This is the hard part but i'll give some psuedo code to help.
//Need to actually get the vertices you need
vector<int> containingVertices = BuildContainingIndexList(mesh,node->extents);

Line boundaries[4];

ConvertExtentsToBoundaryLines(&boundaries,node->extents);

for(int i = 0;i < containingVertices.size();++i)
{
for(int j = 0;j < mesh->indices.size();++j)
{
if(containingVertices[i] == mesh->indices[j])
{
int start = j - j % 3; //Need the start of the triangle
Triangle tri = Triangle(mesh->vertices[start]
,mesh->vertices[start + 1]
,mesh->vertices[start + 2]);

int intersection = TriangleBoundaryIntersection(&tri,boundaries))
switch(intersection + 1)
{
case 0:
//Add tri to list, no collision
break;
case 1:
//need to subdivide the triangle based on
//line [0]
break;
case 2:
//need to subdivide the triangle based on
//line [1]
break;
//etc....
}

}
}
}
}