hikari – Terrain Mesh Generation

Continuing on from the last post, I have implemented the basic mesh generation for heightmapped terrain. This was probably the easiest part, but did require some cleanup of existing code first.

Mesh Handling Cleanup:

Up to this point, meshes have not been dealt with in a systematic manner in hikari. The Mesh struct contained buffer handles and an index count and that was it. All meshes were assumed to be triangle lists. This was workable, because all object meshes had a common vertex layout, and rendered with variants of a single shader with fixed attribute indices. Rendering a mesh was easy enough:

glBindVertexArray(mesh->vao);
glBindBuffer(GL_ARRAY_BUFFER, mesh->vertex_buffer);
glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, mesh->index_buffer);

glEnableVertexAttribArray(0);
glEnableVertexAttribArray(1);
glEnableVertexAttribArray(2);
glEnableVertexAttribArray(3);

glDrawElements(GL_TRIANGLES, mesh->index_count, GL_UNSIGNED_INT, NULL);

glDisableVertexAttribArray(3);
glDisableVertexAttribArray(2);
glDisableVertexAttribArray(1);
glDisableVertexAttribArray(0);

There were already other meshes with different layouts, but they were special cases: a quad used for full-screen render passes (with only position and uv), a cube used to render the skybox (position only), etc.

Rather than hack around the limitations here (such as using separate render pass for terrain), I decided a mesh should know its vertex layout and be able to do the attribute setup itself.

Enter VertexBufferLayout:

struct VertexBufferLayout {
    struct Property {
        char * name;
        u32 size;
        GLenum type;
        bool normalized;
        u32 offset;
    };
    
    u32 stride;
    std::vector<Property> props;

    u32 GetPropertySizeBytes(Property p) {
        static const u32 TypeToByteTable[] {
            GL_BYTE, 1,
            GL_UNSIGNED_BYTE, 1,
            GL_SHORT, 2,
            GL_UNSIGNED_SHORT, 2,
            GL_INT, 4,
            GL_UNSIGNED_INT, 4,
            GL_HALF_FLOAT, 2,
            GL_FLOAT, 4,
            GL_DOUBLE, 8,
        };

        for (u32 i = 0; i < array_count(TypeToByteTable); i += 2) {
            if (TypeToByteTable[i] == p.type) {
                u32 byte_size = TypeToByteTable[i + 1];
                return byte_size * p.size;
            }
        }
        return 0;
    }
    
    void AddProperty(char * name, u32 size, GLenum type, bool normalized) {
        Property p;
        p.name = name;
        p.size = size;
        p.type = type;
        p.normalized = normalized;
        p.offset = stride;
        u32 byte_size = GetPropertySizeBytes(p);
        if (byte_size > 0) {
            stride += byte_size;
            props.push_back(p);
        }
        else {
            Assert(false, "Invalid vertex buffer property type.");
        }
    }
};

No real surprises here, just stuffing everything into an array, with a bit of extra bookkeeping to prevent errors in calculating stride and offset pointers. This isn’t a general solution, it makes the assumption that vertex attributes are always stored interleaved (not necessarily true), and does not permit a base offset (for storing multiple meshes in one vertex buffer). But it works, and there’s little point buying more complexity than needed.

Meshes each store a pointer to a layout. Prior to rendering, the renderer passes the shader handle to the mesh, which then uses the handle plus its layout data to determine attribute indices in the shader and bind the pointer to the buffer:

void
SetAttribPointersForShader(GLuint shader_program) {
    Assert(layout != NULL && attrib_indices.size() == layout->props.size(),
            "Invalid vertex buffer layout.");

    glBindBuffer(GL_ARRAY_BUFFER, vertex_buffer);

    for (u32 i = 0; i < attrib_indices.size(); ++i) {
        VertexBufferLayout::Property p = layout->props[i];
        attrib_indices[i] = glGetAttribLocation(shader_program, p.name);
        if (attrib_indices[i] != -1) {
            glEnableVertexAttribArray(attrib_indices[i]);
            glVertexAttribPointer(attrib_indices[i], p.size, p.type, p.normalized, layout->stride, (void *)p.offset);
            glDisableVertexAttribArray(attrib_indices[i]);
        }
    }
    
    glBindBuffer(GL_ARRAY_BUFFER, 0);
}

(Ideally we’d like to cache this — the index lookup should only need to be run once per layout/shader combination, not per-mesh.)

Now we have the list of attribute indices to enable, so we can render very similarly to how we did before.

This still leaves a lot to be desired, but it is enough to unblock the terrain work, so let’s get back on track.

Terrain Mesh Generation:

After all that, generating the terrain mesh itself seems almost trivial. Here is the entire loop for building the vertex positions:

u32 vertex_count = x_count*y_count;
TerrainVertex * verts = (TerrainVertex *)calloc(vertex_count, sizeof(TerrainVertex));

float xo = x_count * 0.5f;
float yo = y_count * 0.5f;\
Vector3 bounds_min(FLT_MAX, FLT_MAX, FLT_MAX);
Vector3 bounds_max = -bounds_min;

