Skip to main content
added 5817 characters in body
Source Link

Here is the Algorithm:

public Mesh GreedyMesh()
{
    List<Vector3> vertices = new List<Vector3>();
    List<int> triangles = new List<int>();
    
    // 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_SQUARED];
        q[d] = 1;

        // Check each slice of the chunk one at a time
        for (x[d] = -1; x[d] < CHUNK_SIZE;)
        {
            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
                    // IsVoidAt(x,y,z) takes global map positions and returns true if no block exists there.
                 
                    bool blockCurrent = (0 <= x[d])? IsVoidAt(x[0] + chunkPosX, x[1] + chunkPosY, x[2] + chunkPosZ): true;
                    bool blockCompare = (x[d] < CHUNK_SIZE - 1)? IsVoidAt(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;

                        // Here is where we create the faces.
                        triangles.AddRange(new int[]{
                            // Note: Triangles are generated by 3 vertex (We use the index of those points in vertices array).
                            // upper left triangle
                            vertices.Count+0, vertices.Count+1, vertices.Count+2,
                            // lower right triangle
                            vertices.Count+2, vertices.Count+1, vertices.Count+3
                        });
                        
                        // And here we add the vertices to the mesh.
                        vertices.Add(new Vector3(x[0], x[1], x[2]));
                        vertices.Add(new Vector3(x[0] + du[0], x[1] + du[1], x[2] + du[2]));
                        vertices.Add(new Vector3(x[0] + dv[0], x[1] + dv[1], x[2] + dv[2]));
                        vertices.Add(new Vector3(x[0] + du[0] + dv[0], x[1] + du[1] + dv[1], x[2] + du[2] + dv[2]));
                        
                        // 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++;
                    }
                }
        }
    }
    
    Mesh mesh = new Mesh();
    mesh.vertices = vertices;
    mesh.triangles = triangles;
    return mesh;
}

Here is the Algorithm:

public Mesh GreedyMesh()
{
    List<Vector3> vertices = new List<Vector3>();
    List<int> triangles = new List<int>();
    
    // 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_SQUARED];
        q[d] = 1;

        // Check each slice of the chunk one at a time
        for (x[d] = -1; x[d] < CHUNK_SIZE;)
        {
            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
                    // IsVoidAt(x,y,z) takes global map positions and returns true if no block exists there.
                 
                    bool blockCurrent = (0 <= x[d])? IsVoidAt(x[0] + chunkPosX, x[1] + chunkPosY, x[2] + chunkPosZ): true;
                    bool blockCompare = (x[d] < CHUNK_SIZE - 1)? IsVoidAt(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;

                        // Here is where we create the faces.
                        triangles.AddRange(new int[]{
                            // Note: Triangles are generated by 3 vertex (We use the index of those points in vertices array).
                            // upper left triangle
                            vertices.Count+0, vertices.Count+1, vertices.Count+2,
                            // lower right triangle
                            vertices.Count+2, vertices.Count+1, vertices.Count+3
                        });
                        
                        // And here we add the vertices to the mesh.
                        vertices.Add(new Vector3(x[0], x[1], x[2]));
                        vertices.Add(new Vector3(x[0] + du[0], x[1] + du[1], x[2] + du[2]));
                        vertices.Add(new Vector3(x[0] + dv[0], x[1] + dv[1], x[2] + dv[2]));
                        vertices.Add(new Vector3(x[0] + du[0] + dv[0], x[1] + du[1] + dv[1], x[2] + du[2] + dv[2]));
                        
                        // 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++;
                    }
                }
        }
    }
    
    Mesh mesh = new Mesh();
    mesh.vertices = vertices;
    mesh.triangles = triangles;
    return mesh;
}
Source Link

Check if a triangle is back-facing in a 3d model

I'm creating 3d models with an algorithm, but i have no idea how to make all triangles in the mesh face the right direction, so some faces are facing inside the model. The list of vertices is sorted by position, so I can't distinguish front triangles from back triangles (or left triangles from right triangles, etc).

This is how it look:

This is how it have to look: