Hey all you advanced coders out there.
If any of you know what and how the greedy algorithm works it would be greatly appreciated if you shot me some of your knowledge, as I have been searching for the past 4 hours and yet I have returned with nothing.
Let me explain what I am trying to do. In my voxel “engine”, I wish to collect verticies and combine faces for both the rendered mesh and the collision mesh to give me more leeway in my future programming ventures. In short, for optimization.
I have stumbled across a goldmine of information with this piece of code :
public void RenderWithVAOGreedy(ShaderProgram program, bool draw = true)
{
// This greedy algorithm is converted from PHP to C# from this article:
// http://0fps.wordpress.com/2012/06/30/meshing-in-a-minecraft-game/
//
// The original source code can be found here:
// https://github.com/mikolalysenko/mikolalysenko.github.com/blob/gh-pages/MinecraftMeshes/js/greedy.js
if (chunkVAO == null)
{
List<Vector3> vertices = new List<Vector3>();
List<int> elements = new List<int>();
for (int d = 0; d < 3; d++)
{
int i, j, k, l, w, h, u = (d + 1) % 3, v = (d + 2) % 3;
int[] x = new int[3];
int[] q = new int[3];
bool[] mask = new bool[32 * 32];
q[d] = 1;
for (x[d] = -1; x[d] < 32; )
{
// Compute the mask
int n = 0;
for (x[v] = 0; x[v] < 32; ++x[v])
{
for (x[u] = 0; x[u] < 32; ++x[u])
{
mask[n++] = (0 <= x[d] ? data(x[0], x[1], x[2]) : false) !=
(x[d] < 32 - 1 ? data(x[0] + q[0], x[1] + q[1], x[2] + q[2]) : false);
}
}
// Increment x[d]
++x[d];
// Generate mesh for mask using lexicographic ordering
n = 0;
for (j = 0; j < 32; ++j)
{
for (i = 0; i < 32; )
{
if (mask[n])
{
// Compute width
for (w = 1; i + w < 32 mask[n + w]; ++w) ;
// Compute height (this is slightly awkward
var done = false;
for (h = 1; j + h < 32; ++h)
{
for (k = 0; k < w; ++k)
{
if (!mask[n + k + h * 32])
{
done = true;
break;
}
}
if (done) break;
}
// Add quad
x[u] = i; x[v] = j;
int[] du = new int[3];
int[] dv = new int[3];
du[u] = w;
dv[v] = h;
AddFace(new Vector3(x[0], x[1], x[2]),
new Vector3(x[0] + du[0], x[1] + du[1], x[2] + du[2]),
new Vector3(x[0] + du[0] + dv[0], x[1] + du[1] + dv[1], x[2] + du[2] + dv[2]),
new Vector3(x[0] + dv[0], x[1] + dv[1], x[2] + dv[2]), vertices, elements);
// Zero-out mask
for (l = 0; l < h; ++l)
{
for (k = 0; k < w; ++k)
{
mask[n + k + l * 32] = false;
}
}
// Increment counters and continue
i += w; n += w;
}
else
{
++i; ++n;
}
}
}
}
}
Vector3[] vertex = vertices.ToArray();
int[] element = elements.ToArray();
Vector3[] normals = OpenGL.Geometry.CalculateNormals(vertex, element);
chunkVAO = new VAO(program, new VBO<Vector3>(vertex), new VBO<Vector3>(normals), new VBO<int>(element, BufferTarget.ElementArrayBuffer, BufferUsageHint.StaticRead));
}
if (draw)
{
program["model_matrix"].SetValue(ModelMatrix);
chunkVAO.Draw();
}
}
private bool data(int x, int y, int z)
{
return voxelData[x + 32 * y + 32 * 32 * z] != 0;
}
However, so much of it I do not understand or just cannot wrap my head around what goes where, because as you can see… It is only barely documented. And I realize there are a few non-Unity language pieces in there.
This example is using a flat array, whereas I would like to somehow re-arrange it to work my chunk system in which Blocks are in the form chunkBlocks[x,y,z].
I realize that this is talking in terms of 2D space and is a method for finding the least amount of elements and then using that one (although not always optimal) and this is talking in terms of quads rather than triangles.
I’m not asking for a specific styled re-write just for me(although that would be amazing), I am just asking for some help with understanding what exactly it does.
I will be working on this trying to understand for the next few days, but if you can help me in any way I would be greatly appreciative.
Thanks
Myhi
However if not that is completely understandable and I shall keep hacking away at this code.