Skip to content

Instantly share code, notes, and snippets.

@andrew-raphael-lukasik

andrew-raphael-lukasik/.NativeQuadTree.cs.md

Last active October 19, 2024 05:33
Show Gist options
  • Save andrew-raphael-lukasik/02cd430757421f15a21ef23aa7368fb3 to your computer and use it in GitHub Desktop.
Save andrew-raphael-lukasik/02cd430757421f15a21ef23aa7368fb3 to your computer and use it in GitHub Desktop.
Download ZIP
Quadtree built on `Unity.Collections`, `Unity.Jobs` and `Unity.Burst`
Raw
.NativeQuadTree.cs.md

Quadtree built on Unity.Collections, Unity.Jobs and Unity.Burst

Screenshot 2023-10-12 170345

Raw
NativeQuadtree unit tests.cs
// src*: https://gist.github.com/andrew-raphael-lukasik/02cd430757421f15a21ef23aa7368fb3
using NUnit.Framework;
using UnityEngine;
using UnityEngine.TestTools;
using Unity.Mathematics;
using Unity.Collections;
using Unity.Jobs;
namespace NativeQuadtree_Tests
{
public class constructor
{
[Test]
public void root ()
{
float2 min = new float2( 0 , 0 );
float2 max = new float2( 1 , 1 );
var node = new NativeQuadtree.Node<byte>( min , max );
Assert.AreEqual( expected:NativeQuadtree.EType.Empty , actual:node.type );
Assert.AreEqual( expected:min , actual:node.min );
Assert.AreEqual( expected:max , actual:node.max );
Assert.AreEqual( expected:new float2( 0 , 0 ) , actual:node.point );
Assert.AreEqual( expected:0 , actual:node.parentIndex );
Assert.AreEqual( expected:0 , actual:node.firstChildIndex );
Assert.AreEqual( expected:0 , actual:node.value );
}
[Test]
public void child ()
{
float2 min = new float2( 0 , 0 );
float2 max = new float2( 1 , 1 );
int parentIndex = 123;
var node = new NativeQuadtree.Node<byte>( min , max , parentIndex );
Assert.AreEqual( expected:NativeQuadtree.EType.Empty , actual:node.type );
Assert.AreEqual( expected:min , actual:node.min );
Assert.AreEqual( expected:max , actual:node.max );
Assert.AreEqual( expected:new float2( 0 , 0 ) , actual:node.point );
Assert.AreEqual( expected:parentIndex , actual:node.parentIndex );
Assert.AreEqual( expected:0 , actual:node.firstChildIndex );
Assert.AreEqual( expected:0 , actual:node.value );
}
}
public class Insert
{
[Test]
public void single_point ()
{
float2 min = new float2( 0 , 0 );
float2 max = new float2( 1 , 1 );
float2 p0 = new float2( 0.5f , 0.5f );
var quadtree = new NativeList<NativeQuadtree.Node<byte>>( Allocator.TempJob ) { new NativeQuadtree.Node<byte>(min,max) };
bool success = NativeQuadtree.Insert<byte>( p0 , 1 , quadtree );
int length = quadtree.Length;
var node = quadtree[0];
quadtree.Dispose();
Assert.IsTrue( success );
Assert.AreEqual( expected:1 , actual:length );
Assert.AreEqual( expected:min , actual:node.min );
Assert.AreEqual( expected:max , actual:node.max );
Assert.AreEqual( expected:1 , actual:node.value , node.ToString() );
}
[Test]
public void two_points ()
{
float2 min = new float2( 0 , 0 );
float2 max = new float2( 1 , 1 );
float2 p0 = new float2( 0.25f , 0.25f );
float2 p1 = new float2( 0.75f , 0.75f );
var quadtree = new NativeList<NativeQuadtree.Node<byte>>( Allocator.TempJob ) { new NativeQuadtree.Node<byte>( min , max ) };
bool success = NativeQuadtree.Insert<byte>( p0 , 1 , quadtree );
success &= NativeQuadtree.Insert<byte>( p1 , 2 , quadtree );
int length = quadtree.Length;
var node0 = quadtree[1];
var node1 = quadtree[3];
quadtree.Dispose();
Assert.IsTrue( success );
Assert.AreEqual( expected:5 , actual:length );
Assert.AreEqual( expected:3 , actual:3 );
Assert.AreEqual( expected:new float2( 0.5f , 0.5f ) , actual:node1.min );
Assert.AreEqual( expected:max , actual:node1.max );
Assert.AreEqual( expected:1 , actual:node0.value , node0.ToString() );
Assert.AreEqual( expected:2 , actual:node1.value , node1.ToString() );
}
[Test]
public void three_points___no_subdivision ()
{
float2 min = new float2( 0 , 0 );
float2 max = new float2( 1 , 1 );
float2 p0 = new float2( 0.25f , 0.25f );
float2 p1 = new float2( 0.75f , 0.75f );
float2 p2 = new float2( 0.75f , 0.25f );
var quadtree = new NativeList<NativeQuadtree.Node<byte>>( Allocator.TempJob ) { new NativeQuadtree.Node<byte>( min , max ) };
bool success = NativeQuadtree.Insert<byte>( p0 , 1 , quadtree );
success &= NativeQuadtree.Insert<byte>( p1 , 2 , quadtree );
success &= NativeQuadtree.Insert<byte>( p2 , 3 , quadtree );
int length = quadtree.Length;
var node0 = quadtree[1];
var node1 = quadtree[3];
var node2 = quadtree[4];
quadtree.Dispose();
Assert.IsTrue( success );
Assert.AreEqual( expected:1+4 , actual:length );
Assert.AreEqual( expected:4 , actual:4 );
Assert.AreEqual( expected:new float2( 0.5f , 0 ) , actual:node2.min );
Assert.AreEqual( expected:new float2( 1 , 0.5f ) , actual:node2.max );
Assert.AreEqual( expected:1 , actual:node0.value , node0.ToString() );
Assert.AreEqual( expected:2 , actual:node1.value , node1.ToString() );
Assert.AreEqual( expected:3 , actual:node2.value , node2.ToString() );
}
[Test]
public void three_points___subdivision ()
{
float2 min = new float2( 0 , 0 );
float2 max = new float2( 1 , 1 );
float2 p0 = new float2( 0.25f , 0.25f );
float2 p1 = new float2( 0.75f , 0.75f );
float2 p2 = new float2( 0.8f , 0.8f );
var quadtree = new NativeList<NativeQuadtree.Node<byte>>( Allocator.TempJob ) { new NativeQuadtree.Node<byte>( min , max ) };
bool success = NativeQuadtree.Insert<byte>( p0 , 1 , quadtree );
success &= NativeQuadtree.Insert<byte>( p1 , 2 , quadtree );
success &= NativeQuadtree.Insert<byte>( p2 , 3 , quadtree );
int length = quadtree.Length;
var node0 = quadtree[1];
var node1 = quadtree[5];
var node2 = quadtree[7];
quadtree.Dispose();
Assert.IsTrue( success );
Assert.AreEqual( expected:1+4+4 , actual:length );
Assert.AreEqual( expected:7 , actual:7 );
Assert.AreEqual( expected:new float2( 0.75f , 0.75f ) , actual:node2.min );
Assert.AreEqual( expected:new float2( 1 , 1 ) , actual:node2.max );
Assert.AreEqual( expected:1 , actual:node0.value , node0.ToString() );
Assert.AreEqual( expected:2 , actual:node1.value , node1.ToString() );
Assert.AreEqual( expected:3 , actual:node2.value , node2.ToString() );
}
}
}
Raw
NativeQuadtree.cs
// src*: https://gist.github.com/andrew-raphael-lukasik/02cd430757421f15a21ef23aa7368fb3
using UnityEngine;
using Unity.Collections;
using Unity.Mathematics;
using Unity.Jobs;
public static class NativeQuadtree
{
[System.Serializable]
public struct Node<T>
{
public NativeQuadtree.EType type;
public float2 point;
public T value;
public float2 min, max;
public int parentIndex;
public int firstChildIndex;// nodes will always be placed in fours
public float2 center => min + ( max - min )/2;
/// <remarks> Constructs an empty childless leaf node. </remarks>
public Node ( float2 min , float2 max )
{
this.type = NativeQuadtree.EType.Empty;
this.min = min;
this.max = max;
this.point = 0;
this.value = default;
this.parentIndex = 0;
this.firstChildIndex = 0;
}
/// <remarks> Constructs an empty child leaf node. </remarks>
public Node ( float2 min , float2 max , int parentIndex )
: this( min, max )
{
this.parentIndex = parentIndex;
}
public override string ToString () => $"( {type} , {point} , {value} , {min} , {max} , {parentIndex} , {firstChildIndex} )";
}
public enum EType : byte
{
UNDEFINED = 0 ,
Empty = 1 ,// leaf
Point = 2 ,// leaf with a point
Trunk = 3
};
public static JobHandle Insert <T> ( NativeSlice<(float2 point,T value)> pointValuePairs , NativeList<Node<T>> quadtree , JobHandle dependency ) where T : unmanaged
{
if( quadtree.Length!=0 )
return new InsertJob<T>( pointValuePairs , quadtree ).Schedule( dependency );
else
throw new System.Exception($"{nameof(quadtree)} is expected to contain at least a single root entry already where initial bounds are defined.");
}
/// (mid.x,max.y)
/// (min.x,max.y) +-------+-------+ max
/// | | |
/// | TL | TR |
/// | | |
/// (min.x,mid.y) +------mid------+ (max.x,mid.y)
/// | | |
/// y | BL | BR |
/// | | | |
/// +--x min +-------+-------+ (max.x,min.y)
/// (mid.x,min.y)
/// <remarks> IMPORTANT: <paramref name="nodeIndex"/> is guaranteed valid only until next <see cref="Insert"/> call as it can change the structure of the quadtree.</remarks>
/// <returns>True on success. False when this point already exists in the quadtree.</returns>
public static bool Insert <T> ( float2 point , T value , NativeList<Node<T>> quadtree ) where T : unmanaged
{
int nodeIndex = 0;
insert_again:
var node = quadtree[nodeIndex];
if( node.type==EType.Empty )// insert point into an empty leaf
{
node.point = point;
node.type = EType.Point;
node.value = value;
quadtree[nodeIndex] = node;
return true;
}
else if( node.type==EType.Point )// insert point into a leaf that contains a point already
{
if( math.all(point==node.point) )
{
// duplicate detected, ignore it
return false;
}
float2 min = node.min;
float2 max = node.max;
float2 mid = node.center;
var BL = new Node<T>( min , mid , parentIndex:nodeIndex );
var TL = new Node<T>( new float2(min.x,mid.y) , new float2(mid.x,max.y) , parentIndex:nodeIndex );
var TR = new Node<T>( mid , max , parentIndex:nodeIndex );
var BR = new Node<T>( new float2(mid.x,min.y) , new float2(max.x,mid.y) , parentIndex:nodeIndex );
// re-insert existing point
bool2 greater = node.point > mid;
if( math.all(greater) )// top right
{
TR.point = node.point;
TR.type = EType.Point;
TR.value = node.value;
}
else if( greater.x )// bottom right
{
BR.point = node.point;
BR.type = EType.Point;
BR.value = node.value;
}
else if( greater.y )// top left
{
TL.point = node.point;
TL.type = EType.Point;
TL.value = node.value;
}
else// bottom left
{
BL.point = node.point;
BL.type = EType.Point;
BL.value = node.value;
}
node.firstChildIndex = quadtree.Length;
node.type = EType.Trunk;
node.point = default;
node.value = default;
quadtree[nodeIndex] = node;
quadtree.Add( BL );
quadtree.Add( TL );
quadtree.Add( TR );
quadtree.Add( BR );
goto insert_again;
}
else if( node.type==EType.Trunk )// just a trunk, we need to go deeper
{
float2 min = node.min;
float2 max = node.max;
float2 mid = node.center;
bool2 greater = point > mid;
if( math.all(greater) )// top right
{
nodeIndex = node.firstChildIndex + 2;
goto insert_again;
}
else if( greater.x )// bottom right
{
nodeIndex = node.firstChildIndex + 3;
goto insert_again;
}
else if( greater.y )// top left
{
nodeIndex = node.firstChildIndex + 1;
goto insert_again;
}
else// bottom left
{
nodeIndex = node.firstChildIndex + 0;
goto insert_again;
}
}
else// undefined node
{
// this should never happen
// definitely an error somewhere
throw new System.Exception($"ERROR SOMEWHERE; READING AN UNDEFINED NODE:{node}");
}
}
public static JobHandle Search <T> ( NativeSlice<float2> points , NativeList<Node<T>> quadtree , NativeSlice<int> searchResult , JobHandle dependency ) where T : unmanaged
{
if( quadtree.Length!=0 )
{
return new SearchJob<T>( points , quadtree , searchResult ).Schedule( dependency );
}
else throw new System.Exception($"{nameof(quadtree)} is expected to contain at least a single root entry already where initial bounds are defined.");
}
public static JobHandle Search <T> ( float2 point , NativeList<Node<T>> quadtree , NativeSlice<int> searchResult , JobHandle dependency ) where T : unmanaged
{
if( quadtree.Length!=0 )
{
var points = new NativeArray<float2>( 1 , Allocator.TempJob );
points[0] = point;
var jobHandle = new SearchJob<T>( points , quadtree , searchResult ).Schedule( dependency );
points.Dispose( jobHandle );
return jobHandle;
}
else throw new System.Exception($"{nameof(quadtree)} is expected to contain at least a single root entry already where initial bounds are defined.");
}
/// <returns>Node index.</returns>
public static int Search <T> ( float2 point , NativeList<Node<T>> quadtree ) where T : unmanaged
{
int nodeIndex = 0;
search_again:
var node = quadtree[nodeIndex];
if( node.type==EType.Trunk )
{
float2 min = node.min;
float2 max = node.max;
float2 mid = node.center;
bool2 greater = point > mid;
if( math.all(greater) )// top right
{
nodeIndex = node.firstChildIndex + 2;
goto search_again;
}
else if( greater.x )// bottom right
{
nodeIndex = node.firstChildIndex + 3;
goto search_again;
}
else if( greater.y )// top left
{
nodeIndex = node.firstChildIndex + 1;
goto search_again;
}
else// bottom left
{
nodeIndex = node.firstChildIndex + 0;
goto search_again;
}
}
else if( node.type==EType.Empty )
{
return nodeIndex;
}
else if( node.type==EType.Point )
{
return nodeIndex;
}
else// undefined node
{
// this should never happen
// definitely an error somewhere
throw new System.Exception($"ERROR SOMEWHERE; READING AN UNDEFINED NODE:{node}");
}
}
public static JobHandle SearchNearestOther <T> ( int nodeIndex , NativeList<Node<T>> quadtree , NativeSlice<int> searchResult , JobHandle dependency ) where T : unmanaged
{
if( quadtree.Length!=0 )
{
return new SearchNearestOtherJob<T>( nodeIndex , quadtree , searchResult ).Schedule( dependency );
}
else throw new System.Exception($"{nameof(quadtree)} is expected to contain at least a single root entry already where initial bounds are defined.");
}
/// <returns>Node index. -1 on fail.</returns>
public static bool SearchNearestOther <T> ( int nodeIndex , NativeList<Node<T>> quadtree , out int nearestOtherIndex ) where T : unmanaged
{
var node = quadtree[nodeIndex];
var visited = new NativeHashSet<int>( 1 , Allocator.Temp ){
nodeIndex// ignore self
};
nearestOtherIndex = -1;
float nearestDist = float.MaxValue;
float2 myPosition = node.type==EType.Point ? node.point : node.center;
SearchNearestOther( quadtree , nodeIndex , myPosition , visited , ref nearestOtherIndex , ref nearestDist );
return nearestOtherIndex != -1;
}
static void SearchNearestOther <T>
(
NativeList<Node<T>> quadtree ,
int nodeIndex ,
float2 myPosition ,
NativeHashSet<int> visitedNodes ,
ref int nearestNode ,
ref float nearestDist
) where T : unmanaged
{
repeat:
var node = quadtree[nodeIndex];
visitedNodes.Add( nodeIndex );
if( node.type==EType.Trunk )
for( int i=0 ; i<4 ; i++ )
{
int childIndex = node.firstChildIndex + i;
if( visitedNodes.Contains(childIndex) ) continue;// skip visited
visitedNodes.Add( childIndex );
var child = quadtree[ childIndex ];
if( child.type==EType.Point )
{
float dist = math.length( myPosition - child.point );
if( dist<nearestDist )
{
nearestNode = childIndex;
nearestDist = dist;
}
}
else if( child.type==EType.Trunk )
{
// we need to go deeper
SearchNearestOther( quadtree , childIndex , myPosition , visitedNodes , ref nearestNode , ref nearestDist );
}
}
if( nearestNode==-1 )// nothing found yet
if( nodeIndex!=0 )// is not root
if( !visitedNodes.Contains(node.parentIndex) )// parent not visited yet
{
// we need to go up
nodeIndex = node.parentIndex;
goto repeat;
}
}
/// <summary> Removes every node but root. Cuts the tree :V </summary>
public static void CutDown <T> ( NativeList<Node<T>> quadtree ) where T : unmanaged
{
if( quadtree.Length>1 )
{
quadtree.Length = 1;
var root = quadtree[0];
{
root.parentIndex = 0;
root.firstChildIndex = 0;
root.point = 0;
root.value = default;
root.type = EType.Empty;
}
quadtree[0] = root;
}
}
public static void CutBranch <T> ( int nodeIndex , NativeList<Node<T>> quadtree ) where T : unmanaged
{
throw new System.NotImplementedException();
}
[Unity.Burst.BurstCompile( CompileSynchronously=true )]
public partial struct InsertJob <T> : IJob where T : unmanaged
{
NativeSlice<(float2 point,T value)> _pointValuePairs;
NativeList<Node<T>> _quadtree;
public InsertJob ( NativeSlice<(float2 point,T value)> pointValuePairs , NativeList<Node<T>> quadtree )
{
this._pointValuePairs = pointValuePairs;
this._quadtree = quadtree;
}
void IJob.Execute ()
{
for( int i=0 ; i<_pointValuePairs.Length ; i++ )
NativeQuadtree.Insert<T>( point:_pointValuePairs[i].point , _pointValuePairs[i].value , quadtree:_quadtree );
}
}
[Unity.Burst.BurstCompile( CompileSynchronously=true )]
public partial struct SearchJob <T> : IJob where T : unmanaged
{
[ReadOnly] NativeList<Node<T>> _quadtree;
[ReadOnly] NativeSlice<float2> _points;
[WriteOnly] NativeSlice<int> _searchResult;
public SearchJob ( NativeSlice<float2> points , NativeList<Node<T>> quadtree , NativeSlice<int> searchResult )
{
this._points = points;
this._quadtree = quadtree;
this._searchResult = searchResult;
}
void IJob.Execute ()
{
for( int i=0 ; i<_points.Length ; i++ )
_searchResult[i] = NativeQuadtree.Search( point:_points[i] , quadtree:_quadtree );
}
}
[Unity.Burst.BurstCompile( CompileSynchronously=true )]
public partial struct SearchNearestOtherJob <T> : IJob where T : unmanaged
{
int _nodeIndex;
[ReadOnly] NativeList<Node<T>> _quadtree;
[WriteOnly] NativeSlice<int> _searchResult;
public SearchNearestOtherJob ( int nodeIndex , NativeList<Node<T>> quadtree , NativeSlice<int> searchResult )
{
this._nodeIndex = nodeIndex;
this._quadtree = quadtree;
this._searchResult = searchResult;
}
void IJob.Execute ()
{
NativeQuadtree.SearchNearestOther(_nodeIndex,_quadtree,out int nearestOtherIndex);
_searchResult[0] = nearestOtherIndex;
}
}
#if UNITY_EDITOR
// note: you can use `Gizmos.matrix` to rotate these gizmos
public static void DrawGizmos <T> ( NativeList<Node<T>> quadtree , Vector3 worldCenter , Vector3 worldSize ) where T : unmanaged
{
Gizmos.color = Color.green;
Gizmos.DrawWireCube( worldCenter , worldSize );
Vector2 regionMin = worldCenter - worldSize/2;
Vector2 regionMax = worldCenter + worldSize/2;
UnityEditor.Handles.Label( regionMin , $"( {regionMin.x} , {regionMin.y} )" );
UnityEditor.Handles.Label( regionMax , $"( {regionMax.x} , {regionMax.y} )" );
float sphereSize = math.min( worldSize.x , worldSize.y ) * 0.005f;
int length = quadtree.Length;
float fmax = (float)math.max( length - 1 , 1 );
for( int nodeIndex=0 ; nodeIndex<length ; nodeIndex++ )
{
var node = quadtree[nodeIndex];
if( node.type==NativeQuadtree.EType.Trunk )
{
Gizmos.color = (nodeIndex/fmax)!=float.NaN ? Color.Lerp( Color.green , Color.red , nodeIndex/fmax ) : Color.magenta;
float2 min = node.min;
float2 max = node.max;
float2 mid = node.center;
Gizmos.DrawLine( new Vector2(min.x,mid.y) , new Vector2(max.x,mid.y) );
Gizmos.DrawLine( new Vector2(mid.x,min.y) , new Vector2(mid.x,max.y) );
}
else if( node.type==NativeQuadtree.EType.Point )
{
Gizmos.DrawWireSphere( new Vector3( node.point.x , node.point.y ) , sphereSize );
}
if( length<100 )
{
UnityEditor.Handles.color = Gizmos.color;
UnityEditor.Handles.Label( new Vector3(node.center.x,node.center.y,0) , $"{nodeIndex}" );
}
}
}
#endif
}
Raw
NativeQuadtreeTester.cs
// src*: https://gist.github.com/andrew-raphael-lukasik/02cd430757421f15a21ef23aa7368fb3
using UnityEngine;
using Unity.Mathematics;
using Unity.Collections;
using Unity.Jobs;
using Random = Unity.Mathematics.Random;
[ExecuteInEditMode]
public class NativeQuadtreeTester : MonoBehaviour
{
[SerializeField][Range( 0 , 100000 )] int _numRandomPoints = 9;
[SerializeField][Min( 1 )] uint _seed = 1;
[SerializeField] Rect _rect = new Rect( 0 , 0 , 10 , 6 );
NativeList<NativeQuadtree.Node<int>> _quadtree;
JobHandle Dependency;
void OnValidate ()
{
if( _quadtree.IsCreated )
{
OnDisable();
OnEnable();
}
}
void OnEnable ()
{
var watch = System.Diagnostics.Stopwatch.StartNew();
_quadtree = new( 1024 , Allocator.Persistent ) { new NativeQuadtree.Node<int>(_rect.min,_rect.max) };
var rnd = new Random( _seed );
float2 rectOrigin = _rect.position;
float2 rectSize = _rect.size;
var points = new NativeArray<(float2, int)>( _numRandomPoints , Allocator.TempJob );
for( int i = 0 ; i<_numRandomPoints ; i++ )
{
float2 point = rectOrigin + rnd.NextFloat2() * rectSize;
points[i] = ( point , i );
}
var job = new NativeQuadtree.InsertJob<int>( points , _quadtree );
Dependency = job.Schedule( Dependency );
points.Dispose( Dependency );
Dependency.Complete();
Debug.Log( $"{_numRandomPoints} Quadtree insertions took {(double)watch.ElapsedTicks/(double)System.TimeSpan.TicksPerMillisecond:0.0000} ms" );
}
void OnDisable ()
{
Dependency.Complete();
if( _quadtree.IsCreated ) _quadtree.Dispose();
}
#if UNITY_EDITOR
void OnDrawGizmos ()
{
if( !Dependency.IsCompleted ) return;
NativeQuadtree.DrawGizmos( _quadtree , worldCenter: _rect.center , worldSize: _rect.size );
Vector2 mousePos = Event.current.mousePosition;
mousePos *= UnityEditor.EditorGUIUtility.pixelsPerPoint;
var camera = UnityEditor.SceneView.lastActiveSceneView.camera;
Vector3 vec = new Vector3( mousePos.x , camera.pixelHeight-mousePos.y , 1 );
Ray ray = camera.ScreenPointToRay( vec );
if( new Plane( inNormal: Vector3.forward , inPoint: Vector3.zero ).Raycast( ray , out float dist ) )
{
Vector3 rayHitPoint = ray.origin + ray.direction * dist;
Gizmos.color = Color.yellow;
Gizmos.DrawRay( rayHitPoint , Vector3.forward );
var watch = System.Diagnostics.Stopwatch.StartNew();
int nodeIndex = NativeQuadtree.Search( new float2( rayHitPoint.x , rayHitPoint.y ) , _quadtree );
Debug.Log( $"Quadtree {nameof( NativeQuadtree.Search )} took {(double)watch.ElapsedTicks/(double)System.TimeSpan.TicksPerMillisecond:0.0000} ms" );
var node = _quadtree[nodeIndex];
var bounds = new Bounds()
{
min = new Vector3( node.min.x , node.min.y ) ,
max = new Vector3( node.max.x , node.max.y )
};
Gizmos.color = new Color( 1 , 0 , 1 , 0.1f );
Gizmos.DrawCube( bounds.center , bounds.size );
watch.Restart();
var array = new NativeArray<int>( 1 , Allocator.TempJob );
array[0] = -1;
var jobHandle = NativeQuadtree.SearchNearestOther( nodeIndex , _quadtree , array , Dependency );
jobHandle.Complete();
int otherNodeIndex = array[0];
array.Dispose();
Debug.Log( $"Quadtree {nameof( NativeQuadtree.SearchNearestOther )} took {(double)watch.ElapsedTicks/(double)System.TimeSpan.TicksPerMillisecond:0.0000} ms" );
if( otherNodeIndex!=-1 )
{
var other = _quadtree[otherNodeIndex];
float2 nodePos = node.type==NativeQuadtree.EType.Point ? node.point : node.center;
Gizmos.color = Color.magenta;
Gizmos.DrawLine( new Vector3( nodePos.x , nodePos.y , 0 ) , new Vector3( other.point.x , other.point.y , 0 ) );
}
}
}
#endif
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment