Fast Search For Neighbourhood Points

[sibarrick]

Hi all,

I'm putting together a wrap deformer for public consumption.

How efficient is the getPointBSphere method for finding points in the neighbourhood of a test point?

Do I need to get into using kd-tree structures if I want to quickly find neighbourhood points or can I use getPointBSphere as a hack around it?

Or in fact is there some other built in method that will do this already?

If I do need to use kd-tree structures does anyone have any code they are willing to share.

ta

[Daniel]

If I do need to use kd-tree structures does anyone have any code they are willing to share.

Take a look at the GEO_PointTree class in the HDK, it's pretty easy to use and gives fast nearest neighbors.

daniel

[sibarrick]

That should do the trick. Thanks Daniel.

[Mario Marengo]

If I do need to use kd-tree structures does anyone have any code they are willing to share.

Hey Simon,

I haven't used the GEO_PointTree class (which AFAIK is only available in H8). It derives from KDTree, so it seems to be a specialization for 3D positional info, and obviously conveniently manages the interface between the storage/representation required by itself (a kd-tree) and a gdp-based list of points and point groups (seemingly using a planar UT_Vector3Array as a representational bridge, which is compatible with what UT_KDTree expects).

But, in case you need to roll your own, or need to deal with more than 3 dimensions (not uncommon), or just for the fun of it, then setting up UT_KDTree is pretty simple. You just inherit from it (as GEO_PointTree does) and define the two pure virtual methods comparePosition and getP. Optionally, you can also define the three query methods: pointsHaveRadius, getRadius, and isValid (with isValid being the most likely one to need a custom implementation, if any).

The method const fpreal *getP(int idx) const; is expected to return the address to the Nth "position" data, where N is given by the parameter "idx", and where a "position" is a set of DIM contiguous fpreals, each one corresponding to a different dimension. The dimensionality (DIM) of the space being partitioned is passed to the constructor on creation. So for 3 dimensions, getP(5) should return the address of 3 contiguous fpreals whose values represent the "position" of the fifth "point". I keep putting "position" and "point" in quotes because these points could represent positions in an arbitrary space with an arbitrary number of dimensions (RGB color space, tangent space, some simulation's "phase" space, etc), not just Euclidian space. The allowed dimensionality is "restricted" to a maximum of 255 dimensions.... which should be plenty

The method int comparePosition(int idx0,int idx1, int dim) const; is, I believe, called for each dimension of each point when carrying out the splits (building the tree) and it returns one of three possible values: -1, 0, or 1.

Think of it as a comparison function used in a sort -- this function is the one that determines whether P0 is less-than, equal-to, or greater-than P1 (remember this comparison is one-dimensional since it's called separately for each dimension).

Now if you go and look at Crunch's little example from this post, it should complete the picture for you.

Hope that helps,

Cheers.

[sibarrick]

Cheers Mario,

It looks like UT_PointTree is available in H7, I haven't tried it yet, but it appears in the doxygen docs and the header is available in the include files.

I have the basic deformer together, I just need to experiment with a couple of special tweaks and then optimise it with either the UT_PointTree stuff or a kdtree implimentation. So I'll find out soon enough. Thanks as ever for the extra info, all useful stuff, I'm sure I'll need to roll my own kdtree at some point for some crazy idea or other

[Mario Marengo]

It looks like UT_PointTree is available in H7, I haven't tried it yet, but it appears in the doxygen docs and the header is available in the include files.

Huh... I don't see it anywhere in our H7.0.434 installation...

Not that it matters since you probably want to be using H8 anyway.

Good luck!

[Mario Marengo]

Huh... I don't see it anywhere in our H7.0.434 installation...

I see what happened now, you're talking about UT_PointTree, and Daniel was referring to GEO_PointTree. So yes, you're right, UT_PointTree *is* available in H7... it's a different animal though (an octree vs a kd-tree)... or so it seems from the comments.

[sibarrick]

Oh yes, I didn't actually spot that, I just did a search for Pointtree, never thought there was more than one . I guess an octree sort will be pretty good, but kdtree maybe better, yes? That's a bit awkward though, I'm not really using H8 yet.... hmmm.

[Mario Marengo]

I guess an octree sort will be pretty good, but kdtree maybe better, yes?

They both do similar things, but they do it differently. For proximity searches, I believe a kd-tree should be faster (and likely more memory efficient) than an octree -- it splits on one plane at a time so has a tighter fit. But either one could be used. Also, the comments in UT_PointTree describe it as an "octree variant" so, who knows, maybe it's been optimized beyond a plain-vanilla octree... (Ed?)

But, of course, both PointTrees are designed for points (3D positions), whereas the kd-tree is generic... so that may be a deal breaker in some situations...

Either should work for points though.