java – Terraced terrain generation artifacting

This is for procedural mesh generation. I have a heightmap of points in a square grid, forming what could be considered standard heightmapped terrain. I want to take this terrain and divide it vertically into terraces.

I have done some work on implementing the algorithm described in https://icospheric.com/blog/2016/07/17/making-terraced-terrain/

To sum up:

  • For each triangle in the mesh, find its highest and lowest vertex (based on Y for flat terrain)
  • Calculate the minimum and maximum ‘slice’ the triangle passes through. In the article, each slice is 1.0 units tall, so a triangle with a vertex at (0, 1, 0) and another at (0, 10, 0) would pass through 10 slices.
  • For each slice the triangle passes through:
    • find the number of vertices that are above the slice
    • Create some geometry based on the results of how many vertices are above the slice:
      • For triangles with 3 vertices above the slice, 1 triangle forming a ‘roof’ is added
      • For triangles with 2 vertices above the slice, 2 triangles forming a trapezoid ‘roof’, and 2 triangles forming a ‘wall’ are added
      • For triangles with 1 vertex above the slice, 1 triangle forming a ‘roof’ and 2 triangles forming a ‘wall’ are added

For the most part, it works as expected, creating distinct slices out of rolling hills. However, there are strange artifacts that appear along a 45-ish degree angle, depicted as such: https://i.stack.imgur.com/gIHEu.png

I am not certain as to where in my code these artifacts are cropping up. The code in question:

private float terraceHeight;

