Hi, I’m trying to make a custom Voxel Engine for my game which is little similar to Minecraft (at least in cubic map). I watched several playlist about making Minecraft on youtube, but most of them do not implement Greedy Meshing, and use Tasks for multi-threading. There was one engine that i took fancy to, but it’s too complex for my game, and as i understand from authors youtube videos, he has reduced usage of virtual methods to increase performance, but it made engine less flexible. At least it’s not flexible enough for my needs.
Long story short - I started to make my own little engine. I took something from youtube tutorirals, something from other articles, and glued it all in ChatGPT. Yeah… As expected, i stumbled upon a problem when i wanted to implement Greedy Meshing algorithm from this article Greedy Meshing for Vertex Colored Voxels In Unity
Simple generation via ‘ChunkMeshDataGenerationJob’ works fine.
Problem is - when generating mesh via ‘ChunkGreedyMeshDataGenerationJob’ - it does not generate properly.
Here is my code. There are only 5 scripts, so it’s not so much. I will add ChatGPT explanations about Greedy meshing part.
Block.cs
using System;
using Unity.Collections;
using Unity.Mathematics;
namespace HAELENT
{
/// <summary>
/// Enum representing the different types of blocks in the voxel engine.
/// </summary>
public enum BlockType
{
AIR, // Represents an empty space
STONE, // Represents a stone block
DIRT, // Represents a dirt block
GRASS, // Represents a grass block
WATER, // Represents a water block
SAND, // Represents a sand block
WOOD, // Represents a wood block
LEAFS, // Represents leaves
ERROR, // Represents an error block (used for debugging or invalid states)
HIDDEN // Represents an hidden block (used for Greedy Meshing)
}
/// <summary>
/// Struct representing a single block in the voxel engine.
/// </summary>
public struct Block
{
/// <summary>
/// The type of the block, defined by the BlockType enum.
/// </summary>
public BlockType type;
}
public struct BlockData
{
[ReadOnly]
public static readonly int3[] Vertices = new int3[8]
{
new int3(0, 0, 0), //[0]
new int3(1, 0, 0), //[1]
new int3(1, 1, 0), //[2]
new int3(0, 1, 0), //[3]
new int3(0, 0, 1), //[4]
new int3(1, 0, 1), //[5]
new int3(1, 1, 1), //[6]
new int3(0, 1, 1) //[7]
};
[ReadOnly]
public static readonly int[] Triangles = new int[36] {
0, 2, 1, 0, 3, 2, // Front
5, 6, 4, 4, 6, 7, // Back
4, 7, 0, 0, 7, 3, // Left
1, 2, 5, 5, 2, 6, // Right
3, 7, 2, 2, 7, 6, // Top
4, 0, 5, 5, 0, 1 // Bottom
};
}
}
Chunk.cs
using Unity.Collections;
using Unity.Mathematics;
namespace HAELENT
{
/// <summary>
/// Represents a chunk of blocks in the voxel engine.
/// </summary>
public struct Chunk
{
/// <summary>
/// The array of blocks within this chunk.
/// </summary>
public NativeArray<Block> blocks;
/// <summary>
/// The size of the chunk in 3D space (width, height, depth).
/// </summary>
public int3 size;
/// <summary>
/// Initializes a new chunk with the specified size.
/// </summary>
/// <param name="size">The size of the chunk.</param>
public Chunk(int3 size)
{
this.size = size;
blocks = new NativeArray<Block>(size.x * size.y * size.z, Allocator.Persistent);
}
/// <summary>
/// Disposes of the chunk, releasing its resources.
/// </summary>
public void Dispose()
{
if (blocks.IsCreated)
blocks.Dispose();
}
/// <summary>
/// Gets the block at the specified coordinates within the chunk.
/// </summary>
/// <param name="x">The x-coordinate.</param>
/// <param name="y">The y-coordinate.</param>
/// <param name="z">The z-coordinate.</param>
/// <returns>The block at the specified coordinates.</returns>
public Block GetBlock(int x, int y, int z)
{
int index = x + size.x * (y + size.y * z);
return blocks[index];
}
/// <summary>
/// Sets the block at the specified coordinates within the chunk.
/// </summary>
/// <param name="x">The x-coordinate.</param>
/// <param name="y">The y-coordinate.</param>
/// <param name="z">The z-coordinate.</param>
/// <param name="block">The block to set.</param>
public void SetBlock(int x, int y, int z, Block block)
{
int index = x + size.x * (y + size.y * z);
blocks[index] = block;
}
}
}
ChunkMeshDataGenerationJob.cs
using Unity.Burst;
using Unity.Collections;
using Unity.Jobs;
using Unity.Mathematics;
using UnityEngine;
namespace HAELENT
{
/// <summary>
/// Job to generate mesh data for a chunk of blocks.
/// </summary>
[BurstCompile]
public struct ChunkMeshDataGenerationJob : IJob
{
/// <summary>
/// The array of blocks to generate the mesh for.
/// </summary>
[ReadOnly] public NativeArray<Block> blocks;
/// <summary>
/// The size of the chunk in 3D space (width, height, depth).
/// </summary>
public int3 chunkSize;
/// <summary>
/// The list of vertices to be populated by the job.
/// </summary>
public NativeList<float3> vertices;
/// <summary>
/// The list of triangles to be populated by the job.
/// </summary>
public NativeList<int> triangles;
/// <summary>
/// Executes the job to generate the mesh data.
/// </summary>
public void Execute()
{
for (int x = 0; x < chunkSize.x; x++)
{
for (int y = 0; y < chunkSize.y; y++)
{
for (int z = 0; z < chunkSize.z; z++)
{
int index = x + chunkSize.x * (y + chunkSize.y * z);
if (blocks[index].type != BlockType.AIR)
{
// Add cube mesh for solid block
AddCubeMesh(new float3(x, y, z));
}
}
}
}
}
/// <summary>
/// Adds the vertices and triangles for a cube at the given position.
/// </summary>
/// <param name="position">The position of the cube.</param>
void AddCubeMesh(float3 position)
{
int vertexStart = vertices.Length;
// Add vertices (8 vertices for a cube)
vertices.Add(position + BlockData.Vertices[0]);
vertices.Add(position + BlockData.Vertices[1]);
vertices.Add(position + BlockData.Vertices[2]);
vertices.Add(position + BlockData.Vertices[3]);
vertices.Add(position + BlockData.Vertices[4]);
vertices.Add(position + BlockData.Vertices[5]);
vertices.Add(position + BlockData.Vertices[6]);
vertices.Add(position + BlockData.Vertices[7]);
for (int i = 0; i < BlockData.Triangles.Length; i++)
{
triangles.Add(vertexStart + BlockData.Triangles[i]);
}
}
}
}
ChunkGreedyMeshDataGenerationJob.cs
using Unity.Burst;
using Unity.Collections;
using Unity.Jobs;
using Unity.Mathematics;
namespace HAELENT
{
/// <summary>
/// Job to generate mesh data for a chunk using the greedy meshing algorithm.
/// </summary>
[BurstCompile]
public struct ChunkGreedyMeshDataGenerationJob : IJob
{
// The array of blocks within the chunk.
[ReadOnly] public NativeArray<Block> blocks;
// The size of the chunk in 3D space (width, height, depth).
public int3 chunkSize;
// NativeList to store the vertices of the generated mesh.
public NativeList<float3> vertices;
// NativeList to store the indices of the generated mesh.
public NativeList<int> triangles;
/// <summary>
/// The main execution method of the job.
/// </summary>
public void Execute()
{
GreedyMesh();
}
/// <summary>
/// Implements the greedy meshing algorithm to optimize mesh generation by reducing the number of polygons.
/// </summary>
private void GreedyMesh()
{
// Greedy meshing algorithm loops over each dimension.
for (int d = 0; d < 3; d++)
{
int i, j, k, l, w, h;
int u = (d + 1) % 3;
int v = (d + 2) % 3;
NativeArray<int3> x = new NativeArray<int3>(3, Allocator.Temp);
NativeArray<int3> q = new NativeArray<int3>(3, Allocator.Temp);
NativeArray<Block> mask = new NativeArray<Block>(chunkSize[u] * chunkSize[v], Allocator.Temp);
// Increment in the current dimension.
q[d] = 1;
// Iterate over the current dimension.
for (x[d] = -1; math.all(x[d] < chunkSize[d]);)
{
int n = 0;
// Create a mask for the current slice.
for (x[v] = 0; math.all(x[v] < chunkSize[v]); x[v]++)
{
for (x[u] = 0; math.all(x[u] < chunkSize[u]); x[u]++)
{
// Get blocks at the current and adjacent positions.
Block block1 = math.all((x[d] >= 0)) ? GetBlock(x[0].x, x[1].y, x[2].z) : new Block { type = BlockType.HIDDEN };
Block block2 = math.all((x[d] < chunkSize[d] - 1)) ? GetBlock(x[0].x + q[0].x, x[1].y + q[1].y, x[2].z + q[2].z) : new Block { type = BlockType.HIDDEN };
// If blocks are different, add the current block to the mask.
if (block1.type != block2.type)
{
mask[n++] = block1;
}
else
{
mask[n++] = new Block { type = BlockType.HIDDEN };
}
}
}
x[d]++;
n = 0;
// Process the mask to create quads.
for (j = 0; j < chunkSize[v]; j++)
{
for (i = 0; i < chunkSize[u];)
{
if (mask[n].type != BlockType.HIDDEN )
{
// Determine the width of the quad.
for (w = 1; i + w < chunkSize[u] && mask[n + w].type == mask[n].type; w++) { }
bool done = false;
// Determine the height of the quad.
for (h = 1; j + h < chunkSize[v]; h++)
{
for (k = 0; k < w; k++)
{
if (mask[n + k + h * chunkSize[u]].type != mask[n].type)
{
done = true;
break;
}
}
if (done) break;
}
x[u] = i;
x[v] = j;
int3 du = new int3();
du[u] = w;
int3 dv = new int3();
dv[v] = h;
// Add the vertices for the quad.
vertices.Add(new float3(x[0].x, x[1].y, x[2].z));
vertices.Add(new float3(x[0].x + du[0], x[1].y + du[1], x[2].z + du[2]));
vertices.Add(new float3(x[0].x + du[0] + dv[0], x[1].y + du[1] + dv[1], x[2].z + du[2] + dv[2]));
vertices.Add(new float3(x[0].x + dv[0], x[1].y + dv[1], x[2].z + dv[2]));
int vertCount = vertices.Length;
// Add the triangles for the quad.
triangles.Add(vertCount - 4);
triangles.Add(vertCount - 3);
triangles.Add(vertCount - 2);
triangles.Add(vertCount - 4);
triangles.Add(vertCount - 2);
triangles.Add(vertCount - 1);
// Clear the mask for the processed area.
for (l = 0; l < h; l++)
{
for (k = 0; k < w; k++)
{
var index = n + k + l * chunkSize[u];
// Get the block from the mask array
Block tempBlock = mask[index];
tempBlock.type = BlockType.HIDDEN ;
mask[index] = tempBlock;
}
}
i += w;
n += w;
}
else
{
i++;
n++;
}
}
}
}
mask.Dispose();
x.Dispose();
q.Dispose();
}
}
/// <summary>
/// Gets the block at the specified coordinates within the chunk.
/// </summary>
/// <param name="x">The x-coordinate.</param>
/// <param name="y">The y-coordinate.</param>
/// <param name="z">The z-coordinate.</param>
/// <returns>The block at the specified coordinates.</returns>
private Block GetBlock(int x, int y, int z)
{
int index = x + chunkSize.x * (y + chunkSize.y * z);
return blocks[index];
}
}
}
ChunkMeshGenerator.cs
using Unity.Collections;
using Unity.Jobs;
using Unity.Mathematics;
using UnityEngine;
namespace HAELENT
{
/// <summary>
/// Generates the mesh for a chunk of blocks and assigns it to a MeshFilter.
/// </summary>
public class ChunkMeshGenerator : MonoBehaviour
{
/// <summary>
/// The size of the chunk to generate.
/// </summary>
public int3 chunkSize = new int3(16, 16, 16);
/// <summary>
/// If should use Greedy Meshing algorithm to generate mesh.
/// </summary>
public bool UseGreedyMeshing = true;
/// <summary>
/// The chunk of blocks.
/// </summary>
private Chunk chunk;
/// <summary>
/// The MeshFilter component used to display the generated mesh.
/// </summary>
private MeshFilter meshFilter;
/// <summary>
/// Initializes the chunk and starts the mesh generation.
/// </summary>
void Start()
{
chunk = new Chunk(chunkSize);
meshFilter = GetComponent<MeshFilter>();
if (meshFilter == null)
meshFilter = this.gameObject.AddComponent<MeshFilter>();
// Populate chunk with sample data
for (int x = 0; x < chunkSize.x; x++)
{
for (int y = 0; y < chunkSize.y; y++)
{
for (int z = 0; z < chunkSize.z; z++)
{
// Example data: create a ground layer of stone blocks at y = 0, air blocks elsewhere
Block block = new Block { type = y == 0 ? BlockType.STONE : BlockType.AIR };
chunk.SetBlock(x, y, z, block);
}
}
}
if (UseGreedyMeshing)
GenerateGreedyMesh();
else
GenerateMesh();
}
/// <summary>
/// Generates the mesh for the chunk and assigns it to the MeshFilter.
/// </summary>
void GenerateMesh()
{
NativeList<float3> vertices = new NativeList<float3>(Allocator.TempJob);
NativeList<int> triangles = new NativeList<int>(Allocator.TempJob);
ChunkMeshDataGenerationJob job = new ChunkMeshDataGenerationJob
{
blocks = chunk.blocks,
chunkSize = chunkSize,
vertices = vertices,
triangles = triangles
};
JobHandle handle = job.Schedule();
handle.Complete();
Vector3[] verticesAsVector3 = new Vector3[vertices.Length];
for (int i = 0; i < vertices.Length; i++)
{
verticesAsVector3[i] = vertices[i];
}
Mesh mesh = new Mesh
{
vertices = verticesAsVector3,
triangles = triangles.ToArray()
};
mesh.RecalculateNormals();
meshFilter.mesh = mesh;
vertices.Dispose();
triangles.Dispose();
}
/// <summary>
/// Generates the greedy mesh for the chunk and assigns it to the MeshFilter.
/// </summary>
void GenerateGreedyMesh()
{
NativeList<float3> vertices = new NativeList<float3>(Allocator.TempJob);
NativeList<int> triangles = new NativeList<int>(Allocator.TempJob);
ChunkGreedyMeshDataGenerationJob job = new ChunkGreedyMeshDataGenerationJob
{
blocks = chunk.blocks,
chunkSize = chunkSize,
vertices = vertices,
triangles = triangles
};
JobHandle handle = job.Schedule();
handle.Complete();
Vector3[] verticesAsVector3 = new Vector3[vertices.Length];
for (int i = 0; i < vertices.Length; i++)
{
verticesAsVector3[i] = vertices[i];
}
Mesh mesh = new Mesh
{
vertices = verticesAsVector3,
triangles = triangles.ToArray()
};
mesh.RecalculateNormals();
meshFilter.mesh = mesh;
Debug.Log($"Generated Greedy Mesh with {vertices.Length} vertices and {triangles.Length / 3} triangles");
vertices.Dispose();
triangles.Dispose();
}
/// <summary>
/// Disposes of the chunk to release resources.
/// </summary>
void OnDestroy()
{
chunk.Dispose();
}
}
}
ChatGPT explanation about ‘ChunkGreedyMeshDataGenerationJob’
Let’s walk through the ChunkGreedyMeshDataGenerationJob using 3D text illustrations and its variables to illustrate the greedy meshing process.
3D Text Illustrations with Variables
1. Chunk Initialization
Consider a small chunk with dimensions 3x3x3, represented as a 3D grid of blocks. Assume the chunk size is chunkSize = new int3(3, 3, 3). Each block in the chunk can be of different types (e.g., air (A), solid (S)).
Chunk Grid (3x3x3):
Level 0:
[S] [S] [A]
[S] [A] [A]
[A] [A] [A]
Level 1:
[S] [S] [A]
[S] [A] [A]
[A] [A] [A]
Level 2:
[S] [S] [A]
[S] [A] [A]
[A] [A] [A]
2. Iterate Over Dimensions
The algorithm iterates over three principal dimensions (X, Y, Z) using the outer loop: for (int d = 0; d < 3; d++).
3. Create Mask for Current Slice
For a slice in the X dimension (d=0), the slice at x=-1:
- q[d] = new int3(1, 0, 0), increment in the X dimension.
- Initialize x = new NativeArray(3, Allocator.Temp) to store coordinates.
- Initialize mask = new NativeArray(chunkSize.y * chunkSize.z, Allocator.Temp) to store the mask.
Initialize Mask for X=-1:
Mask =
[A] [A] [A]
[A] [A] [A]
[A] [A] [A]
4. Fill Mask
Fill the mask by comparing each block with its neighbor in the X direction (q[d]):
- x[d] = -1 (current slice at x=-1).
- Iterate through YZ plane.
Example slice at x=0:
- block1 = GetBlock(0, y, z) and block2 = GetBlock(1, y, z).
- If block1 and block2 are different, set mask value to block1.
Mask Filled for X=0:
Mask =
[S] [S] [A]
[S] [A] [A]
[A] [A] [A]
5. Create Quads from Mask
Identify continuous areas of the same block type (e.g., solid blocks) and form quads:
- Initialize variables w (width) and h (height) for the quads.
For mask[0,0] = S, find the largest continuous area:
Mask:
[S] [S]
[S] [A]
Width (w) = 2, Height (h) = 1
6. Add Vertices and Triangles for Quad
Vertices for the quad (using vertices.Add()):
- x = 0, x[v] = 0, du = new int3(2, 0, 0), dv = new int3(0, 1, 0).
Vertices:
V0 = [0, 0, 0]
V1 = [2, 0, 0]
V2 = [2, 1, 0]
V3 = [0, 1, 0]
Triangles for the quad (using triangles.Add()):
- Add indices to form two triangles for the quad.
Triangles:
T0 = (V0, V1, V2)
T1 = (V0, V2, V3)
7. Clear Processed Area in Mask
Update the mask to indicate processed blocks (set to BlockType.HIDDEN).
Updated Mask:
Mask:
[HIDDEN, HIDDEN, A]
[S, A, A]
[A, A, A]
8. Repeat for Remaining Mask
Continue this process for the rest of the mask and other slices.
Detailed Variable Walkthrough
Variables:
-
- d: Current dimension (0 for X, 1 for Y, 2 for Z).
-
i, j, k, l, w, h: Loop variables for iterating through the slice and determining quad size.
-
u, v: Dimensions orthogonal to d (e.g., for d=0, u=1 (Y) and v=2 (Z)).
-
x: Array of coordinates in the chunk.
-
q: Array for dimension increment.
-
mask: Mask array for current slice.
Greedy Mesh Process Illustrated in Detail:
-
- Initialize Variables:
NativeArray<int3> x = new NativeArray<int3>(3, Allocator.Temp);
NativeArray<int3> q = new NativeArray<int3>(3, Allocator.Temp);
NativeArray<Block> mask = new NativeArray<Block>(chunkSize[u] * chunkSize[v], Allocator.Temp);
q[d] = new int3(0);
q[d][d] = 1;
- Iterate Over Dimensions and Create Mask:
for (int d = 0; d < 3; d++) {
for (x[d] = -1; math.all(x[d] < chunkSize[d]); x[d]++) {
int n = 0;
for (x[v] = 0; math.all(x[v] < chunkSize[v]); x[v]++) {
for (x[u] = 0; math.all(x[u] < chunkSize[u]); x[u]++) {
Block block1 = math.all(x[d] >= 0) ? GetBlock(x[0].x, x[1].y, x[2].z) : new Block { type = BlockType.HIDDEN };
Block block2 = math.all(x[d] < chunkSize[d] - 1) ? GetBlock(x[0].x + q[0].x, x[1].y + q[1].y, x[2].z + q[2].z) : new Block { type = BlockType.HIDDEN };
mask[n++] = block1.type != block2.type ? block1 : new Block { type = BlockType.HIDDEN };
}
}
}
}
- Create Quads from Mask:
for (int j = 0; j < chunkSize[v]; j++) {
for (int i = 0; i < chunkSize[u];) {
if (mask[n].type != BlockType.HIDDEN) {
for (w = 1; i + w < chunkSize[u] && mask[n + w].type == mask[n].type; w++) {}
bool done = false;
for (h = 1; j + h < chunkSize[v]; h++) {
for (int k = 0; k < w; k++) {
if (mask[n + k + h * chunkSize[u]].type != mask[n].type) {
done = true;
break;
}
}
if (done) break;
}
x[u] = i;
x[v] = j;
int3 du = new int3(0); du[u] = w;
int3 dv = new int3(0); dv[v] = h;
vertices.Add(new float3(x[0].x, x[1].y, x[2].z));
vertices.Add(new float3(x[0].x + du[0], x[1].y + du[1], x[2].z + du[2]));
vertices.Add(new float3(x[0].x + du[0] + dv[0], x[1].y + du[1] + dv[1], x[2].z + du[2] + dv[2]));
vertices.Add(new float3(x[0].x + dv[0], x[1].y + dv[1], x[2].z + dv[2]));
int vertCount = vertices.Length;
triangles.Add(vertCount - 4);
triangles.Add(vertCount - 3);
triangles.Add(vertCount - 2);
triangles.Add(vertCount - 4);
triangles.Add(vertCount - 2);
triangles.Add(vertCount - 1);
for (l = 0; l < h; l++) {
for (k = 0; k < w; k++) {
mask[n + k + l * chunkSize[u]] = new Block { type = BlockType.HIDDEN };
}
}
i += w;
n += w;
} else {
i++;
n++;
}
}
}
- Dispose Temporary Arrays:
mask.Dispose();
x.Dispose();
q.Dispose();
