3

我制作了一个八叉树来快速匹配 3 维点。而且速度很快！但是，删除八叉树比构建八叉树需要多 100 倍的时间。我不明白为什么会这样。这是我的课：

#pragma once
#include "LeakCheck.h"
#include "vec3.h"

namespace Geometry 
{

static const float tolerance = 1.0e-30f;

class VertexOctree
{
private:
    float halfSize;
    vec3 center;
    VertexOctree *subTrees;
    int vertexIndex;
    void CreateSubTree()
    {
        subTrees = news VertexOctree[8];
        subTrees[0] = VertexOctree(center+(vec3(-1.0f,-1.0f,-1.0f)*halfSize),halfSize*0.5f);
        subTrees[1] = VertexOctree(center+(vec3(+1.0f,-1.0f,-1.0f)*halfSize),halfSize*0.5f);
        subTrees[2] = VertexOctree(center+(vec3(-1.0f,+1.0f,-1.0f)*halfSize),halfSize*0.5f);
        subTrees[3] = VertexOctree(center+(vec3(+1.0f,+1.0f,-1.0f)*halfSize),halfSize*0.5f);
        subTrees[4] = VertexOctree(center+(vec3(-1.0f,-1.0f,+1.0f)*halfSize),halfSize*0.5f);
        subTrees[5] = VertexOctree(center+(vec3(+1.0f,-1.0f,+1.0f)*halfSize),halfSize*0.5f);
        subTrees[6] = VertexOctree(center+(vec3(-1.0f,+1.0f,+1.0f)*halfSize),halfSize*0.5f);
        subTrees[7] = VertexOctree(center+(vec3(+1.0f,+1.0f,+1.0f)*halfSize),halfSize*0.5f);
    }
public:
    int AddVertex(std::vector<vec3> &VertexList, const vec3& Point)
    {
        if (vertexIndex == -1) {
            vertexIndex = VertexList.size();
            VertexList.push_back(Point);
            return vertexIndex;
        }
        if ((VertexList[vertexIndex]-Point).lengthSq() < tolerance) {
            return vertexIndex;
        }
        if (subTrees == NULL)
            CreateSubTree();

        return subTrees[(Point.x>center.x)+(2*(Point.y>center.y))+(4*(Point.z>center.z))].AddVertex(VertexList, Point);
    }
    VertexOctree()
    {
        subTrees = NULL;
        vertexIndex = -1;
    }
    VertexOctree(vec3 Center, float HalfSize)
    {
        subTrees = NULL;
        center = Center;
        halfSize = HalfSize;
        vertexIndex = -1;
    }
    ~VertexOctree()
    {
        if (subTrees)
            delete[] subTrees;
    }
};

};

删除 VertexOctree 需要很长时间。比创建还必须进行浮点运算来比较点和分配内存的树要长得多。为什么删除这么慢？我使用 Visual Studio 2012 并在发布模式下编译。

4

1 回答 1

4

当您按 F5 运行您的程序时，它使用一个特殊的、较慢的调试堆，即使在发布模式下也是如此。如果按 ctrl+F5，它会使用常规堆，即使在调试模式下也是如此。尝试一下，如果它加快了速度，那么在项目的调试属性中，在环境框中放置 _NO_DEBUG_HEAP=1 以始终使用快速堆。

于 2013-08-01T20:09:15.700 回答