pcl
pcl copied to clipboard
PointCloudLibrary
Correct usage of `radiusSearch` results when unsorted search trees are provided as input
Provides a more robust fix to issues described in #4999
TL;DR: current algorithm assumes the output of radiusSearch is sorted. This is not always the case. A solution is to skip the point when it matches the query index (implemented here)
It is also possible to only perform this when the search is un-sorted, and the current patch can be updated to reflect that. I'm not sure how much of a difference that is going to make, specially since a lot of logic would need to be duplicated to provide the minimal benefit. That could also be done simply by using [[unlikely]] (but that's added in C++20 in the standard, with compiler specific versions available). A separate PR can add that to pcl_macros.h + update here and other places
Thoughts?
Seems like seed_queue should be of type pcl::Indices in our_cvfh.
Also: maybe range-for loops are an option?
In the extract_clusters, they query the tree if it returns sorted or not, like this:
// Check if the tree is sorted -- if it is we don't need to check the first element
int nn_start_idx = tree->getSortedResults () ? 1 : 0;
I guess that would be faster, than to (sometimes several times) compare and do array indexing?
@larshg Like I mentioned, it's possible, but I didn't know if the effort would be worth it. I've pushed a change in our_cvfh, so you can take a look and decide if this is the way to go for the other files.
@larshg Like I mentioned, it's possible, but I didn't know if the effort would be worth it. I've pushed a change in our_cvfh, so you can take a look and decide if this is the way to go for the other files.
Ah. sorry didn't get that from the initial post.
I think it's fine to just have your original implementation since the tree will always return unordered points, it doesn't make much sense to check if it does / doesn't.
Since the tree is exposed, we can't be sure if it'd return ordered or unordered outputs, specially if kdtree_flann is used (which returns sorted results by default)
It's not in all cases the tree is fully exposed to the user - sometimes they are private in PCL, ie. in our_cvfh. But I guess the most save approach is to assume its exposed and the increased runtime is probably neglectable.
ie. in our_cvfh.
Not really. See https://github.com/PointCloudLibrary/pcl/blob/master/features/include/pcl/features/impl/our_cvfh.hpp#L612 (the false argument implies that the output results are unsorted)
ie. in our_cvfh.
Not really. See https://github.com/PointCloudLibrary/pcl/blob/master/features/include/pcl/features/impl/our_cvfh.hpp#L612 (the false argument implies that the output results are unsorted)
Yes, and in this case the user can't change that. It at least requires a code change, if the tree in the our_cvfh, should output sorted results?