Skip to content

Instantly share code, notes, and snippets.

@andrew-raphael-lukasik
Last active August 9, 2023 21:07
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save andrew-raphael-lukasik/c8836b2b1f05e773abf9fb76dc7884af to your computer and use it in GitHub Desktop.
Save andrew-raphael-lukasik/c8836b2b1f05e773abf9fb76dc7884af to your computer and use it in GitHub Desktop.
unity dots spatial hashing (this was made for entities 0.17... I think)
// src: https://gist.github.com/andrew-raphael-lukasik/c8836b2b1f05e773abf9fb76dc7884af
using Unity.Entities;
using Unity.Mathematics;
using Unity.Collections;
using Unity.Transforms;
using Unity.Rendering;
using Unity.Jobs;
public class SpatialHashAuthoringComponent : UnityEngine.MonoBehaviour, IConvertGameObjectToEntity
{
void IConvertGameObjectToEntity.Convert ( Entity entity , EntityManager dstManager , GameObjectConversionSystem conversionSystem )
{
dstManager.AddComponent<SpatialHash>( entity );
dstManager.AddComponent<SpatialHashPrevious>( entity );
}
#if UNITY_EDITOR
void OnDrawGizmos () { UnityEngine.Gizmos.color = UnityEngine.Color.blue; UnityEngine.Gizmos.DrawSphere( transform.position , 1f ); }
#endif
}
public struct SpatialHash : IComponentData
{
public int4 Value;
public static int4 Encode ( float3 point , float cellSize ) => new int4( (int3)( point/cellSize ) , (int)PackSignMask( math.sign(point) ) );
public static float3 DecodeOrigin ( int4 hash , float cellSize ) => math.abs(new float3{ x=hash.x , y=hash.y , z=hash.z }) * UnpackSignMask((byte)hash.w) * cellSize;
public static float3 DecodeCenter ( int4 hash , float cellSize )
{
float3 sign = UnpackSignMask((byte)hash.w);
return sign*math.abs(new float3{ x=hash.x , y=hash.y , z=hash.z })*cellSize + sign*cellSize*0.5f;
}
static byte PackSignMask ( float3 sign )
{
float3 offset = new float3{ x=1 , y=1 , z=1 };
int3 signCoded = (int3)( sign + offset );// -1f as 00, 0f as 01, 1f as 10
return (byte)( signCoded.x | (signCoded.y<<2) | (signCoded.z<<4) );
}
static float3 UnpackSignMask ( byte signMask )
{
float3 offset = new float3{ x=1 , y=1 , z=1 };
int3 maskedBytes = new int3{ x=signMask , y=signMask , z=signMask } & new int3{ x=0b_0000_0011 , y=0b_0000_1100 , z=0b_0011_0000 };
return new float3{ x=maskedBytes.x , y=maskedBytes.y>>2 , z=maskedBytes.z>>4 } - offset;
}
#if DEBUG
[System.Diagnostics.Conditional("DEBUG")]
[UnityEngine.RuntimeInitializeOnLoadMethod(UnityEngine.RuntimeInitializeLoadType.AfterAssembliesLoaded)]
static void _UnitTests ()
{
UnityEngine.Assertions.Assert.AreEqual( (byte) 0b_0010_0100 , PackSignMask( new float3{ x=-1f , y=0f , z=1f } ) , $"{nameof(SpatialHash)}::{nameof(PackSignMask)}(float3) doesn't work" );
UnityEngine.Assertions.Assert.AreEqual( new float3{ x=-1f , y=0f , z=1f } , UnpackSignMask( (byte) 0b_0010_0100 ) , $"{nameof(SpatialHash)}::{nameof(UnpackSignMask)}(byte) doesn't work" );
}
#endif
}
public struct SpatialHashPrevious : IComponentData
{
public int4 Value;
}
[UpdateInGroup( typeof(InitializationSystemGroup) )]
public class SpatialHashSystem : SystemBase
{
NativeMultiHashMap<int4,Entity> _spatialHashMap;
public NativeMultiHashMap<int4,Entity> SpatialHashMap => _spatialHashMap;// so other systems can access it
public JobHandle SpatialHashMapDependency;
public const float k_neighbourhoodSize = 100f;
protected override void OnCreate () => _spatialHashMap = new NativeMultiHashMap<int4,Entity>( capacity:10000 , Allocator.Persistent );
protected override void OnDestroy () => _spatialHashMap.Dispose();
protected override void OnUpdate ()
{
Dependency = JobHandle.CombineDependencies( Dependency , SpatialHashMapDependency );
var spatialHashMap = _spatialHashMap;
var spatialHashMap_pw = _spatialHashMap.AsParallelWriter();
Entities
.WithName("calculate_hashes_job")
.WithChangeFilter<LocalToWorld>()
.ForEach(( ref SpatialHash spatialHash, ref SpatialHashPrevious spatialHashPrevious, in LocalToWorld ltw , in Entity entity ) =>
{
spatialHashPrevious.Value = spatialHash.Value;
float3 point = ltw.Position;
spatialHash.Value = SpatialHash.Encode( point , k_neighbourhoodSize );
})
.WithBurst().ScheduleParallel();
Entities
.WithName("remove_old_hashes_job")
.WithChangeFilter<LocalToWorld>()
.ForEach(( in SpatialHash spatialHash, in SpatialHashPrevious spatialHashPrevious, in Entity entity )
=> spatialHashMap.Remove( spatialHashPrevious.Value , entity ) )
.WithBurst().Schedule();// parallel Remove not found
Entities
.WithName("add_new_hashes_job")
.WithChangeFilter<LocalToWorld>()
.ForEach(( in SpatialHash spatialHash, in Entity entity )
=> spatialHashMap_pw.Add( spatialHash.Value , entity ) )
.WithBurst().ScheduleParallel();
#if DEBUG
Entities
.WithName("print_neighbours_job")
.WithChangeFilter<LocalToWorld>()
.WithReadOnly( spatialHashMap )
.ForEach(( in SpatialHash spatialHash, in Entity entity ) =>
{
var text = new FixedString128($"{entity}'s neighbours are: ");
int count = 0;
foreach( Entity otherEntity in spatialHashMap.GetValuesForKey(spatialHash.Value) )
if( otherEntity!=entity )
{
if( count!=0 ) text.Append(", ");
text.Append($"{otherEntity}");
count++;
}
if( count!=0 ) UnityEngine.Debug.Log(text);
})
.WithoutBurst().Schedule();
#endif
SpatialHashMapDependency = Dependency;
}
}
#if UNITY_EDITOR
[UpdateInGroup( typeof(PresentationSystemGroup) )]
public class SpatialHashDebugSystem : SystemBase
{
protected override void OnUpdate ()
{
var spatialHashSystem = EntityManager.World.GetExistingSystem<SpatialHashSystem>();
float3 cellSize = new float3{ x=SpatialHashSystem.k_neighbourhoodSize , y=SpatialHashSystem.k_neighbourhoodSize , z=SpatialHashSystem.k_neighbourhoodSize };
Dependency = JobHandle.CombineDependencies( Dependency , spatialHashSystem.SpatialHashMapDependency );
var multimap = spatialHashSystem.SpatialHashMap;
var ltwData = GetComponentDataFromEntity<LocalToWorld>( isReadOnly:true );
Job
.WithName("debug_job")
.WithReadOnly(multimap).WithReadOnly(ltwData)
.WithCode( () =>
{
var keys = multimap.GetKeyArray( Allocator.Temp );
for( int i=0 ; i<keys.Length ; i++ )
{
int4 hash = keys[i];
float3 center = SpatialHash.DecodeCenter( hash , SpatialHashSystem.k_neighbourhoodSize );
float3 ncol = new Unity.Mathematics.Random((uint)hash.GetHashCode()).NextFloat3( new float3{} , new float3{x=1,y=1,z=1} );
var neighbourhoodColor = new UnityEngine.Color{ r=ncol.x , g=ncol.y , b=ncol.z , a=1 };
foreach( Entity e in multimap.GetValuesForKey(hash) )
UnityEngine.Debug.DrawLine( center , ltwData[e].Position , neighbourhoodColor );
}
keys.Dispose();
})
.WithoutBurst().Schedule();
spatialHashSystem.SpatialHashMapDependency = Dependency;
}
}
#endif
@andrew-raphael-lukasik
Copy link
Author

Neat and super simple hash function: https://twitter.com/eriknordeus/status/1591377286183686149
FhW0jFaWIAEa2dm

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment