如何在C＃中实现八叉树？

Question

第一次在这里发布，但我已经阅读了几年的网站。我正在尝试在C＃中实现一个简单的通用类型Octree（使用一些XNA包含项）。我已经进行了深入的研究，并且理解了这个概念，但似乎无法使其实用。到处搜索会产生其他语言的一些实现，但是它们似乎都是针对特定应用定制的。而且我还真的无法从这些事情中获得多大意义。

下面是到目前为止的Octree类，Vector3，BoundingBox和ContainmentType来自XNA。我输入最大和最小点，以及边界内的点列表。但是，实际上没有任何点添加到树中。任何帮助将非常感激！

public class Octree<T> : ISerializable
{   
    Vector3 max;
    Vector3 min;
    OctreeNode head;

    public Octree(Vector3 min, Vector3 max, List<Vector3> values)
    {
        this.max = max;
        this.min = min;
        head = new OctreeNode( min, max,  values);           
    }

    public Octree() { }

    public Octree(SerializationInfo info, StreamingContext context)
    {
    }

    public void GetObjectData(SerializationInfo info, StreamingContext context)
    {            
    }

    internal class OctreeNode
    {            
        Vector3 max;
        Vector3 min;
        Vector3 center;
        public Vector3 position;
        public T data;

        public BoundingBox nodeBox;
        public List<OctreeNode> subNodes;
        public OctreeNode( Vector3 min, Vector3 max,List<Vector3> coords)
        {
            nodeBox = new BoundingBox(min, max);
            subNodes = new List<OctreeNode>();

            this.min = min;
            this.max = max;
            center = (min + ((max - min) / 2));

            nodeBox = new BoundingBox(min, max);
            if (coords.Count == 0)
            { return; }
            subNodes.Add(new OctreeNode(center, max));
            subNodes.Add(new OctreeNode(new Vector3(min.X, center.Y, center.Z), new Vector3(center.X, max.Y, min.Z)));
            subNodes.Add(new OctreeNode(new Vector3(min.X, center.Y, max.Z), new Vector3(center.X, max.Y, center.Z)));
            subNodes.Add(new OctreeNode(new Vector3(center.X, center.Y, max.Z), new Vector3(max.X, max.Y, center.Z)));

            subNodes.Add(new OctreeNode(new Vector3(center.X, min.Y, center.Z), new Vector3(max.X, center.Y, min.Z)));
            subNodes.Add(new OctreeNode(new Vector3(min.X, min.Y, center.Z), new Vector3(center.X, center.Y, min.Z)));
            subNodes.Add(new OctreeNode(new Vector3(min.X, min.Y, max.Z), center));
            subNodes.Add(new OctreeNode(new Vector3(center.X,min.Y,max.Z), new Vector3(max.X,center.Y,center.Z)));


            List<List<Vector3>> octants = new List<List<Vector3>>();
            for (int i = 0; i < 8; i++)
            {
                octants.Add(new List<Vector3>());
            }
            foreach (Vector3 v in coords)
            {
                int i = 0;
                foreach(OctreeNode n in subNodes)
                {
                    ContainmentType t = n.nodeBox.Contains(v);

                    if (t.Equals(ContainmentType.Contains))
                    {
                        octants[i].Add(v);
                    }
                    i++;
                }
            }

            for (int i=0;i<subNodes.Count;i++)
            {
                if (octants[i].Count > 0)
                {
                    Vector3 v = octants[i][0];
                    octants[i].Remove(v);
                    subNodes[i] = new OctreeNode(subNodes[i].min, subNodes[i].max, octants[i]);
                }
            }
        }

        public OctreeNode(Vector3 min, Vector3 max)
        {
            nodeBox = new BoundingBox(min, max);
        }            
    }
}

Answer 1

我将您的代码粘贴到Visual Studio的新项目中，并调试了Octree带有几个点值的构造函数。这里有一些简单的选择，应该可以帮助您使八叉树发挥作用。

1. 在中OctreeNode(Vector3 min, Vector3 max, List<Vector3> coords)，有些subNodes没有合理的最小和最大界限。例如，new Vector3(min.X, min.Y, max.Z), center范围从max.Z到center.z。上限始终小于下限。尝试系统地列出节点，以减少发生此类错误的可能性，如下所示：

   subNodes.Add(new OctreeNode(new Vector3(min.X,    min.Y,    min.Z),    new Vector3(center.X, center.Y, center.Z)));
   subNodes.Add(new OctreeNode(new Vector3(min.X,    min.Y,    center.Z), new Vector3(center.X, center.Y, max.Z)));
   subNodes.Add(new OctreeNode(new Vector3(min.X,    center.Y, min.Z),    new Vector3(center.X, max.Y,    center.Z)));
   subNodes.Add(new OctreeNode(new Vector3(min.X,    center.Y, center.Z), new Vector3(center.X, max.Y,    max.Z)));
   subNodes.Add(new OctreeNode(new Vector3(center.X, min.Y,    min.Z),    new Vector3(max.X,    center.Y, center.Z)));
   subNodes.Add(new OctreeNode(new Vector3(center.X, min.Y,    center.Z), new Vector3(max.X,    center.Y, max.Z)));
   subNodes.Add(new OctreeNode(new Vector3(center.X, center.Y, min.Z),    new Vector3(max.X,    max.Y,    center.Z)));
   subNodes.Add(new OctreeNode(new Vector3(center.X, center.Y, center.Z), new Vector3(max.X,    max.Y,    max.Z)));
   

2. 在构造函数中OctreeNode(Vector3 min, Vector3 max)你不初始化场min，max和center。结果，当最终的OctreeNodes的上下限始终在行上设置为零时

      subNodes[i] = new OctreeNode(subNodes[i].min, subNodes[i].max, octants[i]);
   

3. 在同一行，你作为节点值的所有点通过，但在一个实际上就在于节点的范围。局部变量v是该范围内的值。将其从中删除octants后octants作为节点值传递。

4. 传递给OctreeNode构造函数的值实际上不会存储在任何位置，但是创建的节点始终会拆分为较小的节点，并将这些值传递给子节点。因此，解决以上三个问题将导致代码无限递归。要中断递归，您需要实现暂停条件。通常在八叉树中的条件是，如果节点内的值数量足够少，则该节点不会拆分为子节点，而是将值存储在该节点中。仅当节点包含足够多的值时，才对节点进行拆分，并将其值分布在新的子节点之间。