Skip to content

Instantly share code, notes, and snippets.

@enbugger

enbugger/OAHashMap.cs

Last active August 3, 2025 19:14
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save enbugger/37e7e363e3b93786d748deaf55f9d7a5 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save enbugger/37e7e363e3b93786d748deaf55f9d7a5 to your computer and use it in GitHub Desktop.
Download ZIP
Array-based octree #octree #unity #burst
Raw
OAHashMap.cs
#define LOG_COUNTER
#define LOG_OPS
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using Unity.Collections;
using Unity.Collections.LowLevel.Unsafe;
using Unity.Jobs;
using UnityEngine;
namespace Game
{
/// <summary>
/// Stateless adapter that must be implemented by user
/// Value must contain or be derivable from value
/// </summary>
public interface IOAAdapter<TKey, TValue>
where TKey : unmanaged, IEquatable<TKey>
where TValue : unmanaged
{
/// <summary>
/// You must implement logic that mark value as deleted
/// The implementation should allow to determine if
/// the element is deleted in IsDeleted()
/// </summary>
public void MarkDeleted(ref TValue value);
/// <summary>
/// Check if element was marked as deleted previously
/// </summary>
public bool IsDeleted(TValue value);
/// <summary>
/// Check if element is 0 or empty
/// </summary>
public bool IsEmpty(TValue value);
/// <summary>
/// Implement (or don't) your hashing here
/// Index must be less that length
/// Index must be different with different attempt value
/// </summary>
public int ConvertToIndex(TKey key, int length, int attempt = 0);
/// <summary>
/// Extract key from value
/// </summary>
public TKey ValueToKey(TValue value);
}
/// <summary>
/// Hash map that uses open addressing instead of chaining for collision resolving
/// Only values are stored
/// NOTE: Key must be stored or be derivable from value data
/// </summary>
public struct OAHashMap<TKey, TValue, TAdapter>
where TKey : unmanaged, IEquatable<TKey>
where TValue : unmanaged
where TAdapter : IOAAdapter<TKey, TValue>
{
private UnsafeList<TValue> _data;
private uint _count;
private readonly TAdapter _adapter;
public OAHashMap(int capacity, Allocator allocator)
{
_data = new UnsafeList<TValue>(capacity, allocator);
_data.Resize(capacity, NativeArrayOptions.ClearMemory);
_count = 0;
_adapter = default;
}
public OAHashMap(UnsafeList<TValue> data, uint count)
{
_data = data;
_count = count;
_adapter = default;
}
/// <summary>
/// Put a new value to map
/// Always returns -1 if load factor is 1.0
/// </summary>
public int Put(TValue value)
{
#if LOG_OPS
Debug.LogFormat("HashMap::Put() <= {0}", value);
#endif
if (_count >= _data.Length)
return -1;
var inc = 0;
var index = _adapter.ConvertToIndex(_adapter.ValueToKey(value), _data.Length);
var cur = _data[index];
while (!_adapter.IsEmpty(cur)
&& !_adapter.IsDeleted(cur)
&& !_adapter.ValueToKey(cur).Equals(_adapter.ValueToKey(value)))
{
inc++;
index = _adapter.ConvertToIndex(_adapter.ValueToKey(value), _data.Length, inc);
cur = _data[index];
}
_data[index] = value;
if (_adapter.IsEmpty(cur) || _adapter.IsDeleted(cur))
{
#if LOG_COUNTER
Debug.LogFormat("COUNT: INC {0} => {1} ({2}) ({3})",
_count, _count + 1, _adapter.IsEmpty(cur) ? "Set-Empty" : "Set-Deleted", cur);
#endif
_count++;
}
if ((float)_count / _data.Length > 0.75f)
Resize();
return index;
}
/// <summary>
/// Retrieve value from map
/// Returns -1 if no such key found otherwise returns index of the element
/// </summary>
public readonly int TryGet(TKey key, out TValue value)
{
var inc = 0;
var index = _adapter.ConvertToIndex(key, _data.Length);
value = _data[index];
while (!_adapter.IsEmpty(value)
// && !_adapter.IsDeleted(value)
&& !_adapter.ValueToKey(value).Equals(key))
{
// Special case: when we have load factor 1
// we quit after one full iteration of array
// because we'd never reach the of cluster
if (_count >= _data.Length && inc >= _data.Length)
{
return -1;
}
inc++;
index = _adapter.ConvertToIndex(key, _data.Length, inc);
value = _data[index];
}
if (_adapter.IsEmpty(value) || _adapter.IsDeleted(value))
{
value = default;
return -1;
}
return index;
}
/// <summary>
/// Remove (actually mark as removed) value from map
/// Returns -1 if no such key found otherwise returns index of the element
/// </summary>
public int Remove(TKey key)
{
#if LOG_OPS
Debug.LogFormat("HashMap::Remove() <= {0}", key);
#endif
var index = TryGet(key, out var value);
if (index < 0)
{
return index;
}
#if LOG_COUNTER
Debug.LogFormat("MARK DELETED: {0}", value);
#endif
_adapter.MarkDeleted(ref value);
_data[index] = value;
#if LOG_COUNTER
Debug.LogFormat("COUNT: DEC {0} => {1} (Remove)", _count, _count - 1);
#endif
_count--;
return index;
}
private unsafe void Resize()
{
#if LOG_OPS
Debug.LogFormat("HashMap::Resize()");
#endif
var tmp = new UnsafeList<TValue>(_data.Length, Allocator.Temp);
tmp.AddRange(_data.Ptr, _data.Length);
#if LOG_COUNTER
Debug.LogFormat("COUNT: NULLIFY from {0} (Resize)", _count);
#endif
_count = 0;
_data.Clear();
_data.Resize(tmp.Length * 2, NativeArrayOptions.ClearMemory);
for (int i = 0; i < tmp.Length; i++)
{
Put(tmp[i]);
}
tmp.Dispose();
}
public void Clear()
{
#if LOG_OPS
Debug.LogFormat("HashMap::Clear()");
#endif
var len = _data.Length;
_data.Clear();
_data.Resize(len, NativeArrayOptions.ClearMemory);
#if LOG_COUNTER
Debug.LogFormat("COUNT: NULLIFY from {0} (Clear)", _count);
#endif
_count = 0;
}
public readonly int Count => (int)_count;
public readonly int Capacity => _data.Length;
public readonly bool IsCreated => _data.IsCreated;
public readonly float LoadFactor => (float)_count / _data.Length;
public readonly UnsafeList<TValue> Data => _data;
public readonly string ToStringDebug()
{
var sb = new StringBuilder();
sb.AppendFormat("HashMap [size={0}/{1}]\n", _count, _data.Capacity);
for (int i = 0; i < _data.Length; i++)
{
var node = _data[i];
var index = "";
if (!_adapter.IsDeleted(node))
{
index = string.Format("->{0}", _adapter.ConvertToIndex(_adapter.ValueToKey(node), _data.Length));
}
sb.AppendFormat("#{0}{1}\t{2}\n", i, index, node);
}
return sb.ToString();
}
}
}
Raw
Octree.cs
#define LOG_OPS
using System.Runtime.CompilerServices;
using System.Text;
using Unity.Collections;
using Unity.Collections.LowLevel.Unsafe;
using Unity.Jobs;
using Unity.Mathematics;
using UnityEngine;
using static Unity.Mathematics.math;
namespace Game
{
// TODO
// Long-term:
// - Use templates to generate non-generic OctreeNode.
// It can be used with ExplicitLayout to save us a byte pre node.
// - Use templates to generate 2 versions: With UnsafeHashMap and NativeHashMap.
// There is no common interface for these two.
// - Use templates for 64-bit-based implementation
// Current 32-bit-based supports only 10 levels
// - [DONE] Research on replacing HashMap with array(s) for passing it in compute shaders
// without copying. Likely, it'll need custom hash implementation
// - Use quadratic probing
// Short-term:
// - How to effectively determine neighbor?
// Implement GetNeighbor() where traverse from parent?
// - Iterator over levels
public struct Octree<TValue>
where TValue : unmanaged
{
private OAHashMap<LocationalCode, OctreeNode<TValue>, OctreeHashMapAdapter<TValue>> _data;
public const int CAPACITY = 128;
public Octree(Allocator allocator)
{
_data = new OAHashMap<LocationalCode, OctreeNode<TValue>, OctreeHashMapAdapter<TValue>>(CAPACITY, allocator);
InternalPut(CreateRoot());
}
public Octree(UnsafeList<OctreeNode<TValue>> data, uint count)
{
_data = new OAHashMap<LocationalCode, OctreeNode<TValue>, OctreeHashMapAdapter<TValue>>(data, count);
InternalPut(CreateRoot());
}
private static OctreeNode<TValue> CreateRoot()
{
return new OctreeNode<TValue>()
{
Bits = 0x00000001, // Non-Leaf with level 0
ChildrenMask = 0 // No children
};
}
public void Set(uint3 pos, int level, TValue value)
{
var loc = LocationalCode.Encode(pos, level);
Set(loc, value);
}
/// <summary>
/// Set value. Parent nodes will be created automatically
/// </summary>
/// Level - Bounds
/// 0 - 0-0 // 0x0...01 can't have coords
/// 1 - 0-1
/// 2 - 0-3
/// 3 - 0-7
/// 4 - 0-15
/// 5 - 0-31
/// 6 - 0-63
/// 7 - 0-127
/// 8 - 0-255
/// 9 - 0-511
/// 10- 0-1023 -- deprecated
public void Set(LocationalCode loc, TValue value)
{
var node = new OctreeNode<TValue>
{
Bits = loc.Code,
ChildrenMask = 0,
Value = value
};
node.SetLeaf();
InternalPut(node);
while (loc.Level > 0)
{
var curCode = loc.Code;
loc.ToParent();
if (InternalTryGet(loc.Code, out var parentNode) < 0)
{
parentNode = new OctreeNode<TValue>
{
Bits = loc.Code,
};
}
parentNode.UnsetLeaf();
parentNode.ChildrenMask |= (byte)(1 << (int)(curCode & 0b111));
InternalPut(parentNode);
}
}
public void SetBlock(uint3 pos, int level, TValue value)
{
var loc = LocationalCode.Encode(pos, level);
SetBlock(loc, value);
}
public void SetBlock(LocationalCode loc, TValue value)
{
#if LOG_OPS
Debug.LogFormat("Octree::SetBlock() <= ({0}, {1})", loc.ToStringOctal(), value);
#endif
RemoveChildrenRecursive(loc);
Set(loc, value);
}
public bool RemoveBlock(uint3 pos, int level)
{
var loc = LocationalCode.Encode(pos, level);
#if LOG_OPS
Debug.LogFormat("Octree::RemoveBlock() <= {0}", loc.ToStringOctal());
#endif
for (var i = 1; i < loc.Level; i++)
{
var lc = loc.GetParent(i);
if (InternalTryGet(lc, out var value) >= 0 && value.IsLeaf())
{
Subdivide(lc);
}
}
return Remove(loc);
}
public bool Subdivide(LocationalCode loc, byte exclude)
{
// Debug.LogFormat("Subdividing {0}", loc.ToStringBinary());
if (InternalTryGet(loc, out var value) < 0 || !value.IsLeaf()) return false;
for (var i = 0; i < 8; i++)
{
if (exclude == i) continue;
var copy = value;
copy.Bits = loc.GetChild((NRP)i);
copy.SetLeaf();
InternalPut(copy);
}
value.UnsetLeaf();
value.ChildrenMask = 0b11111111;
value.UnsetChild(exclude);
InternalPut(value);
return true;
}
public bool Subdivide(LocationalCode loc)
{
if (InternalTryGet(loc, out var value) < 0 || !value.IsLeaf()) return false;
for (var i = 0; i < 8; i++)
{
var copy = value;
copy.Bits = loc.GetChild((NRP)i);
copy.SetLeaf();
InternalPut(copy);
}
value.UnsetLeaf();
value.ChildrenMask = 0b11111111;
InternalPut(value);
return true;
}
public bool Subdivide(uint3 pos, int level, byte exclude = 0b1111)
{
var loc = LocationalCode.Encode(pos, level);
return Subdivide(loc, exclude);
}
// TODO Level should be uint
public readonly int TryGet(uint3 pos, int level, out OctreeNode<TValue> value)
{
var loc = LocationalCode.Encode(pos, level);
return InternalTryGet(loc.Code, out value);
}
public readonly int TryGet(LocationalCode code, out OctreeNode<TValue> value)
{
return InternalTryGet(code, out value);
}
public readonly OctreeNode<TValue> GetRoot()
{
InternalTryGet(LocationalCode.ROOT, out var root);
return root;
}
public bool Remove(uint3 pos, int level)
{
if (level == 0)
return false;
var loc = LocationalCode.Encode(pos, level);
return Remove(loc);
}
public bool Remove(LocationalCode loc)
{
if (InternalTryGet(loc.Code, out var _) < 0)
return false;
CleanParents(loc);
RemoveChildrenRecursive(loc);
return InternalRemove(loc);
}
private void CleanParents(LocationalCode code)
{
var prevCode = code;
var curCode = prevCode.GetParent();
while (InternalTryGet(curCode, out var pValue) >= 0)
{
pValue.UnsetChild(prevCode);
if (curCode.Level > 0 && pValue.ChildrenMask == 0)
{
InternalRemove(curCode);
prevCode = curCode;
curCode = curCode.GetParent();
continue;
}
InternalPut(pValue);
break;
}
}
private void RemoveChildrenRecursive(LocationalCode parent)
{
var toRemove = new UnsafeList<uint>(0, Allocator.Temp);
var toRetrieve = new UnsafeList<uint>(0, Allocator.Temp);
toRetrieve.Add(parent);
while (!toRetrieve.IsEmpty)
{
var lastIndex = toRetrieve.Length - 1;
var curCode = toRetrieve[lastIndex];
toRetrieve.RemoveAt(lastIndex);
if (InternalTryGet(curCode, out var curValue) < 0)
break;
for (uint i = 0; i < 8; i++)
{
if (!curValue.ChildIsSet(i))
continue;
var next = curValue.Code;
next.ToChild((NRP)i);
if (InternalTryGet(next, out var childValue) < 0)
continue;
toRemove.Add(next);
if (!childValue.IsLeaf())
{
toRetrieve.Add(next);
}
}
}
toRetrieve.Dispose();
for (int i = 0; i < toRemove.Length; i++)
{
InternalRemove(toRemove[i]);
}
toRemove.Dispose();
}
public readonly int Count => _data.Count;
public readonly bool IsCreated => _data.IsCreated;
private readonly DebugNode<TValue> Visit(LocationalCode code, StringBuilder sb)
{
InternalTryGet(code, out var val);
for (var i = 0; i < code.Level; i++)
{
sb.Append('+');
}
sb.Append(val.ToString());
sb.Append("\n");
if (val.IsLeaf()) {
return new DebugNode<TValue> {IsLeaf = true, Value = val.Value};
} else {
var result = new DebugNode<TValue>{Children = new DebugNode<TValue>[8]};
for (byte i = 0; i < 8; i++)
{
if (!val.ChildIsSet(i)) continue;
result.Children[i] = Visit(code.GetChild((NRP)i), sb);
}
return result;
}
}
public void Clear()
{
_data.Clear();
InternalPut(CreateRoot());
}
public readonly string ToStringTree()
{
var sb = new StringBuilder();
Visit(LocationalCode.ROOT, sb);
return sb.ToString();
}
public readonly string ToStringData() => _data.ToStringDebug();
public void InternalPut(OctreeNode<TValue> value)
{
_data.Put(value);
}
public readonly int InternalTryGet(LocationalCode code, out OctreeNode<TValue> value)
{
return _data.TryGet(code, out value);
}
private bool InternalRemove(LocationalCode code)
{
return _data.Remove(code) >= 0;
}
public readonly UnsafeList<OctreeNode<TValue>> Data => _data.Data;
}
public struct OctreeHashMapAdapter<TValue> : IOAAdapter<LocationalCode, OctreeNode<TValue>>
where TValue : unmanaged
{
public int ConvertToIndex(LocationalCode key, int length, int attempt = 0)
=> key.ToIndex(length, attempt);
public bool IsDeleted(OctreeNode<TValue> value) => value.IsDeleted();
public bool IsEmpty(OctreeNode<TValue> value) => value.IsEmpty();
public void MarkDeleted(ref OctreeNode<TValue> value) => value.SetDeleted();
public LocationalCode ValueToKey(OctreeNode<TValue> value) => value.Code;
}
/// <summary>
/// Node's relative position to it's parent's center
/// </summary>
/// 011@3----111@7
/// 010@2-+--110@6 |
/// | | | | Y Z
/// | 001@1--+-101@5 |/
/// 000@0----100@4 +--X
public enum NRP : byte
{
LEFT_BOTTOM_FRONT = 0b000,
LEFT_BOTTOM_BACK = 0b001,
LEFT_TOP_FRONT = 0b010,
LEFT_TOP_BACK = 0b011,
RIGHT_BOTTOM_FRONT = 0b100,
RIGHT_BOTTOM_BACK = 0b101,
RIGHT_TOP_FRONT = 0b110,
RIGHT_TOP_BACK = 0b111
}
public struct LocationalCode : System.IEquatable<LocationalCode>
{
public const int MAX_LEVEL = 9;
public const uint ROOT = 0x00000001; // Level 0
public const uint NULL = 0x00000000;
public uint Code;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static implicit operator uint(LocationalCode c) => c.Code;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static implicit operator LocationalCode(uint v) => new LocationalCode { Code = v };
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public void ToChild(NRP pos)
{
Code <<= 3;
Code |= (byte)pos;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public void ToParent()
{
Code >>= 3;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public readonly LocationalCode GetParent()
{
return new LocationalCode { Code = Code >> 3 };
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public readonly LocationalCode GetParent(int level)
{
var diff = (int) Level - level;
return new LocationalCode { Code = diff > 0 ? Code >> 3 * diff : Code << 3 * abs(diff) };
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public readonly LocationalCode GetChild(NRP pos)
{
var code = Code << 3;
code |= (byte)pos;
return new LocationalCode { Code = code };
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public readonly LocationalCode GetChild(int pos)
{
return GetChild((NRP) pos);
}
public uint Level
{
[MethodImpl(MethodImplOptions.AggressiveInlining)]
readonly get =>
MAX_LEVEL - ((uint) lzcnt(Code) - (sizeof(uint) * 8 - (MAX_LEVEL * 3 + 1))) / 3; // Bit scan
[MethodImpl(MethodImplOptions.AggressiveInlining)]
set => Code |= 1U << (int)(value * 3);
}
// Be careful. This is a duplicate from OctreeNode
private const uint LEAF_BIT = 0x80000000;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public readonly int ToIndex(int length, int inc = 0)
{
var code = Code & (~(LEAF_BIT));
return (int) ((code * code + inc) % (length - 1));
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static bool CheckInput(uint3 pos, uint level)
{
return level <= MAX_LEVEL && all(pos <= uint3(GetMaxForLevel(level)));
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static uint GetMaxForLevel(uint level) => (uint)(1 << (int)level) - 1;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static LocationalCode Encode(uint3 pos, int level)
{
var code = ROOT;
for (var i = level - 1; i >= 0; i--)
{
code <<= 3;
var t = (pos >> i) & 1;
code |= (t.x << 0) | (t.y << 1) | (t.z << 2);
}
return new LocationalCode { Code = code };
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public readonly uint3 Decode()
{
var pos = uint3(0);
var code = Code;
for (var i = 0; i < Level; i++)
{
var bits = uint3((code >> 0) & 1, (code >> 1) & 1, (code >> 2) & 1);
pos += bits * (1U << i);
code >>= 3;
}
return pos;
}
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public readonly float3 Decode(float sceneSize)
{
var pos = float3(0);
var level = Level;
var code = Code;
for (var i = (int)level; i > 0; i--)
{
var bits = uint3((code >> 0) & 1, (code >> 1) & 1, (code >> 2) & 1);
pos += float3(bits) * sceneSize / (1 << i);
code >>= 3;
}
return pos;
}
public readonly LocationalCode NeighborTop {
get
{
return Code + 4;
}
}
public override string ToString()
{
// return System.Convert.ToString(Code, 16).PadLeft(8, '0');
// return System.Convert.ToString(Code, 2).PadLeft(32, '0');
return ToStringOctal();
}
public readonly string ToStringBinary()
{
return System.Convert.ToString(Code, 2).PadLeft(32, '0');
}
public readonly string ToStringOctal()
{
return System.Convert.ToString(Code, 8).PadLeft((int)MAX_LEVEL + 1, '0');
}
public readonly bool Equals(LocationalCode other)
{
return Code.Equals(other.Code);
}
}
// TODO: ExplicitLayout is not compatible with generics
public struct OctreeNode<T> where T : struct
{
/*
* 1 - 27: Locational code
* 1 - 28: Level bit (follows locational code)
* Must be always set
* 29 - 30: Reserved
* 31: Deleted flag bit
* 32: Leaf bit
*/
public uint Bits;
public byte ChildrenMask;
public T Value;
private const uint LEAF_BIT = 0x80000000;
private const uint DELETED_BIT = 0x40000000;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public readonly bool IsLeaf() => (Bits & LEAF_BIT) > 0;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public void SetLeaf() => Bits |= LEAF_BIT;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public void UnsetLeaf() => Bits &= ~LEAF_BIT;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public readonly bool IsDeleted() => (Bits & DELETED_BIT) > 0;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public void SetDeleted() => Bits |= DELETED_BIT;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public void UnsetDeleted() => Bits &= ~DELETED_BIT;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public void SetChild(uint childCode) => ChildrenMask |= (byte) (1 << (int) (childCode & 0b111));
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public void UnsetChild(uint childCode) => ChildrenMask &= (byte) ~(1 << (int) (childCode & 0b111));
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public readonly bool ChildIsSet(NRP childCode) =>
(ChildrenMask & (byte) (1 << ((byte) childCode & 0b111))) > 0;
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public readonly bool ChildIsSet(int childCode) => ChildIsSet((NRP) childCode);
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public readonly bool ChildIsSet(uint childCode) => ChildIsSet((NRP) childCode);
// Minimal bits is 1 for root
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public readonly bool IsEmpty() => Bits == 0;
public readonly LocationalCode Code
{
[MethodImpl(MethodImplOptions.AggressiveInlining)]
get => Bits & (~LEAF_BIT);
}
public readonly uint Level
{
[MethodImpl(MethodImplOptions.AggressiveInlining)]
get => Code.Level;
}
public override string ToString()
{
if (IsEmpty())
return "Empty";
var deleted = IsDeleted() ? "[DELETED]" : "";
var locCodeHex = Code;
if (IsLeaf())
{
return $"{deleted} {locCodeHex.ToStringOctal()} LEAF \"{Value}\"({locCodeHex.Level})";
}
var childrenMaskHex = System.Convert.ToString(ChildrenMask, 2).PadLeft(8, '0');
return $"{deleted} {locCodeHex.ToStringOctal()} PARENT. Children: {childrenMaskHex}({locCodeHex.Level})";
}
}
public class DebugNode<T> where T : unmanaged
{
public T Value;
public bool IsLeaf;
// public DebugNode<T> _000LBF, _001LBB, _010LTF, _011LTB, _100RBF, _101RBB, _110RTF, _111RTB;
public DebugNode<T>[] Children;
}
}
Raw
OctreeNodeExtensions.cs
using Unity.Mathematics;
using UnityEngine;
using static Unity.Mathematics.math;
namespace Game
{
// You MUST use "this ref" instead of "this"!
public static partial class OctreeExtensions
{
public static bool SetBlockTryMerge(this ref Octree<BlockNode> octree, LocationalCode code, BlockNode node)
{
octree.SetBlock(code, node);
// Check if we can "merge" children leaves into one parent leaf
var thereWasMerge = false;
var i = 10; // Infinite loop breaker
var currentCode = code.GetParent();
octree.TryGet(currentCode, out var val);
while (val.Level > 1 && i > 0)
{
i--;
thereWasMerge |= octree.TryMergeBlock(val);
currentCode = currentCode.GetParent();
octree.TryGet(currentCode, out val);
}
if (i <= 0)
{
Debug.LogError("Infinite loop!!");
}
return thereWasMerge;
}
public static bool SetBlockTryMerge(this ref Octree<BlockNode> octree, uint3 pos, int level, BlockNode node)
{
var code = LocationalCode.Encode(pos, level);
return octree.SetBlockTryMerge(code, node);
}
public static bool TryMergeBlock(this ref Octree<BlockNode> octree, OctreeNode<BlockNode> node)
{
if (node.ChildrenMask != 0xff) return false;
octree.TryGet(node.Code.GetChild(0b000), out var c000);
octree.TryGet(node.Code.GetChild(0b001), out var c001);
octree.TryGet(node.Code.GetChild(0b010), out var c010);
octree.TryGet(node.Code.GetChild(0b011), out var c011);
octree.TryGet(node.Code.GetChild(0b100), out var c100);
octree.TryGet(node.Code.GetChild(0b101), out var c101);
octree.TryGet(node.Code.GetChild(0b110), out var c110);
octree.TryGet(node.Code.GetChild(0b111), out var c111);
var allAreLeaves = c000.IsLeaf() && c001.IsLeaf() && c010.IsLeaf() && c011.IsLeaf() && c100.IsLeaf()
&& c101.IsLeaf() && c110.IsLeaf() && c111.IsLeaf();
if (!allAreLeaves) return false;
var allAreOfOneType = c000.Value.Type == c001.Value.Type &&
c000.Value.Type == c010.Value.Type &&
c000.Value.Type == c011.Value.Type &&
c000.Value.Type == c100.Value.Type &&
c000.Value.Type == c101.Value.Type &&
c000.Value.Type == c110.Value.Type &&
c000.Value.Type == c111.Value.Type;
if (!allAreOfOneType) return false;
// Check deformation
if (any(c000.Value.Deformation.data != 0)) return false;
if (any(c001.Value.Deformation.data != 0)) return false;
if (any(c010.Value.Deformation.data != 0)) return false;
if (any(c011.Value.Deformation.data != 0)) return false;
if (any(c100.Value.Deformation.data != 0)) return false;
if (any(c101.Value.Deformation.data != 0)) return false;
if (any(c110.Value.Deformation.data != 0)) return false;
if (any(c111.Value.Deformation.data != 0)) return false;
node.SetLeaf();
node.Value.Type = c000.Value.Type;
node.Value.NeighborMask = NeighborMask.Full;
node.ChildrenMask = 0;
octree.SetBlock(node.Code, node.Value);
return true;
}
}
public static partial class OctreeNodeExtensions
{
public static float ScaleFactor(this OctreeNode<BlockNode> node)
=> 1 << (int) (LocationalCode.MAX_LEVEL - node.Level);
public static float3 Offset(this OctreeNode<BlockNode> node) => node.Code.Decode(OctreeConstants.SceneSize);
public static float3 TransformVertex(this OctreeNode<BlockNode> node, float3 point)
=> node.Offset() + point * node.ScaleFactor();
public static float3 Min(this OctreeNode<BlockNode> node) => node.TransformVertex(0);
public static float3 Max(this OctreeNode<BlockNode> node) => node.TransformVertex(1);
public static float3x2 Bounds(this OctreeNode<BlockNode> node) => math.float3x2(node.Min(), node.Max());
public static float3 Center(this OctreeNode<BlockNode> node) => node.TransformVertex(0.5f);
public static float3 HalfExtents(this OctreeNode<BlockNode> node) => node.Max() - node.Center();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment