Chunk Class for Unity Voxel Engine (Example)

Here’s an example of a Chunk class i use in some variants of the engine. This one is a bit experimental but working OK so far.

chunk

 

using UnityEngine;
using System.Collections.Generic;

public enum ChunkState:int {
    Invalid = 0,
    Base = 1,
    Terra = 10,
    ReGen = 11,
    Light = 15,
    Post_Light = 16,
    Mesh = 20,
    Render = 30   

}
public class LightSource {

    public Lux light;
    public int x;
    public int y;
    public int z;
}

public class Chunk {

    //render mesh data
    public List<int> triangles;
    public List<int>[] subtriangles;
    public List<Vector2> uvs;
    public List<Vector3> vertices;
    public List<Color> colours;
    public List<Vector3> normals;
    public List<Vector4> tangents;
    public List<Lux> lightsources;
    public List<IntVect> sunlitBlocks;

    //collision mesh data
    public List<int> col_triangles;
    public List<Vector3> col_vertices;



    //chunk world position
    public int x;
    public int y;
    public int z;

    public GameObject chunkObject;
    public ChunkState state;

 

    public bool AboveReady(ChunkState s) {
      
        if (y == World.yChunkRadius - 1) { return true; }

        int ts = (int)s;
        int cs = (int)World.GetChunkState(x, y + 1, z);

        if (cs == 0) { return true; }
        if (cs >= ts) { return true; }
        return false;
    }

    public bool SurroundingState(ChunkState cstate)
    {
        ChunkState north = World.GetChunkState(x, y, z + 1);
        if ((int)north < (int)cstate && north != ChunkState.Invalid) { return false; }

        ChunkState south = World.GetChunkState(x, y, z - 1);
        if ((int)south < (int)cstate && south != ChunkState.Invalid) { return false; }

        ChunkState east = World.GetChunkState(x + 1, y, z);
        if ((int)east < (int)cstate && east != ChunkState.Invalid) { return false; }

        ChunkState west = World.GetChunkState(x - 1, y, z);
        if ((int)west < (int)cstate && west != ChunkState.Invalid) { return false; }
        if (!AboveReady(cstate)) { return false; }

        /*
        ChunkState stack;
        for (int i = 0; i < World.yChunkRadius; i++)
        {
            stack = World.GetChunkState(x, i, z);
            if ((int)stack < (int)cstate && stack != ChunkState.Invalid) { return false; }
        }
        */


        return true;
    }

    public void Init(int _x, int _y, int _z)
    {
        x = _x; y = _y; z = _z;
        state = ChunkState.Base;

    }
    public void ReBuild() {
        sunlitBlocks = new List<IntVect>();
        col_vertices = new List<Vector3>();
        col_triangles = new List<int>();
        vertices = new List<Vector3>();
        triangles = new List<int>();
        uvs = new List<Vector2>();
        colours = new List<Color>();
        normals = new List<Vector3>();
        tangents = new List<Vector4>();

        subtriangles = new List<int>[Mats.matCount];
        for (int n = 0; n < Mats.matCount; n++) { subtriangles[n] = new List<int>(); }

    }





}

Creating a grid mesh programmatically in Unity 3D

using System;
using System.Collections.Generic;
using UnityEngine;

public static class Grid
{

    public static void Create(bool withCollision)
    {
        GameObject gridObject = new GameObject();
        gridObject.name = "Grid";
        gridObject.transform.position = Vector3.zero;

        List<int> triangles = new List<int>();
        List<Vector3> vertices = new List<Vector3>();
        List<Vector2> uvs = new List<Vector2>();

        List<int> collision_triangles = new List<int>();
        List<Vector3> collision_vertices = new List<Vector3>();

        int vertexIndex = 0;
        int collisionVertexIndex = 0;

        int count = 64; // n+1 grid lines (n = even number)
        int n = count / 2; // halve count for +/- iteration

        float w = 0.05f; //line width
        float s = 1.0f; //width of space

        Vector3 v1;
        Vector3 v2;
        Vector3 v3;
        Vector3 v4;


        //Collision mesh

        if (withCollision)
        {
            v1 = new Vector3(-n, 0, -n);
            v2 = new Vector3(-n, 0, n);
            v3 = new Vector3(n, 0, n);
            v4 = new Vector3(n, 0, -n);

            collision_vertices.Add(v1);
            collision_vertices.Add(v2);
            collision_vertices.Add(v3);
            collision_vertices.Add(v4);

            collision_triangles.Add(collisionVertexIndex);
            collision_triangles.Add((collisionVertexIndex + 1));
            collision_triangles.Add((collisionVertexIndex + 2));
            collision_triangles.Add((collisionVertexIndex + 2));
            collision_triangles.Add((collisionVertexIndex + 3));
            collision_triangles.Add(collisionVertexIndex);

        }


        //Grid mesh
        for (int x = -n; x < n + 1; x++)
        {

            v1 = new Vector3((x * s), 0, -n);
            v2 = new Vector3((x * s), 0, n);
            v3 = new Vector3((x * s) + w, 0, n);
            v4 = new Vector3((x * s) + w, 0, -n);

            vertexIndex = vertices.Count;

            vertices.Add(v1);
            vertices.Add(v2);
            vertices.Add(v3);
            vertices.Add(v4);

            triangles.Add(vertexIndex);
            triangles.Add((vertexIndex + 1));
            triangles.Add((vertexIndex + 2));
            triangles.Add((vertexIndex + 2));
            triangles.Add((vertexIndex + 3));
            triangles.Add(vertexIndex);

            uvs.AddRange(Mats.Generic);

            //back face
            vertexIndex = vertices.Count;

            vertices.Add(v4);
            vertices.Add(v3);
            vertices.Add(v2);
            vertices.Add(v1);

            triangles.Add(vertexIndex);
            triangles.Add((vertexIndex + 1));
            triangles.Add((vertexIndex + 2));
            triangles.Add((vertexIndex + 2));
            triangles.Add((vertexIndex + 3));
            triangles.Add(vertexIndex);

            uvs.AddRange(Mats.Generic);

        }


        for (int z = -n; z < n + 1; z++)
        {

            v1 = new Vector3(-n, 0, (z * s));
            v2 = new Vector3(n, 0, (z * s));
            v3 = new Vector3(n, 0, (z * s) + w);
            v4 = new Vector3(-n, 0, (z * s) + w);

            vertexIndex = vertices.Count;

            vertices.Add(v1);
            vertices.Add(v2);
            vertices.Add(v3);
            vertices.Add(v4);

            triangles.Add(vertexIndex);
            triangles.Add((vertexIndex + 1));
            triangles.Add((vertexIndex + 2));
            triangles.Add((vertexIndex + 2));
            triangles.Add((vertexIndex + 3));
            triangles.Add(vertexIndex);

            uvs.AddRange(Mats.Generic);

            //back face
            vertexIndex = vertices.Count;

            vertices.Add(v4);
            vertices.Add(v3);
            vertices.Add(v2);
            vertices.Add(v1);

            triangles.Add(vertexIndex);
            triangles.Add((vertexIndex + 1));
            triangles.Add((vertexIndex + 2));
            triangles.Add((vertexIndex + 2));
            triangles.Add((vertexIndex + 3));
            triangles.Add(vertexIndex);

            uvs.AddRange(Mats.Generic);

        }

        Mesh mesh = new Mesh();
        mesh.vertices = vertices.ToArray();
        mesh.triangles = triangles.ToArray();
        mesh.uv = uvs.ToArray();

        mesh.RecalculateNormals();
        mesh.Optimize();

        MeshFilter meshFilter = gridObject.AddComponent<MeshFilter>();
        MeshRenderer meshRenderer = gridObject.AddComponent<MeshRenderer>();

        if (withCollision)
        {
            MeshCollider meshCollider = gridObject.AddComponent<MeshCollider>();
            Mesh collision_mesh = new Mesh();
            collision_mesh.vertices = collision_vertices.ToArray();
            collision_mesh.triangles = collision_triangles.ToArray();
            meshCollider.sharedMesh = collision_mesh;
        }

        meshRenderer.material = Mats.Grid();
        meshFilter.sharedMesh = mesh;

    }

}

Some old voxel lighting code

