I started tackling creating some simple mesh simplification for my blocking prototype, so that I could fix various visual artifacts and keep the polygons down to a minimum.
And in the case where I allow the user to create his own custom blocks to paint in along side the regular blocks, you would like the custom items to be as small as possible.
The algorithm itself is not all too complicated, but with any software piece that you create, you should consider any connected items that can simplify the heavier computation bits and leave as many bread crumbs about so that you can keep the complications also to a minimum.
Since we are just dealing with voxels, the shape of the geometry will not change at all, but rather just fit as few polygons as it can get away with.
The first step is to remove all the hidden faces.
All the blocks keep a tally of what other blocks are adjacent to them. So from every block in the scene you can remove the faces that are on top of each other. Special rules for transparent and opaque connections, but such rules are needed so that transparent effects look correct.
To be able to recreate the cubes on demand with particular faces removed, the cubes are always created procedurally and all the faces created with the same index layout so that the actual face merging can be done with a very simple algorithm without much added data for the faces.
private void MergeFaces(Face a, Face b)
{
// Since all faces on each axis,
// up, down, right, left, forward, back
// are created in the same way, and with the same indices
// this simple algorithm works for all faces of the voxels.
// Merge faces a and b into a.
var aVerts = a.m_vertices;
var bVerts = b.m_vertices;
for(int i = 0; i < 4; i++)
{
bool areEqual = false;
for(int j = 0; j < 4; j++)
{
// Compare a vertex face of a to a vertex face in b. It is basically just a
// distance measurement compared to an epsilon
if(a.ArePointsEqual(b, i, j))
{
areEqual = true;
break;
}
}
if(areEqual)
{
aVerts[i] = bVerts[i];
}
}
}
Second step is too iterate through each material and every face of the bounding cube and create construction planes that collect the faces on each step. Merge them column by column, one row at a time and at the end of that, collect all those merges and walk row by row and find which faces are adjacent, equal length and start at the same column. The faces created from those construction planes are tallied up into an array assembled into a final mesh at the end.
public static ArrayList ConstructForwardFaces(CustomBlockGridController cgc, ArrayList blocks, Vector3 min, Vector3 max)
{
// The steps for each axis, calculated from the bounding volume of collection of voxels.
int ySteps = (int)(max.y - min.y) + 1;
int xSteps = (int)(max.x - min.x) + 1;
int zSteps = (int)(max.z - min.z) + 1;
ArrayList faces = new ArrayList();
float z = min.z;
for (int iz = 0; iz < zSteps; iz++)
{
// Create a construction plane for the current plane
ConstructionPlane plane = new ConstructionPlane(ySteps, xSteps);
float y = min.y;
for (int iy = 0; iy < ySteps; iy++)
{
float x = min.x;
for (int ix = 0; ix < xSteps; ix++)
{
Vector3 pos = new Vector3(x, y, z);
GameObject go = cgc.BlockAtPos(pos);
if(go)
{
BlockItem bi = go.GetComponent<BlockItem>();
if(blocks.Contains(bi))
{
Face f = bi.m_cubeDesc.m_forward;
if (f != null)
{
plane.AddFace(iy, ix, f);
}
}
}
x += 1.0f;
}
plane.MergeColumns(iy);
y += 1.0f;
}
// Merge the construction plane
plane.MergeRows();
faces.AddRange(plane.GetFaces());
z += 1.0f;
}
return faces;
}
You can visualize these construction planes walking back and forth, up and down, left and right and collecting all the faces that are on the plane at each point and merging them into quads. I don’t do any iterations to find the minimal amount of quads for each plane, since the most optimal solution and my brute force crude heuristic approach should not differ all that much.
A little bit of cleanup to do, and if future features need it to do less work, I might move it into native libraries.
When all of this has been done, you collect the faces that belong to each material and add those to sub-meshes of the single mesh item it returns. Keep the material count to a minimum to reduce the draw calls as well.
V 