How to efficiently render a large terrain mesh?

Question

Recently I've been stuck on a problem thinking about the best way to generate a terrain into my game. In another projects I normally used heightmaps, so all the core-work was based on the engine used, but now this cannot be done because the terrain has millions of specific polygons that must be drawn accurately. Also, many of them cannot be parsed from the Y vector (because of polygons hidden beneath), that is, a heightmap is not useful here. In this case I had to use a COLLADA object.

Someone told me to manually divide the model inside a software like Blender, but unfortunately this is also not possible because these terrains are created in chunks in another software and loaded after into the game (that's the idea). Therefore this would be a big work to be obliged to manually slice them everytime.

Thus, since a week I've been studying about how could I solve this problem and procedurally load this mesh, the terrain, accordingly to the camera frustrum, saving as much performance as possible. I came accross many documents about procedural mesh generation and I think that my problem could be solved by mapping the mesh into octrees. This is BIG work, at least for me, and that's why I'm here, because I don't want to risk taking the wrong path without before hearing from experienced people.

In short, I have millions of vertices and indices that together form the terrain, but for obvious reasons I cannot draw them at the same time. It's needed some kind of procedure. What's the best way to do that, to treat a big mesh as a terrain? Is there any specific book about that? Is there a best way to implement it?

Sorry for any kind of mistake, I'm very novice on this area.

Answer 1

Basic chunking is a good way to start. You can move to more sophisticated data structures like octrees later, if you need. For now, simply divide your terrain into chunks of given dimensions when loading the model from disk.

Depending on your data, you might either want to split your terrain into pillars on a plane spanning the full height, or in cubes in space. The code isn't complete (fmod, vector initialization, indices, ...) but should give you a start.

// Load vertices from disk
struct point { double x, y, z; };    
vector<point> vertices;

// Create container for chunks
typedef pair<int, int> key;
unordered_map<key, vector<point>> chunks;
const int chunksize = 10;

// For each vertex
for (int i = 0; i < vertices.size(); ++i) {
    // Fetch global coordinates
    int x = vertices[i].x,
        y = vertices[i].y,
        z = vertices[i].z;

    // Find containing chunk
    key k;
    k.first  = x / chunksize;
    k.second = z / chunksize;

    // Calculate local coordinates
    point p;
    p.x = x % chunksize;
    p.y = y;
    p.z = z % chunksize;

    // Add to chunk
    chunks[k].push_back(p);
}

// Create separate buffers for each chunk
// ...

Since you have split up the mesh now, you can perform LOD and culling techniques on it to skip rendering of hidden chunks.

• View distance is where you start. You would only render chunks within a given distance, for example the view distance of your camera. The smaller the view distance, the more performance you get since fewer chunks of the terrain must be drawn.

• Frustum culling is a common technique to only render meshes that intersect with the camera's view frustum. This will most likely give you the largest performance gain.

Experiment with the chunk size and view distance to get the best results. Chunk size is a trade-off between accurate culling versus easy computation. To further optimize, you could take a look at these more advanced optimizations.

• Occlusion culling can be done by rendering the meshes on the CPU at very low resolution. This allows you to early detect meshes hidden behind other ones. They don't have to be sent to the GPU, so you save a lot of vertex shader executions which otherwise would have been performed before rejecting the triangles.

• Level of detail means that you calculate lower resolution meshes of your chunks. Based on the distance to the camera, you choose one of the meshes to draw. This allows you to reduce the number of vertices since chunks far away don't need so much detail. This approach plays well with octrees because you could merge multiple cubes into one low resolution mesh for areas far away from the camera. However, it is non-trivial to seamlessly merge the edges between two chunks of a different resolution.