search for a specific number of nodes?

Wed Apr 28 15:45:16 UTC 2010

Hi Sylvain, when you do ray tracing, it doesn't necessarily have to be on
boxes or voxels.  You sometimes do break up a scene into box-shaped sections
in order to speed up rendering, because then you don't have to test your
rays for intersection on every object.  It's mostly an optimization thing.

With something like photon mapping (which rests on top of ray tracing)
however, in a first step you shoot individual "photons" into a scene out of
each light source, much like what happens in nature.  The photons may hit an
object, and that intersection point is what you save into the kd-tree.  So,
for this particular algorithm, you are saving points and not boxes.  In the
second step, you shoot rays out of the camera into the scene.  They bounce
off the same objects, and at each of these intersection points you search
the kd-tree for any photons that may have bounced in the same general area
to get their light contribution.  Getting these photons is where the
question comes in - do you search in a certain specific area around the
interesection point, like "get me all the photons within 2 units of this
point" or, and this is what most photon mapping algorithms involve, do you
"get me the nearest 50 photons to this point, regardless of distance"?  I
managed to figure out a way to do it by getting all the photons within a
certain distance (what your library and the other library I'm using do) and
just adding up their contributions in a slightly different way.

I hope this helps your understanding!
Have a good day,
Damon

On Thu, Apr 22, 2010 at 10:23 PM, Sylvain Bougerel <
sylvain.bougerel.devel at gmail.com> wrote:

> Hi Damon,
>
> The ray-tracing algorithm that I know of all work on boxes or voxel.
> And they are all about intersecting these volumes with a segment of
> finite or semi-finite length?
>
> At present, nothing prevents you from storing boxes in the k-D tree
> using the following technique: if you have a 2D box, store all the
> "low" components of your box in dimension 0 and 1, and the high
> component in dimension 3 and 4. E.g.:
>
>  Box2d (low(a, b), high(c, d) ) = Point4d (a, b, c, d)
>
> But you have to be aware that all the algorithms in this library where
> designed to work on points and not on boxes.
>
> Could you let us know more about your needs for the photon mapping
> algorithm?
>
> Sylvain
>
> On Thu, Apr 22, 2010 at 3:54 AM, Damon Blanchette <damonbla at gmail.com>
> wrote:
> > Hi Paul and Sylvain, thank you very much again for your time.  Paul, what
> > I'm doing is ray tracing - which can be real time if you really try (and
> > have many processors and optimize immensely), but that's way beyond the
> > scope of my project.  I'm trying much more for realism than speed.
>  Photon
> > mapping is an algorithm you can add to a ray tracer that models light in
> a
> > more realistic way, making images that are sometimes hard to tell from
> real
> > life.  The traditional way to accomplish photon mapping is to store the
> data
> > in a spatial data structure like a kd-tree.
> > I've been using another kd-tree library and also spoke with the person
> who
> > wrote it, and he said it's possible to do what I need to do without doing
> a
> > search for n results from the tree.  So, that's what I'm going with for
> now.
> >  I've only got another week before this project is due, and don't have
> much
> > time during the day to work on this, but I think I'm making progress.  If
> > the other library doesn't end up working out, I will most likely go with
> > yours, and the emails you've sent will help, so thank you!
> > Have a good day,
> > Damon
> >
> >
> > On Tue, Apr 20, 2010 at 8:02 PM, Sylvain Bougerel
> > <sylvain.bougerel.devel at gmail.com> wrote:
> >>
> >> Hi Damon,
> >>
> >> My implementation is not ready yet so you better off with libkdtree at
> the
> >> moment.
> >>
> >> The point is neighboring iterators are definitely writteable. In fact
> the
> >> function in libkdtree to find the nearest neighbor is a very good start
> for
> >> such iterator.
> >>
> >> The library currently does not permit to find the furthest. But finding
> >> the furthest is basically the same process of finding nearest with some
> >> operator reversed. With a bit of time you should be able to write it by
> >> copy-pasting the find nearest and reverting some of its comparisions.
> >>
> >> Regards,
> >> Sylvain
> >>
> >> On 20 Apr 2010 08:04, "Paul" <elegant_dice at yahoo.com> wrote:
> >>
> >> Hi Damon,
> >>
> >> It could do the nearest 50 and return the nearest, but you would
> implement
> >> that in the form of a custom visitor.
> >>
> >> I'll forward you emails from the mailing list where something like this
> >> had been discussed before.
> >> Basically, instead of searching for the nearest point via incrementally
> >> reducing the search space, you only reduce the search space if its
> smaller
> >> than the 50th currently found point.
> >>
> >> The basic idea is that the visitor remembers the last 50 nearest events,
> >> and returns true if the node it just visited should be culled due to the
> >> distance (so nodes further away in the current search dimension won't be
> >> visited in the future).
> >> So if the visitor always returned false, it would eventually visit all
> the
> >> nodes in the kdtree.
> >> If the visitor always returned true, it would only visit the very top
> few
> >> nodes of the tree.
> >> And if the visitor always returned true where X > 10, it would visit all
> >> the nodes where X <= 10, and a few (at least one) nodes where X > 10.
> >>
> >> I'm not sure if it would be very efficient as the search space wouldn't
> be
> >> reduced at all until you'd visited 50 points!  To improve the
> performance,
> >> your visitor could tell kdtree to reduce the search space if it visits a
> >> node that is further than X distance.
> >>
> >> I'll forward you two emails from the mailing list that discussed and had
> >> some code in regards to this issue (one is a patch, one is an example).
> >> called "New function: find_k_nearest()" and "find_pth_nearest or
> >> find_kth_nearest or whatever"
> >>
> >> I'm not sure how other implementations might do it.  Sylvain was talking
> >> about an iterator that could walk the tree starting from the nearest,
> but I
> >> don't know if he ever finished that idea.
> >>
> >> see ya
> >> Paul
> >>
> >>
> >> On 19 April 2010 23:24, Damon Blanchette <damonbla at gmail.com> wrote:
> >>>
> >>> >
> >>> > Hi, my name is Damon Blanchette, and I found libkdtree++ through some
> >>> > google searches.  I'm a gr...
> >>>
> >>> _______________________________________________
> >>> libkdtree-devel mailing list
> >>> libkdtree-devel at lists.alioth.debian.org
> >>> http://lists.alioth.debian.org/mailman/listinfo/libkdtree-devel
> >>>
> >>
> >>
> >> _______________________________________________
> >> libkdtree-devel mailing list
> >> libkdtree-devel at lists.alioth.debian.org
> >> http://lists.alioth.debian.org/mailman/listinfo/libkdtree-devel
> >>
> >
> >
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.alioth.debian.org/pipermail/libkdtree-devel/attachments/20100428/82dac31a/attachment.htm>