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

