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

    public static Boolean All<A>(this List<A> a, Predicate<A> pred) {
        for (int i = 0; i < a.Count; i++) {
            if (!pred(a[i])) {
                return false;
            }
        }
        return true;
    }

    /*
     * 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];
    }

    public static string Show<A>(this List<A> a) {
        string s = "[]";
        a.ForEach(x => s = x + " :: " + s);
        return s;
    }
}

/*
 * 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,
        };
    }

    public override string ToString() {
        return $"({X}, {Y}, {Z})";
    }
}

/*
 * 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 = 2
    ) {
        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
    ) {
        return MergeList(new List<T<A>> {
            ldn, rdn, ldf, rdf, lun, run, luf, ruf,
        });
    }

    public static T<A> MergeList<A>(
        List<T<A>> trees
    ) {
        var children = trees.ConvertAll(it => it.Root);

        return new T<A> {
            Root   = new T<A>.Node { Children = children },
            Origin = trees.First().Origin,
            Edge   = trees.First().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 override string ToString() {
                if (IsLeaf) {
                    return $"Leaf {Value}";
                } else {
                    return $"Split {Children.Show()}";
                }
            }
        }

        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) {
            int x = 0;
            var stack = new Stack<T<A>>();
            stack.Push(this);

            while (stack.Count > 0) {
                x++;

                if (x > 50000) {
                    return;
                    throw new Exception($"what {stack.Count}");
                }

                var i = stack.Pop();
                if (goIn(i)) {
                    iter(i);
                    if (!i.Root.IsLeaf) {
                        i.Descent().ForEach(s => {
                            stack.Push(s);
                        });
                    }
                }
            }
        }

        public List<T<A>> Descent() {
            return DescentOf(Root.Children);
        }

        /*
        * Returns a list of direct subtrees.
        */
        public List<T<A>> DescentOf(List<T<A>.Node> children) {
            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 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 && !i.Root.IsLeaf) {
                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
        ;
        
        public void Insert(Point point, A value, Func<A, A, Boolean> compare, int size = 2) {
            Stack<T<A>> stack = new Stack<T<A>>();
            point = point.Clamp(this.Edge);

            var i = this;
            while (i.Edge > size) {
                stack.Push(i);
                i.AtomToSplit();
                var subs = i.Descent();
                // Debug.Log($"i {i.Edge}");
                // Debug.Log($"i {subs}");
                // Debug.Log($"i {point}");
                // Debug.Log($"i {subs.ConvertAll(s => (s.Origin, s.Edge)).Show()}");
                i = subs
                    .Where(tree => tree.Covers(point))
                    .First();
            }
            i.Root.Value = value;
            if (!i.Root.IsLeaf) {
                throw new Exception($"Nuclear launch detected {i}");
            }

            while (stack.Count > 0) {
                var j = stack.Pop();
                if (j.Root.Children.All(child => child.IsLeaf)) {
                    var atoms = j.Root.Children.ConvertAll(c => c.Value);

                    if (atoms.All(atom => compare(atom, atoms[0]))) {
                        j.Root.Value = atoms[0];
                        j.Root.Children = null;
                    }
                }
            }
        }

        public void AtomToSplit() {
            if (this.Root.IsLeaf) {
                List<T<A>.Node> subatoms = new List<T<A>.Node>();
                for (int i = 0; i < 8; i++) {
                    subatoms.Add(new Node { Value = this.Root.Value });
                    this.Root.Children = subatoms;
                }
            }
        }

        public List<T<A>> Split() {
            if (this.Root.IsLeaf) {
                return DescentOf(
                    new List<T<A>.Node> {
                        this.Root,
                        this.Root,
                        this.Root,
                        this.Root,
                        this.Root,
                        this.Root,
                        this.Root,
                        this.Root
                    }
                );
            } else {
                return Descent();
            }
        }
    }
}

TreeController.cs

using System;
using System.IO;
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using UnityEditor;

