C＃quadtree效率

我相對較新的統一，所以我決定開始寫一個小平臺物理引擎在C＃中的主要統計結構是四叉樹。不幸的是，我的代碼速度非常慢，需要4秒鐘才能爲10K對象（普通的C＃對象而不是GameObjects）構建四叉樹。C＃quadtree效率

該代碼與普通四叉樹略有不同，而不是存儲在根節點中重疊區域的對象，引用存儲在包含對象的每個子節點中。由於我的所有對象都具有相同的大小，並且節點的最小大小是此大小的兩倍，因此以此方式構建樹會將碰撞算法的效率從〜O（N ^（3/2））提高到〜O （N）。

我的簡單四叉樹類如下所示：

using UnityEngine; 
using System.Collections; 
using System.Collections.Generic; 
using System; 

public class QuadTree { 

    public QuadTree parent = null; 
    public QuadTree[] childern = null; 
    public List<PPObject> objectList = null; 
    public BBox bbox = null; 

    public bool leaf = true; 
    public float minSize = 1.0f; 
    public float maxObjs = 4; 

    public float width; 
    public float height; 
    public Vector3 position; 
    public int level; 

    public QuadTree(QuadTree parent, BBox bbox, int level) 
    { 
     this.parent = parent; 
     this.bbox = bbox; 
     this.level = level; 
     width = bbox.xmax - bbox.xmin; 
     height = bbox.ymax - bbox.ymin; 
     position = new Vector3(bbox.xmin + width * 0.5f, bbox.ymin + height * 0.5f, 0.0f); 

     objectList = new List<PPObject>(); 
    } 

    public void Subdivide() 
    { 
     Profiler.BeginSample("Subdivide"); 
     float x1 = bbox.xmin; 
     float x2 = bbox.xmin + 0.5f * width; 
     float x3 = bbox.xmax; 
     float y1 = bbox.ymin; 
     float y2 = bbox.ymin + height * 0.5f; 
     float y3 = bbox.ymax; 

     Profiler.BeginSample("allocate new quadtrees"); 
     childern = new QuadTree[4]; 
     QuadTree tl = new QuadTree(this, new BBox(x1, x2, y2, y3), level + 1); 
     QuadTree tr = new QuadTree(this, new BBox(x2, x3, y2, y3), level + 1); 
     QuadTree br = new QuadTree(this, new BBox(x2, x3, y1, y2), level + 1); 
     QuadTree bl = new QuadTree(this, new BBox(x1, x2, y1, y2), level + 1); 

     childern[0] = tl; 
     childern[1] = tr; 
     childern[2] = br; 
     childern[3] = bl; 
     Profiler.EndSample(); 

     PushToChildern(); 

     leaf = false; 
     Profiler.EndSample(); 
    } 

    public void PushToChildern() 
    { 
     Profiler.BeginSample("pushToChildern"); 
     foreach (QuadTree child in childern) 
     { 
      foreach (PPObject obj in objectList) 
      { 
       child.AddObject(obj); 
      } 
     } 

     objectList = null; 
     Profiler.EndSample(); 
    } 

    public void AddObject(PPObject obj) 
    { 
     Profiler.BeginSample("addObject"); 
     if (childern == null) 
     { 
      if (obj != null) 
      { 
       float x1 = obj.position.x; 
       float w1 = obj.bbox.xmax - obj.bbox.xmin; 

       float y1 = obj.position.y; 
       float h1 = obj.bbox.ymax - obj.bbox.ymin; 

       float dx = Math.Abs(x1-position.x); 

       float dy = Math.Abs(y1-position.y); 

       if (dx < ((width+w1) * 0.5f) && dy < (height + h1) *0.5f) 
       { 
        objectList.Add(obj); 
       } 
      } 

      if (objectList.Count > maxObjs && width > minSize && height > minSize) 
      { 
       Subdivide(); 
      } 
     } else { 
      foreach (QuadTree child in childern) 
      { 
       child.AddObject(obj); 
      } 
     } 
     Profiler.EndSample(); 
    } 
}

這裏BBOX和PPObject是含有位置，範圍，速度等只是簡單的類，而不必詳細分析器用於進行4秒上述執行時間對象空間範圍在0.99到0.4之間。如果有人能幫助我理解爲什麼這麼慢，那會很棒。可能有100K函數調用的順序，以及總共3.4 Mb的20K實例化。也許我太習慣在Fortran中編寫代碼，但這對於在〜10 GFlop內核上運行似乎很荒謬。

謝謝！

來源

2016-10-18 Graham Reid

作爲參考，創建10K PPObjects並將其添加到列表中需要4.8毫秒：/ –

乍一看'foreach'很慢，用'float's工作降低性能，您可能要考慮使用' struct's而不是'class'es，最後取決於堆的'動態性'和object-count，你的GC可能會顯着減慢速度 – Benj

