Below is my custom version of a greedy mesh optimizer for voxel data in Unity3d translated from JavaScript to c# using the original awesome mind bending code of Mikola Lysenko.

This is useful if you need to use mesh for collision data and it can drastically improve speed when building/rebuilding game objects. I’ve added a method of excluding some data from generating mesh which is great for blocks which the player should fall through.

Don’t forget to include the original copyright if you use it in your project or share it. Feel free to also credit this site if you wish.

It’s worth noting that there is a kind of “bug” in Mikola’s code which is possibly only apparent when used with Unity3d/c# which returns incorrect normals on 3/6 sides of the cube. This is corrected in the c# below.

If you have a more efficient mesh optimizer you’d like to share. please do! dev@nuzly.com

c#

// The MIT License (MIT)
//
// Copyright (c) 2012-2013 Mikola Lysenko
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.
public static Mesh ReduceMesh(Chunk chunk)
{
List vertices = new List();
List elements = new List();
List uvs = new List();
List colours = new List();
List noCollision = World.noCollision;
int size = World.CHUNK_SIZE;
//Sweep over 3-axes
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];
int[] mask = new int[(size + 1) * (size + 1)];
q[d] = 1;
for (x[d] = -1; x[d] < size; )
{
// Compute the mask
int n = 0;
for (x[v] = 0; x[v] < size; ++x[v])
{
for (x[u] = 0; x[u] < size; ++x[u], ++n)
{
int a = 0; if (0 <= x[d]) { a = (int)World.GetBlock(chunk, x[0], x[1], x[2]).Type; if (noCollision.IndexOf(a)!=-1) { a = 0; } }
int b = 0; if (x[d] < size - 1) { b = (int)World.GetBlock(chunk, x[0] + q[0], x[1] + q[1], x[2] + q[2]).Type; if (noCollision.IndexOf(b) != -1) { b = 0; } } if (a != -1 && b != -1 && a == b) { mask[n] = 0; } else if (a > 0)
{
a = 1;
mask[n] = a;
}
else
{
b = 1;
mask[n] = -b;
}
}
}
// Increment x[d]
++x[d];
// Generate mesh for mask using lexicographic ordering
n = 0;
for (j = 0; j < size; ++j)
{
for (i = 0; i < size; ) { var c = mask[n]; if (c > -3)
{
// Compute width
for (w = 1; c == mask[n + w] && i + w < size; ++w) { }
// Compute height
bool done = false;
for (h = 1; j + h < size; ++h)
{
for (k = 0; k < w; ++k) { if (c != mask[n + k + h * size]) { done = true; break; } } if (done) break; } // Add quad bool flip = false; x[u] = i; x[v] = j; int[] du = new int[3]; int[] dv = new int[3]; if (c > -1)
{
du[u] = w;
dv[v] = h;
}
else
{
flip = true;
c = -c;
du[u] = w;
dv[v] = h;
}
Vector3 v1 = new Vector3(x[0], x[1], x[2]);
Vector3 v2 = new Vector3(x[0] + du[0], x[1] + du[1], x[2] + du[2]);
Vector3 v3 = new Vector3(x[0] + du[0] + dv[0], x[1] + du[1] + dv[1], x[2] + du[2] + dv[2]);
Vector3 v4 = new Vector3(x[0] + dv[0], x[1] + dv[1], x[2] + dv[2]);
if (c > 0 && !flip)
{
AddFace(v1, v2, v3, v4, vertices, elements, 0);
}
if (flip)
{
AddFace(v4, v3, v2, v1, vertices, elements, 0);
}
// Zero-out mask
for (l = 0; l < h; ++l)
for (k = 0; k < w; ++k)
{
mask[n + k + l * size] = 0;
}
// Increment counters and continue
i += w; n += w;
}
else
{
++i;
++n;
}
}
}
}
}
Mesh mesh = new Mesh();
mesh.Clear();
mesh.vertices = vertices.ToArray();
mesh.triangles = elements.ToArray();
mesh.RecalculateBounds();
mesh.RecalculateNormals();
return mesh;
}
private static void AddFace(Vector3 v1, Vector3 v2, Vector3 v3, Vector3 v4, List vertices, List elements, int order)
{
if (order == 0)
{
int index = vertices.Count;
vertices.Add(v1);
vertices.Add(v2);
vertices.Add(v3);
vertices.Add(v4);
elements.Add(index);
elements.Add(index + 1);
elements.Add(index + 2);
elements.Add(index + 2);
elements.Add(index + 3);
elements.Add(index);
}
if (order == 1)
{
int index = vertices.Count;
vertices.Add(v1);
vertices.Add(v2);
vertices.Add(v3);
vertices.Add(v4);
elements.Add(index);
elements.Add(index + 3);
elements.Add(index + 2);
elements.Add(index + 2);
elements.Add(index + 1);
elements.Add(index);
}

JavaScript

// The MIT License (MIT)
//
// Copyright (c) 2012-2013 Mikola Lysenko
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.
function GreedyMesh(volume, dims) {
function f(i,j,k) {
return volume[i + dims[0] * (j + dims[1] * k)];
}
//Sweep over 3-axes
var quads = [];
for(var d=0; d<3; ++d) {
var i, j, k, l, w, h
, u = (d+1)%3
, v = (d+2)%3
, x = [0,0,0]
, q = [0,0,0]
, mask = new Int32Array(dims[u] * dims[v]);
q[d] = 1;
for(x[d]=-1; x[d]<dims[d]; ) {
//Compute mask
var n = 0;
for(x[v]=0; x[v]<dims[v]; ++x[v])
for(x[u]=0; x[u]<dims[u]; ++x[u]) {
mask[n++] =
(0 <= x[d] ? f(x[0], x[1], x[2]) : false) !=
(x[d] < dims[d]-1 ? f(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<dims[v]; ++j)
for(i=0; i<dims[u]; ) {
if(mask[n]) {
//Compute width
for(w=1; mask[n+w] && i+w<dims[u]; ++w) {
}
//Compute height (this is slightly awkward
var done = false;
for(h=1; j+h<dims[v]; ++h) {
for(k=0; k<w; ++k) {
if(!mask[n+k+h*dims[u]]) {
done = true;
break;
}
}
if(done) {
break;
}
}
//Add quad
x[u] = i; x[v] = j;
var du = [0,0,0]; du[u] = w;
var dv = [0,0,0]; dv[v] = h;
quads.push([
[x[0], x[1], x[2] ]
, [x[0]+du[0], x[1]+du[1], x[2]+du[2] ]
, [x[0]+du[0]+dv[0], x[1]+du[1]+dv[1], x[2]+du[2]+dv[2]]
, [x[0] +dv[0], x[1] +dv[1], x[2] +dv[2]]
]);
//Zero-out mask
for(l=0; l<h; ++l)
for(k=0; k<w; ++k) {
mask[n+k+l*dims[u]] = false;
}
//Increment counters and continue
i += w; n += w;
} else {
++i; ++n;
}
}
}
}
return quads;
}