opengl - Greedy Mesh generation for a voxel-based game

EDIT: I have already found my problem and fixed it (but I cant accept my own answer for another 2 days)

I'm currently making a 3D voxel-based game and now that I have started optimising some aspects of the render-engine I've come across a problem with my mesh generation.

My voxel world is divided in 16x16x16 Segments; these segments hold the blocks and some more data which helps me to decide if the segment is visible or not. The blocks also have some data about it's visibility and a BlockType; the blocktype basically holds the color and some other material information about the block.

I'm currently only rendering the top, bottom, and left sides of the blocks. But somehow there is something wrong with the mesh generation whenever there are empty blocks above and next to the current block.

(In the image you are facing +x +z)

As you can see in the image above, there are rows of sticking out which shouldn't be there. (Red is what shouldn't be there)

This is my code:

private static HashMap> vertices = new HashMap>();
private static HashMap> indices = new HashMap>();


...

public static void processSegment(Segment segment) {
    BlockType[] mask = new BlockType[4096];
    boolean[] done = new boolean[4096];

    Block block;
    BlockType type;
    int x, y, z;
    int y_, z_;

    int k;
    int w = 0, h = 0;
    int sum;
    int i, j;
    int q, p;
    boolean done_;
    boolean continue_;

    int bX, bY, bZ;
    int segX = segment.getAbsPos().x * 16;

    int segY = segment.getAbsPos().y * 16;
    int segZ = segment.getAbsPos().z * 16;

    // Filling the mask with the blocktypes, every block which is not visible (or isn't there) will be masked with AIR
    for (i = 0; i < 4096; i++) {
        block = segment.getBlock(i);
        if (block == null) mask[i] = BlockType.AIR;
        else if (!block.isVisible()) mask[i] = BlockType.AIR;
        else {
            mask[i] = block.getType();

        }
    }

    // Loop through the six sides 0TOP 1BOT 2LEFT 3RIGH 4FRONT 5BACK
    for (i = 0; i < 6; i++) {
        // Faces of the segment which are not facing the camera should not be rendered
        if (!shouldRenderSegSide(i, segX, segY, segZ)) continue;

        continue_ = true;
        for (j = 0; j < 4096; j++) {

            if (mask[j] == BlockType.AIR) {
                done[j] = true;
                continue;
            }

            // All the blocks of which the current face is not visible should not be rendered
            block = segment.getBlock(j);
            if (!block.isSideVisible(i)) done[j] = true;
            else {
                done[j] = false;

                continue_ = false;
            }
        }
        if (continue_) continue; // Skips the rest of the code for this side if the side somehow appears to be empty

        for (y = 0; y <  16; y++) { // Loops through all the blocks (of the segment)
            y_ = y << 8; // This is for calculating the index of a 1-dimensional array
            bY = y + segY; // Absolute Y-value of the block in the world
            for (z = 0; z < 16; z++) {
                z_ = z << 4;

                bZ = z + segZ;
                for (x = 0; x < 16; x++) {
                    sum = x + z_ + y_;
                    if (done[sum]) continue;
                    bX = x + segX;
                    type = mask[sum];

                    // Finding with and height
                    done_ = false;
                    if (i == Side.TOP || i == Side.BOT) {

                        for (w = 0; mask[sum + w] == type && !done[sum + w] && w < 15 - x; w++) {} // x

                        for (h = 0; h < 15 - z; h++) { // z
                            q = sum + (h << 4);
                            for (k = 0; k <= w; k++) { // x
                                if (mask[q + k] != type) {
                                    done_ = true;
                                    break;
                                }
                            }

                            if (done_) break;
                        }

                        // Make sure the block won't be used again
                        for (j = 0; j <= h; j++) { // z
                            q = j << 4;
                            for (k = 0; k <= w; k++) { // x
                                done[sum + q + k] = true;
                            }
                        }

                    } else if (i == Side.LEFT || i == Side.RIGHT) {
                        for (w = 0; mask[sum + (w << 4)] == type && !done[sum + (w << 4)] && w < 15 - z; w++) {} // z

                        for (h = 0; h < 15 - y; h++) { // y
                            q = sum + (h << 8);
                            for (k = 0; k <= w; k++) { // z
                                if (mask[q + (k << 4)] != type) {
                                    done_ = true;
                                    break;
                                }

                            }
                            if (done_) break;
                        }

                        for (j = 0; j <= h; j++) { // y
                            q = sum + (j << 8);
                            for (k = 0; k <= w; k++) { // z
                                done[q + (k << 4)] = true;
                            }
                        }

                    } else if (i == Side.FRONT || i == Side.BACK) {
                        continue; // TEMP
                    }

                    addVertices(type.getColor(), i, bX, bY, bZ, w, h);
                }
            }
        }

    }

}

