c++ - 八叉树实现的速度问题

标签 c++ algorithm tree

几天来，我一直在努力加快我的“力导向图”实现。到目前为止，我已经实现了使用octree减少计算数量的Barnes-Hut算法。我已经对其进行了多次测试，并且与力相关的计算的数量确实大大减少了。以下是不带Barns-Hut(带蓝线)和带(红线)的节点数量的计算图:
plot
即使现在它应该快得多，但事实是，就速度(时间)而言，升级仅占百分之几。
我想可能是造成这种情况的一部分是树的创建和树放置中的元素。因为元素在不断移动，所以我需要在每个循环中重新创建树，直到达到某些停止条件为止。但是，如果我要花很多时间来创建树，那我会浪费时间在增加力计算上。至少这是我的想法。这是我在主文件循环中添加元素的方式:

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))
尽管我不确定如何省略/加快速度。有人有什么建议可以在这里做什么？
编辑:
我已经做了一些餐巾纸数学运算，我想还有一个地方可能会导致速度大幅下降。在Update方法中检查边界似乎做得很多，而我计算出的是，在最坏的情况下，由于这样做而增加的复杂性:
元素数量*子代数量*面孔数量* MAX_LEVELS
在我的情况下，它等于number_of_elements * 240个。
有人可以确认我的想法是否合理吗？

最佳答案

如果我理解正确，您是在每个八叉树节点中存储一个指针 vector 吗？

std::vector<Element*> objects;

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

从这段代码中我了解到，对于八叉树构建，您的父节点会从父 vector 中获取pop_back元素指针，并开始向后推，以将适当的元素传递给子元素。

如果是这样，我可以立即说这是一个瓶颈，甚至无法衡量，因为我之前已经处理过此类octree实现，并将其构建提高了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 在内存使用中将具有相当大的爆炸性，因为即使通常只是默认构造， vector 也通常会占用32+字节，因为许多实现在必须存储数据指针，大小和容量的基础上预先分配了一些内存。

仍有很多改进的空间，但是第一次通过应该会有所帮助，因此，如果您使用高效的分配器(例如，自由列表或顺序分配器)分配OctreeElement *或将其存储在不会失效的稳定数据结构中，则还有更多改进的余地指针，但提供一些连续性，例如std::deque。如果您愿意做更多的工作，请使用std::vector存储所有元素(整棵树的所有元素，而不是每个节点一个 vector )，然后使用索引而不是指针将这些元素链接在一起。如果对链接列表使用索引而不是指针，则可以连续存储所有节点，而不必担心内存分配器，而只需使用一个大的旧vector存储所有内容以及将链接的内存需求减半(假设64位指针和如果您可以使用索引，则32位索引就足够了)。

如果您使用32位索引，则可能还不需要全部32位，此时您可以使用31位，然后将leaf bool(boolean) 值加起来，这会增加节点的大小(大约4字节，填充和指向该 bool(boolean) 字段的指针的对齐要求(假设该 bool(boolean) 字段为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;
};

这一切仍然非常基础，还有很大的改进空间，我无法真正在一个答案中涵盖，但是仅做这些事情就已经有很大帮助，首先避免每个节点使用单独的vector作为最大的改进。

链接列表，用于减少堆分配并提高引用的位置

我觉得这是我过去与之合作的许多C++开发人员的遗忘之处，或者也许是他们从未学习过，但是链接列表不必总是转换为增加的堆分配和缓存未命中的情况，尤其是当每个节点都没有这样做时不需要单独的堆分配。如果比较点是大量 vector ，那么链表实际上将减少高速缓存未命中并减少堆分配。举个基本的例子:

enter image description here

假设实际的网格有10,000个单元。在那种情况下，仅在每个单元格中存储32位索引并使用存储在一个大数组(或一个大vector)中的32位索引将元素链接在一起会便宜得多，并且所需的内存分配也要少得多通常比存储10,000个 vector 少得多)。 vector 是用于存储大量数据的出色结构，但是它并不是您想要用于存储大量可变大小列表的东西。单链接列表已经可以进行实质性的改进，非常适合于将元素从一个列表连续地转移到另一个列表，而且便宜，因为这只需要操作3个指针(或3个索引)而无需任何其他分支。

因此，链表仍然有很多用途。当您以减少而不是增加堆分配的方式实际使用它们时，它们特别有用。

关于c++ - 八叉树实现的速度问题，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/37073239/

上一篇：c++ - 如何使用 C++ 读取文件并打印到控制台而不使用变量？

下一篇：c++ - QT 上传(PUT)文件

相关文章：

c++ - 在不再次使用 std::move(t) 的情况下重复调用 f(T&& t) 形式的函数？

php - 用于获取类别表中级联项目计数的 mySQL 查询

javascript - 使用没有插件的 ul li 和 javascript 的树

c - KD 树 - 理解指针的困难

c++ - 如何正确地将变量传递给线程中的lambda函数

c++ - 将击键发送到 X 窗口

C++:将 unsigned long long int 转换为 vector<char> ，反之亦然

在 map 上放置对象标签的算法

algorithm - 如何找到最大派系的大小或派系数量？

algorithm - 子数组查询

©2024 IT工具网  联系我们