I am using CGAL's (the latest) KD-tree implementation for searching nearest neighbors in point sets. And also Wikipedia and other resources seem to suggest that KD-trees are the way to go. But somehow they are too slow and Wiki also suggests their worst-case time of O(n), which is far from ideal.
[BEGIN-EDIT] I am now using "nanoflann", which is about 100-1000 times faster than the equivalent in CGAL for K-neighbor search. And I am using "Intel Embree" for raycasting, which is about 100-200 times faster than CGAL's AABB trees. [END-EDIT]
My task looks like this:
I have a HUGE point set, say like up to a few 100 mio. points!! and their distribution is on surfaces of triangulated geometry (yes, a photon tracer). So one could say that their distribution is 2D in 3D space, because it is sparse in 3D but dense when looking at the surfaces... This could be the problem right? Because to me this seems to trigger the worst-case performance of a KD-tree which probably could deal much better with 3D dense point sets...
CGAl is quite good at what it does, so I have a bit doubt that their implementation just sucks. Their AABB tree I am using for raytracing burns a straight billion raytraces in a few mintues in the ground... That is remarkable I guess. But their KD-tree on the other hand can't even deal with a mio. points and 250k samples (point queries) in any reasonable time...
I came up with two solutions which kick the crap out of KD-trees:
1) Use texture maps to store the photons in a linked list on the geometry. This is always an O(1) operation, since you have to do the raycast anyway...
2) Use view dependent sliced hashsets. That is the farther away you get, the more coarse the hashsets get. So basically you can think of a 1024x1024x1024 raster in NDC coordinates, but with hashsets, to save memory in sparse areas. This basically has O(1) complexity and can be parallelized efficiently, both for ins