If you look at some of the previous posts you will see this code or a variant of it in use. It may be useful to some. It is very much a hack and i hope to revisit it perhaps in c++ or java.

 public static void SpreadChunkLight(Chunk chunk)
    {

        int x, y, z; byte l;


        using (new Timer("Spread Light"))
        {
            while (chunk.lightSources.Count > 0)
            {
                LightUnit lu = chunk.lightSources.Dequeue();
                x = lu.pos.X; y = lu.pos.Y; z = lu.pos.Z;
                l = lu.val;
                if (IsolatedSunlight(lu.pos.X, lu.pos.Y, lu.pos.Z)) { continue; }

                Spread(x - 1, y, z, l, chunk);
                Spread(x + 1, y, z, l, chunk);
                Spread(x, y + 1, z, l, chunk);
                Spread(x, y - 1, z, l, chunk);
                Spread(x, y, z + 1, l, chunk);
                Spread(x, y, z - 1, l, chunk);
            }
        }


        chunk.State = ChunkState.SpreadLight; chunk.working = false;
        chunk.StateCheck();

    }

    static void Spread(int x, int y, int z, byte l, Chunk pchunk)
    {

        if (l <2) { return; }
        if (World.IsOpaque(x, y, z)) { return; }

        Chunk chunk = World.GetChunkFromHit(x, y, z);
       
        if (chunk == null) { return; }
        byte blocklight = GetBlockLightIndex(x, y, z);
        if (blocklight > (byte)(l - 2)) { return; }


        if (World.loadedChunks >= World.totalChunks)
        {
          
            if (chunk.X != pchunk.X || chunk.Y != pchunk.Y || chunk.Z != pchunk.Z)
            {
             //   Debug.Log("light into chunk");

              //  if (!Pool.toCheckState.Contains(chunk) && chunk.State == ChunkState.Render) { chunk.working = false; chunk.State = ChunkState.SpreadLight; Pool.toCheckState.Enqueue(chunk); }
            }
        }

        lightspreadcount++;
        l = (byte)(l - 1);

        CoreLighting.SetBlockLight(x, y, z, l);

        Spread(x - 1, y, z, l, pchunk);
        Spread(x + 1, y, z, l, pchunk);
        Spread(x, y + 1, z, l, pchunk);
        Spread(x, y - 1, z, l, pchunk);
        Spread(x, y, z + 1, l, pchunk);
        Spread(x, y, z - 1, l, pchunk);

    }

LWJGL OpenGL VBO Issue on Linux

I struggled for a while with some code that generates 2 triangles using indices with more modern OpenGL methods. It worked fine when run on my windows boxes but not on my 2011 MBP running linux. There were no errors or anything i could see (i may not have configured the error checking correctly)

The issue was resolved by replacing the video driver. The xorg driver while it did support some OpenGL functions, did not apparently allow VBO. So if you notice issue with VBO/VBA code on linux where it runs fine on windows, try swapping out your graphics card drivers.

Below is the code used for the loader class thanks to ThinMatrix @ youtube who has some excellent tutorials for lwjgl.

package Engine;

import org.lwjgl.BufferUtils;
import org.lwjgl.opengl.*;
import java.nio.FloatBuffer;
import java.nio.IntBuffer;
import java.util.ArrayList;
import java.util.List;


public class Loader {

    private List<Integer> vaos = new ArrayList<Integer>();
    private List<Integer> vbos = new ArrayList<Integer>();

    public Model LoadToVAO(float[] points, int[]indicies)throws OpenGLException
    {
        int vaoID = CreateVAO();
        BindIndiciesBuffer(indicies);
        StoreDataInAttributeList(0,points);
        UnBindVAO();
        return new Model(vaoID,indicies.length);
    }

