13

ポイントセット内の最近傍を検索するために、CGAL(最新)のKDツリー実装を使用しています。また、ウィキペディアやその他のリソースは、KDツリーが進むべき道であることを示唆しているようです。しかし、どういうわけかそれらは遅すぎて、WikiはO(n)の最悪の場合の時間を示唆しています。これは理想からはほど遠いです。

[BEGIN-EDIT] 現在、「nanoflann」を使用しています。これは、K近傍検索用のCGALの同等のものよりも約100〜1000倍高速です。また、レイキャスティングには「Intel Embree」を使用しています。これは、CGALのAABBツリーよりも約100〜200倍高速です。 [終了-編集]

私のタスクは次のようになります。

私は巨大なポイントセットを持っています、例えば数百ミオまでのように。ポイント!! そして、それらの分布は、三角形分割されたジオメトリの表面上にあります(はい、フォトントレーサー)。つまり、それらの分布は3D空間では2Dであると言えます。これは、3Dではまばらですが、表面を見ると密であるためです...これは問題である可能性がありますか?私には、これがKDツリーの最悪の場合のパフォーマンスをトリガーするように思われるため、おそらく3Dの密なポイントセットをはるかにうまく処理できる可能性があります...

CGAlはそれが何をするのか非常に優れているので、それらの実装がうまくいかないのではないかと少し疑問があります。私がレイトレーシングに使用している彼らのAABBツリーは、地面の数分でまっすぐな10億のレイトレースを燃やします...それは驚くべきことだと思います。しかし、その一方で、彼らのKDツリーはmioを扱うことさえできません。妥当な時間内のポイントと25万サンプル(ポイントクエリ)...

私はKDツリーからがらくたを追い出す2つの解決策を思いついた:

1)テクスチャマップを使用して、ジオメトリ上のリンクリストにフォトンを保存します。とにかくレイキャストを実行する必要があるため、これは常にO(1)操作です...

2)ビューに依存するスライスされたハッシュセットを使用します。つまり、遠くに行くほど、ハッシュセットは粗くなります。したがって、基本的には、NDC座標で1024x1024x1024ラスターを考えることができますが、スパース領域のメモリを節約するためにハッシュセットを使用します。これは基本的にO(1)の複雑さを持ち、挿入(マイクロシャーディング)とクエリ(ロックフリー)の両方で効率的に並列化できます。

前者の解決策には、隣接するフォトンリストを平均化することがほぼ不可能であるという欠点があります。これは、ノイズを回避するために暗い領域で重要です。後者のソリューションにはこの問題はなく、KDツリーと同等の機能を備えている必要があります。O(1)の最悪の場合のパフォーマンスがあります(笑)。

それで、あなたはどう思いますか?悪いKDツリーの実装?そうでない場合、制限付き最近傍クエリのKDツリーよりも「優れた」ものはありますか?上記の2番目のソリューションに反対するものは何もありませんが、同様のパフォーマンスを提供する「実証済みの」データ構造の方が優れています。

ありがとう!

これが私が使用したコードです(ただしコンパイルできません):

#include "stdafx.h"
#include "PhotonMap.h"

#pragma warning (push)
    #pragma warning (disable: 4512 4244 4061)
    #pragma warning (disable: 4706 4702 4512 4310 4267 4244 4917 4820 4710 4514 4365 4350 4640 4571 4127 4242 4350 4668 4626)
    #pragma warning (disable: 4625 4265 4371)

    #include <CGAL/Simple_cartesian.h>
    #include <CGAL/Orthogonal_incremental_neighbor_search.h>
    #include <CGAL/basic.h>
    #include <CGAL/Search_traits.h>
    #include <CGAL/point_generators_3.h>

#pragma warning (pop)

struct PhotonicPoint
{
    float vec[3];
    const Photon* photon;