public MeshData process(MeshData data) {

    List<Vector3f> vertices = data.getVertexPositions();
    List<Integer> colors = data.getVertexColors();
    List<Vector3i> triangles = data.getTriangles();

    int ndf = 0;
    int n3a = 0;
    int n2a = 0;
    int n1a = 0;

    List<Vector3f> nVerts = new ArrayList<>();
    List<Vector3f> nNorms = new ArrayList<>();
    List<Integer> nCols = new ArrayList<>();
    List<Vector3i> nTris = new ArrayList<>();

    for (Vector3i tri : triangles) {

        Vector3f a = vertices.get(tri.x);
        Vector3f b = vertices.get(tri.y);
        Vector3f c = vertices.get(tri.z);

        Vector3f v1 = a;
        Vector3f v2 = b;
        Vector3f v3 = c;

        float h1 = v1.y;
        float h2 = v2.y;
        float h3 = v3.y;

        float minHeight = (float) Math.floor(Math.min(h1, Math.min(h2, h3)));
        float maxHeight = (float) Math.floor(Math.max(h1, Math.max(h2, h3)));

        int minSlice = (int) (minHeight / terraceHeight);
        int maxSlice = (int) (maxHeight / terraceHeight);

        int acol = colors.get(tri.x);
        int bcol = colors.get(tri.y);
        int ccol = colors.get(tri.z);

        for (int i = minSlice; i <= maxSlice; i++) {

            float h = i * terraceHeight;
            int above = 0;

            if (h1 < h) {
                if (h2 < h) {
                    if (h3 < h) {
                        // Shouldn't happen
                        System.out.println("Weirdness happened, 3 points below!");
                    }
                    else {
                        above = 1;
                    }
                }
                else {
                    if (h3 < h) {
                        above = 1;
                        v1 = c;
                        v2 = a;
                        v3 = b;
                    }
                    else {
                        above = 2;
                        v1 = b;
                        v2 = c;
                        v3 = a;
                    }
                }
            }
            else {
                if (h2 < h) {
                    if (h3 < h) {
                        above = 1;
                        v1 = b;
                        v2 = c;
                        v3 = a;
                    }
                    else {
                        above = 2;
                        v1 = c;
                        v2 = a;
                        v3 = b;
                    }
                }
                else {
                    if (h3 < h) {
                        above = 2;
                    }
                    else {
                        above = 3;
                    }
                }
            }


            h1 = v1.y;
            h2 = v2.y;
            h3 = v3.y;

            // Current height plane
            Vector3f v1c = new Vector3f(v1.x, h, v1.z);
            Vector3f v2c = new Vector3f(v2.x, h, v2.z);
            Vector3f v3c = new Vector3f(v3.x, h, v3.z);

            // plane 1 terrace below
            Vector3f v1b = new Vector3f(v1.x, h - terraceHeight, v1.z);
            Vector3f v2b = new Vector3f(v2.x, h - terraceHeight, v2.z);
            Vector3f v3b = new Vector3f(v3.x, h - terraceHeight, v3.z);

            int iv = nVerts.size();

            if (above == 3) {
                n3a++;
                nVerts.add(v1c);
                nVerts.add(v2c);
                nVerts.add(v3c);
                nNorms.add(new Vector3f(0f, 1f, 0f));
                nNorms.add(new Vector3f(0f, 1f, 0f));
                nNorms.add(new Vector3f(0f, 1f, 0f));
                nCols.add(acol);
                nCols.add(bcol);
                nCols.add(ccol);
                nTris.add(new Vector3i(iv, iv + 1, iv + 2));
            }

            else {

                float t1 = (h1 - h) / (h1 - h3); // interpolation for v1
                if (t1 < 0f) t1 = 0f; if (t1 > 1f) t1 = 1f;
                Vector3f v1cn = new Vector3f();
                v1c.lerp(v3c, t1, v1cn);

                Vector3f v1bn = new Vector3f();
                v1b.lerp(v3b, t1, v1bn);

                float t2 = (h2 - h) / (h2 - h3);
                if (t2 < 0f) t2 = 0f; if (t2 > 1f) t2 = 1f;

                Vector3f v2cn = new Vector3f();
                v2c.lerp(v3c, t2, v2cn);

                Vector3f v2bn = new Vector3f();
                v2b.lerp(v3b, t2, v2bn);

                if (above == 2) {
                    n2a++;
                    // roof
                    nVerts.add(v1c);
                    nVerts.add(v2c);
                    nVerts.add(v2cn);
                    nVerts.add(v1cn);
                    nNorms.add(new Vector3f(0f, 1f, 0f));
                    nNorms.add(new Vector3f(0f, 1f, 0f));
                    nNorms.add(new Vector3f(0f, 1f, 0f));
                    nNorms.add(new Vector3f(0f, 1f, 0f));
                    nCols.add(acol);
                    nCols.add(bcol);
                    nCols.add(ccol);
                    nCols.add(acol);
                    nTris.add(new Vector3i(iv, iv + 1, iv + 2));
                    nTris.add(new Vector3i(iv + 2, iv + 3, iv));
                    iv += 4;

                    // walls
                    nVerts.add(v1cn);
                    nVerts.add(v2cn);
                    nVerts.add(v2bn);
                    nVerts.add(v1bn);

                    // normals calc
                    Vector3f ab = new Vector3f(v1cn).sub(v2cn);
                    Vector3f bc = new Vector3f(v2cn).sub(v2bn);
                    ab.cross(bc);
                    nNorms.add(ab);
                    nNorms.add(ab);
                    nNorms.add(ab);
                    nNorms.add(ab);

                    nCols.add(acol);
                    nCols.add(bcol);
                    nCols.add(ccol);
                    nCols.add(acol);
                    nTris.add(new Vector3i(iv, iv + 1, iv + 2));
                    nTris.add(new Vector3i(iv, iv + 2, iv + 3));
                }
                else if (above == 1) {
                    n1a++;
                    // roof
                    nVerts.add(v3c);
                    nVerts.add(v1cn);
                    nVerts.add(v2cn);
                    nNorms.add(new Vector3f(0f, 1f, 0f));
                    nNorms.add(new Vector3f(0f, 1f, 0f));
                    nNorms.add(new Vector3f(0f, 1f, 0f));
                    nCols.add(acol);
                    nCols.add(bcol);
                    nCols.add(ccol);
                    nTris.add(new Vector3i(iv, iv + 1, iv + 2));
                    iv += 3;

                    // walls
                    nVerts.add(v2cn);
                    nVerts.add(v1cn);
                    nVerts.add(v1bn);
                    nVerts.add(v2bn);

                    Vector3f ab = new Vector3f(v2cn).sub(v1cn);
                    Vector3f bc = new Vector3f(v1cn).sub(v1bn);
                    ab.cross(bc);
                    nNorms.add(ab);
                    nNorms.add(ab);
                    nNorms.add(ab);
                    nNorms.add(ab);

                    nCols.add(acol);
                    nCols.add(bcol);
                    nCols.add(ccol);
                    nCols.add(acol);
                    nTris.add(new Vector3i(iv, iv + 1, iv + 3));
                    nTris.add(new Vector3i(iv + 1, iv + 2, iv + 3));
                }
            }
        }
    }

    data.setVertexPositions(nVerts);
    data.setVertexNormals(nNorms);
    data.setVertexColors(nCols);
    data.setTriangles(nTris);

    System.out.println("totals ->  defaulted: " + ndf + ",  3 above: " + n3a + ",  2 above: " + n2a + ",  1 above: " + n1a);
    System.out.println("vertices: " + nVerts.size() + ",  normals: " + nNorms.size() + ",  colors: " + nCols.size() + ",  tris: " + nTris.size());

    return data;
}

Some further thoughts on why this might be:

  • The algorithm used in the Ecospheric blog involves the usage of ‘meandering triangles’, which is likened to being similar to marching squares, but for triangles. My mesh is made of triangles, but they are arranged in squares. I have been doing research into equilateral triangle grids as a potential alternative. Any pointers towards useful resources would be appreciated.

If any further information would be helpful, please let me know.

Leave a Comment