    private void BindIndiciesBuffer(int[] indicies){

        int vboID= GL15.glGenBuffers();
        vbos.add(vboID);
        GL15.glBindBuffer(GL15.GL_ELEMENT_ARRAY_BUFFER,vboID);
        IntBuffer buffer  =StoreDataInIntBuffer(indicies);
        GL15.glBufferData(GL15.GL_ELEMENT_ARRAY_BUFFER,buffer, GL15.GL_STATIC_DRAW);
    }
    private IntBuffer StoreDataInIntBuffer(int[] data){
        IntBuffer buffer = BufferUtils.createIntBuffer(data.length);
        buffer.put(data);
        buffer.flip();
        return buffer;

    }
    private int CreateVAO() throws OpenGLException {

        int vaoID = GL30.glGenVertexArrays();
        vaos.add(vaoID);
        GL30.glBindVertexArray(vaoID);
        return vaoID;
    }

    private void StoreDataInAttributeList(int attributeNumber, float[] data) throws OpenGLException{

        int vboID = GL15.glGenBuffers();
        vbos.add(vboID);

        GL15.glBindBuffer(GL15.GL_ARRAY_BUFFER, vboID);
        FloatBuffer buffer = storeDataInFloatBuffer(data);

        GL15.glBufferData(GL15.GL_ARRAY_BUFFER, buffer, GL15.GL_STATIC_DRAW);
        GL20.glVertexAttribPointer(attributeNumber, 3, GL11.GL_FLOAT, false, 0, 0); //stride here maybe
        GL15.glBindBuffer(GL15.GL_ARRAY_BUFFER, 0);
    }

    private FloatBuffer storeDataInFloatBuffer(float[] data) {
        FloatBuffer buffer = BufferUtils.createFloatBuffer(data.length);
        buffer.put(data);
        buffer.flip();
        return buffer;
    }

    private void UnBindVAO() {
        GL30.glBindVertexArray(0);
    }

    public void Clean() {
        for (int vao : vaos) {
            GL30.glDeleteVertexArrays(vao);
        }

        for (int vbo : vbos) {
            GL15.glDeleteBuffers(vbo);
        }
    }

}

Compressing Voxel Data

My first attempt at saving and loading voxel data seems to work reasonably well. It manages to save approx 4 million voxel points in about 64kb which seems reasonable. The compression ratio would decrease as the usefulness of RLE (Run Length Encoding) wanes due to excessive fragmentation. What remains to be done is to only save those blocks that have changed along with the seed. I’m not building never ending minecraft type worlds so i’m dealing with known quantities here. Currently it just saves and loads everything, surprising quickly.

public static void SaveWorld()
    {
        string saveFile = Directory.GetCurrentDirectory() + @"SavesSave000.txt";
        byte[] wb = new byte[World.blocks.Length];       
        int i = 0;
        for (int x = 0; x < World.maxX - 1; x++)
        {
            for (int y = 0; y < World.maxY - 1; y++)
            {
                for (int z = 0; z < World.maxZ - 1; z++)
                {
                    wb[i] = (byte)World.blocks[x, y, z].blocktype;
                    i++;
                }
            }
        }

        wb = CLZF2.Compress(wb);
        using (BinaryWriter writer = new BinaryWriter(File.Open(saveFile, FileMode.Create)))
        {
            writer.Write(wb);
        }
    }
/*
 * Improved version to C# LibLZF Port:
 * Copyright (c) 2010 Roman Atachiants 
 *
 * Original CLZF Port:
 * Copyright (c) 2005 Oren J. Maurice 
 *
 * Original LibLZF Library  Algorithm:
 * Copyright (c) 2000-2008 Marc Alexander Lehmann 
 *
 * Redistribution and use in source and binary forms, with or without modifica-
 * tion, are permitted provided that the following conditions are met:
 *
 *   1.  Redistributions of source code must retain the above copyright notice,
 *       this list of conditions and the following disclaimer.
 *
 *   2.  Redistributions in binary form must reproduce the above copyright
 *       notice, this list of conditions and the following disclaimer in the
 *       documentation and/or other materials provided with the distribution.
 *
 *   3.  The name of the author may not be used to endorse or promote products
 *       derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR IMPLIED
 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MER-
 * CHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO
 * EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPE-
 * CIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTH-
 * ERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
 * OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * Alternatively, the contents of this file may be used under the terms of
 * the GNU General Public License version 2 (the "GPL"), in which case the
 * provisions of the GPL are applicable instead of the above. If you wish to
 * allow the use of your version of this file only under the terms of the
 * GPL and not to allow others to use your version of this file under the
 * BSD license, indicate your decision by deleting the provisions above and
 * replace them with the notice and other provisions required by the GPL. If
 * you do not delete the provisions above, a recipient may use your version
 * of this file under either the BSD or the GPL.
 */
