オクトリーの実装のスピードの懸念

Question

今、私はForce Directed Graphの実装をスピードアップしようとしています。これまで私は、計算数を減らすためにオクトリーを使用しているBarnes-Hutアルゴリズムを実装しました。私はそれを何度も試してみましたが、力に関連する計算の数は実際には大幅に減少しました。以下は、Barns-Hut（青い線）を使わないノードの数に対する計算のプロットです。 今はもっと速くなければなりませんが、真実はスピード（時間）アップグレードはわずか数パーセントです。

これは、ツリーの作成とツリー配置の要素が原因と考えられます。要素は絶えず動いているので、何らかの停止条件に達するまで、各ループを再作成する必要があります。しかし、木をつくるのに多くの時間を費やすと、そこでは力の計算が増えた時があります。それは少なくとも私の考えです。私はここでやっていることは、グラフ内のすべての私の要素を通過し、ツリーのルートに追加され

void AddTreeElements(Octree* tree, glm::vec3* boundries, Graph& graph) 
{ 
    for(auto& node:graph.NodeVector()) 
    { 
     node.parent_group = nullptr; 
     if(node.pos[0] < boundries[1][0] && node.pos[0] > boundries[0][0] && 
       node.pos[1] > boundries[4][1] && node.pos[1] < boundries[1][1] && 
       node.pos[2] < boundries[0][2] && node.pos[2] > boundries[3][2]) 
     { 
      tree->AddObject(&node.second); 
      continue; 
     } 

     if(node.pos[0] < boundries[0][0]) 
     { 
      boundries[0][0] = node.pos[0]-1.0f; 
      boundries[3][0] = node.pos[0]-1.0f; 
      boundries[4][0] = node.pos[0]-1.0f; 
      boundries[7][0] = node.pos[0]-1.0f; 
     } 
     else if(node.pos[0] > boundries[1][0]) 
     { 
      boundries[1][0] = node.pos[0]+1.0f; 
      boundries[2][0] = node.pos[0]+1.0f; 
      boundries[5][0] = node.pos[0]+1.0f; 
      boundries[6][0] = node.pos[0]+1.0f; 
     } 

     if(node.pos[1] < boundries[4][1]) 
     { 
      boundries[4][1] = node.pos[1]-1.0f; 
      boundries[5][1] = node.pos[1]-1.0f; 
      boundries[6][1] = node.pos[1]-1.0f; 
      boundries[7][1] = node.pos[1]-1.0f; 
     } 
     else if(node.pos[1] > boundries[0][1]) 
     { 
      boundries[0][1] = node.pos[1]+1.0f; 
      boundries[1][1] = node.pos[1]+1.0f; 
      boundries[2][1] = node.pos[1]+1.0f; 
      boundries[3][1] = node.pos[1]+1.0f; 
     } 

     if(node.pos[2] < boundries[3][2]) 
     { 
      boundries[2][2] = node.pos[2]-1.0f; 
      boundries[3][2] = node.pos[2]-1.0f; 
      boundries[6][2] = node.pos[2]-1.0f; 
      boundries[7][2] = node.pos[2]-1.0f; 
     } 
     else if(node.pos[2] > boundries[0][2]) 
     { 
      boundries[0][2] = node.pos[2]+1.0f; 
      boundries[1][2] = node.pos[2]+1.0f; 
      boundries[4][2] = node.pos[2]+1.0f; 
      boundries[5][2] = node.pos[2]+1.0f; 
     } 
    } 
} 

：私は私のメインのファイルループ内の要素を追加してい方法です。また、私は、次のループのために私のオクトリーボーダーを表すボックスを拡張しているので、すべてのノードが内部に収まるでしょう。次のような構造の更新をオクトリすることが重要

フィールドは、次のとおりです。

Octree* trees[2][2][2]; 
glm::vec3 vBoundriesBox[8]; 
bool leaf; 
float combined_weight = 0; 
std::vector<Element*> objects; 

および更新を担当するコードの一部：

#define MAX_LEVELS 5 

void Octree::AddObject(Element* object) 
{ 
    this->objects.push_back(object); 
} 

