4

第一次在这里发帖，但我已经阅读该网站几年了。我正在尝试在 C# 中实现一个简单的泛型八叉树（使用一些 XNA 包括）。我已经进行了彻底的研究并且我理解了这个概念，但我似乎无法让它发挥作用。四处搜索会产生一些其他语言的实现，但它们似乎都是针对特定应用程序定制的；我还没有真正理解这些。

下面是到目前为止我的八叉树类，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);
        }            
    }
}
4

1 回答 1

7

我将您的代码粘贴到 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。结果，当最后OctreeNode的 s 的下限和上限始终设置为零时

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

  3. 在同一行上，您将所有点作为节点值传入，但实际上位于节点范围内的点除外。局部变量v是位于范围内的值。它被删除，octants之后octants作为节点值传递。

  4. 传递给OctreeNode构造函数的值实际上并没有存储在任何地方，但是创建的节点总是被分割成更小的节点，并且这些值被传递给子节点。因此修复上述三个问题将导致代码无限递归。要中断递归，您需要实现一个停止条件。通常在八叉树中，条件是如果节点内的值数量足够少，则该节点不会拆分为子节点，而是将值存储在节点中。只有当节点包含足够多的值时，节点才会被拆分，并且它的值会分布在新的子节点中。

于 2013-03-15T22:27:39.653 回答