using System;

/* Benchmark with Alice29 Canterbury Corpus
        ---------------------------------------
        (Compression) Original CLZF C#
        Raw = 152089, Compressed = 101092
         8292,4743 ms.
        ---------------------------------------
        (Compression) My LZF C#
        Raw = 152089, Compressed = 101092
         33,0019 ms.
        ---------------------------------------
        (Compression) Zlib using SharpZipLib
        Raw = 152089, Compressed = 54388
         8389,4799 ms.
        ---------------------------------------
        (Compression) QuickLZ C#
        Raw = 152089, Compressed = 83494
         80,0046 ms.
        ---------------------------------------
        (Decompression) Original CLZF C#
        Decompressed = 152089
         16,0009 ms.
        ---------------------------------------
        (Decompression) My LZF C#
        Decompressed = 152089
         15,0009 ms.
        ---------------------------------------
        (Decompression) Zlib using SharpZipLib
        Decompressed = 152089
         3577,2046 ms.
        ---------------------------------------
        (Decompression) QuickLZ C#
        Decompressed = 152089
         21,0012 ms.
    */


/// 
/// Improved C# LZF Compressor, a very small data compression library. The compression algorithm is extremely fast.
public static class CLZF2
{
	private static readonly uint HLOG = 14;
	private static readonly uint HSIZE = (1 << 14);
	private static readonly uint MAX_LIT = (1 << 5);
	private static readonly uint MAX_OFF = (1 << 13);
	private static readonly uint MAX_REF = ((1 << 8) + (1 << 3));
	
	/// 
	/// Hashtable, that can be allocated only once
	/// 
	private static readonly long[] HashTable = new long[HSIZE];
	
	// Compresses inputBytes
	public static byte[] Compress(byte[] inputBytes)
	{
		// Starting guess, increase it later if needed
		int outputByteCountGuess = inputBytes.Length * 2;
		byte[] tempBuffer = new byte[outputByteCountGuess];
		int byteCount = lzf_compress (inputBytes, ref tempBuffer);
		
		// If byteCount is 0, then increase buffer and try again
		while (byteCount == 0)
		{
			outputByteCountGuess *=2;
			tempBuffer = new byte[outputByteCountGuess];
			byteCount = lzf_compress (inputBytes, ref tempBuffer);
		}
		
		byte[] outputBytes = new byte[byteCount];
		Buffer.BlockCopy(tempBuffer, 0, outputBytes, 0, byteCount);
		return outputBytes;
	}
	
	// Decompress outputBytes
	public static byte[] Decompress(byte[] inputBytes)
	{
		// Starting guess, increase it later if needed
		int outputByteCountGuess = inputBytes.Length * 2;
		byte[] tempBuffer = new byte[outputByteCountGuess];
		int byteCount = lzf_decompress (inputBytes, ref tempBuffer);
		
		// If byteCount is 0, then increase buffer and try again
		while (byteCount == 0)
		{
			outputByteCountGuess *=2;
			tempBuffer = new byte[outputByteCountGuess];
			byteCount = lzf_decompress (inputBytes, ref tempBuffer);
		}
		
		byte[] outputBytes = new byte[byteCount];
		Buffer.BlockCopy(tempBuffer, 0, outputBytes, 0, byteCount);
		return outputBytes;
	}
	
