Greedy Voxel Meshing ported to C#

greedyvoxelmeshing

// Code ported from https://0fps.net/2012/06/30/meshing-in-a-minecraft-game/

// Note this implementation does not support different block types or block normals
// The original author describes how to do this here: https://0fps.net/2012/07/07/meshing-minecraft-part-2/



const int CHUNK_SIZE = 32;

// These variables store the location of the chunk in the world, e.g. (0,0,0), (32,0,0), (64,0,0)
int chunkPosX = 0;
int chunkPosY = 0;
int chunkPosZ = 0;

public void GreedyMesh()
{
    // Sweep over each axis (X, Y and Z)
    for (var d = 0; d < 3; ++d)
    {
        int i, j, k, l, w, h;
        int u = (d + 1) % 3;
        int v = (d + 2) % 3;
        var x = new int[3];
        var q = new int[3];

        var mask = new bool[CHUNK_SIZE * CHUNK_SIZE];
        q[d] = 1;

        // Check each slice of the chunk one at a time
        for (x[d] = -1; x[d] < CHUNK_SIZE;)
        {
            // Compute the mask
            var n = 0;
            for (x[v] = 0; x[v] < CHUNK_SIZE; ++x[v])
            {
                for (x[u] = 0; x[u] < CHUNK_SIZE; ++x[u])
                {                    
                    // q determines the direction (X, Y or Z) that we are searching
                    // m.IsBlockAt(x,y,z) takes global map positions and returns true if a block exists there
                    
                    bool blockCurrent = 0 <= x[d]             ? IsBlockAt(x[0] + chunkPosX,        x[1] + chunkPosY,        x[2] + chunkPosZ)        : true;
                    bool blockCompare = x[d] < CHUNK_SIZE - 1 ? IsBlockAt(x[0] + q[0] + chunkPosX, x[1] + q[1] + chunkPosY, x[2] + q[2] + chunkPosZ) : true;

                    // The mask is set to true if there is a visible face between two blocks,
                    //   i.e. both aren't empty and both aren't blocks
                    mask[n++] = blockCurrent != blockCompare;
                }
            }

            ++x[d];

            n = 0;
            
            // Generate a mesh from the mask using lexicographic ordering,      
            //   by looping over each block in this slice of the chunk
            for (j = 0; j < CHUNK_SIZE; ++j)
            {
                for (i = 0; i < CHUNK_SIZE;)
                {
                    if (mask[n])
                    {
                        // Compute the width of this quad and store it in w                        
                        //   This is done by searching along the current axis until mask[n + w] is false
                        for (w = 1; i + w < CHUNK_SIZE && mask[n + w]; w++) { }

                        // Compute the height of this quad and store it in h                        
                        //   This is done by checking if every block next to this row (range 0 to w) is also part of the mask.
                        //   For example, if w is 5 we currently have a quad of dimensions 1 x 5. To reduce triangle count,
                        //   greedy meshing will attempt to expand this quad out to CHUNK_SIZE x 5, but will stop if it reaches a hole in the mask
                        
                        var done = false;
                        for (h = 1; j + h < CHUNK_SIZE; h++)
                        {
                            // Check each block next to this quad
                            for (k = 0; k < w; ++k)
                            {
                                // If there's a hole in the mask, exit
                                if (!mask[n + k + h * CHUNK_SIZE])
                                {
                                    done = true;
                                    break;
                                }
                            }

                            if (done)
                                break;
                        }

                        x[u] = i;
                        x[v] = j;

                        // du and dv determine the size and orientation of this face
                        var du = new int[3];
                        du[u] = w;

                        var dv = new int[3];
                        dv[v] = h;

                        // Create a quad for this face. Colour, normal or textures are not stored in this block vertex format.
                        BlockVertex.AppendQuad(new Int3(x[0],                 x[1],                 x[2]),                 // Top-left vertice position
                                               new Int3(x[0] + du[0],         x[1] + du[1],         x[2] + du[2]),         // Top right vertice position
                                               new Int3(x[0] + dv[0],         x[1] + dv[1],         x[2] + dv[2]),         // Bottom left vertice position
                                               new Int3(x[0] + du[0] + dv[0], x[1] + du[1] + dv[1], x[2] + du[2] + dv[2])  // Bottom right vertice position
                                               );

                        // Clear this part of the mask, so we don't add duplicate faces
                        for (l = 0; l < h; ++l)
                            for (k = 0; k < w; ++k)
                                mask[n + k + l * CHUNK_SIZE] = false;

                        // Increment counters and continue
                        i += w;
                        n += w;
                    }
                    else
                    {
                        i++;
                        n++;
                    }
                }
            }
        }
    }
}

