How do I merge quads to simplify a heightmap?

Question

I'm trying to improve my frame rates.

My map has an area of 200 * 200 vertices, where each vertex has a height. 200 * 200 = 40000 vertices per frame.

I'd like to create a method to simplify the whole heightmap (i.e. decrease vertex count). Every 4 vertices form a quad, so when there are 2 or more adjacent quads with the same height on each vertex, they could be merged.

How do I detect and merge vertices like that?

My height map is a list of floats representing the height of each vertex. The list is indexed by an x and y coordinate.

package rgc.area;

import org.lwjgl.opengl.Display;
import org.lwjgl.opengl.GL11;

public class Terrain {

    private HeightMap map;

    public Terrain(HeightMap map) {

        this.map = map;
    }

    public void render() {

        float spaceBetwVert = 1f; // Space between each vertex

        GL11.glColor3f(0.1f, 1.0f, 0.2f);
        GL11.glBegin(GL11.GL_QUADS);
            for(int i = 0; i < map.getHeight() - 1; i++) {

                for(int ii = 0; ii < map.getWidth(); ii++) {

                    GL11.glColor3f(0.1f, 1.0f - ii * 0.1f, 0.2f);

                    float vz = i * spaceBetwVert;
                    float vx = ii * spaceBetwVert;
                    float nextVz = (i + 1) * spaceBetwVert;
                    float nextVx = (ii + 1) * spaceBetwVert;

                    GL11.glVertex3f(vx, map.getHeight(vx, vz), vz - 80);
                    GL11.glVertex3f(nextVx, map.getHeight(nextVx, vz), vz - 80);
                    GL11.glVertex3f(nextVx, map.getHeight(nextVx, nextVz), nextVz - 80);
                    GL11.glVertex3f(vx, map.getHeight(vx, nextVz), nextVz - 80);



                }
            }
        GL11.glEnd();
    }
}

Answer 1

I suggest you change the way you render your vertices instead of trying to merge them.

You are using immediate rendering. While good for debugging and proof of concept, it is "deprecated", and not a preferrable way to render when it comes to performance. You have several alternatives, but the most versatile and robust way I would recommend is using Vertex Buffer Objects (VBO's).

You push the vertices to the GPU once (or once they change), instead of every vertex on its own, every time.

Compared to using immediate mode, VBO's can be hard to grasp at first glance, but they're actually not that hard to use. I recommend you start with something really easy, just to confirm that you get it working. LWJGL has some nice tutorials on using VBO's, and instead of writing them down here, I will link to their site so that this answer points to updated tutorials.

http://lwjgl.org/wiki/index.php?title=Using_Vertex_Buffer_Objects_(VBO)

http://www.java-gaming.org/index.php?topic=24272.0

I am pretty sure this will give you the performance boost you're after.

Answer 2

Use float[] or float[][] instead of List[Float] for the map. if you use List[Float] every time you add or get a float value to/from the map Java creates A Float instance form the primitive float value or convert the Float instance to a primitive float value (auto-boxing, -unboxing) this needs more memory and time.