Comparisons of really simple near neighbor search algorithms

[nhm]

Hi Guys,

I would have stuck this in my thread on OMPF but since it's down I'll just make a new one here. I'm pretty much a newb regarding actually implementing photon mapping (my engine doesn't do anything beyond standard raytracing and global illumination via photons yet) and I figure there are a number of other people in a similar place. I wanted to see how really basic (ie really easy to write) implementations of a couple of different near neighbor search algorithms would work out for the photon map. I wrote a couple of quick implements and did some rather non scientific benchmarking to see how they did. I'm sure others here could write significantly faster implementations (especially of the KD-Tree), so feel free to comment/question/flame me if you know better. I've posted some results and the code on my website here:

http://www.clusterfaq.org/programming/near-neighbor-search-benchmarks/

[graphicsMan]

INteresting comparison. Have you looked at the volume heuristic used by Wald et. al? "Balancing Considered Harmful -- Faster Photon Mapping using the Voxel Volume Heuristic" I'd be interested in seeing how that performs. Also, a comparison of how long it takes to build the data structures would be nice. Is the hash grid updateable at run time, or is it a build once, use many type of deal?

[Dade]

I did some test while writing SPPM for LuxRender too. I use near neighbor search algorithms to find eye hit points near the photon bounce point. I observed about the same results (but in my case I had usually an higher number of points to check: high resolution images generate a lot of eye hit points). However I tested an additional kind of lookup structure: an hybrid between hashgrid and kd-tree (i.e. each hash grid cell stores a kd-tree instead of a list).

The hybrid hashgrid/kd-tree offers the best of both solutions and it performed quite well on my tests. It is also very easy to write: first you build a normal hashgrd than you transform the list in each cell in a kd-tree.

You may be interested to try it and to compare to you other results.

[nhm]

Next time I get a spare bit of time I'll try to implement the Voxel Volume Heuristic described in that paper. All of the tests I've done so far have been of the "build everything upfront" variety. Dade: I had the exact same idea about using kd-trees instead of vectors in the hash grid cells. Glad it hear that it works well. If I get some spare time I'll also try to look at that too. I might do it before the Voxel Volume Heuristic since it seems like it should be fairly simple to implement.