void Octree::Update() 
{ 
    if(this->objects.size()<=1 || level > MAX_LEVELS) 
    { 
     for(Element* Element:this->objects) 
     { 
      Element->parent_group = this; 
     } 
     return; 
    } 

    if(leaf) 
    { 
     GenerateChildren(); 
     leaf = false; 
    } 

    while (!this->objects.empty()) 
    { 
     Element* obj = this->objects.back(); 
     this->objects.pop_back(); 
     if(contains(trees[0][0][0],obj)) 
     { 
      trees[0][0][0]->AddObject(obj); 
      trees[0][0][0]->combined_weight += obj->weight; 
     } else if(contains(trees[0][0][1],obj)) 
     { 
      trees[0][0][1]->AddObject(obj); 
      trees[0][0][1]->combined_weight += obj->weight; 
     } else if(contains(trees[0][1][0],obj)) 
     { 
      trees[0][1][0]->AddObject(obj); 
      trees[0][1][0]->combined_weight += obj->weight; 
     } else if(contains(trees[0][1][1],obj)) 
     { 
      trees[0][1][1]->AddObject(obj); 
      trees[0][1][1]->combined_weight += obj->weight; 
     } else if(contains(trees[1][0][0],obj)) 
     { 
      trees[1][0][0]->AddObject(obj); 
      trees[1][0][0]->combined_weight += obj->weight; 
     } else if(contains(trees[1][0][1],obj)) 
     { 
      trees[1][0][1]->AddObject(obj); 
      trees[1][0][1]->combined_weight += obj->weight; 
     } else if(contains(trees[1][1][0],obj)) 
     { 
      trees[1][1][0]->AddObject(obj); 
      trees[1][1][0]->combined_weight += obj->weight; 
     } else if(contains(trees[1][1][1],obj)) 
     { 
      trees[1][1][1]->AddObject(obj); 
      trees[1][1][1]->combined_weight += obj->weight; 
     } 
    } 

    for(int i=0;i<2;i++) 
    { 
     for(int j=0;j<2;j++) 
     { 
      for(int k=0;k<2;k++) 
      { 
       trees[i][j][k]->Update(); 
      } 
     } 
    } 
} 

bool Octree::contains(Octree* child, Element* object) 
{ 
    if(object->pos[0] >= child->vBoundriesBox[0][0] && object->pos[0] <= child->vBoundriesBox[1][0] && 
     object->pos[1] >= child->vBoundriesBox[4][1] && object->pos[1] <= child->vBoundriesBox[0][1] && 
     object->pos[2] >= child->vBoundriesBox[3][2] && object->pos[2] <= child->vBoundriesBox[0][2]) 
     return true; 
    return false; 
} 

私は私にはない木の要素を移動するためにポインタを使用していますのでオブジェクトの作成/破壊がここで問題になると思う。

Element* obj = this->objects.back(); 
this->objects.pop_back(); 
if(contains(trees[0][0][0],obj)) 

私はどのように私がそれを楽しむことができるか、それをスピードアップすることはできませんが、スピードに影響を及ぼす可能性があります。誰かがここで何ができるのですか？

編集：私はいくつかのナプキンの数学をやったと私は大きな速度低下を引き起こしている可能性がありますもう一つの場所があるとし

。私の場合には同じである

number_of_elements * number_of_childern * number_of_faces * MAX_LEVELS

：Update方法でチェックBoundriesは多くのことをやって私が計算すると、これによる追加の複雑さは、最悪のシナリオであるということですように見えますnumber_of_elements * 240になります。

私のアイデアが妥当かどうか誰かが確認できますか？

Answer 1

私が正しく理解していれば、すべての単一オクツリーノードにポインタのベクトルを格納していますか？

std::vector<Element*> objects; 

...

void Octree::AddObject(Element* object) 
{ 
    this->objects.push_back(object); 
} 

私はこのコードからわかるように、八分木の建物のため、あなたの親ノードpop_back要素のポインタ親ベクターからと子供たちに適切な要素を転送するために押し戻す開始。

これが当てはまる場合、私は直前にこのようなオクツリーの実装を扱い、10xを超えるようにビルドを改善しただけでなく、トラバースのキャッシュミスを単純にこの特定のケースでは、関連するヒープ割り当て/割り当て解除を大幅に削減するだけでなく、小さなvectors（1ノードにつき1つ）のボートロードと比べて空間的局所性を改善することもできます。私はそれが唯一のボトルネックだと言っているわけではありませんが、それは間違いなく重要なものです。

そのような場合ので、これは私がお勧めです：

struct OctreeElement 
{ 
    // Points to next sibling. 
    OctreeElement* next; 

    // Points to the element data (point, triangle, whatever). 
    Element* element; 
}; 

struct OctreeNode 
{ 
    OctreeNode* children[8]; 
    glm::vec3 vBoundriesBox[8]; 

    // Points to the first element in this node 
    // or null if there are none. 
    OctreeElement* first_element; 

    float combined_weight; 
    bool leaf; 
}; 

これは実際には最初の初歩的なパスですが、大いに役立つはずです。親から子へ要素を転送すると、押し戻されることなくポップバックされ、ヒープ割り当てはありません。あなたがしているのはポインタを操作するだけです。親から子へ要素を転送するには： - なしヒープ割り当て

// Pop off element from parent. 
OctreeElement* elt = parent->first_element; 
parent->first_element = elt->next; 