private static void addVertices(Vector3f color, int side, int x, int y, int z, int w, int h) {
    ArrayList sideVertices = vertices.get(side);
    ArrayList sideIndices = indices.get(side);

    if (side == Side.TOP) {
        sideVertices.add(new WorldVertex(new Vector3f(x - 0.5f,     y + 0.5f,   z - 0.5f),      color));
        sideVertices.add(new WorldVertex(new Vector3f(x - 0.5f,     y + 0.5f,   z + 0.5f + h),  color));
        sideVertices.add(new WorldVertex(new Vector3f(x + 0.5f + w, y + 0.5f,   z + 0.5f + h),  color));

        sideVertices.add(new WorldVertex(new Vector3f(x + 0.5f + w, y + 0.5f,   z - 0.5f),      color));
    }

    if (side == Side.BOT) {
        sideVertices.add(new WorldVertex(new Vector3f(x - 0.5f,     y - 0.5f,   z - 0.5f),      color));
        sideVertices.add(new WorldVertex(new Vector3f(x + 0.5f + w, y - 0.5f,   z - 0.5f),      color));
        sideVertices.add(new WorldVertex(new Vector3f(x + 0.5f + w, y - 0.5f,   z + 0.5f + h),  color));
        sideVertices.add(new WorldVertex(new Vector3f(x - 0.5f,     y - 0.5f,   z + 0.5f + h),  color));
    }


    if (side == Side.LEFT) {
        sideVertices.add(new WorldVertex(new Vector3f(x - 0.5f,     y + 0.5f + h,   z + 0.5f + w),  color));
        sideVertices.add(new WorldVertex(new Vector3f(x - 0.5f,     y + 0.5f + h,   z - 0.5f),  color));
        sideVertices.add(new WorldVertex(new Vector3f(x - 0.5f,     y - 0.5f,   z - 0.5f),      color));
        sideVertices.add(new WorldVertex(new Vector3f(x - 0.5f,     y - 0.5f,   z + 0.5f + w),      color));
    }

    ... // For the other 3 sides

    // Adding indices for the 2 triangles

    sideIndices.add(sideVertices.size() - 4);
    sideIndices.add(sideVertices.size() - 3);
    sideIndices.add(sideVertices.size() - 2);
    sideIndices.add(sideVertices.size() - 2);
    sideIndices.add(sideVertices.size() - 1);
    sideIndices.add(sideVertices.size() - 4);
}

Can you help me to find what I did wrong? I've already looked multiple times at my code for a few hours, but I still cant find it.

EDIT: Got the idea for this meshing technique from this article

Answer

I've found what I've done wrong:

for (w = 0; mask[sum + w] == type && !done[sum + w] && w < 15 - x; w++) {}

The code above was wrong, because it incremented w first and then it checked everything. Therefor the code should be:

for (w = 0; w < 15 - x && mask[sum + 1 + w] == type && !done[sum + 1 + w]; w++) {}

This code is better, because:

1. It doesn't give an ArrayIndexOutOfBoundsException because I check if w is too large first.



2. It doesn't check the block which was already included (the first one at w = 0).


3. It does work.

And I applied a similar fix to the other loop which had to find the correct height.

Thanks for taking the time to look at my problem.