    PhotonicPoint(const Photon& photon) : photon(&photon) 
    { 
        vec[0] = photon.hitPoint.getX();
        vec[1] = photon.hitPoint.getY();
        vec[2] = photon.hitPoint.getZ();
    }

    PhotonicPoint(Vector3 pos) : photon(nullptr) 
    { 
        vec[0] = pos.getX();
        vec[1] = pos.getY();
        vec[2] = pos.getZ();
    }

    PhotonicPoint() : photon(nullptr) { vec[0] = vec[1] = vec[2] = 0; }

    float x() const { return vec[0]; }
    float y() const { return vec[1]; }
    float z() const { return vec[2]; }
    float& x() { return vec[0]; }
    float& y() { return vec[1]; }
    float& z() { return vec[2]; }

    bool operator==(const PhotonicPoint& p) const
    {
        return (x() == p.x()) && (y() == p.y()) && (z() == p.z()) ;
    }

    bool operator!=(const PhotonicPoint& p) const 
    { 
        return ! (*this == p); 
    }
}; 

namespace CGAL 
{
    template <>
    struct Kernel_traits<PhotonicPoint> 
    {
        struct Kernel 
        {
            typedef float FT;
            typedef float RT;
        };
    };
}

struct Construct_coord_iterator
{
    typedef const float* result_type;

    const float* operator()(const PhotonicPoint& p) const
    { 
        return static_cast<const float*>(p.vec); 
    }

    const float* operator()(const PhotonicPoint& p, int) const
    { 
        return static_cast<const float*>(p.vec+3); 
    }
};

typedef CGAL::Search_traits<float, PhotonicPoint, const float*, Construct_coord_iterator> Traits;
typedef CGAL::Orthogonal_incremental_neighbor_search<Traits> NN_incremental_search;
typedef NN_incremental_search::iterator NN_iterator;
typedef NN_incremental_search::Tree Tree;


struct PhotonMap_Impl
{
    Tree tree;

    PhotonMap_Impl(const PhotonAllocator& allocator) : tree()
    {
        int counter = 0, maxCount = allocator.GetAllocationCounter();
        for(auto& list : allocator.GetPhotonLists())
        {
            int listLength = std::min((int)list.size(), maxCount - counter);
            counter += listLength; 
            tree.insert(std::begin(list), std::begin(list) + listLength);
        }

        tree.build();
    }
};

PhotonMap::PhotonMap(const PhotonAllocator& allocator)
{
    impl = std::make_shared<PhotonMap_Impl>(allocator);
}

void PhotonMap::Sample(Vector3 where, float radius, int minCount, std::vector<const Photon*>& outPhotons)
{
    NN_incremental_search search(impl->tree, PhotonicPoint(where));
    int count = 0;

    for(auto& p : search)
    {
        if((p.second > radius) && (count > minCount) || (count > 50))
            break;

        count++;
        outPhotons.push_back(p.first.photon);
    }

}
4

5 に答える 5

12

答えは質問をする場所ではありませんが、あなたの質問は質問ではなく、CGALのkdツリーが吸うステートメントです。

地質データモデルの1.8mioポイントを読み取り、これらの各ポイントの50のclostestポイントを計算すると、Dell Precision、Windows7、64ビット、VC10で次のパフォーマンスが得られます。

  • ファイルからポイントを読み取る:10秒
  • 木の建設1.3秒
  • 最も近い50ポイントを報告する1.8mioクエリ:17秒

似たようなパフォーマンスはありますか?kdツリーの方が速いと思いますか?

また、クエリポイントはどこにあるのか、つまりサーフェスに近いのか、スケルトンに近いのか疑問に思います。

于 2013-03-05T15:24:56.107 に答える
7

私は数か月前に高速KDツリーの実装についていくつかの調査を行いましたが、品質(およびライブラリの「重み」)が大きく異なるというAnony-Mousseに同意します。これが私の発見のいくつかです:

