4

LIDAR ファイルから大量のポイント クラウド データを表示および変更するために使用するアプリケーションがあります (それぞれ最大数ギガバイトで、同時に読み込まれることもあります)。アプリでは、ユーザーはロードされたポイントの 2D 画像を (上から) 表示し、プロファイルを選択して別のウィンドウで (横から) 表示することができます。繰り返しますが、これには数百万のポイントが含まれ、それらは OpenGL を使用して表示されます。

データを処理するために、四分木ライブラリもあり、機能しますが、非常に低速です。しばらく使用されていましたが、最近、LIDAR ポイントの形式が変更され、LidarPoint オブジェクトに多数の属性 (クラス メンバー) を追加する必要がありました。これにより、サイズが大きくなり、パフォーマンスがほとんど使用できないレベルにまで影響しました (5 分と考えてください)。単一の 2GB ファイルをロードする場合)。

四分木は現在、指定された容量と定義された境界 (空間クエリ用) を持つ LidarPoint オブジェクトの単純な配列である PointBucket オブジェクトへのポインターで構成されています。バケット容量を超えると、4 つのバケットに分割されます。また、ポイント データが大量のメモリを消費している場合に、ポイント バケットがディスクにダンプされるようにする、一種のキャッシュ システムも用意されています。これらは、必要に応じてメモリにロードされます。最後に、すべての 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

さて、私の質問は、このデザインを改善する方法を考えられるかどうかです。

はい：オブジェクト自体をクワッドツリーに保存しないでください。それらをフラットな構造（配列、リンクリストなど）に配置し、Quadtreeに実際のオブジェクトへのポインターを保持させるだけです。四分木が（すべてのノードで）特定の深さを持っている場合は、それを平坦化することもできます。

于 2012-03-20T12:34:12.980 に答える