Improve efficiency for finding point closest to cursor
Closed this issue · 8 comments
It's pretty slow right now for large point clouds (naive O(n)). Probably depends on having the octree stuff set up.
If the use-case is typically static camera position and nearest point, perhaps bake an offscreen texture with point id for easy look-up? I think modern OpenGL will let you fetch a subregion, rather than the whole screen.
Yeah, definitely an option I've considered: render a region with a small viewport around the user click and look up the closest colour as vertex id (or use a proper vertex id if it's portable enough). Unfortunately having user-defined vertex shaders makes this harder than I'd like.
Also consider that selecting the "point the user intended" in a point cloud of 10e8 points can be difficult because surfaces made of points tend to have a lot of holes, and the point cloud is volumetric in some places. Having said that, the current algorithm is far from ideal and often results in nonintuitive point selection. issue #10 is related to this, but I didn't write enough there for anyone else to reasonably know what I was talking about ;-)
If you are currently searching all points (naive O(n)) then I can see why this is slow for large data sets. In my DEM work I subdivide the bounding cartesian box into cartesian sub-domains. Not quite as efficient as octree but very easy to implement. Each cartesian sub-domain would then have its own list of point IDs that lie inside. You could then calculate which sub-domains the ray line (from the cursor click) passes through and only search the points in those sub-domains. You could reasonably expect 1000x speed up on large datasets and it would approximately scale with cbrt(n) depending on orientation.
To be clear, I've been using an octree data structure for rendering the points for some time now, (see PointArray::drawPoints()) so there's nothing stopping us from using the same datastructure to accelerate point picking queries.
I've been puzzling a little over the closestPointToRay function in src/util.cpp
I can appreciate that along the ray each point has a "radius" (distance to closest point on ray) and a "distance" along the ray. And we need to factor both of these to choose the "closest". I haven't quite unravelled the math, but it seems like we ought to reject points "behind" the ray origin.
Formulation as a cylinder or cone of interest may be helpful in terms of a spatial datastructure traversal. Any light you can shed on the logic? (beyond the comment in util.h):
/// The distance function is the euclidian distance from the ray origin to the
/// point, where the space has been scaled along the ray direction by the amout
/// longitudinalScale.
I can verify using displaz that shift-clicking in voids will successfully find a nearby point. But it complicates a spatial datastructure traversal to have an ill-defined volume of interest.
An alternative approach, especially for mouse-based panning is to infer a "ground plane" by choosing z based on the the bounding box, or the 1st percentile of a subsample of the point cloud. In the two data sets I looked at, there seems to be more noisy samples above the ground, than below it.
Hah, now you can see why I haven't implemented this using a spatial data structure yet. I started and it got messy fast ;-) However, you're right, it would be fine to clip the volume of interest to some cylinder. There's also no need to stick with the current selection logic if something better can be done. What I was planning, was to traverse the octree nodes in sorted order of distance from the ray to the node bounding boxes. Keep the candidate closest point during the traversal, so that any bounding boxes which are further away than the current closest point can be discarded wholesale.
Yes, there's no rejection of points behind the camera. This is indeed stupid :-) Note that the ray reference point isn't the camera however.
Regarding inferring a ground plane - something I've considered, but I do like displaz to work for any point cloud data, not just the stuff at Roames.