	/// 
	/// Compresses the data using LibLZF algorithm
	/// 
	/// Reference to the data to compress
	/// Reference to a buffer which will contain the compressed data
	/// The size of the compressed archive in the output buffer
	public static int lzf_compress(byte[] input, ref byte[] output)
	{
		int inputLength = input.Length;
		int outputLength = output.Length;
		
		Array.Clear(HashTable, 0, (int)HSIZE);
		
		long hslot;
		uint iidx = 0;
		uint oidx = 0;
		long reference;
		
		uint hval = (uint)(((input[iidx]) << 8) | input[iidx + 1]); // FRST(in_data, iidx);
		long off;
		int lit = 0;
		
		for (; 😉
		{
			if (iidx < inputLength - 2)
			{
				hval = (hval << 8) | input[iidx + 2];
				hslot = ((hval ^ (hval <> (int)(((3 * 8 - HLOG)) - hval * 5) & (HSIZE - 1));
				reference = HashTable[hslot];
				HashTable[hslot] = (long)iidx;
				
				
				if ((off = iidx - reference - 1) < MAX_OFF
				    && iidx + 4  0
				    && input[reference + 0] == input[iidx + 0]
				    && input[reference + 1] == input[iidx + 1]
				    && input[reference + 2] == input[iidx + 2]
				    )
				{
					/* match found at *reference++ */
					uint len = 2;
					uint maxlen = (uint)inputLength - iidx - len;
					maxlen = maxlen > MAX_REF ? MAX_REF : maxlen;
					
					if (oidx + lit + 1 + 3 >= outputLength)
						return 0;
					
					do
						len++;
					while (len < maxlen && input[reference + len] == input[iidx + len]);
					
					if (lit != 0)
					{
						output[oidx++] = (byte)(lit - 1);
						lit = -lit;
						do
							output[oidx++] = input[iidx + lit];
						while ((++lit) != 0);
					}
					
					len -= 2;
					iidx++;
					
					if (len > 8) + (len <> 8) + (7 << 5));
						output[oidx++] = (byte)(len - 7);
					}
					
					output[oidx++] = (byte)off;
					
					iidx += len - 1;
					hval = (uint)(((input[iidx]) << 8) | input[iidx + 1]);
					
					hval = (hval << 8) | input[iidx + 2];
					HashTable[((hval ^ (hval <> (int)(((3 * 8 - HLOG)) - hval * 5) & (HSIZE - 1))] = iidx;
					iidx++;
					
					hval = (hval << 8) | input[iidx + 2];
					HashTable[((hval ^ (hval <> (int)(((3 * 8 - HLOG)) - hval * 5) & (HSIZE - 1))] = iidx;
					iidx++;
					continue;
				}
			}
			else if (iidx == inputLength)
				break;
			
			/* one more literal byte we must copy */
			lit++;
			iidx++;
			
			if (lit == MAX_LIT)
			{
				if (oidx + 1 + MAX_LIT >= outputLength)
					return 0;
				
				output[oidx++] = (byte)(MAX_LIT - 1);
				lit = -lit;
				do
					output[oidx++] = input[iidx + lit];
				while ((++lit) != 0);
			}
		}
		
		if (lit != 0)
		{
			if (oidx + lit + 1 >= outputLength)
				return 0;
			
			output[oidx++] = (byte)(lit - 1);
			lit = -lit;
			do
				output[oidx++] = input[iidx + lit];
			while ((++lit) != 0);
		}
		
		return (int)oidx;
	}
	
	
	/// 
	/// Decompresses the data using LibLZF algorithm
	/// 
	/// Reference to the data to decompress
	/// Reference to a buffer which will contain the decompressed data
	/// Returns decompressed size
	public static int lzf_decompress(byte[] input, ref byte[] output)
	{
		int inputLength = input.Length;
		int outputLength = output.Length;
		
		uint iidx = 0;
		uint oidx = 0;
		
		do
		{
			uint ctrl = input[iidx++];
			
			if (ctrl < (1 < outputLength)
				{
					//SET_ERRNO (E2BIG);
					return 0;
				}
				
				do
					output[oidx++] = input[iidx++];
				while ((--ctrl) != 0);
			}
			else /* back reference */
			{
				uint len = ctrl >> 5;
				
				int reference = (int)(oidx - ((ctrl & 0x1f) < outputLength)
				{
					//SET_ERRNO (E2BIG);
					return 0;
				}
				
				if (reference < 0)
				{
					//SET_ERRNO (EINVAL);
					return 0;
				}
				
				output[oidx++] = output[reference++];
				output[oidx++] = output[reference++];
				
				do
					output[oidx++] = output[reference++];
				while ((--len) != 0);
			}
		}
		while (iidx < inputLength);
		
		return (int)oidx;
	}
	
}

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