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++;
                    }
                }
            }
        }
    }
}

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.