/// <summary>
 /// Initializes and divides tree
 /// </summary>
 /// <param name="depthDivision">Depth of division</param>
 /// <param name="transformParent">Parent for tree trunk GameObject</param>
 public void InitializeTree(int depthDivision, Transform transformParent = null)
 {
     trunk = new OctreeNode();
     trunk.gameObject = new GameObject();
     trunk.gameObject.transform.parent = transformParent;
     trunk.AABB = new Bounds(Vector3.zero, new Vector3(4, 4, 4));
     DivideTree(2);
     InitializeDeepestNodesValue();
 }

 public void Build(MeshDesc desc, OctreeNode root)
 {
     desc.Clear();
     meshDesc = desc;
     if (root != null)
     {
         GenerateVertices(root);
         ContourCellProc(root);
     }
 }

    /// <summary>
    /// Recursively divides tree
    /// </summary>
    /// <param name="n">Current node</param>
    /// <param name="depth">Depth of division</param>
    /// <param name="_deepestNodes">List to add deepest nodes to</param>
    private void DivideTreeNode(OctreeNode n, int depth, List<OctreeNode> _deepestNodes)
    {
        var parentBB = n.AABB;
        OctreeNode t;
        Vector3 e = parentBB.extents /= 2;

        n.children.Add(t = new OctreeNode());
        t.AABB = parentBB;
        t.AABB.center += new Vector3(e.x, e.y, e.z);

        n.children.Add(t = new OctreeNode());
        t.AABB = parentBB;
        t.AABB.center += new Vector3(-e.x, e.y, e.z);

        n.children.Add(t = new OctreeNode());
        t.AABB = parentBB;
        t.AABB.center += new Vector3(e.x, -e.y, e.z);

        n.children.Add(t = new OctreeNode());
        t.AABB = parentBB;
        t.AABB.center += new Vector3(-e.x, -e.y, e.z);

        n.children.Add(t = new OctreeNode());
        t.AABB = parentBB;
        t.AABB.center += new Vector3(e.x, e.y, -e.z);

        n.children.Add(t = new OctreeNode());
        t.AABB = parentBB;
        t.AABB.center += new Vector3(-e.x, e.y, -e.z);

        n.children.Add(t = new OctreeNode());
        t.AABB = parentBB;
        t.AABB.center += new Vector3(e.x, -e.y, -e.z);

        n.children.Add(t = new OctreeNode());
        t.AABB = parentBB;
        t.AABB.center += new Vector3(-e.x, -e.y, -e.z);

        for (int i = 0; i < n.children.Count; i++)
        {
            t = n.children[i];
            t.parent = n;
            t.gameObject = new GameObject();
            t.gameObject.transform.position = t.AABB.center;
            t.gameObject.transform.localScale = t.AABB.size;
            t.gameObject.transform.parent = n.gameObject.transform;
        }

        if (depth-- > 0)
            for (int i = 0; i < n.children.Count; i++)
                DivideTreeNode(n.children[i], depth, _deepestNodes);
        else
            _deepestNodes.AddRange(n.children);
    }

    void DrawNode_EdgesMode(OctreeNode node)
    {
        const float dotSize = 0.01f;
        if (node.type == OctreeNode.Type.Leaf)
        {
            Vector3 nodeSize = new Vector3(size, size, size) * node.size;
            Vector3 center = node.min + nodeSize * 0.5f;
            Gizmos.DrawWireCube(center, nodeSize);

            Gizmos.DrawCube(node.info.position, new Vector3(dotSize, dotSize, dotSize));
        }
    }

 void DrawNode(OctreeNode node)
 {
     switch (mode)
     {
         case Mode.Hierarchy:
             DrawNode_HierarchyMode(node);
             break;
         case Mode.Edges:
             DrawNode_EdgesMode(node);
             break;
     }
 }

 public Octree(BoundingBox bounds, int maxDepth, int maxObjectsPerNode, int minObjectsPerNode)
 {
     Bounds = bounds;
     MaxDepth = maxDepth;
     MaxObjectsPerNode = maxObjectsPerNode;
     MinObjectsPerNode = minObjectsPerNode;
     Root = new OctreeNode(Bounds, this, 0, null);
     DebugDraw = false;
     Lock = new ReaderWriterLockSlim(LockRecursionPolicy.SupportsRecursion);
     ObjectsToNodes = new Dictionary<IBoundedObject, OctreeNode>();
     ObjectsToUpdate = new Dictionary<IBoundedObject, bool>();
     UpdateTimer = new Timer(1.0f, false);
 }

 void DrawNode_HierarchyMode(OctreeNode node)
 {
     Vector3 nodeSize = new Vector3(size, size, size) * node.size;
     Vector3 center = node.min + nodeSize * 0.5f;
     switch (node.type)
     {
         case OctreeNode.Type.Leaf:
             Gizmos.DrawCube(center, nodeSize);
             break;
         case OctreeNode.Type.Internal:
             Gizmos.DrawWireCube(center, nodeSize);
             break;
     }
 }

    public static void Build(OctreeNode node, int minSize)
    {
        if (node == null)
            return;
        if (node.size < minSize)
            return;

        int childSize = node.size / 2;
        for (int i = 0; i < 8; ++i)
        {
            OctreeNode child = new OctreeNode();
            child.type = OctreeNode.Type.Internal;
            child.size = childSize;
            child.min = node.min + (CHILD_MIN_OFFSETS[i] * childSize);
            Build(child, minSize);
            node.children[i] = child;
        }
    }

    void ContourCellProc(OctreeNode node)
    {
        if (node.type == OctreeNode.Type.Internal)
        {
            for (int i = 0; i < node.children.Length; ++i)
            {
                OctreeNode child = node.children[i];
                if (child != null)
                    ContourCellProc(child);
            }

            for (int i = 0; i < 12; ++i)
            {
                OctreeNode[] faceNodes = new OctreeNode[2];
                int[] c = new int[2]{ cellProcFaceMask[i, 0], cellProcFaceMask[i, 1] };

                faceNodes[0] = node.children[c[0]];
                faceNodes[1] = node.children[c[1]];

                ContourFaceProc(faceNodes, cellProcFaceMask[i, 2]);
            }

            for (int i = 0; i < 6; ++i)
            {
                OctreeNode[] edgeNodes = new OctreeNode[4];
                int[] c = new int[4]
                {
                    cellProcEdgeMask[i, 0],
                    cellProcEdgeMask[i, 1],
                    cellProcEdgeMask[i, 2],
                    cellProcEdgeMask[i, 3],
                };

                for (int j = 0; j < 4; ++j)
                {
                    edgeNodes[j] = node.children[c[j]];
                }

                ContourEdgeProc(edgeNodes, cellProcEdgeMask[i, 4]);
            }
        }
    }

 public static OctreeChildCoords FromIndex(OctreeNode.ChildIndex index)
 {
     switch (index)
     {
         case OctreeNode.ChildIndex.LeftBelowBack:
             return new OctreeChildCoords(0, 0, 0);
         case OctreeNode.ChildIndex.LeftBelowForward:
             return new OctreeChildCoords(0, 0, 1);
         case OctreeNode.ChildIndex.LeftAboveBack:
             return new OctreeChildCoords(0, 1, 0);
         case OctreeNode.ChildIndex.LeftAboveForward:
             return new OctreeChildCoords(0, 1, 1);
         case OctreeNode.ChildIndex.RightBelowBack:
             return new OctreeChildCoords(1, 0, 0);
         case OctreeNode.ChildIndex.RightBelowForward:
             return new OctreeChildCoords(1, 0, 1);
         case OctreeNode.ChildIndex.RightAboveBack:
             return new OctreeChildCoords(1, 1, 0);
         case OctreeNode.ChildIndex.RightAboveForward:
             return new OctreeChildCoords(1, 1, 1);
         default:
             throw new ArgumentOutOfRangeException("index", index, null);
     }
 }

                /// <summary>
                /// Add a color into the tree
                /// </summary>
                /// <param name="pixel">
                /// The color
                /// </param>
                /// <param name="colorBits">
                /// The number of significant color bits
                /// </param>
                /// <param name="level">
                /// The level in the tree
                /// </param>
                /// <param name="octree">
                /// The tree to which this node belongs
                /// </param>
                public void AddColor(Color32* pixel, int colorBits, int level, Octree octree)
                {
                    // Update the color information if this is a leaf
                    if (this.leaf)
                    {
                        this.Increment(pixel);

                        // Setup the previous node
                        octree.TrackPrevious(this);
                    }
                    else
                    {
                        // Go to the next level down in the tree
                        int shift = 7 - level;
                        int index = ((pixel->R & Mask[level]) >> (shift - 2)) |
                                    ((pixel->G & Mask[level]) >> (shift - 1)) |
                                    ((pixel->B & Mask[level]) >> shift);

                        OctreeNode child = this.children[index];

                        if (null == child)
                        {
                            // Create a new child node & store in the array
                            child = new OctreeNode(level + 1, colorBits, octree);
                            this.children[index] = child;
                        }

                        // Add the color to the child node
                        child.AddColor(pixel, colorBits, level + 1, octree);
                    }
                }

                /// <summary>
                /// Initializes a new instance of the <see cref="OctreeNode"/> class. 
                /// </summary>
                /// <param name="level">
                /// The level in the tree = 0 - 7
                /// </param>
                /// <param name="colorBits">
                /// The number of significant color bits in the image
                /// </param>
                /// <param name="octree">
                /// The tree to which this node belongs
                /// </param>
                public OctreeNode(int level, int colorBits, Octree octree)
                {
                    // Construct the new node
                    this.leaf = level == colorBits;

                    this.red = this.green = this.blue = 0;
                    this.pixelCount = 0;

                    // If a leaf, increment the leaf count
                    if (this.leaf)
                    {
                        octree.Leaves++;
                        this.nextReducible = null;
                        this.children = null;
                    }
                    else
                    {
                        // Otherwise add this to the reducible nodes
                        this.nextReducible = octree.ReducibleNodes[level];
                        octree.ReducibleNodes[level] = this;
                        this.children = new OctreeNode[8];
                    }
                }

            /// <summary>
            /// Reduce the depth of the tree
            /// </summary>
            private void Reduce()
            {
                // Find the deepest level containing at least one reducible node
                int index = this.maxColorBits - 1;
                while ((index > 0) && (null == this.reducibleNodes[index]))
                {
                    index--;
                }

                // Reduce the node most recently added to the list at level 'index'
                OctreeNode node = this.reducibleNodes[index];
                this.reducibleNodes[index] = node.NextReducible;

                // Decrement the leaf count after reducing the node
                this.leafCount -= node.Reduce();

                // And just in case I've reduced the last color to be added, and the next color to
                // be added is the same, invalidate the previousNode...
                this.previousNode = null;
            }

 /// <summary>
 /// Keep track of the previous node that was quantized
 /// </summary>
 /// <param name="node">
 /// The node last quantized
 /// </param>
 protected void TrackPrevious(OctreeNode node)
 {
     this.previousNode = node;
 }

 /// <summary>
 /// Initializes a new instance of the <see cref="Octree"/> class. 
 /// </summary>
 /// <param name="maxColorBits">
 /// The maximum number of significant bits in the image
 /// </param>
 public Octree(int maxColorBits)
 {
     this.maxColorBits = maxColorBits;
     this.leafCount = 0;
     this.reducibleNodes = new OctreeNode[9];
     this.root = new OctreeNode(0, this.maxColorBits, this);
     this.previousColor = 0;
     this.previousNode = null;
 }

 /// <summary>
 /// Keep track of the previous node that was quantized
 /// </summary>
 /// <param name="node">The node last quantized</param>
 protected void trackPrevious(OctreeNode node)
 {
     _previousNode = node;
 }

 /// <summary>When a reducible node is added, this method is called to add it to the appropriate
 /// reducible node list (given its level)</summary>
 /// <param name="reducibleNode">node to add to a reducible list</param>
 private void AddReducibleNode(OctreeNode reducibleNode)
 {
     // hook this node into the front of the list.
     // this means the last one added will be the first in the list.
     reducibleNode.NextReducibleNode = this.octreeReducibleNodes[reducibleNode.Level];
     this.octreeReducibleNodes[reducibleNode.Level] = reducibleNode;
 }

 /// <summary>
 /// Construct the octree
 /// </summary>
 /// <param name="maxColorBits">The maximum number of significant bits in the image</param>
 public Octree(int maxColorBits)
 {
     _maxColorBits = maxColorBits;
     _leafCount = 0;
     _reducibleNodes = new OctreeNode[9];
     _root = new OctreeNode(0, _maxColorBits, this);
     _previousColor = 0;
     _previousNode = null;
 }

 /// <summary> Keep track of the previous node that was quantized. </summary>
 /// <param name="node"> The node last quantized. </param>
 void TrackPrevious( OctreeNode node ) {
     previousNode = node;
 }

 public Octree(float xMax, float xMin, float yMax, float yMin, float zMax, float zMin, int maxItems, float minSize)
 {
     Top = new OctreeNode(xMax, xMin, yMax, yMin, zMax, zMin, maxItems, minSize);
 }