Great work!
I suppose IsBlockAt should be inverted to IsVoidAt

is there any way to understand which direction quad is pointed? normals get screwed in unity

@eocron it's based on the winding order of the triangle (clockwise vs anti-clockwise). Unity must use a different order than I do, try swapping the 1st and 3rd parameters that are passed to BlockVertex.AppendQuad(...) to change between clockwise and anticlockwise

Hi, what coordinate system was used for this? Y up? Z inverted?

@Yamahari hey this uses Y-up

Hi, how can I figure out which side of a cube the quad is on when adding it to the mesh. I need to know for blocks with different textured faces. I saw that the "q" 3d vector variable stores x, y, z direction but only as a positive 1 so I cannot differentiate between whether the block quad is on the top or bottom of a cube for example.

you have to check and keep track of whether or not "blockCurrent" or "blockCompare" is true and decide based on that which direction the face is facing (both true or both false is no face), using the mask only is not possible @Spacerulerwill

Here's the code for my X-Sweep, if that helps

struct XSweep
{
    auto operator()(const glm::ivec3 &chunkPos, const Chunk &chunk, const Chunk &west, const Chunk &east) const -> std::pair<std::vector<Vertex>, std::vector<GLuint>>
    {
#pragma region USING_DECLARATIONS
        using std::move;
        using std::vector;

        using glm::ivec3;
        using glm::vec2;

        using enum Direction;
#pragma endregion

        int n{0};
        int width;
        int height;
        ivec3 pos{0};
        vector<Vertex> vertices;
        vector<GLuint> indices;

        const auto &eastMask{east.masks[0][0]};
        const auto &westMask{west.masks[0][CHUNK_SIZE - 1]};

        for (pos.x = -1; pos.x < 0;)
        {
            auto mask = ~westMask & chunk.masks[0][0];
            ++pos.x;
            n = 0;

            for (pos.y = 0; pos.y < CHUNK_SIZE; ++pos.y)
            {
                for (pos.z = 0; pos.z < CHUNK_SIZE;)
                {
                    if (mask[n])
                    {
                        const auto blockType{chunk.blocks[pos.z * CHUNK_SIZE + pos.y * CHUNK_AREA].type};
                        for (width = 1; pos.z + width < CHUNK_SIZE && mask[n + width] && chunk.blocks[(pos.z + width) * CHUNK_SIZE + pos.y * CHUNK_AREA].type == blockType; ++width)
                        {
                        }

                        for (height = 1; pos.y + height < CHUNK_SIZE; ++height)
                        {
                            for (int k = 0; k < width; ++k)
                            {
                                if (!mask[n + k + height * CHUNK_SIZE] || chunk.blocks[(pos.z + k) * CHUNK_SIZE + (pos.y + height) * CHUNK_AREA].type != blockType)
                                {
                                    goto labelX1;
                                }
                            }
                        }

                    labelX1:
                        const auto txz{getTXZ(blockType, WEST)};

                        const ivec3 blockPos{chunkPos * CHUNK_SIZE + pos};
                        const ivec3 topLeft{blockPos.x, blockPos.y + height, blockPos.z};
                        const ivec3 topRight{blockPos.x, blockPos.y + height, blockPos.z + width};
                        const ivec3 bottomLeft{blockPos};
                        const ivec3 bottomRight{blockPos.x, blockPos.y, blockPos.z + width};

                        makeVertices(vertices, indices, topLeft, topRight, bottomLeft, bottomRight, WEST, static_cast<float>(width), static_cast<float>(height), txz);

                        for (int l = 0; l < height; ++l)
                        {
                            for (int k = 0; k < width; ++k)
                            {
                                mask[n + k + l * CHUNK_SIZE] = false;
                            }
                        }

                        pos.z += width;
                        n += width;
                    }
                    else
                    {
                        ++pos.z;
                        ++n;
                    }
                }
            }
        }

        for (pos.x = 0; pos.x < CHUNK_SIZE - 1;)
        {
            const auto &aMask{chunk.masks[0][pos.x]};
            const auto &bMask{chunk.masks[0][++pos.x]};
            auto mask = aMask ^ bMask;

            n = 0;

            for (pos.y = 0; pos.y < CHUNK_SIZE; ++pos.y)
            {
                for (pos.z = 0; pos.z < CHUNK_SIZE;)
                {
                    if (mask[n])
                    {
                        if (aMask[n])
                        {
                            // quad is facing east
                            const auto blockType{chunk.blocks[index(pos.x - 1, pos.y, pos.z)].type};
                            for (width = 1; pos.z + width < CHUNK_SIZE && mask[n + width] && aMask[n + width] && chunk.blocks[index(pos.x - 1, pos.y, pos.z + width)].type == blockType; ++width)
                            {
                            }

                            for (height = 1; pos.y + height < CHUNK_SIZE; ++height)
                            {
                                for (int k = 0; k < width; ++k)
                                {
                                    if (const auto maskIndex{n + k + height * CHUNK_SIZE}; !mask[maskIndex] || !aMask[maskIndex] || chunk.blocks[index(pos.x - 1, pos.y + height, pos.z + k)].type != blockType)
                                    {
                                        goto labelX21;
                                    }
                                }
                            }
                        labelX21:
                            const auto txz{getTXZ(blockType, EAST)};

                            const ivec3 blockPos{chunkPos * CHUNK_SIZE + pos};
                            const ivec3 topLeft{blockPos.x, blockPos.y + height, blockPos.z};
                            const ivec3 topRight{blockPos.x, blockPos.y + height, blockPos.z + width};
                            const ivec3 bottomLeft{blockPos};
                            const ivec3 bottomRight{blockPos.x, blockPos.y, blockPos.z + width};

                            makeVertices(vertices, indices, topRight, topLeft, bottomRight, bottomLeft, EAST, static_cast<float>(width), static_cast<float>(height), txz);
                        }
                        else
                        {
                            // quad is facing west
                            const auto blockType{chunk.blocks[vecIndex(pos)].type};
                            for (width = 1; pos.z + width < CHUNK_SIZE && mask[n + width] && bMask[n + width] && chunk.blocks[index(pos.x, pos.y, pos.z + width)].type == blockType; ++width)
                            {
                            }

                            for (height = 1; pos.y + height < CHUNK_SIZE; ++height)
                            {
                                for (int k = 0; k < width; ++k)
                                {
                                    if (const auto maskIndex{n + k + height * CHUNK_SIZE}; !mask[maskIndex] || !bMask[maskIndex] || chunk.blocks[index(pos.x, pos.y + height, pos.z + k)].type != blockType)
                                    {
                                        goto labelX22;
                                    }
                                }
                            }
                        labelX22:
                            const auto txz{getTXZ(blockType, WEST)};

                            const ivec3 blockPos{chunkPos * CHUNK_SIZE + pos};
                            const ivec3 topLeft{blockPos.x, blockPos.y + height, blockPos.z};
                            const ivec3 topRight{blockPos.x, blockPos.y + height, blockPos.z + width};
                            const ivec3 bottomLeft{blockPos};
                            const ivec3 bottomRight{blockPos.x, blockPos.y, blockPos.z + width};

                            makeVertices(vertices, indices, topLeft, topRight, bottomLeft, bottomRight, WEST, static_cast<float>(width), static_cast<float>(height), txz);
                        }

                        for (int l = 0; l < height; ++l)
                        {
                            for (int k = 0; k < width; ++k)
                            {
                                mask[n + k + l * CHUNK_SIZE] = false;
                            }
                        }

                        pos.z += width;
                        n += width;
                    }
                    else
                    {
                        ++pos.z;
                        ++n;
                    }
                }
            }
        }

        for (pos.x = CHUNK_SIZE - 1; pos.x < CHUNK_SIZE;)
        {
            auto mask = chunk.masks[0][CHUNK_SIZE - 1] & ~eastMask;
            ++pos.x;
            n = 0;

            for (pos.y = 0; pos.y < CHUNK_SIZE; ++pos.y)
            {
                for (pos.z = 0; pos.z < CHUNK_SIZE;)
                {
                    if (mask[n])
                    {
                        const auto blockType{chunk.blocks[CHUNK_SIZE - 1 + pos.z * CHUNK_SIZE + pos.y * CHUNK_AREA].type};
                        for (width = 1; pos.z + width < CHUNK_SIZE && mask[n + width] && chunk.blocks[CHUNK_SIZE - 1 + (pos.z + width) * CHUNK_SIZE + pos.y * CHUNK_AREA].type == blockType; ++width)
                        {
                        }

                        for (height = 1; pos.y + height < CHUNK_SIZE; ++height)
                        {
                            for (int k = 0; k < width; ++k)
                            {
                                if (!mask[n + k + height * CHUNK_SIZE] || chunk.blocks[CHUNK_SIZE - 1 + (pos.z + k) * CHUNK_SIZE + (pos.y + height) * CHUNK_AREA].type != blockType)
                                {
                                    goto labelX3;
                                }
                            }
                        }

                    labelX3:
                        const auto txz{getTXZ(blockType, EAST)};

                        const ivec3 blockPos{chunkPos * CHUNK_SIZE + pos};
                        const ivec3 topLeft{blockPos.x, blockPos.y + height, blockPos.z};
                        const ivec3 topRight{blockPos.x, blockPos.y + height, blockPos.z + width};
                        const ivec3 bottomLeft{blockPos};
                        const ivec3 bottomRight{blockPos.x, blockPos.y, blockPos.z + width};

                        // flipped on purpose
                        makeVertices(vertices, indices, topRight, topLeft, bottomRight, bottomLeft, EAST, static_cast<float>(width), static_cast<float>(height), txz);

                        for (int l = 0; l < height; ++l)
                        {
                            for (int k = 0; k < width; ++k)
                            {
                                mask[n + k + l * CHUNK_SIZE] = false;
                            }
                        }

                        pos.z += width;
                        n += width;
                    }
                    else
                    {
                        ++pos.z;
                        ++n;
                    }
                }
            }
        }

        return {move(vertices), move(indices)};
    }
};