kdtree2は、あまり知られていない非常に単純なKDツリーの実装であり、特にデータのコピーと再ソートを許可した場合、3Dの問題に対して非常に高速であることがわかりました。また、それは小さく、組み込みと適応が非常に簡単です。これは、作者による実装に関する論文です(タイトルにFortranが記載されていることを躊躇しないでください)。これは私が使用することになったライブラリです。私の同僚は、 VLFeatのKDツリーと私が覚えていない別のライブラリ(多くのFLANN、以下を参照)に対して3Dポイントの速度をベンチマークし、勝ちました。

FLANNは高速であるという評判があり、最近よく使用され、推奨されています。これは、近似アルゴリズムを提供する高次元のケースを対象としていますが、3D問題を処理するポイントクラウドライブラリでも使用されます。

ライブラリが重すぎることがわかったので、CGALを試しませんでした。CGALの評判は良いと思いますが、時折過度に洗練されているように感じます。

于 2013-03-05T17:14:41.380 に答える
4

私の経験から、残念ながら、実装の品質は大きく異なります。しかし、私はCGALの実装を見たことがありません。

kdツリーの最悪のケースは、通常、増分変更のために不均衡になりすぎて、再ロードする必要がある場合です。

ただし、一般に、このようなツリーは、データの分布がわからない場合に最も効率的です。

あなたの場合、単純なグリッドベースのアプローチが最良の選択であるかのように聞こえます。必要に応じて、テクスチャを密な2Dグリッドと見なすことができます。したがって、グリッドが適切に機能する2D投影を見つけて、この投影と交差させることができるかもしれません。

于 2013-03-01T23:25:20.907 に答える
0

MPLライセンスの下にある近似MVBBライブラリを見てください。

https://github.com/gabyx/AppearanceMVBB

kdTreeの実装はPCL(FLANN)に匹敵するはずであり、さらに高速になる可能性があります。(PCLを使用したテストは、私の実装の方が速いようです!)

免責事項:私はこのライブラリの所有者であり、このライブラリがより高速で本格的なパフォーマンステストがまだ実施されていないと主張しているわけではありませんが、速度が重要な粒状の剛体力学でこのライブラリを使用しています。ただし、このライブラリは非常に小さく、kdTreeの実装は非常に一般的であり(例を参照)、カスタム分割ヒュースティックやその他の凝ったものを使用できます:-)。

nanoflann(直接データアクセスなど、汎用データ、n次元)と同様の改善と考慮事項が実装されています...(KdTree.hppを参照)ヘッダー。

タイミングに関するいくつかの更新:
kdTreeFilteringにはいくつかの小さなベンチマークが含まれています:35947ポイントの標準バニーがロードされます(箱から出してすぐにリポジトリで完全に機能する例):

結果:

Bunny.txt

Loaded: 35947 points 
KDTree::  Exotic point traits , Vector3* +  id, start: =====
KdTree build took: 3.1685ms.
Tree Stats: 
     nodes      : 1199
     leafs      : 600
     tree level : 11
     avg. leaf data size : 29.9808
     min. leaf data size : 0
     max. leaf data size : 261
     min. leaf extent    : 0.00964587
     max. leaf extent    : 0.060337
SplitHeuristics Stats: 
     splits            : 599
     avg. split ratio  (0,0.5] : 0.5
     avg. point ratio  [0,0.5] : 0.22947
     avg. extent ratio (0,1]   : 0.616848
     tries / calls     : 599/716 = 0.836592
Neighbour Stats (if computed): 

     min. leaf neighbours    : 6
     max. leaf neighbours    : 69
     avg. leaf neighbours    : 18.7867
(Built with methods: midpoint, no split heuristic optimization loop)


Saving KdTree XML to: KdTreeResults.xml
KDTree:: Simple point traits , Vector3 only , start: =====
KdTree build took: 18.3371ms.
Tree Stats: 
     nodes      : 1199
     leafs      : 600
     tree level : 10
     avg. leaf data size : 29.9808
     min. leaf data size : 0
     max. leaf data size : 306
     min. leaf extent    : 0.01
     max. leaf extent    : 0.076794