for (u32 y = 0; y < y_count; ++y) {
    for (u32 x = 0; x < x_count; ++x) {
        float map_val = map->ReadPixel(x_off + x, y_off + y);

        Vector3 pos = Vector3(
            x - xo,
            map_val, 
            y - yo);

        // Scale up from pixel to world space.
        pos *= chunk_meters_per_pixel;

        verts[y * x_count + x].position = pos;

        bounds_min = MinV(bounds_min, pos);
        bounds_max = MaxV(bounds_max, pos);
    }
}

This is a regular grid of squares in the XZ plane, with the Y coordinate taken directly from the heightmap. Next we build an index buffer (in the most naive manner), and calculate surface normals from the resulting triangles.

All of this is pretty straightforward, but there are a few subtle issues that come up:

– Triangulation. Unlike triangles, the vertices of a quad do not necessarily all fall in one plane. This is in fact *usually* the case with terrain. So how we decide to split that quad into triangles has an effect on the final shape:

quad_triangulation_illust

Currently, I split all quads uniformly. Another option I explored is switching the split direction in a checkerboard fashion. With the noise-based heightmap I’m testing with, the difference is negligible. This may prove more of an issue when producing sparser, low-LOD meshes for distant terrain. It also would *absolutely* matter if the terrain was flat-shaded (i.e., constant normal for each face), but that isn’t the case here.

– Calculating vertex normals. I calculate normals for this terrain mesh the same as any other mesh: loop through the faces and add face normals to each vertex, then normalize in another pass:

for (u32 i = 0; i < index_buffer_count; i += 3) {
    u32 idx_a = indices[i + 0];
    u32 idx_b = indices[i + 1];
    u32 idx_c = indices[i + 2];

    Vector3 a = verts[idx_a].position;
    Vector3 b = verts[idx_b].position;
    Vector3 c = verts[idx_c].position;

    Vector3 normal = Cross(a - b, a - c);

    verts[idx_a].normal += normal;
    verts[idx_b].normal += normal;
    verts[idx_c].normal += normal;
}

// We sum the unnormalized normals for each triangle, and then normalize
// the sum.  Since the cross product is scaled by the area of the triangle,
// this means that larger triangles contribute more heavily to the resulting
// vertex normal.
for (u32 i = 0; i < vertex_count; ++i) {
    verts[i].normal = Normalize(verts[i].normal);
}

So far so good, but there is a crucial problem here.

We iterate the faces of the mesh. But some of the points in question actually belong to several meshes! When we’re at the edge of the terrain chunk, we only account for the face normals of the triangles inside the current chunk. Which means the same point, on two different chunks, may produce a different normal.

And so, we get seams:

normal_seams

This is not necessarily easy to fix. The simplest option would be to iterate over neighboring chunks, find the shared vertices, and average the normals — not 100% correct, but it eliminates the seam. It’s unclear, though, how this would interact with streaming: a new chunk being loaded might change the normals on a mesh that’s been loaded for a while; should we read that mesh data back from the GPU? Keep a CPU copy and update? In addition, one of the design goals is for the terrain system to be agnostic about the source of meshes. For a well-structured grid finding the adjacent vertex is simple, but how does that work with an arbitrary hand-produced mesh?

Ultimately, there’s also the question of whether this seam in the normals actually matters. Obviously it *is* a bug, but it is only so glaringly visible because of the shiny plastic material I’m using to debug. I’m not sure how many of these artifacts will remain visible when applying actual terrain materials.

I’m counting this as a bug but I’m going to leave it alone for now.

– Alternate tiling strategies. I started with laying a square grid over the world. Why squares? There are other good tiling arrangements. In fact, we can tile the plane with *just* triangles, and avoid the question of how to triangulate our tiles altogether.

It turns out this is *really* easy to do:

pos.x += (y & 1) * 0.5f;  // Offset odd rows by half a unit
pos.z *= sqrtf(3.0f) / 2.0f; // Scale vertically by sin(pi/3)

Make sure the triangles cut across the short diagonal of that skewed grid, and now the plane is tiled with equilateral triangles.

There isn’t a huge amount of difference with my noise terrain (just a scaling on the Z axis):

This slideshow requires JavaScript.

However, tiling square chunks with equilateral triangles has a sticking point when it comes to downsampling the terrain for distant LOD meshes. The sawtooth edge can’t be merged into larger triangles without either breaking the tiling pattern or leaving gaps or overlap between chunks.

With that said, I feel like the triangle tiling has some really nice properties. No triangulation needed, and no ambiguity on the final mesh’s shape. It can still be represented easily in an image map (although, we’re pushing the limits on that). Grids make it easy to create 90 degree angles, which stick out, while a triangle tiling makes 60 degree angles which are less obviously objectionable. (This one is decidedly a matter of taste, but: my engine, my taste.)

Things get *really* interesting when we decide chunks don’t need to be rectangular. A hexagonal chunk tiles perfectly with equilateral triangles, which means the LOD reduction works fine as well. Using hexes for chunks also fits into the half-offset tiling described by Alan Wolfe here. (In addition to the memory savings he mentions in the post, the hex tiling also means a constant streaming cost as you move about the world, which is a very nice property to have.)

I haven’t implemented hex tiling, and this post is getting quite long as it is. I do think it is an avenue worth exploring, and will probably return to this after fixing up the material system.

Until next time!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s