search for a specific number of nodes?

[Sylvain Bougerel]

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
>>
>
>