0
\$\begingroup\$

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:

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;
}
\$\endgroup\$
4
  • \$\begingroup\$ How exactly are you determining left vs right triangles? It should not depend on sorting. \$\endgroup\$ Commented Mar 19, 2021 at 8:37
  • \$\begingroup\$ What can you tell us about your mesh generation algorithm? It might have some structure we can exploit to get the right winding more efficiently. If all we have is a polygon soup, then the solutions can get quite messy and expensive. \$\endgroup\$ Commented Mar 19, 2021 at 11:13
  • \$\begingroup\$ @DMGregory Yes, im using a Greedy Meshing algorithm to create a voxel-based mesh, gist.github.com/Vercidium/a3002bd083cce2bc854c9ff8f0118d33 \$\endgroup\$ Commented Mar 19, 2021 at 19:44
  • \$\begingroup\$ You do not need to post the same comment a second time. The question has been updated, the comments are no longer needed. \$\endgroup\$ Commented Mar 19, 2021 at 23:11

0

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.