10 ポイントから 10 億ポイントの範囲の Octree ベースのコンテナーをメモリに書き込んでいます。ロードされるデータの量が多いため、メモリの消費に注意する必要があります。
すべてが適切に機能し、必要に応じてセグメント化されているように見えますが、挿入時間は非常に遅いです。おそらく、親から子へのデータの再配布が原因です。これを最適化するためにできることはありますか? これを適切に実装しましたか？ポイントの最大量を含めるために各ノードのベクトルを予約することもできますが、これにより必要なメモリが大幅に急増します。
単純な R ツリー タイプのコンテナーを使用すると、約 48 秒で 4 億 6800 万ポイントを読み込んでいます。以下の octree を使用すると、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 ¤tNode = 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();
}