我想我知道我的問題是什麼。事實上，我正在非常糟糕地構建四叉樹。最終結果是，我有效地構建了大約1000x（和1000x4ms = 4s）的相同列表。將發佈更新的版本，這與我原來的愚蠢設計分析一起正常工作。 –

基本上，我首先實例化了樹的深度，而不是第一個寬度。這導致我製作了相關列表的許多額外的（原始未分配的）副本。下面的代碼在我的機器上執行約50ms，減少100倍。有一點tweeking，它應該適用於遊戲引擎。

using UnityEngine; 
using System.Collections; 
using System.Collections.Generic; 
using System; 

public class QuadTree 
{ 

    public QuadTree parent = null; 
    public QuadTree[] childern = null; 
    public List<PPObject> objectList = null; 
    public BBox bbox = null; 

    public bool leaf = true; 
    public float minSize = 1.0f; 
    public float maxObjs = 4; 

    public float width; 
    public float height; 
    public Vector3 position; 
    public int level; 

    public QuadTree(QuadTree parent, BBox bbox, List<PPObject> objectList, int level) 
    { 
     this.parent = parent; 
     this.bbox = bbox; 
     this.level = level; 
     width = bbox.xmax - bbox.xmin; 
     height = bbox.ymax - bbox.ymin; 
     position = new Vector3(bbox.xmin + width * 0.5f, bbox.ymin + height * 0.5f, 0.0f); 

     this.objectList = objectList; 
     BuildTree(); 
    } 

    public QuadTree(QuadTree parent, BBox bbox, int level) 
    { 
     this.parent = parent; 
     this.bbox = bbox; 
     this.level = level; 
     width = bbox.xmax - bbox.xmin; 
     height = bbox.ymax - bbox.ymin; 
     position = new Vector3(bbox.xmin + width * 0.5f, bbox.ymin + height * 0.5f, 0.0f); 

     objectList = new List<PPObject>(); 
    } 

    public void Subdivide() 
    { 
     if (objectList.Count > maxObjs && childern == null && width > minSize && height > minSize) 
     { 
      float x1 = bbox.xmin; 
      float x2 = bbox.xmin + 0.5f * width; 
      float x3 = bbox.xmax; 
      float y1 = bbox.ymin; 
      float y2 = bbox.ymin + height * 0.5f; 
      float y3 = bbox.ymax; 

      childern = new QuadTree[4]; 
      BBox tlBBox = new BBox(x1, x2, y2, y3); 
      BBox trBBox = new BBox(x2, x3, y2, y3); 
      BBox brBBox = new BBox(x2, x3, y1, y2); 
      BBox blBBox = new BBox(x1, x2, y1, y2); 

      QuadTree tl = new QuadTree(this, tlBBox, level + 1); 
      QuadTree tr = new QuadTree(this, trBBox, level + 1); 
      QuadTree br = new QuadTree(this, brBBox, level + 1); 
      QuadTree bl = new QuadTree(this, blBBox, level + 1); 

      foreach (PPObject obj in objectList) 
      { 
       tl.AddObject(obj); 
       tr.AddObject(obj); 
       br.AddObject(obj); 
       bl.AddObject(obj); 
      } 

      childern[0] = tl; 
      childern[1] = tr; 
      childern[2] = br; 
      childern[3] = bl; 

      objectList = new List<PPObject>(); 

      leaf = false; 

     } 
     else if (childern != null) 
     { 
      PushToChildern(); 
     } 
    } 

    public void PushToChildern() 
    { 
     foreach (QuadTree child in childern) 
     { 
      foreach (PPObject obj in objectList) 
      { 
       child.AddObject(obj); 
      } 
     } 

     objectList = null; 
    } 

    public bool CheckBounds(PPObject obj, BBox region) 
    { 
     float x1 = obj.position.x; 
     float w1 = obj.bbox.xmax - obj.bbox.xmin; 

     float y1 = obj.position.y; 
     float h1 = obj.bbox.ymax - obj.bbox.ymin; 

     float dx = Math.Abs(x1 - position.x); 

     float dy = Math.Abs(y1 - position.y); 

     if (dx < ((width + w1) * 0.5f) && dy < (height + h1) * 0.5f) 
     { 
      return true; 
     } 
     return false; 
    } 

    /* 
    * Make this faster by building the list to push here 
    */ 
    public void AddObject(PPObject obj) 
    { 
     if (obj != null) 
     { 
      if (CheckBounds(obj, bbox)) 
      { 
       objectList.Add(obj); 
      } 
     } 
    } 

    public void BuildTree() 
    { 
     Subdivide(); 
     if (childern != null) 
     { 
      foreach(QuadTree child in childern) 
      { 
       child.BuildTree(); 
      } 
     } 
    } 
}

來源

2016-10-19 05:03:19

C＃quadtree效率

回答

相關問題