Octree.cs

using System;
using System.Collections;
using System.Collections.Generic;
using UnityEngine;

/*
 * I need these functions.
 */
public static class ListExt {
    /*
     * Merge two lists pairwise.
     *
     * [1, 2, 3].Zip(["a", "b"]) == [(1, "a"), (2, "b")]
     */
    public static List<(A, B)> Zip<A, B>(this List<A> a, List<B> b) {
        var res = new List<(A, B)>();
        for (int i = 0; i < Math.Min(a.Count, b.Count); i++) {
            res.Add((a[i], b[i]));
        }
        return res;
    }

    /*
     * Filter a list.
     *
     * [1, 2, 3].Where(x => x % 2 == 1) == [1, 3]
     */
    public static List<A> Where<A>(this List<A> a, Predicate<A> pred) {
        var res = new List<A>();
        a.ForEach(x => {
            if (pred(x)) {
                res.Add(x);
            }
        });
        return res;
    }

    public static A First<A>(this List<A> a) {
        return a[0];
    }

    public static A Last<A>(this List<A> a) {
        return a[a.Count - 1];
    }
}

/*
 * A point in the discrete Octree (L3) space.
 */
public struct Point {
    public int X {get; set;}
    public int Y {get; set;}
    public int Z {get; set;}

    /*
     * A tree always covers a finite cube. So we essentially make  
     * the cube fill infinite space by repeating it in all directions.
     */
    public Point Clamp(int size) {
        return new Point {
            X = X % size,
            Y = Y % size,
            Z = Z % size,
        };
    }
}

/*
 * Space partition tree.
 *
 * Represents a cube of discrete L3-space, filled by matter.
 *
 * Contains raw partition data, origin point and the size of the cube.
 */
public class Octree {

    /*
    * Create simplest octree of 1 atom.
    */
    public static T<A> Atom<A>(
        A material,
        Point point = new Point(),
        int size = 1
    ) {
        return new T<A> {
            Root   = new T<A>.Node { Value = material },
            Origin = point,
            Edge   = size,
        };
    }

    /*
    * Merge 8 octrees into one.
    *
    * This will assume they all have the same size as
    * left-down-near tree and realign them near it.
    */
    public static T<A> Merge<A>(
        T<A> ldn,
        T<A> rdn,
        T<A> ldf,
        T<A> rdf,
        T<A> lun,
        T<A> run,
        T<A> luf,
        T<A> ruf
    ) {
        var children = new List<T<A>> {
            ldn, rdn, ldf, rdf, lun, run, luf, ruf,
        }.ConvertAll(it => it.Root);

        return new T<A> {
            Root   = new T<A>.Node { Children = children },
            Origin = ldn.Origin,
            Edge   = ldn.Edge * 2
        };
    }

    public class T<A> {

        /*
        * Tree node. Contains either an atom of matter
        * (which includes empty space) or an 8-subdivision
        * of nodes.
        */
        public class Node {
            public A          Value    {get; set;}
            public List<Node> Children {get; set;}

            /*
            * We can't really check Value (what if null is "air"?),
            * so "atom is when you can't divide further".
            */
            public bool IsLeaf { get { return Children == null; }}
        }

        public  Point  Origin   {get; set;}
        public  int    Edge     {get; set;}
        public  Node   Root     {get; set;}

        /*
        * Applies a function to each subtree.
        */
        public void Iterate(Action<T<A>> iter) =>
            Iterate(iter, _ => true);

        /*
        * Applies a function to each subtree.
        *
        * Predicate argument is for frustrum culling.
        */
        public void Iterate(Action<T<A>> iter, Predicate<T<A>> goIn) {
            if (goIn(this)) {
                iter(this);
                Descent().ForEach(subtree => {
                    subtree.Iterate(iter);
                });
            }
        }

        /*
        * Returns a list of direct subtrees.
        */
        public List<T<A>> Descent() {
            var radius = Edge / 2;

            var pts = new List<int> {
                0,1,2,3,4,5,6,7
            }.ConvertAll(i => new Point {
                X = Origin.X + ((i & 1) != 0 ? radius : 0),
                Y = Origin.Y + ((i & 2) != 0 ? radius : 0),
                Z = Origin.Z + ((i & 4) != 0 ? radius : 0),
            });

            return Root.Children.Zip(pts).ConvertAll((pair) =>
                new T<A> {
                    Root   = pair.Item1,
                    Origin = pair.Item2,
                    Edge   = radius,
                }
            );
        }

        /*
        * Applies a function to each atom.
        */
        public void Project(Action<Point, int, A> project) =>
            Project(project, _ => true);

        /*
        * Applies a function to each atom.
        *
        * Predicate argument is for frustrum culling.
        */
        public void Project(Action<Point, int, A> project, Predicate<T<A>> goIn) {
            Iterate(subtree => {
                if (subtree.Root.IsLeaf) {
                    project(subtree.Origin, subtree.Edge, subtree.Root.Value);
                }
            }, goIn);
        }

        /*
        * Returns a subtree, covering that point,
        * which is no smaller than given size.
        */
        public T<A> Focus(Point at, int size) =>
            SpineTo(at, size).Last();

        /*
        * Returns a path to point.
        */
        public List<T<A>> SpineTo(Point at, int size) {
            var i = this;
            var res = new List<T<A>>();

            at = at.Clamp(Edge);

            while (size < Edge) {
                res.Add(i);
                i = i.Descent().Where(subtree => subtree.Covers(at)).First();
            }

            return res;
        }

        /*
        * Checks if tree covers given point.
        */
        public bool Covers(Point point)
            => Origin.X >= point.X && Origin.X + Edge < point.X
            && Origin.Y >= point.Y && Origin.Y + Edge < point.Y
            && Origin.Z >= point.Z && Origin.Z + Edge < point.Z
        ;
    }
}

TreeController.cs

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class TreeController : MonoBehaviour
{
    Octree.T<Color?> space;

    Dictionary<(Point, int), GameObject> objects =
        new Dictionary<(Point, int), GameObject>();

    // Start is called before the first frame update
    void Start()
    {
        Debug.Log("Start");
        var air = Octree.Atom<Color?>(null);
        space = Octree.Merge(
            Octree.Atom<Color?>(Color.red),
            air, air, air, air, air, air,
            Octree.Atom<Color?>(Color.red)
        );
    }

    // Update is called once per frame
    void Update()
    {
        Debug.Log("Update");
        space.Project((pt, size, color) => {
            if (color != null) {
                Debug.Log("Drawing " + pt);
                var cube = GameObject.CreatePrimitive(PrimitiveType.Cube);
                cube.transform.position   = new Vector3(pt.X, pt.Y, pt.Z);
                cube.transform.localScale = new Vector3(size, size, size);
                objects[(pt, size)] = cube;
            }
        });
    }
}