我制作了一个八叉树来快速匹配三维点。而且速度很快!然而,删除八叉树所花费的时间是构建八叉树的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;
}
};
};
删除顶点八叉树需要很长时间。比创建树要长得多,树还必须进行浮点运算来比较点和分配内存。为什么删除它这么慢?我使用Visual Studio 2012并在发布模式下编译。
当您按F5运行程序时,即使在发布模式下,它也会使用一个特殊的、较慢的调试堆。如果按ctrl+F5,它将使用常规堆,即使在调试模式下也是如此。尝试一下,如果它加快了速度,那么在项目的调试属性中,在环境框中放入_NO_DEBUG_HEAP=1,以始终使用快速堆。