kd-tree and sph

[Sylvain Bougerel]

On Mon, Mar 10, 2008 at 5:44 PM, Paul Harris <paulharris at computer.org> wrote:
>
>
>
> On 10/03/2008, Mickael POUCHOL <mickael.pouchol at xlim.fr> wrote:
> > Hi,
> >
> > I'm using libkdtree++ for 2D SPH simulation for nearest neighbour
> > search. The structure stored in the kd-tree is :
> >
> >
> > struct ParticlePtr {
> >   typedef float value_type;
> >
> >   inline value_type operator[](size_t const N) const { return
> > ptr->position[N]; }
> >   // The position if of type vec2f
> >   Particle *ptr;
> > };
> >
> > For each particle in the simulation, I use the tree to get its
> > neighbours with a call to : t.find_within_range(current_particle, RANGE,
> > std::back_inserter(v));
> > Sometimes I would like to query the tree with a vec2f value and not with
> > a ParticlePtr. Is there a way to do that?
>
>
> I'm not sure if you can do it with the current KD-Tree.  I have some pending
> changes to commit to the tree that opens up the templates a bit more and
> makes it possible.
>
>
> > Secondly I would like to use another kd-tree to store segments (or
> > triangles in 3D) and query it with a ray in the collision detection
> > phase. I didn't not understand how to define such a kd-tree with the lib.
>
> I don't know how you would do this either
>

What you could do is: store the axis-aligned bounding boxes of your
shapes in the Kdtree. Be it triangle, segments, sphere, etc...

Axis aligned bounding boxes can be considered as hyperpoints:

i.e: in 2dimension, a box would be represented by 2 points. So
consider that your boxes are 4D objects along these dimensions (Xmin,
Xmax, Ymin, Ymax). You can then use the kdtree to do range search.
Suppose you want to do ray tracing along another segment, do a range
search with the "inverted" bounding box of that segment: (Xmax, Xmin,
Ymax, Ymin). This should return all the intersecting bounding boxes in
the tree.

You will then need to further refine what intersect what, but this
will give you a smaller set of objects to care about.

I hope this helps.

Sylvain