八叉树实现的速度问题

Question

现在我试图加速我的Force-Directed图形实现。到目前为止，我已经实现了使用八叉树来减少计算次数的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)) 

虽然我不知道我该怎么ommit /加快速度。有人有什么建议可以在这里做什么？

编辑：

我已经做了一些餐巾数学，我想还有一个地方可能会造成重大的速度下降。 Boundries在Update方法如下检查就像是做了很多，我的计算是，由于这种增加的复杂性是在最坏的情况下：

number_of_elements * number_of_childern * number_of_faces * MAX_LEVELS

这在我的情况下，等于到number_of_elements * 240。

有人可以确认我的想法是否合理吗？

Answer 1

如果我理解正确，你在每一个八叉树节点存储一个指针向量？

std::vector<Element*> objects; 

...

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

当我从这段代码的理解，对八叉树大厦，你父节点pop_back元素的指针从父向量，并开始推回至适当的元素传递给孩子。如果是这种情况，我可以立即说这是一个甚至没有测量的主要瓶颈，因为我之前已经处理了这种八叉树实现，并将它们的建筑改进了10倍以上，并且通过简单地使用单链表，在这种特殊情况下，与一堆小型的vectors（每个节点一个）相比，这大大减少了涉及的堆分配/释放以及甚至改善了空间局部性。我并不是说这是唯一的瓶颈，但它绝对是一个重要的瓶颈。

所以，如果是这样的话，这是我的建议：

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个指针转移从一个节点到另一个节点 - 无堆分配，无需增加大小，检查容量等。此外，您可以减少将元素存储到每个节点一个指针和每个元素一个指针的开销。每个节点的一个向量在内存使用上往往会相当具有爆炸性，因为即使只是默认构造，vector往往可以采用32+字节，因为许多实现会在必须存储数据指针，大小和容量之前预先分配一些内存。

还有很多需要改进的空间，但如果您使用高效的分配器（自由列表或顺序分配器，例如）分配OctreeElement *或将它们存储在稳定的数据结构中，不会使指针失效，但会提供一些连续性，如std::deque。如果你愿意做更多的工作，使用std::vector来存储所有元素（整个树的所有元素，而不是每个节点一个向量），并使用索引将元素链接在一起，而不是指针。如果使用索引而不是指针指向链接列表，则可以连续存储所有节点，而不必使用内存分配器，只需使用一个大的旧vector来存储所有内容并将链接的内存需求减半（假设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; 
}; 

这是所有仍然非常简陋，有一种我不能在一个答案中真正覆盖的改善空间，但只是做这些事情应该已经有很大帮助，从避免单独的每个节点的是您最大的改进。

为减少堆分配和参考

的改进局部性链表这是我觉得像很多C++开发人员，我在过去要么忘记或工作也许从来没有学过，但联系列表不必总是转化为增加的堆分配和缓存未命中，特别是当每个节点不需要单独的堆分配时。如果比较的重点是少量载体，那么链接列表实际上会减少缓存未命中并减少堆分配。拿这个简单的例子：

而且我们说的实际电网有10000个细胞。在这种情况下，每个单元存储32位索引并使用存储在一个大阵列中的32位索引将元素链接在一起（或者一个大的vector）将会便宜得多，并且需要更少的内存分配（以及作为通常少得多的内存）比存储10,000个向量。向量是存储不重要数据量的优秀结构，但它不是您想要用于存储少量可变大小列表的东西。单链表可能已经有了很大的改进，并且它们非常适合以恒定时间和廉价的方式将元素从一个列表转移到另一个列表，因为只需要操纵3个指针（或3个索引）而不需要任何额外的分支。

因此，链接列表还有很多用处。当您真正以减少而不是增加堆分配的方式使用它们时，它们特别有用。