如何在C＃中實現八叉樹？

Question

第一次在這裏發佈，但我已經閱讀了幾年現在的網站。我試圖在C＃中實現一個簡單的泛型類型的八叉樹（使用一些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構造。其結果是，當最終OctreeNode■找他們的上限和下限始終設爲零上線

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

3. 在同一條線上，你傳遞的節點值的所有點但的一個實際上位於節點的範圍內。局部變量v是位於範圍內的值。它從octants中刪除，之後octants作爲節點值傳遞。

4. 傳遞給OctreeNode構造函數的值實際上並沒有存儲在任何地方，但創建的節點總是被分割成更小的節點，並將值傳遞給子節點。因此修復上述三個問題將導致代碼進入無限遞歸。要打破遞歸，你需要實現一個停止條件。通常情況下，在八進制中，條件是如果節點內有足夠少的值，則節點不會被分割爲子節點，而是將值存儲在節點中。只有當節點包含足夠多的值時，節點纔會被拆分，並且其值分佈在新的子節點中。