SplitHeuristics Stats: 
     splits            : 599
     avg. split ratio  (0,0.5] : 0.448302
     avg. point ratio  [0,0.5] : 0.268614
     avg. extent ratio (0,1]   : 0.502048
     tries / calls     : 3312/816 = 4.05882
Neighbour Stats (if computed): 

     min. leaf neighbours    : 6
     max. leaf neighbours    : 43
     avg. leaf neighbours    : 21.11
(Built with methods: midpoint, median,geometric mean, full split heuristic optimization)

1,400万ポイントのLucy.txtモデル:

Loaded: 14027872 points 
KDTree::  Exotic point traits , Vector3* +  id, start: =====
KdTree build took: 3123.85ms.
Tree Stats: 
         nodes      : 999999
         leafs      : 500000
         tree level : 25
         avg. leaf data size : 14.0279
         min. leaf data size : 0
         max. leaf data size : 159
         min. leaf extent    : 2.08504
         max. leaf extent    : 399.26
SplitHeuristics Stats: 
         splits            : 499999
         avg. split ratio  (0,0.5] : 0.5
         avg. point ratio  [0,0.5] : 0.194764
         avg. extent ratio (0,1]   : 0.649163
         tries / calls     : 499999/636416 = 0.785648
(Built with methods: midpoint, no split heuristic optimization loop)

KDTree:: Simple point traits , Vector3 only , start: =====
KdTree build took: 7766.79ms.
Tree Stats: 
     nodes      : 1199
     leafs      : 600
     tree level : 10
     avg. leaf data size : 11699.6
     min. leaf data size : 0
     max. leaf data size : 35534
     min. leaf extent    : 9.87306
     max. leaf extent    : 413.195
SplitHeuristics Stats: 
     splits            : 599
     avg. split ratio  (0,0.5] : 0.297657
     avg. point ratio  [0,0.5] : 0.492414
     avg. extent ratio (0,1]   : 0.312965
     tries / calls     : 5391/600 = 8.985
Neighbour Stats (if computed): 

     min. leaf neighbours    : 4
     max. leaf neighbours    : 37
     avg. leaf neighbours    : 12.9233
(Built with methods: midpoint, median,geometric mean, full split heuristic optimization)

解釈に注意してください!サンプルファイルで使用されている設定を確認してください。ただし、他の人の結果と比較すると、14*10⁶ポイントで約3100msはかなり滑らかです:-)

使用したプロセッサー:Intel®Core™i7 CPU 970 @ 3.20GHz×12、12GB RAM

于 2015-09-16T13:12:15.857 に答える
0

kdtreeが小さいセットでは高速であるが、大きい(> 100000?)セットでは「遅い」場合は、プロセッサキャッシュのフラッシュに問題がある可能性があります。上位のいくつかのノードがめったに使用されないリーフノードとインターリーブされている場合は、使用頻度の高いノードをプロセッサキャッシュに収めることができます。これは、ノードのサイズを最小限に抑え、メモリ内のノードを注意深くレイアウトすることで改善できますが、最終的にはかなりの数のノードをフラッシュすることになります。メインメモリへのアクセスがボトルネックになる可能性があります。

Valgrindは、私のコードの1つのバージョンは命令が5%少ないと言っていますが、ストップウォッチが同じ入力に対して約10%遅いと言ったときは信じています。フルキャッシュシミュレーションを実行するvalgrindが正しい答えを教えてくれると思います。

マルチスレッドの場合は、スレッドが同様の領域で検索を実行してキャッシュを再利用するように促すことができます。これは、単一のマルチコアプロセッサを想定しています。複数のプロセッサが反対のアプローチを必要とする場合があります。

ヒント:64ビットポインタよりも多くの32ビットインデックスをメモリにパックします。

于 2018-02-22T21:54:20.397 に答える