[InitializeOnLoad]
public class TreeController : MonoBehaviour
{
    static TreeController() {
        if (true) {
            Start();

            EditorApplication.update += Update;
        }

        if (true) {
            VoxLoader loader = new VoxLoader(
                File.OpenRead("Assets/Models/ul.vox")
            );
            VoxLoader.Vox vox;
            try {
                vox = loader.GetVox();
                vox.Models.First().Item2.Voxels.ForEach(voxel => {
                    space.Insert(
                        new Point { X = voxel.X, Y = voxel.Y, Z = voxel.Z }, 
                        Color.red,
                        (a, b) => a == b
                    );
                });
                Debug.Log($"LOADED! {vox.Models.First().Item2.Voxels.Count}");
            } catch (Exception e) {
                Debug.Log(e);
            }
        }

        if (true) {
            space.Project((pt, size, color) => {
                if (color != null && !objects.ContainsKey(pt) && size > 2) {
                    var cube = GameObject.CreatePrimitive(PrimitiveType.Cube);
                    
                    cube.transform.localScale = new Vector3(size, size, size);
                    cube.transform.position   = new Vector3(
                        (float) pt.X + size / 2,
                        (float) pt.Y + size / 2,
                        (float) pt.Z + size / 2
                    );
                    
                    Dictionary<int, Color> colors = new Dictionary<int, Color>();

                    colors.Add(2,  Color.red);
                    colors.Add(4,  Color.yellow);
                    colors.Add(8,  Color.green);
                    colors.Add(16, Color.blue);

                    cube.GetComponent<Renderer>().material.color =
                        colors.ContainsKey(size) ? colors[size] : Color.red;
                    
                    objects[pt] = cube;
                }
            });
        }
    }

    static Octree.T<Color?> space;

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

    // Start is called before the first frame update
    static void Start()
    {
        space = Octree.Atom<Color?>(null, new Point(), 128);
    }

    // Update is called once per frame
    static void Update()
    {
    }
}

VoxLoader.cs

