4

我有一个应用程序,用于显示和修改来自激光雷达文件的大量点云数据(每个文件最多几个 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]++;
      }
   }
}

现在我的问题是,您是否可以想办法改进这个设计?在处理大量无法放入内存的数据时,有哪些通用策略?如何使四叉树更有效率?有没有办法加快点的渲染?

4

1 回答 1

3

现在我的问题是,您是否可以想办法改进这个设计?

是:不要将对象本身存储在四叉树中。将它们放入一个平面结构(数组、链表等)中,并让四叉树只保留一个指向实际对象的指针。如果四叉树具有一定的深度(在所有节点上),您也可以将其展平。

于 2012-03-20T12:34:12.980 回答