source: OniSplit/Akira/QuadtreeNode.cs@ 1148

using System;
using System.Collections.Generic;

namespace Oni.Akira
{
    internal class QuadtreeNode
    {
        public const int ChildCount = 4;
        private QuadtreeNode[] nodes = new QuadtreeNode[ChildCount];
        private OctreeNode[] leafs = new OctreeNode[ChildCount];
        private readonly Vector3 center;
        private readonly float size;
        private readonly OctreeNode.Face face;
        private int index;

        public enum Axis
        {
            U = 0,
            V = 1
        }

        public struct ChildPosition
        {
            private readonly int index;

            public ChildPosition(int index)
            {
                this.index = index;
            }

            public int Index => index;

            public int U => this[Axis.U];
            public int V => this[Axis.V];

            public int this[Axis axis] => ((index >> (int)axis) & 1);

            public static IEnumerable<ChildPosition> All
            {
                get
                {
                    for (int i = 0; i < 4; i++)
                        yield return new ChildPosition(i);
                }
            }
        }

        public QuadtreeNode(Vector3 center, float size, OctreeNode.Face face)
        {
            this.center = center;
            this.size = size;
            this.face = face;
        }

        public QuadtreeNode[] Nodes => nodes;
        public OctreeNode[] Leafs => leafs;

        public void Build(OctreeNode adjacentNode)
        {
            float childSize = size * 0.5f;

            foreach (var position in ChildPosition.All)
            {
                var childCenter = GetChildNodeCenter(position);
                var adjacentCenter = OctreeNode.MovePoint(childCenter, face, childSize * 0.5f);
                var childAdjacentNode = adjacentNode.FindLargestOrEqual(adjacentCenter, childSize);

                if (childAdjacentNode.IsLeaf)
                {
                    leafs[position.Index] = childAdjacentNode;
                }
                else
                {
                    var child = new QuadtreeNode(childCenter, childSize, face);
                    child.Build(childAdjacentNode);
                    nodes[position.Index] = child;
                }
            }
        }

        private Vector3 GetChildNodeCenter(ChildPosition position)
        {
            float offset = size * 0.25f;

            float u = (position.U == 0) ? -offset : offset;
            float v = (position.V == 0) ? -offset : offset;

            var result = center;

            if (face.Axis == OctreeNode.Axis.X)
            {
                result.Y += u;
                result.Z += v;
            }
            else if (face.Axis == OctreeNode.Axis.Y)
            {
                result.X += u;
                result.Z += v;
            }
            else
            {
                result.X += u;
                result.Y += v;
            }

            return result;
        }

        public int Index => index;

        public List<QuadtreeNode> GetDfsList()
        {
            var list = new List<QuadtreeNode>();

            DfsTraversal(node => {
                node.index = list.Count;
                list.Add(node);
            });

            return list;
        }

        private void DfsTraversal(Action<QuadtreeNode> action)
        {
            action(this);

            foreach (var node in nodes)
            {
                if (node != null)
                    node.DfsTraversal(action);
            }
        }
    }
}