Mesh Optimization

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.

meshopt-1

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

5 comments

  1. good · January 31, 2016

    good work man

    Like

  2. Krythic · July 25, 2016

    Do you have a github page or something, where I can view the code together with your Chunk class and Mesh class? Thanks.

    Like

    • ndev · July 26, 2016

      Not currently. The Mesh class is a part of UnityEngine. I will post a copy of a Chunk class for reference but it’s really just a place to store all the related data; vertices, triangles, uvs, colour & sub-material data for the final mesh.

      Like

  3. Recs · October 25, 2017

    Are you try to paste this code to Unity? Where Type of List in function AddFace? Where declaration of du and dv in C# example?

    Like

    • ndev · October 25, 2017

      The WordPress code format plugin broke the formatting. You can scroll to the right and see it. Or below;

      for (h = 1; j + h < size; ++h)
      {
      for (k = 0; k -1)
      {
      du[u] = w;
      dv[v] = h;
      }
      else
      {
      flip = true;
      c = -c;
      du[u] = w;
      dv[v] = h;
      }

      AddFace is using vector3 list for vertices and integer list (elements) for triangles. Each chunk stores these lists prior to rendering.

      Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s