Ronald L. Parker wrote:
> 
> The kd-tree is like an octree, but it only splits along one dimension
> at a time.  The code I mailed Nathan takes a predefined array of
> points, splits it along the median of the dimension with the greatest
> (range? variance? I don't remember) and then subdivides the halves
> until it reaches the desired leaf size.  Obviously, this generates
> a perfectly balanced tree every time, and since you don't need the
> tree until after you generate all the data, the postprocessing is
> just fine.

My current implementatin uses mean-split balancing instead of median-
split.  This saves time during the balancing phase (no full-fledged
sorting required), but requires a little bit more memory (although
not more than than ranger).  With the median-split, you don't really
need left/right pointers in the tree... searching the tree is like
doing a binary search on an array.

> >Well, consider the edge of a cube.  Two points on different sides of an edge
> >will have normals that deviate by 90 degrees.  They are very close, but
> >possibly receiving totally different amounts of light.
> 
> True.  I'm pretty sure Jensen's formulas take this into account.

Maybe, but I don't think he mentioned it in the paper.  He does store
the direction the light came from, but I don't think he stores the
surface normal where it hit.  This may be a good thing to do, though.

> I'm not sure this is entirely correct, Nathan.  You might want to read
> that part again.  My understanding was that he combined the nearby
> photons with more traditional methods to create a close approximation
> without actually having to fire any additional rays for diffuse
> surfaces.  I could be wrong, though.  It's been a couple of months
> since I read it. :)

Jensen has a paper on this topic called "Importance Driven Path Tracing
using the Photon Map".  From what it sounds like in the paper, he still
has to sample rays fro diffuse surfaces, but the photon map just adds
appropriate importance to directions of higher contribution.

-Nathan

Post a reply to this message