Skip to content

Instantly share code, notes, and snippets.

@himanshugoel2797

himanshugoel2797/mesher.cs

Created April 24, 2020 00:38
Show Gist options
  • Save himanshugoel2797/449e4282dfa7ffe69c0f5f5f76a2b300 to your computer and use it in GitHub Desktop.
Save himanshugoel2797/449e4282dfa7ffe69c0f5f5f76a2b300 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
mesher.cs
using Kokoro.Math;
using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Runtime.CompilerServices;
using System.Text;
using System.Threading;
using System.Threading.Tasks;
namespace Kokoro.Graphics.Voxel
{
public class VoxelMesher
{
class MeshOp
{
public SemaphoreSlim Signal { get; set; }
public VoxelCacheEntry CacheIdx { get; set; }
}
private ConcurrentQueue<MeshOp> PendingMeshOps;
private ConcurrentQueue<MeshOp> BacklogOps;
private Thread[] MeshingThreads;
private SemaphoreSlim PendingMeshSync;
public VoxelWorld Parent { get; private set; }
public VoxelMesher(VoxelWorld world)
{
Parent = world;
PendingMeshOps = new ConcurrentQueue<MeshOp>();
BacklogOps = new ConcurrentQueue<MeshOp>();
PendingMeshSync = new SemaphoreSlim(0);
MeshingThreads = new Thread[Environment.ProcessorCount - VoxelWorld.IOThreads - 1]; //leave threads for streaming and culling
for (int i = 0; i < MeshingThreads.Length; i++)
{
MeshingThreads[i] = new Thread(MeshOpThread);
MeshingThreads[i].Start(i);
}
}
//Receive a queue of things to mesh, meshing distributed across multiple threads
private void MeshOpThread(object arg)
{
int tidx = (int)arg;
while (true)
{
PendingMeshSync.Wait();
if (PendingMeshOps.TryDequeue(out var op))
{
var ent = op.CacheIdx;
if (ent.CacheID != null) //Only remesh if the node is still allocated
{
//Parent.Cache.UpdateEntry(ent).ConfigureAwait(false);
RebuildFullMesh(ent, ent.Offset);
}
op.Signal.Release();
}
else
PendingMeshSync.Release(); //Failed to acquire job, prepare to try again
while (PendingMeshOps.Count < VoxelWorld.MaxMeshJobs - 10 && BacklogOps.Count > 0)
if (BacklogOps.TryDequeue(out var backlog))
PendingMeshOps.Enqueue(backlog);
}
}
public void MeshObject(VoxelCacheEntry idx)
{
idx.RemeshingStatus.Wait();
var op = new MeshOp()
{
Signal = idx.RemeshingStatus,
CacheIdx = idx,
};
if (PendingMeshOps.Count > VoxelWorld.MaxMeshJobs)
if (PendingMeshOps.TryDequeue(out var backlog))
BacklogOps.Enqueue(backlog);
PendingMeshOps.Enqueue(op);
PendingMeshSync.Release();
}
#region Meshing
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static int GetIndex(int x, int y, int z)
{
//int idx = 0;
//for (int i = 0; i < VoxelWorld.SideLog; i++)
//{
// idx |= ((x >> i) & 1) << (i * 3 + 0);
// idx |= ((y >> i) & 1) << (i * 3 + 1);
// idx |= ((z >> i) & 1) << (i * 3 + 2);
//}
//return idx;
x += 1;
y += 1;
z += 1;
return x * ((VoxelWorld.Side + 2) * (VoxelWorld.Side + 2)) + y * (VoxelWorld.Side + 2) + z;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static int GetIndex(int x, int y)
{
return (y & (VoxelWorld.Side - 1)) << VoxelWorld.SideLog | (x & (VoxelWorld.Side - 1));
}
public void RebuildFullMesh(VoxelCacheEntry entry, Vector3 offset)
{
unsafe
{
entry.VoxelCount = 0;
var data = entry.Voxels;
//System.Diagnostics.Stopwatch stopwatch = System.Diagnostics.Stopwatch.StartNew();
var indices = new List<uint>(VoxelWorld.Side * VoxelWorld.Side * VoxelWorld.Side * 6);
var boundingAABB = new List<BoundingBox>((VoxelWorld.Side * VoxelWorld.Side * VoxelWorld.Side) / VoxelWorld.BlockSize + 1);
var boundingSphere = new List<Vector4>((VoxelWorld.Side * VoxelWorld.Side * VoxelWorld.Side) / VoxelWorld.BlockSize + 1);
ushort blk_idx_cnt = 0;
var min = stackalloc byte[3];
var max = stackalloc byte[3];
var tmp = stackalloc byte[6 * 3];
for (int i = 0; i < 3; i++)
{
min[i] = byte.MaxValue;
max[i] = byte.MinValue;
}
void computeBounds()
{
if (blk_idx_cnt != 0)
{
//while (blk_idx_cnt % 3 != 0)
//{
// indices.Add(indices[indices.Count - 1]);
// blk_idx_cnt++;
//}
for (int i = 0; i < 3; i++)
if (min[i] == max[i])
{
if (min[i] == byte.MinValue) //Can't decrement min
max[i]++;
else if (max[i] == byte.MaxValue) //Can't increment max
min[i]--;
else
max[i]++; //Default to incrementing max
}
Vector3 minv = new Vector3(min[0], min[1], min[2]) + offset;
Vector3 maxv = new Vector3(max[0], max[1], max[2]) + offset;
Vector3 c = (minv + maxv) * 0.5f;
float rad = (maxv - c).Length;
boundingAABB.Add(new BoundingBox(minv, maxv));
boundingSphere.Add(new Vector4(c, rad));
blk_idx_cnt = 0;
for (int i = 0; i < 3; i++)
{
min[i] = byte.MaxValue;
max[i] = byte.MinValue;
}
}
}
void addFace(byte* tmp, byte cur)
{
for (int i = 0; i < 6; i++)
{
var vec = tmp[i * 3] << (VoxelWorld.SideLog * 2 + 2) | tmp[i * 3 + 1] << (VoxelWorld.SideLog + 1) | tmp[i * 3 + 2];
min[0] = System.Math.Min(min[0], tmp[i * 3]);
min[1] = System.Math.Min(min[1], tmp[i * 3 + 1]);
min[2] = System.Math.Min(min[2], tmp[i * 3 + 2]);
max[0] = System.Math.Max(max[0], tmp[i * 3]);
max[1] = System.Math.Max(max[1], tmp[i * 3 + 1]);
max[2] = System.Math.Max(max[2], tmp[i * 3 + 2]);
blk_idx_cnt++;
indices.Add((uint)cur << 18 | (uint)(vec & 0x3ffff));
}
if (blk_idx_cnt == VoxelWorld.BlockSize)
{
computeBounds();
}
}
void addPackedFace(byte x, byte y, byte z, byte dir, byte cur)
{
min[0] = System.Math.Min(min[0], x);
min[1] = System.Math.Min(min[1], y);
min[2] = System.Math.Min(min[2], z);
max[0] = System.Math.Max(max[0], (byte)(x + 1));
max[1] = System.Math.Max(max[1], (byte)(y + 1));
max[2] = System.Math.Max(max[2], (byte)(z + 1));
var vec = x << (VoxelWorld.SideLog * 2 + 2) | y << (VoxelWorld.SideLog + 1) | z;
blk_idx_cnt++;
indices.Add((uint)cur << 24 | (uint)dir << 18 | (uint)(vec & 0x3ffff));
if (blk_idx_cnt == VoxelWorld.BlockSize)
computeBounds();
}
entry.VoxelLock.EnterWriteLock();
try
{
if (!entry.VoxelDirty)
return; //No changes to mesh
//ComputeVisibility(data, vis, entry.NeighborFaces);
//for each height value along each axis, extract faces
//assign bit value to each face, then emit faces when doing localized iteration
for (int j = 0; j < data.Length; j++)
{
int xi, yi, zi;
xi = (j & 0x1) | ((j & 0x8) >> 2) | ((j & 0x40) >> 4) | ((j & 0x200) >> 6) | ((j & 0x1000) >> 8);
yi = (j & 0x2) >> 1 | ((j & 0x10) >> 3) | ((j & 0x80) >> 5) | ((j & 0x400) >> 7) | ((j & 0x2000) >> 9);
zi = (j & 0x4) >> 2 | ((j & 0x20) >> 4) | ((j & 0x100) >> 6) | ((j & 0x800) >> 8) | ((j & 0x4000) >> 10);
//TODO: store voxel data in the above order
byte x = (byte)xi;
byte y = (byte)yi;
byte z = (byte)zi;
//var v = vis[GetIndex(x, y, z)];
var cur = data[GetIndex(x, y, z)];
var top = data[GetIndex(x, y - 1, z)];
var btm = data[GetIndex(x, y + 1, z)];
var frt = data[GetIndex(x, y, z - 1)];
var bck = data[GetIndex(x, y, z + 1)];
var lft = data[GetIndex(x - 1, y, z)];
var rgt = data[GetIndex(x + 1, y, z)];
var v = 0;
if (top == 0)
v |= (1 << 3);
if (btm == 0)
v |= (1 << 4);
if (frt == 0)
v |= (1 << 5);
if (bck == 0)
v |= (1 << 6);
if (lft == 0)
v |= (1 << 1);
if (rgt == 0)
v |= (1 << 2);
if (cur == 0) continue;
if ((v & (1 << 3)) != 0)
{
//0
var vcntr = 0;
tmp[vcntr++] = (byte)(x + 1);
tmp[vcntr++] = y;
tmp[vcntr++] = z;
tmp[vcntr++] = x;
tmp[vcntr++] = y;
tmp[vcntr++] = (byte)(z + 1);
tmp[vcntr++] = x;
tmp[vcntr++] = y;
tmp[vcntr++] = z;
tmp[vcntr++] = (byte)(x + 1);
tmp[vcntr++] = y;
tmp[vcntr++] = z;
tmp[vcntr++] = (byte)(x + 1);
tmp[vcntr++] = y;
tmp[vcntr++] = (byte)(z + 1);
tmp[vcntr++] = x;
tmp[vcntr++] = y;
tmp[vcntr++] = (byte)(z + 1);
addFace(tmp, cur);
//addPackedFace(x, y, z, (1 << 4) | (2 << 2) | 0, cur);
}
if ((v & (1 << 4)) != 0)
{
//1
var vcntr = 0;
tmp[vcntr++] = x;
tmp[vcntr++] = (byte)(y + 1);
tmp[vcntr++] = z;
tmp[vcntr++] = x;
tmp[vcntr++] = (byte)(y + 1);
tmp[vcntr++] = (byte)(z + 1);
tmp[vcntr++] = (byte)(x + 1);
tmp[vcntr++] = (byte)(y + 1);
tmp[vcntr++] = z;
tmp[vcntr++] = x;
tmp[vcntr++] = (byte)(y + 1);
tmp[vcntr++] = (byte)(z + 1);
tmp[vcntr++] = (byte)(x + 1);
tmp[vcntr++] = (byte)(y + 1);
tmp[vcntr++] = (byte)(z + 1);
tmp[vcntr++] = (byte)(x + 1);
tmp[vcntr++] = (byte)(y + 1);
tmp[vcntr++] = z;
addFace(tmp, cur);
//addPackedFace(x, (byte)(y + 1), z, (2 << 4) | (2 << 2) | 0, cur);
}
if ((v & (1 << 1)) != 0)
{
//2
var vcntr = 0;
tmp[vcntr++] = x;
tmp[vcntr++] = y;
tmp[vcntr++] = z;
tmp[vcntr++] = x;
tmp[vcntr++] = y;
tmp[vcntr++] = (byte)(z + 1);
tmp[vcntr++] = x;
tmp[vcntr++] = (byte)(y + 1);
tmp[vcntr++] = z;
tmp[vcntr++] = x;
tmp[vcntr++] = y;
tmp[vcntr++] = (byte)(z + 1);
tmp[vcntr++] = x;
tmp[vcntr++] = (byte)(y + 1);
tmp[vcntr++] = (byte)(z + 1);
tmp[vcntr++] = x;
tmp[vcntr++] = (byte)(y + 1);
tmp[vcntr++] = z;
addFace(tmp, cur);
//addPackedFace(x, y, z, (2 << 4) | (2 << 2) | 1, cur);
}
if ((v & (1 << 2)) != 0)
{
//3
var vcntr = 0;
tmp[vcntr++] = (byte)(x + 1);
tmp[vcntr++] = y;
tmp[vcntr++] = z;
tmp[vcntr++] = (byte)(x + 1);
tmp[vcntr++] = (byte)(y + 1);
tmp[vcntr++] = z;
tmp[vcntr++] = (byte)(x + 1);
tmp[vcntr++] = y;
tmp[vcntr++] = (byte)(z + 1);
tmp[vcntr++] = (byte)(x + 1);
tmp[vcntr++] = (byte)(y + 1);
tmp[vcntr++] = z;
tmp[vcntr++] = (byte)(x + 1);
tmp[vcntr++] = (byte)(y + 1);
tmp[vcntr++] = (byte)(z + 1);
tmp[vcntr++] = (byte)(x + 1);
tmp[vcntr++] = y;
tmp[vcntr++] = (byte)(z + 1);
addFace(tmp, cur);
//addPackedFace((byte)(x + 1), y, z, (1 << 4) | (2 << 2) | 1, cur);
}
if ((v & (1 << 5)) != 0)
{
//4
var vcntr = 0;
tmp[vcntr++] = x;
tmp[vcntr++] = y;
tmp[vcntr++] = z;
tmp[vcntr++] = x;
tmp[vcntr++] = (byte)(y + 1);
tmp[vcntr++] = z;
tmp[vcntr++] = (byte)(x + 1);
tmp[vcntr++] = y;
tmp[vcntr++] = z;
tmp[vcntr++] = x;
tmp[vcntr++] = (byte)(y + 1);
tmp[vcntr++] = z;
tmp[vcntr++] = (byte)(x + 1);
tmp[vcntr++] = (byte)(y + 1);
tmp[vcntr++] = z;
tmp[vcntr++] = (byte)(x + 1);
tmp[vcntr++] = y;
tmp[vcntr++] = z;
addFace(tmp, cur);
//addPackedFace(x, y, z, (2 << 4) | (1 << 2) | 0, cur);
}
if ((v & (1 << 6)) != 0)
{
//5
var vcntr = 0;
tmp[vcntr++] = x;
tmp[vcntr++] = y;
tmp[vcntr++] = (byte)(z + 1);
tmp[vcntr++] = (byte)(x + 1);
tmp[vcntr++] = y;
tmp[vcntr++] = (byte)(z + 1);
tmp[vcntr++] = x;
tmp[vcntr++] = (byte)(y + 1);
tmp[vcntr++] = (byte)(z + 1);
tmp[vcntr++] = (byte)(x + 1);
tmp[vcntr++] = y;
tmp[vcntr++] = (byte)(z + 1);
tmp[vcntr++] = (byte)(x + 1);
tmp[vcntr++] = (byte)(y + 1);
tmp[vcntr++] = (byte)(z + 1);
tmp[vcntr++] = x;
tmp[vcntr++] = (byte)(y + 1);
tmp[vcntr++] = (byte)(z + 1);
addFace(tmp, cur);
//addPackedFace(x, y, (byte)(z + 1), (1 << 4) | (1 << 2) | 0, cur);
}
entry.VoxelCount++;
}
computeBounds();
//Remeshing is done, so voxel data is no longer dirty
entry.VoxelDirty = false;
entry.IsEmpty = indices.Count == 0;
}
finally
{
entry.VoxelLock.ExitWriteLock();
}
entry.MeshLock.EnterWriteLock();
try
{
entry.Indices = indices.ToArray();
entry.BoundingSpheres = boundingSphere.ToArray();
entry.BoundingAABBs = boundingAABB.ToArray();
entry.MeshDirty = true; //Mesh data needs to be reuploaded
}
finally
{
entry.MeshLock.ExitWriteLock();
}
//stopwatch.Stop();
//Console.WriteLine($"[Index Count: {indices.Count}, Meshing time: {stopwatch.Elapsed.TotalMilliseconds}ms");
}
}
#endregion
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment