Skip to content

Instantly share code, notes, and snippets.

@CriDos

CriDos/MergedFaceMeshBuilder

Created November 2, 2019 09:30
Show Gist options
  • Save CriDos/7da695b51b6c56ee49bee80a06b7cf52 to your computer and use it in GitHub Desktop.
Save CriDos/7da695b51b6c56ee49bee80a06b7cf52 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
MergedFaceMeshBuilder
using System.Collections.Generic;
using HardDev.Engine.Experiment.Types;
using HardDev.Engine.Experiment.Voxel.BlockImpl;
using HardDev.Engine.Experiment.Voxel.Directions;
using UnityEngine;
namespace HardDev.Engine.Experiment.Voxel.ChunkImpl
{
public static class MergedFaceMeshBuilder
{
private static readonly bool[] BackFaceStates = {true, false};
// https://github.com/roboleary/GreedyMesh/blob/master/src/mygame/Main.java
public static void ReduceMesh(Chunk chunk, List<Vector3> vertices, List<int> triangles)
{
if (chunk.IsEmpty())
return;
const byte CHUNK_SIZE = ChunkStatic.CHUNK_SIZE;
/*
* These are just working variables for the algorithm - almost all taken
* directly from Mikola Lysenko's javascript implementation.
*/
var x = new[] {0, 0, 0};
var q = new[] {0, 0, 0};
var du = new[] {0, 0, 0};
var dv = new[] {0, 0, 0};
/*
* We create a mask - this will contain the groups of matching voxel faces
* as we proceed through the chunk in 6 directions - once for each face.
*/
var mask = new ushort[CHUNK_SIZE * CHUNK_SIZE];
/**
* This loop runs twice, and the inner loop 3 times - totally 6 iterations - one for each
* voxel face.
*/
foreach (var isBackFace in BackFaceStates)
{
/*
* We sweep over the 3 dimensions - most of what follows is well described by Mikola Lysenko
* in his post - and is ported from his Javascript implementation. Where this implementation
* diverges, I've added commentary.
*/
for (var axis = 0; axis < 3; axis++)
{
var u = (axis + 1) % 3;
var v = (axis + 2) % 3;
x[0] = 0;
x[1] = 0;
x[2] = 0;
q[0] = 0;
q[1] = 0;
q[2] = 0;
q[axis] = 1;
/*
* Here we're keeping track of the face that we're meshing.
*/
var currentFace = FaceEnum.Back;
switch (axis)
{
case 0:
currentFace = isBackFace ? FaceEnum.Back : FaceEnum.Front;
break;
case 1:
currentFace = isBackFace ? FaceEnum.Bottom : FaceEnum.Top;
break;
case 2:
currentFace = isBackFace ? FaceEnum.Left : FaceEnum.Right;
break;
}
/*
* We move through the dimension from front to back
*/
for (x[axis] = -1; x[axis] < CHUNK_SIZE;)
{
/*
* -------------------------------------------------------------------
* We compute the mask
* -------------------------------------------------------------------
*/
var n = 0;
for (x[v] = 0; x[v] < CHUNK_SIZE; x[v]++)
{
for (x[u] = 0; x[u] < CHUNK_SIZE; x[u]++)
{
/*
* Here we retrieve two voxel faces for comparison.
*/
var currentBlockId = BlockStatic.AIR_ID;
if (x[axis] >= 0)
{
var localPos = new Vector3Byte(x[0], x[1], x[2]);
if (!chunk.GetBlock(localPos).IsAir() && !chunk.CheckExistNeighborBlock(currentFace, localPos))
currentBlockId = 1;
}
var nextBlockId = BlockStatic.AIR_ID;
if (x[axis] < CHUNK_SIZE - 1)
{
var localPos = new Vector3Byte(x[0] + q[0], x[1] + q[1], x[2] + q[2]);
if (!chunk.GetBlock(localPos).IsAir() && !chunk.CheckExistNeighborBlock(currentFace, localPos))
nextBlockId = 1;
}
/*
* Note that we're using the equals function in the voxel face class here, which lets the faces
* be compared based on any number of attributes.
*
* Also, we choose the face to add to the mask depending on whether we're moving through on a backface or not.
*/
if (currentBlockId != BlockStatic.AIR_ID && nextBlockId != BlockStatic.AIR_ID && currentBlockId == nextBlockId)
mask[n++] = BlockStatic.AIR_ID;
else if (isBackFace)
mask[n++] = nextBlockId;
else
mask[n++] = currentBlockId;
}
}
x[axis]++;
/*
* Now we generate the mesh for the mask
*/
n = 0;
for (var j = 0; j < CHUNK_SIZE; j++)
{
byte i;
for (i = 0; i < CHUNK_SIZE;)
{
if (mask[n] != BlockStatic.AIR_ID)
{
/*
* We compute the width
*/
byte width = 1;
while (i + width < CHUNK_SIZE && mask[n + width] != BlockStatic.AIR_ID && mask[n + width] == mask[n])
{
++width;
}
/*
* Then we compute height
*/
var done = false;
byte height;
for (height = 1; j + height < CHUNK_SIZE; height++)
{
for (var k = 0; k < width; k++)
{
if (mask[n + k + height * CHUNK_SIZE] == BlockStatic.AIR_ID ||
mask[n + k + height * CHUNK_SIZE] != mask[n])
{
done = true;
break;
}
}
if (done)
break;
}
/*
* Add quad
*/
x[u] = i;
x[v] = j;
du[0] = 0;
du[1] = 0;
du[2] = 0;
du[u] = width;
dv[0] = 0;
dv[1] = 0;
dv[2] = 0;
dv[v] = height;
/*
* And here we call the quad function in order to render a merged quad in the scene.
*
* We pass mask[n] to the function, which is an instance of the VoxelFace class containing
* all the attributes of the face - which allows for variables to be passed to shaders - for
* example lighting values used to create ambient occlusion.
*/
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,
triangles,
isBackFace);
/*
* We zero out the mask
*/
for (var l = 0; l < height; ++l)
{
for (var k = 0; k < width; ++k)
{
mask[n + k + l * CHUNK_SIZE] = BlockStatic.AIR_ID;
}
}
/*
* And then finally increment the counters and continue
*/
i += width;
n += width;
}
else
{
i++;
n++;
}
}
}
}
}
}
}
private static void AddFace(Vector3 v1, Vector3 v2, Vector3 v3, Vector3 v4, List<Vector3> vertices, List<int> triangles, bool backFace)
{
var index = vertices.Count;
if (backFace)
{
vertices.Add(v4);
vertices.Add(v3);
vertices.Add(v2);
vertices.Add(v1);
triangles.Add(index + 0);
triangles.Add(index + 1);
triangles.Add(index + 2);
triangles.Add(index + 0);
triangles.Add(index + 2);
triangles.Add(index + 3);
}
else
{
vertices.Add(v1);
vertices.Add(v2);
vertices.Add(v3);
vertices.Add(v4);
triangles.Add(index + 0);
triangles.Add(index + 1);
triangles.Add(index + 2);
triangles.Add(index + 0);
triangles.Add(index + 2);
triangles.Add(index + 3);
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment