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

.NativeQuadTree.cs.md

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

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() );
		}

	}

}

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

}

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

}