// Push it to the nth child. 
elt->next = children[n]; 
children[n]->first_element = elt; 

をあなたは上から見ることができるように、リンクされた表現で、私たちが行う必要があるすべては、あるノードから別のノードへ転送する3ポインターを操作しないでサイズを増やす必要がなく、容量をチェックする必要がありません。さらに、要素をノードあたり1つのポインタに、要素あたり1つのポインタに格納するオーバーヘッドを削減できます。ノードごとに1つのベクトルは、多くの実装がデータポインタ、サイズ、および容量を格納することの上にいくつかのメモリを事前に割り当てているため、デフォルトで構築されたとしても、ベクトルが32バイト以上かかることがあるので、

まだ改善の余地がありますが、効率的なアロケータ（フリーリストまたはシーケンシャルアロケータなど）を使用してOctreeElement *を割り当てるか、それらを安定したデータ構造に格納する場合は、ポインタを無効にすることはありませんが、std::dequeのようにいくつかの連続性があります。もう少し作業をしたい場合は、すべての要素（ノード全体に1つのベクトルではなくツリー全体のすべての要素）を格納し、ポインタではなくベクトルにインデックスを使用して要素をリンクします。リンクされたリストのポインタの代わりにインデックスを使用すると、すべてのノードを連続して格納することができます。メモリアロケータを使用すると、古いものだけを使用して、すべてのものを格納し、リンクのメモリ要件を半減できます（64ビットポインタとインデックスを使用できる場合は32ビットのインデックスで十分です）。

32ビットインデックスを使用している場合は、すべての32ビットを必要としない場合もあります。たとえば、31ビットを使用して、leafブール値を使用してノードのサイズを大きくします4パディングとバイトとポインタの位置合わせ要件そのブールフィールドの64ビットと仮定して）最初の要素へのまたは周りだけのようなので、葉を示すため-1の最初の子のインデックスを設定します。

struct OctreeElement 
{ 
    // Points to the element data (point, triangle, whatever). 
    int32_t element; 

    // Points to next sibling. 
    int32_t next; 
}; 

struct OctreeNode 
{ 
    // This can be further reduced down to two 
    // vectors: a box center and half-size. A 
    // little bit of arithmetic can still improve 
    // efficiency of traversal and building if 
    // the result is fewer cache misses and less 
    // memory use. 
    glm::vec3 vBoundriesBox[8]; 

    // Points to the first child. We don't need 
    // to store 8 indices for the children if we 
    // can assume that all 8 children are stored 
    // contiguously in an array/vector. If the 
    // node is a leaf, this stores -1. 
    int32_t children; 

    // Points to the first element in this node 
    // or -1 if there are none. 
    int32_t first_element; 

    float combined_weight; 
}; 

struct Octree 
{ 
    // Stores all the elements for the entire tree. 
    vector<OctreeElement> elements; 

    // Stores all the nodes for the entire tree. The 
    // first node is the root. 
    vector<OctreeNode> nodes; 
}; 

これはありますまだまだ基本的なものであり、1つの答えではカバーすることができない種類の改善の余地がありますが、これらのいくつかのことをやっているだけで、すでに多くの助けが必要です。別のノードあたり最大の改善点として

削減ヒープの割り当ておよびリファレンスの改善された地域

ためリンクリストは、これは私が過去に働いてきた開発者が忘れてしまったか、多分学んだことはありませんが、リンクされているいずれかのC++の多くのように感じるものですリストは、特に各ノードが個別のヒープ割り当てを必要としない場合に、増加したヒープ割り当ておよびキャッシュミスに常に翻訳する必要はありません。比較ポイントが小さなベクトルのボートロードである場合、リンクされたリストは実際にキャッシュミスを減らし、ヒープ割り当てを減らします。

をとの実際のグリッドは、10,000個の細胞を持っていたとしましょう：この基本的な例を見てみましょう。その場合、1つの大きな配列（または1つの大きなvector）に格納されている32ビットインデックスを使用してセルごとに32ビットインデックスを格納し、要素をリンクするだけでははるかに安くなり、メモリ割り当ても大幅に少なくなります通常は10,000個のベクトルを格納するよりもはるかに少ないメモリ）。 Vectorは重要ではない量のデータを格納するための優れた構造ですが、これは小さなサイズのリストのボートロードを格納するために使用したいものではありません。 1つのリンク先のリストは既に大幅に改善されている可能性があり、追加の分岐をせずに3つのポインタ（または3つのインデックス）を操作する必要があるため、要素をあるリストから別のリストに転送するのに適しています。

リンクされたリストにはまだ多くの使用があります。ヒープ割り当てを減らすのではなく減らす方法で実際に使用しているときに特に便利です。