我有一个应用程序,用于显示和修改来自激光雷达文件的大量点云数据(每个文件最多几个 GB,有时同时加载)。在应用程序中,用户可以查看加载点的 2D 图像(从顶部)并选择要在另一个窗口中查看的配置文件(从侧面)。这再次涉及数百万个点,它们使用 OpenGL 显示。
为了处理数据,还有一个四叉树库,它可以工作,但速度极慢。它已经使用了一段时间,但最近激光雷达点格式发生了变化,并且 LidarPoint 对象需要添加许多属性(类成员),这导致它的大小增加,进而影响性能到几乎无法使用的水平(想想 5 分钟加载单个 2GB 文件)。
四叉树目前由指向 PointBucket 对象的指针组成,这些对象只是具有指定容量和定义边界(用于空间查询)的 LidarPoint 对象数组。如果超过桶容量,它将分成四个桶。还有一种缓存系统,当点数据占用过多内存时,它会导致点桶被转储到磁盘。如果需要,然后将它们加载回内存。最后,每个 PointBucket 都包含子桶/分辨率级别,它们保存原始数据的每个第 n 个点,并在根据缩放级别显示数据时使用。这是因为一次显示几百万个点,虽然没有必要那么详细,但速度非常慢。
我希望你能从中得到一张照片。如果没有,请询问,我可以提供更多详细信息或上传更多代码。例如,这里是当前(和慢速)插入方法:
// Insert in QuadTree
bool QuadtreeNode::insert(LidarPoint newPoint)
{
// if the point dosen't belong in this subset of the tree return false
if (newPoint.getX() < minX_ || newPoint.getX() > maxX_ ||
newPoint.getY() < minY_ || newPoint.getY() > maxY_)
{
return false;
}
else
{
// if the node has overflowed and is a leaf
if ((numberOfPoints_ + 1) > capacity_ && leaf_ == true)
{
splitNode();
// insert the new point that caused the overflow
if (a_->insert(newPoint))
{
return true;
}
if (b_->insert(newPoint))
{
return true;
}
if (c_->insert(newPoint))
{
return true;
}
if (d_->insert(newPoint))
{
return true;
}
throw OutOfBoundsException("failed to insert new point into any \
of the four child nodes, big problem");
}
// if the node falls within the boundary but this node not a leaf
if (leaf_ == false)
{
return false;
}
// if the node falls within the boundary and will not cause an overflow
else
{
// insert new point
if (bucket_ == NULL)
{
bucket_ = new PointBucket(capacity_, minX_, minY_, maxX_, maxY_,
MCP_, instanceDirectory_, resolutionBase_,
numberOfResolutionLevels_);
}
bucket_->setPoint(newPoint);
numberOfPoints_++;
return true;
}
}
}
// Insert in PointBucket (quadtree holds pointers to PointBuckets which hold the points)
void PointBucket::setPoint(LidarPoint& newPoint)
{
//for each sub bucket
for (int k = 0; k < numberOfResolutionLevels_; ++k)
{
// check if the point falls into this subbucket (always falls into the big one)
if (((numberOfPoints_[0] + 1) % int(pow(resolutionBase_, k)) == 0))
{
if (!incache_[k])
cache(true, k);
// Update max/min intensity/Z values for the bucket.
if (newPoint.getIntensity() > maxIntensity_)
maxIntensity_ = newPoint.getIntensity();
else if (newPoint.getIntensity() < minIntensity_)
minIntensity_ = newPoint.getIntensity();
if (newPoint.getZ() > maxZ_)
maxZ_ = newPoint.getZ();
else if (newPoint.getZ() < minZ_)
minZ_ = newPoint.getZ();
points_[k][numberOfPoints_[k]] = newPoint;
numberOfPoints_[k]++;
}
}
}
现在我的问题是,您是否可以想办法改进这个设计?在处理大量无法放入内存的数据时,有哪些通用策略?如何使四叉树更有效率?有没有办法加快点的渲染?