@eocron it's based on the winding order of the triangle (clockwise vs anti-clockwise). Unity must use a different order than I do, try swapping the 1st and 3rd parameters that are passed to BlockVertex.AppendQuad(...) to change between clockwise and anticlockwise

I tried all 24 permutations inside unity and none of them worked ;( I have the same problem of the normals being skewed. Some are inside, some are outside, and even the wrong rotation some of em.

@PhantomLexs does unity use Y-up or Z-up? This is designed for Y-up

@Vercidium Unity is Y-up but I don't think that's an issue. It renders them correctly when they're on top, but on the bottom they are pointing inward. So both point upward. This applies to the X and Z axes as well, the faces all point the same direction instead of outward. We need a way to tell if the face is pointing up when it should be on the bottom and flip it and I guess something about Unity is screwing with it.

@PhantomLexs Here's what I did to solve this issue, if you're still running into it:

After creating the mask array, create another one called flip:

var mask = new bool[CHUNK_SIZE * CHUNK_SIZE];
var flip = new bool[CHUNK_SIZE * CHUNK_SIZE];

If this is true and there is an edge here, its normals should be flipped (i.e. its winding direction reversed).

You calculate this when building the mask:

mask[n] = blockCurrent != blockCompare;
flip[n] =blockCompare;
n++

Next, when we calculate the width and height while creating our quads, we need to ensure that adjacent quads are not merged if they are flipped opposite directions:

// Compute the width of this quad and store it in w                        
//   This is done by searching along the current axis until mask[n + w] is false
for (w = 1; i + w < CHUNK_SIZE && mask[n + w] && (flip[n] == flip[n + w]); w++) { }

// Compute the height of this quad and store it in h                        
//   This is done by checking if every block next to this row (range 0 to w) is also part of the mask.
//   For example, if w is 5 we currently have a quad of dimensions 1 x 5. To reduce triangle count,
//   greedy meshing will attempt to expand this quad out to CHUNK_SIZE x 5, but will stop if it reaches a hole in the mask
                        
var done = false;
for (h = 1; j + h < CHUNK_SIZE; h++)
{
    // Check each block next to this quad
    for (k = 0; k < w; ++k)
    {
        // If there's a hole in the mask, exit
        if (!mask[n + k + h * CHUNK_SIZE] || flip[n] != flip[n + k + h * CHUNK_SIZE])
        {
            done = true;
            break;
        }
    }

    if (done)
        break;
}

Finally, when adding the quad, check if it should be flipped:

if (!flip[n]) {
    BlockVertex.AppendQuad(new Int3(x[0],                 x[1],                 x[2]),                 // Top-left vertice position
                                               new Int3(x[0] + du[0],         x[1] + du[1],         x[2] + du[2]),         // Top right vertice position
                                               new Int3(x[0] + du[0] + dv[0], x[1] + du[1] + dv[1], x[2] + du[2] + dv[2])  // Bottom right vertice position
                                               new Int3(x[0] + dv[0],         x[1] + dv[1],         x[2] + dv[2]),         // Bottom left vertice position
                                               );
} else {
    BlockVertex.AppendQuad(new Int3(x[0],                 x[1],                 x[2]),                 // Top-left vertice position
                                               new Int3(x[0] + dv[0],         x[1] + dv[1],         x[2] + dv[2]),         // Bottom left vertice position
                                               new Int3(x[0] + du[0] + dv[0], x[1] + du[1] + dv[1], x[2] + du[2] + dv[2])  // Bottom right vertice position
                                               new Int3(x[0] + du[0],         x[1] + du[1],         x[2] + du[2]),         // Top right vertice position
                                               );
}

This will ensure that all faces are flipped correctly. Note that I'm using slightly different code for my particular use case as well as more descriptive variable names so I tried to translate it back, but I may have missed something.