Previous | Next --- Slide 52 of 79
Back to Lecture Thumbnails
wmonroe

This schematic seems to be showing a pre-order traversal of the tree--is there a reason why pbrt [sec. A.8, p. 1033] implements a post-order traversal (calling the process function only after recursing on both children)? For this $k$-nearest-neighbor lookup and radius searches I don't think this would cause any harm, but in general I would think that it might be useful to give the callback function info about the current node as soon as possible.

mmp

Ah, these slides on photon map lookup are fairly borked. tl;dr I think that the traversal order in PBR is the right one.

Specifically, there the implementation is indeed to go depth first. The upshot of this is that the very closest photon is the first one checked (and then things proceed generally near-to-far). While there'd no no harm to visiting nodes when they're first encountered, visiting in generally-near-to-far order means that once the desired number of photons is found and the search is reduced to the distance to the farthest of the found photons, big sections of the tree can then be quickly culled away from needing any further traversal...