using System;
using System.IO;
using System.Text;
using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class VoxLoader {

    public class Header<TBody> {
        public int   Version {get; set;}
        public TBody Body    {get; set;}
    }

    public class Chunk<TContent, TChildren> {
        public TContent        Content  {get; set;}
        public List<TChildren> Children {get; set;}
    }

    public class ChunkConf<TContent> {
        public string   ID          {get; set;}
        public int      ContentSize {get; set;}
        public int      ChildrenCount  {get; set;}
        public TContent Content     {get; set;}
    }

    public interface Or<A, B> {
        C Match<C>(Func<A, C> left, Func<B, C> right);
    }

    public class Left<A, B> : Or<A, B> {
        A a;
        
        public Left(A a) {
            this.a = a;
        }

        public C Match<C>(Func<A, C> left, Func<B, C> right) {
            return left(a);
        }
    }

    public class Right<A, B> : Or<A, B> {
        B b;
        
        public Right(B b) {
            this.b = b;
        }

        public C Match<C>(Func<A, C> left, Func<B, C> right) {
            return right(b);
        }
    }

    public class Pack {
        public int NumModels {get; set;}
    }

    public class Size {
        public int X {get; set;}
        public int Y {get; set;}
        public int Z {get; set;}
    }

    public class Voxel {
        public int X {get; set;}
        public int Y {get; set;}
        public int Z {get; set;}
        
        public int ColorIndex {get; set;}

        public override string ToString() {
            return $"({X}, {Y}, {Z}, {ColorIndex})";
        }
    }

    public class XYZI {
        public List<Voxel> Voxels {get; set;}
    }

    public class Color {
        public byte R {get; set;}
        public byte G {get; set;}
        public byte B {get; set;}
        public byte A {get; set;}
    }

    public class RGBA {
        public List<Color> Colors {get; set;}
    }

    public class Material {
        public enum TType {
            DIFFUSE  = 0,
            METAL    = 1,
            GLASS    = 2,
            EMISSIVE = 3,
        }

        public enum TFlags {
            PLASTIC     = 1,
            ROUGHNESS   = 2,
            SPECULAR    = 4,
            IOR         = 8,
            ATTENUATION = 16,
            POWER       = 32,
            GLOW        = 64,
            TOTAL       = 128,
        }

        public int    ID     {get; set;}
        public TType  Type   {get; set;}
        public float  Weight {get; set;}
        public TFlags Flags  {get; set;}

        public Dictionary<TFlags, float> Values {get; set;}
    }

    public class Vox {
        public int                Version   {get; set;}
        public List<(Size, XYZI)> Models    {get; set;}
        public RGBA               RGBA      {get; set;}
        public List<MATL>         Materials {get; set;}
        public List<LAYR>         Layers    {get; set;}
        public List<Scene>        Scene     {get; set;}
    }

    public class NTRN {
        public int  ID         {get; set;}
        public Dictionary<string, string> Attributes {get; set;}
        public int  ChildID    {get; set;}
        public int  ReservedID {get; set;}
        public int  LayerID    {get; set;}
        public int  Frames     {get; set;}

        public List<Dictionary<string, string>> FrameAttributes {get; set;}
    }

    public class NGRP {
        public int                        ID            {get; set;}
        public Dictionary<string, string> Attributes    {get; set;}
        public int                        ChildrenCount {get; set;}
        public List<int>                  ChildIDs      {get; set;}
    }

    public class NSHP {
        public int                        ID         {get; set;}
        public Dictionary<string, string> Attributes {get; set;}
        public int                        ModelCount {get; set;}
        public List<(int, Dictionary<string, string>)>
            ModelAttributes {get; set;}
    }

    public class MATL {
        public int                        ID         {get; set;}
        public Dictionary<string, string> Attributes {get; set;}
    }

    public class LAYR {
        public int                        ID         {get; set;}
        public Dictionary<string, string> Attributes {get; set;}
        public int                        ReservedID {get; set;}
    }

    public LAYR GetLAYR() {
        var id     = Int();     Debug.Log($"LAYR  {id}");
        var attrs  = GetDict(); Debug.Log($"LAYR' {attrs}");
        var rid    = Int(-1);   Debug.Log($"LAYR` {rid}");

        return new LAYR {
            ID = id,
            Attributes = attrs,
            ReservedID = rid,
        };
    }

    public MATL GetMATL() {
        var id     = Int();
        var attrs  = GetDict();

        return new MATL {
            ID = id,
            Attributes = attrs,
        };
    }

    public NSHP GetnSHP() {
        var id     = Int();
        var attrs  = GetDict();
        var nmods  = Int(1);
        var mods   = Times(nmods, () => And(() => Int(), GetDict));

        return new NSHP {
            ID            = id,
            Attributes    = attrs,
            ModelCount    = nmods,
            ModelAttributes = mods,
        };
    }

    public NGRP GetnGRP() {
        var id     = Int();
        var attrs  = GetDict();
        var ncids  = Int();
        var cids   = Times(ncids, () => Int());

        return new NGRP {
            ID            = id,
            Attributes    = attrs,
            ChildrenCount = ncids,
            ChildIDs      = cids,
        };
    }

    public NTRN GetnTRN() {
        var id     = Int();
        var attrs  = GetDict();
        var cid    = Int();
        var rid    = Int(-1);
        var lid    = Int();
        var frames = Int(1);
        var frAttr = Times(frames, GetDict);

        return new NTRN {
            ID = id,
            Attributes = attrs,
            ChildID = cid,
            ReservedID = rid,
            LayerID = lid,
            Frames = frames,
            FrameAttributes = frAttr,
        };
    }

    public class Scene {
        public NTRN nTRN {get; set;}
        public Or<Group, Item> Stuff {get; set;}
    }

    public class Group : Scene {
        public NGRP nGRP {get; set;}
        public List<Scene> Scenes {get; set;}
    }

    public class Item : Scene {
        public NSHP nSHP {get; set;}
    }

    public Scene GetScene() {
        var trnChunk = GetChunk("nTRN", GetnTRN);
        var scene = Either<Group, Item>(GetGroup, GetItem);

        return new Scene {
            nTRN = trnChunk.Content,
            Stuff = scene,
        };
    }

    public Item GetItem() {
        var item = GetChunk("nSHP", GetnSHP);
        return new Item {
            nSHP = item.Content
        };
    }

    public Group GetGroup() {
        var grpChunk = GetChunk("nGRP", GetnGRP);
        var subscenes = grpChunk.ChildrenCount;
        var subs = Times(subscenes, GetScene);

        return new Group {
            nGRP = grpChunk.Content,
            Scenes = subs,
        };
    }

    public Vox GetVox() {
        Singature("VOX ");
        var version = Int();
        var main    = GetChunk("MAIN", GetUnit);

        Debug.Log($"Version: {version}");
        Debug.Log($"ChildrenCount: {main.ChildrenCount}");

        Func<(Size, XYZI)> getModel = () => And<Size, XYZI>(
            () => GetChunk("SIZE", GetSize).Content,
            () => GetChunk("XYZI", GetZYZI).Content
        );

        var mpack     = Maybe(() => GetChunk("PACK", GetPack));
        var models    = Many(getModel);

        Debug.Log($"Models #: {models.Count}");
        var scene     = Many(GetScene);
        Debug.Log($"Scenes #: {scene.Count}");
        var layers    = Many(() => GetChunk("LAYR", GetLAYR));
        Debug.Log($"Layers #: {layers.Count}");

        var rgba      = Maybe(() => GetChunk("RGBA", GetRGBA));
        Debug.Log($"RGBA?: {rgba != null}");
        var materials = Many(() => GetChunk("MATL", GetMATL));
        Debug.Log($"Materials #: {materials.Count}");

        return new Vox {
            Version = version,
            Models = models,
            RGBA = rgba?.Content,
            Materials = materials.ConvertAll(m => m.Content),
        };
    }

    public A Maybe<A>(Func<A> action) where A : class {
        var pos = input.Position;
        try {
            return action();
        } catch (Exception _e) {
            input.Seek(pos, SeekOrigin.Begin);
            return null;
        }
    }

    public ChunkConf<TContent> GetChunk<TContent>(
        string id,
        Func<TContent> getContent
    ) {
        Singature(id);
        var contentLength = Int();
        var childrenCount = Int();
        var content       = getContent();
        return new ChunkConf<TContent> {
            ContentSize = contentLength,
            ChildrenCount  = childrenCount,
            Content     = content,
        };
    }

    public char GetUnit() { return 'a'; }

    public Pack GetPack() => new Pack { NumModels = Int () };

    public Size GetSize() {
        var x = Int();
        var y = Int();
        var z = Int();
        return new Size { X = x, Y = y, Z = z };
    }

    public XYZI GetZYZI() => new XYZI { Voxels = Times(Int(), GetVoxel) };

    public Voxel GetVoxel() {
        var bytes = Read(4);
        return new Voxel {
            X = bytes[0],
            Y = bytes[1],
            Z = bytes[2],
            ColorIndex = bytes[3],
        };
    }

    public RGBA GetRGBA() => new RGBA { Colors = Times(256, GetColor) };

    public Color GetColor() {
        var bytes = Read(4);
        return new Color {
            R = bytes[0],
            G = bytes[1],
            B = bytes[2],
            A = bytes[3],
        };
    }

    public Material GetMaterial() {
        var id     = Int();
        var type   = Int();
        var weight = Float();
        var flags  = Int();

        var flagKeys = new List<Material.TFlags> {
            Material.TFlags.PLASTIC,
            Material.TFlags.ROUGHNESS,
            Material.TFlags.SPECULAR,
            Material.TFlags.IOR,
            Material.TFlags.ATTENUATION,
            Material.TFlags.POWER,
            Material.TFlags.GLOW,
        };

        var dict = new Dictionary<Material.TFlags, float>();

        flagKeys.ForEach(key => {
            if (((int) key & flags) != 0) {
                dict.Add(key, Float());
            }
        });

        return new Material {
            ID = id,
            Type = (Material.TType) type,
            Weight = weight,
            Flags = (Material.TFlags) flags,
            Values = dict,
        };
    }

    Stream input;
    long offset = 0;

    public VoxLoader(Stream input) {
        this.input = input;
    }

    public byte[] Read(int count) {
        var bytes = new byte[count];
        var moved = input.Read(bytes, 0, count);
        offset = input.Position;

        if (moved < count) {
            throw new Exception("Unexpected EOF");
        }

        return bytes;
    }

    public (A, B) And<A, B>(Func<A> getA, Func<B> getB) {
        var a = getA();
        var b = getB();
        return (a, b);
    }

    public (A, B) Then<A, B>(Func<A> getA, Func<A, B> getB) {
        var a = getA();
        var b = getB(a);
        return (a, b);
    }

    public Or<A, B> Either<A, B>(Func<A> action, Func<B> other) {
        var pos = input.Position;
        try {
            return new Left<A, B>(action());
        } catch (Exception _e) {
            input.Seek(pos, SeekOrigin.Begin);
            offset = pos;
            return new Right<A, B>(other());
        }
    }

    public A While<A>(string message, Func<A> action) {
        var pos = input.Position;
        try {
            return action();
        } catch (Exception e) {
            input.Seek(pos, SeekOrigin.Begin);
            offset = pos;
            throw new Exception(
                e.Message + "\nwhile " + message
            );
        }
    }

    public void Singature(string str) {
        var bytes = Encoding.ASCII.GetBytes(str);
        var from  = Read(bytes.Length);

        for (var i = 0; i < bytes.Length; i++) {
            if (bytes[i] != from[i]) {
                Debug.Log($"Its not {str}, its {Encoding.ASCII.GetString(from)} @ {offset}");
                throw new Exception(
                    $"Expected {str} at offset {offset}"
                );
            }
        }
    }

    public int Int(int? asserted = null) {
        var value = BitConverter.ToInt32(Read(4), 0);
        if (asserted != null && asserted.Value != value) {
            throw new Exception(
                $"Expected {asserted}, got {value} @ {offset}"
            );
        }
        return value;
    }

    public float Float() {
        return BitConverter.ToSingle(Read(4), 0);
    }

    public string String() {
        var len   = Int();
        var bytes = Read(len);
        return Encoding.ASCII.GetString(bytes);
    }

    public class Rotation {
        public List<List<int>> R {get; set;}
    }

    public Rotation GetRotation() {
        var byde = Read(1)[0];
        var fstNZ =   byde       & 3;
        var sndNZ =  (byde >> 2) & 3;
        var fstSG = ((byde >> 4) & 1) == 1? -1 : 1;
        var sndSG = ((byde >> 5) & 1) == 1? -1 : 1;
        var trdSG = ((byde >> 6) & 1) == 1? -1 : 1;

        return new Rotation {
            R = new List<List<int>> {
                new List<int> {
                    fstNZ == 0? fstSG : 0,
                    fstNZ == 1? fstSG : 0,
                    fstNZ == 2? fstSG : 0,
                },
                new List<int> {
                    sndNZ == 0? sndSG : 0,
                    sndNZ == 1? sndSG : 0,
                    sndNZ == 2? sndSG : 0,
                },
                new List<int> {
                    trdSG,
                    0,
                    0,
                }
            }
        };
    }

    public Dictionary<String, String> GetDict() {
        var len   = Int();
        var pairs = Times(len, () => And(String, String));
        var dict  = new Dictionary<String, String>();

        pairs.ForEach(pair => {
            dict[pair.Item1] = pair.Item2;
        });

        return dict;
    }

    public List<A> Times<A>(int n, Func<A> action) {
        var res = new List<A>();
        
        for (var i = 0; i < n; i++) {
            res.Add(action());
        }

        return res;
    }

    public List<A> Many<A>(Func<A> action) {
        var res = new List<A>();
        
        while (true) {
            var pos = input.Position;
            try {
                res.Add(action());
            } catch(Exception _e) {
                input.Seek(pos, SeekOrigin.Begin);
                offset = pos;
                return res;
            }
        }
    }
}