Hi everyone. I need some help with searching neighbours to each single point in the a point cloud. (like nearpoints in vex)

I'm using findAllCloseIdx for GEO_PointTree and it all works perfectly fine.
Now I'm trying to limit number of found points to n. Like vex nearpoints(0,@P,dist,max_pt);

findAllCloseIdx returns an array with all found point indices. If I simply cap that array it does the trick but performance vise it's pointless since findAllCloseIdx is the heaviest operation here.

So I tried to measure performance between my dll and point wrangle and searching for neapoints without limit gives ma a good performance vs pointwrangle.


But once I limit amount of points to search for then pointwragnle runs twice faster.

findAllCloseIdx doesn't take max points as argument so it searches for all the points within the radius.

What would be the optimization technique here ?

Thank you.

UPD: There is findAllCloseIdxQueue that according to different resources supposed to speed up lookup but I can't fingure out how to use ut_KDPQueue.

/// This allows you to create a search queue so you can maintain
/// it over time, avoiding the cost of reallocing for each search.
/// NOTE THAT max_distance_squared IS SQUARED DISTANCE.
static ut_KDPQueuePtr createQueue();
private:
riend class ut_KDPQueueDeleter;
static void destroyQueue(ut_KDPQueue *q);

You probably want GEO_BVH::findClosestPoints: https://www.sidefx.com/docs/hdk/class_g_e_o_1_1_point_b_v_h_t.html#a945f5d41803c274b9a5c0c1bd983ab5b [www.sidefx.com]

Hey johnmather. Thank you for the advice. I did take a look at this but I don't really understand how to use BVHOrderedStackEntry.

So I got:

UT_Array<UT::BVHOrderedStackEntry> bhv_stack;
UT_Array<UT::BVHOrderedStackEntry> bhv_output;

GEO::PointBVHT<3> bvh;

Do I run bvh.init(...) first ?
...
bvh.findClosestPoints(gdp->getPos3(ptoff), bhv_stack, bhv_output, 10, 0.01);

What is supposed to be in bhv_stack ? And I guess I get the result in bhv_output and I need to traverse the data and get point indices out of it ?

I couldn't find any useful information on it. Documentation isn't really helping here.

Thank you.

i haven't tried doing this, but im sure you have to run the init function first, to build the bvh representation, and then as you said there is no good documentation but, i think the first bvh stack input is for all the bounding boxes the function pops, i don't think you have to put anything in there, if you had, it would be a const parameter.
the output queue is just an array of the of all of the found leaf boxes in nearest first order (since it is a "ordered stack") i think, since you can also see the same parameters from the base class of pointbvh, after getting the output queue, you should get the stack entrys, and in the stack entry there is a myNode property, i think it is the index, there is also the pointOffset function the base class of point bvh (BVHBase), i think you use the index in there to get the point offset.
i haven't tried this as i said, im making guesses from documentation, you should try and see if it works.

Umang_Raj
i haven't tried doing this, but im sure you have to run the init function first, to build the bvh representation, and then as you said there is no good documentation but, i think the first bvh stack input is for all the bounding boxes the function pops, i don't think you have to put anything in there, if you had, it would be a const parameter.
the output queue is just an array of the of all of the found leaf boxes in nearest first order (since it is a "ordered stack") i think, since you can also see the same parameters from the base class of pointbvh, after getting the output queue, you should get the stack entrys, and in the stack entry there is a myNode property, i think it is the index, there is also the pointOffset function the base class of point bvh (BVHBase), i think you use the index in there to get the point offset.
i haven't tried this as i said, im making guesses from documentation, you should try and see if it works.

Hey Umang_Raj. Thank you for the tip. That actually works. So the code would be like this:

UT_IntArray temp_array;
GEO::PointBVHT<3> bvh;

bvh.init(*gdp, P_handle);

UT_Array<UT::BVHOrderedStackEntry> bhv_stack;
UT_Array<UT::BVHOrderedStackEntry> bhv_output;

bvh.findClosestPoints(gdp->getPos3(ptoff), bhv_stack, bhv_output, max_pt, radius);

for (int i=0; i< bhv_output.entries(); ++i)
{
temp_array.append(gdp->pointIndex(bvh.pointOffset(bhv_output.myNode)));
}

And temp_array now holds indices of nearpoints for the current pointOffset;

That looks more or less correct. You can also use bvh.sortResultsto sort based on distance.

johnmather
That looks more or less correct. You can also use bvh.sortResultsto sort based on distance.

Yep. That worked. Thank you for helping me again.