A method for indexing triangles from a loaded heightmap?

Question

I am currently making a method to load in a noisy heightmap, but lack the triangles to do so. I want to make an algorithm that will take an image, its width and height and construct a terrain node out of it.

Here's what I have so far, in somewhat pseudo

Vertex* vertices = new Vertices[image.width * image.height];
Index* indices; // How do I judge how many indices I will have?
float scaleX = 1 / image.width;
float scaleY = 1 / image.height;
float currentYScale = 0;

for(int y = 0; y < image.height; ++y) {
    float currentXScale = 0;
    for (int x = 0; x < image.width; ++x) {
       Vertex* v = vertices[x * y];
       v.x = currentXScale;
       v.y = currentYScale;
       v.z = image[x,y]; 
       currentXScale += scaleX;
    }
    currentYScale += scaleY;
}

This works well enough to my needs, my only problem is this: How would I calculate the # of indices and their positions for drawing the triangles? I have somewhat familiarity with indices, but not how to programmatically calculate them, I can only do that statically.

Answer 1

As far as your code above goes, using vertices[x * y] isn't right - if you use that, then e.g. vert(2,3) == vert(3,2). What you want is something like vertices[y * image.width + x], but you can do it more efficiently by incrementing a counter (see below).

Here's the equivalent code I use. It's in C# unfortunately, but hopefully it should illustrate the point:

/// <summary>
/// Constructs the vertex and index buffers for the terrain (for use when rendering the terrain).
/// </summary>
private void ConstructBuffers()
{
    int heightmapHeight = Heightmap.GetLength(0);
    int heightmapWidth = Heightmap.GetLength(1);
    int gridHeight = heightmapHeight - 1;
    int gridWidth = heightmapWidth - 1;

    // Construct the individual vertices for the terrain.
    var vertices = new VertexPositionTexture[heightmapHeight * heightmapWidth];

    int vertIndex = 0;
    for(int y = 0; y < heightmapHeight; ++y)
    {
        for(int x = 0; x < heightmapWidth; ++x)
        {
            var position = new Vector3(x, y, Heightmap[y,x]);
            var texCoords = new Vector2(x * 2f / heightmapWidth, y * 2f / heightmapHeight);
            vertices[vertIndex++] = new VertexPositionTexture(position, texCoords);
        }
    }

    // Create the vertex buffer and fill it with the constructed vertices.
    this.VertexBuffer = new VertexBuffer(Renderer.GraphicsDevice, typeof(VertexPositionTexture), vertices.Length, BufferUsage.WriteOnly);
    this.VertexBuffer.SetData(vertices);

    // Construct the index array.
    var indices = new short[gridHeight * gridWidth * 6];    // 2 triangles per grid square x 3 vertices per triangle

    int indicesIndex = 0;
    for(int y = 0; y < gridHeight; ++y)
    {
        for(int x = 0; x < gridWidth; ++x)
        {
            int start = y * heightmapWidth + x;
            indices[indicesIndex++] = (short)start;
            indices[indicesIndex++] = (short)(start + 1);
            indices[indicesIndex++] = (short)(start + heightmapWidth);
            indices[indicesIndex++] = (short)(start + 1);
            indices[indicesIndex++] = (short)(start + 1 + heightmapWidth);
            indices[indicesIndex++] = (short)(start + heightmapWidth);
        }
    }

    // Create the index buffer.
    this.IndexBuffer = new IndexBuffer(Renderer.GraphicsDevice, typeof(short), indices.Length, BufferUsage.WriteOnly);
    this.IndexBuffer.SetData(indices);
}

I guess the key point is that given a heightmap of size heightmapHeight * heightmapWidth, you need (heightmapHeight - 1) * (heightmapWidth - 1) * 6 indices, since you're drawing:

• 2 triangles per grid square
• 3 vertices per triangle
• (heightmapHeight - 1) * (heightmapWidth - 1) grid squares in your terrain.