ポイントセット内の最近傍を検索するために、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);
}
}