クワッドツリーデザインを改善しますか？

Question

私はlidarファイルから大量のポイントクラウドデータを表示したり変更したりするアプリケーションを持っています（最大数ギガバイトまで、時々同時にロードされることもあります）。このアプリでは、ユーザーは読み込まれたポイント（上から）の2D画像を表示し、別のウィンドウ（側面から）で表示するプロファイルを選択することができます。この場合も、何百万ものポイントが含まれ、OpenGLを使用して表示されます。

データを扱うには、動作するクアッドツリーライブラリもありますが、非常に遅いです。これはしばらく使用されていましたが、最近ライダーポイント形式が変更され、LidarPointオブジェクトには属性（クラスメンバー）が追加される必要があり、サイズが大きくなり、パフォーマンスがほとんど使用できなくなりました（5分1つの2GBファイルを読み込む）。

quadtreeは現在、PointBucketオブジェクトへのポインタで構成されています。これは、指定された容量と定義された境界（空間クエリの場合）を持つLidarPointオブジェクトの単純な配列です。バケット容量を超えると、バケット容量は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]++; 
     } 
    } 
} 

今、私の質問はありますか？メモリに収まらない大量のデータを扱う際の一般的な戦略は何ですか？クワッドツリーをより効率的にするにはどうすればいいですか？ポイントのレンダリングをスピードアップする方法はありますか？

Answer 1

ここで私の質問は、このデザインを改善する方法を考えることができますか？

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