experiment: create a Quadtree that allocates all the nodes in 100% predictable array order

.QuadTree.cs.md

note: this was a programming experiment

Initial goal

To create a Quadtree where

• all nodes are kept in linear order one index next to the other
• nodes and points are stored in separate, dedicated array/list buffers

Lessons learned:

• parent & child indices can be easily calculated one from another (wasn't sure)
• random 100k node insertions can crash the program (!) which is bad news
• probably useful for cases where tree depth is kept under strict control so it doesn't grow above cerain level
• but risky/unusable as general-use quad tree because of memory allocation growth depends so much of point distribution

QuadTree.cs

// src*: https://gist.github.com/andrew-raphael-lukasik/778b8891974d2e18fcfa89854e4f3509
using Unity.Collections;
using Unity.Mathematics;
using Unity.Jobs;

using Debug = UnityEngine.Debug;

[System.Serializable]
public struct QuadTree
{

    public EType type;
    public float2 min, max;
    public int pointIndex;

    /// <remarks> Constructs an empty leaf node. </remarks>
    public QuadTree ( float2 min , float2 max )
    {
        this.min = min;
        this.max = max;
        this.pointIndex = -1;
        this.type = EType.Leaf;
    }

    public enum EType : byte
    {
        UNDEFINED = 0 ,
        Leaf ,
        Trunk
    };

    public override string ToString () => UnityEngine.JsonUtility.ToJson(this,false);

    public static void Insert ( float2 point , NativeList<QuadTree> quadTreeBuffer , NativeList<float2> pointsBuffer )
    {
        if( quadTreeBuffer.Length!=0 )
            Insert( 0 , point , quadTreeBuffer , pointsBuffer );
        else
            Debug.LogError($"NativeList<{nameof(QuadTree)}> is expected to contain at least a single 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)
    static void Insert ( int nodeIndex , float2 point , NativeList<QuadTree> quadTree , NativeList<float2> points )
    {
        if( nodeIndex>=quadTree.Length ) throw new System.Exception($"Given {nameof(nodeIndex)} ({nodeIndex}) must be < than {nameof(quadTree)}.Length ({quadTree.Length})");
        
        insert_again:
        var node = quadTree[nodeIndex];
        if( node.type==EType.Leaf )
        {
            if( node.pointIndex==-1 )// no point content
            {
                // insert point into an empty leaf
                int pointIndex = points.Length;
                points.Add( point );

                node.pointIndex = pointIndex;
                quadTree[nodeIndex] = node;
            }
            else// point content
            {
                float2 existingPoint = points[node.pointIndex];
                
                if( math.all(point==existingPoint) )
                {
                    // duplicate detected, ignore it
                    return;
                }

                _Subdivide( nodeIndex , quadTree , points );
                goto insert_again;
            }
        }
        else if( node.type==EType.Trunk )
        {
            int childIndex = ChildIndex( nodeIndex );

            float2 min = node.min;
            float2 max = node.max;
            float2 mid = min + ( max - min )/2;

            // we need to go deeper
            bool2 greater = point > mid;
            if( math.all(greater) )
            {
                // top right
                nodeIndex = childIndex + 2;
                goto insert_again;
            }
            else if( greater.x )
            {
                // bottom right
                nodeIndex = childIndex + 3;
                goto insert_again;
            }
            else if( greater.y )
            {
                // top left
                nodeIndex = childIndex + 1;
                goto insert_again;
            }
            else
            {
                // bottom left
                nodeIndex = childIndex + 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}");
        }
    }

    static void _Subdivide ( int nodeIndex , NativeList<QuadTree> quadTree , NativeList<float2> points )
    {
        var node = quadTree[nodeIndex];

        int childIndex = ChildIndex( nodeIndex );
        
        // upsize
        int childDepth = IndexDepth( nodeIndex:childIndex );
        {
            int requiredLength = SumPowersOf4( childDepth );
            if( quadTree.Length<requiredLength )
            {
                quadTree.Length = requiredLength;
            }
        }

        float2 min = node.min;
        float2 max = node.max;
        float2 mid = min + ( max - min )/2;

        QuadTree BL = new QuadTree( min , mid );
        QuadTree TL = new QuadTree( new float2(min.x,mid.y) , new float2(mid.x,max.y) );
        QuadTree TR = new QuadTree( mid , max );
        QuadTree BR = new QuadTree( new float2(mid.x,min.y) , new float2(max.x,mid.y) );

        // re-insert existing point
        int pointIndex = node.pointIndex;
        if( pointIndex!=-1 )
        {
            float2 point = points[pointIndex];
            bool2 greater = point > mid;
            if( math.all(greater) )
            {
                // top right
                TR.pointIndex = pointIndex;
            }
            else if( greater.x )
            {
                // bottom right
                BR.pointIndex = pointIndex;
            }
            else if( greater.y )
            {
                // top left
                TL.pointIndex = pointIndex;
            }
            else 
            {
                // bottom left
                BL.pointIndex = pointIndex;
            }
        }

        quadTree[childIndex+0] = BL;
        quadTree[childIndex+1] = TL;
        quadTree[childIndex+2] = TR;
        quadTree[childIndex+3] = BR;

        node.type = EType.Trunk;
        node.pointIndex = -1;
        quadTree[nodeIndex] = node;
    }

    public static int ChildIndex ( int parentIndex )
    {
        return 4 * parentIndex + 1;
    }
    static int ParentIndex ( in int nodeIndex )
    {
        int nodeDepth = IndexDepth( nodeIndex:nodeIndex );
	    return ParentIndex( nodeIndex , nodeDepth );
    }
    static int ParentIndex ( in int nodeIndex , int nodeDepth )
    {
	    return (int)( SumPowersOf4(nodeDepth-2) -1 + math.ceil( ( (nodeIndex - SumPowersOf4(nodeDepth-1) +1 )) / 4.0 ) );
    }
    public static int IndexDepth ( in int nodeIndex )
	{
        int depth = 0;
	    int power = 0;
	    int sum = 0;
	    while( nodeIndex>sum )
	    {
		    depth++;
		    power++;
		    sum += (int)math.pow( 4 , power );
	    }
        return depth;
	}
    static int SumPowersOf4 ( in int power )
    {
	    int accu = 0;
	    for( int i=0 ; i<=power ; i++ )
		    accu += (int)math.pow( 4.0 , i );
	    return accu;
    }
	public static int NumNodes ( int depth )
    {
        return (int)( ( math.pow(4.0,depth) -1 ) / 3 );
    }

    [Unity.Burst.BurstCompile( CompileSynchronously=true )]
    public partial struct InsertJob : IJob
    {
        float2 _point;
        NativeList<QuadTree> _quadTreeBuffer;
        NativeList<float2> _pointsBuffer;
        public InsertJob ( float2 point , NativeList<QuadTree> quadTreeBuffer , NativeList<float2> pointsBuffer )
        {
            this._point = point;
            this._quadTreeBuffer = quadTreeBuffer;
            this._pointsBuffer = pointsBuffer;
        }
        void IJob.Execute()
        {
            QuadTree.Insert( point:_point , quadTreeBuffer:_quadTreeBuffer , pointsBuffer:_pointsBuffer );
        }
    }

}

QuadTreeTester.cs

// src*: https://gist.github.com/andrew-raphael-lukasik/778b8891974d2e18fcfa89854e4f3509
using UnityEngine;
using Unity.Mathematics;
using Unity.Collections;
using Unity.Jobs;

using Random = Unity.Mathematics.Random;

[ExecuteInEditMode]
public class QuadTreeTester : MonoBehaviour
{

    [SerializeField][Min(0)] int _numRandomPoints = 9;
    [SerializeField][Min(1)] uint _seed = 1;
    [SerializeField] Rect _rect = new Rect( 0 , 0 , 10 , 6 );

    NativeList<QuadTree> _quadTree;
    NativeList<float2> _quadTreePoints;

    JobHandle Dependency;

    void OnValidate ()
    {
        if( _quadTree.IsCreated )
        {
            OnDisable();
            OnEnable();
        }
    }

    void OnEnable ()
    {
        _quadTree = new( 1 + 4 + 16 + 64 + 256 + 1024 , Allocator.Persistent ){ new QuadTree(_rect.min,_rect.max) };
        _quadTreePoints = new ( _numRandomPoints , Allocator.Persistent );

        var rnd = new Random(_seed);
        float2 rectOrigin = _rect.position;
        float2 rectSize = _rect.size;
        for( int i = 0 ; i<_numRandomPoints ; i++ )
        {
            float2 point = rectOrigin + rnd.NextFloat2() * rectSize;
            var job = new QuadTree.InsertJob( point , _quadTree , _quadTreePoints );
            Dependency = job.Schedule( Dependency );
        }
        Dependency.Complete();
    }

    void OnDisable ()
    {
        Dependency.Complete();
        if( _quadTree.IsCreated ) _quadTree.Dispose();
        if( _quadTreePoints.IsCreated ) _quadTreePoints.Dispose();
    }

    void OnDrawGizmos ()
    {
        if( Dependency.IsCompleted )
        if( _quadTree.IsCreated )
        {
            float sphereSize = math.min(_rect.size.x,_rect.size.y) * 0.005f;
            int length = _quadTree.Length;
            float fmax = (float)math.max( length - 1 , 1 );
            for( int i=0 ; i<length ; i++ )
            {
                var node = _quadTree[i];
                if( node.type==QuadTree.EType.UNDEFINED ) continue;

                var bounds = new Bounds(){
                    min = new Vector3( node.min.x , node.min.y ) ,
                    max = new Vector3( node.max.x , node.max.y )
                };
                int depth = 0;// QuadTree.IndexDepth(i);
                bounds.center += new Vector3(0,0,depth);
                Gizmos.color = (i/fmax)!=float.NaN ? Color.Lerp( Color.green , Color.red , i/fmax ) : Color.magenta;
                Gizmos.DrawWireCube( bounds.center , bounds.size - new Vector3(0.1f , 0.1f)*depth );

                if( node.pointIndex!=-1 )
                {
                    float2 pointXY = _quadTreePoints[node.pointIndex];
                    Vector3 point = new Vector3( pointXY.x , pointXY.y );
                    Gizmos.DrawSphere( point , sphereSize );
                    Gizmos.DrawLine( point , new Vector3(point.x,point.y,bounds.center.z) );
                }
            }
        }
    }

}