2

我正在将一个基于八叉树的容器从 10 点到 10 亿点之间的任何位置写入内存。由于要加载的数据量，我需要注意内存消耗。

一切似乎都正常工作并根据需要进行分段，但是插入时间非常慢。可能是因为父母之间的数据重新分配给孩子。我能做些什么来优化它吗？我是否正确实施了这一点？我可以在每个节点中保留向量以包含最大数量的点，但这会显着增加所需的内存。

使用一个简单的 R-tree 类型容器，我在大约 48 秒内加载了 4.68 亿个点。使用下面的八叉树，我在 245 秒内加载。

    class OctreeNode {
    public:
        std::vector<std::shared_ptr<OctreeNode>>    Children;
        std::vector<TPoint> Data;
        BoundingBox         Bounds;

        OctreeNode(){}

        OctreeNode(BoundingBox bounds) : Bounds(bounds){
        }

        ~OctreeNode(void){}

        void Split();

    };

    typedef std::shared_ptr<OctreeNode> OctreeNodePtr;


    void OctreeNode::Split()
    {
        Point box[8];
        Bounds.Get8Corners(box);
        Point center = Bounds.Center;

        Children.reserve(8);
        Children.push_back(OctreeNodePtr(new OctreeNode(BoundingBox::From(box[0], center))));
        Children.push_back(OctreeNodePtr(new OctreeNode(BoundingBox::From(box[1], center))));
        Children.push_back(OctreeNodePtr(new OctreeNode(BoundingBox::From(box[3], center))));
        Children.push_back(OctreeNodePtr(new OctreeNode(BoundingBox::From(box[2], center))));


        Children.push_back(OctreeNodePtr(new OctreeNode(BoundingBox::From(box[5], center))));
        Children.push_back(OctreeNodePtr(new OctreeNode(BoundingBox::From(box[4], center))));
        Children.push_back(OctreeNodePtr(new OctreeNode(BoundingBox::From(box[6], center))));
        Children.push_back(OctreeNodePtr(new OctreeNode(BoundingBox::From(box[7], center))));
    }



    Octree::Octree(BoundingBox bounds) : Bounds(bounds)
    {
        _root = OctreeNodePtr(new OctreeNode(bounds));
        _root->Split();
    }


    Octree::~Octree()
    {
    }



    bool Octree::InsertPoint(TPoint &p)
    {
        return InsertPoint(p, _root);
    }

    bool Octree::InsertPoint(TPoint &p, const OctreeNodePtr &parent)
    {
        if (parent->Children.size() != 0){
            for (size_t i = 0; i < parent->Children.size(); i++){
                OctreeNodePtr &currentNode = parent->Children[i];
                if (currentNode->Bounds.IsContained(p.ToPoint3d())){
                    return InsertPoint(p, currentNode);
                }           
            }

            // Was not able to insert a point.
            return false;
        }

        BoundingBox newBounds = parent->Bounds;
        newBounds.Extend(p.ToPoint3d());


        // Check for split condition...
        if (parent->Data.size() == MaxPerNode && newBounds.XLength() > 0.01){

            // Split it...thus generating children nodes
            parent->Split();


            // Resize the children arrays so that we don't have to keep allocating when redistributing points..
            for (size_t i = 0; i < parent->Children.size(); i++){
                parent->Children[i]->Data.reserve(parent->Data.size());
            }


            // Distribute the points that were in the parent to its children..
            for (size_t i = 0; i < parent->Data.size(); i++){
                TPoint originalPoint = parent->Data[i];
                if (!InsertPoint(originalPoint, parent)){
                    printf("Failed to insert point\n");
                    break;
                }
            }

            // Insert the current point.
            if (!InsertPoint(p, parent)){
                printf("Failed to insert point\n");
            }


            // Resize the arrays back so it fits the size of the data.....
            for (size_t i = 0; i < parent->Children.size(); i++){
                parent->Children[i]->Data.shrink_to_fit();
            }

            // clear out the parent information
            parent->Data.clear();
            parent->Data.shrink_to_fit();
            return true;
        } else {
            // Node is valid so insert the data..
            if (parent->Data.size() <= 100000){
                parent->Data.push_back(p);
            } else {
                printf("Too much data in tiny node... Stop adding\n");
            }

            return true;
        }


    }


    void Octree::Compress(){
        Compress(_root);
    }

    void Octree::Compress(const OctreeNodePtr &parent){


        if (parent->Children.size() > 0){

            // Look for and remove useless cells who do not contain children or point cloud data.
            size_t j = 0;
            bool removed = false;
            while (j < parent->Children.size()){
                if (parent->Children[j]->Children.size() == 0 && parent->Children[j]->Data.size() == 0){
                    parent->Children.erase(parent->Children.begin() + j);
                    removed = true;
                } else {
                    Compress(parent->Children[j]);
                    ++j;
                }
            }

            if (removed)
                parent->Children.shrink_to_fit();

            return;
        }

        parent->Data.shrink_to_fit();
    }
4

2 回答 2

1

只是一件小事，但要替换它：

Children.push_back(OctreeNodePtr(new OctreeNode(BoundingBox::From(box[0], center))));

有了这个：

Children.push_back(std::make_shared<OctreeNode>(BoundingBox::From(box[0], center)));

将稍微减少加载时间并减少内存消耗。

对于任何 shared_ptr 都是如此。make_shared<> 路由将控制块与共享对象合并。

于 2016-03-18T20:15:04.023 回答
0

我在这里看到的是插入点，你遍历 8 个孩子并检查每个点是否在里面。

八叉树的主要优点是，根据边界框中心和数据的位置，您可以计算索引而无需迭代您的孩子。这称为八分圆（用于八叉树）。

你可以在这里找到一个简单的实现。 https://github.com/brandonpelfrey/SimpleOctree/blob/master/Octree.h#L79 查找函数 getOc​​tantContainingPoint(...)。

我使用此代码作为实现我的基础，计算索引的方式可以大大加快（使用 SIMD 指令......）。

您还担心内存消耗。为了减少内存消耗，在下降过程中重新计算节点的边界框可以更快更轻。

于 2016-04-06T00:55:58.293 回答