More effective implementation of farthest point sampling
Maintainers usually reply within 3 days
Nobody has claimed this yet.
Assessment
- Difficulty
- 5/5
- Estimated time
- Over a week
- Newbie friendliness
- 25/100
- Issue type
- Feature
- Clarity
- Needs clarification
- Activity status
- Stale
- Tech stack
- cpp
- Domain
- computer-vision, performance
Research direction
Start by locating PCL's current farthest point sampling class and implementation, then study the linked CPU and GPU implementations and the QuickFPS paper. Determine how the proposed KD-tree bucket approach fits PCL and how its small-cloud tradeoff should be handled. Done means the sampling implementation is integrated with its accuracy preserved and performance evaluated against the current version.
Written by the indexing model from the issue text.
Description
Is your feature request related to a problem? Please describe.
Farthest point sampling (FPS) is an important kernel for point cloud processing, I found that the current implementation of FPS needs to process all points to generate one sampling point, which often becomes a bottleneck for point cloud-based applications.
Context
I have implemented a more effective version of farthest point sampling named bucket-based farthest point sampling (BFPS) in both CUDA and CPP.
In short, It applies the KD-tree to split the point cloud into multiple buckets and uses some prune mechanisms to reduce the number of processed points during each iteration.
The test results show that the CPP version achieves a 10-15x speedup against the current implementation without any accuracy loss. It will help the farthest point sampling kernel applied in large-scale point clouds.
Expected behavior
Update the implementation of the farthest point sampling class and implementation.
Current Behavior
I would like to implement the BFPS in PCL, but I am not familiar with the PCL framework. Maybe some volunteers could finish it.
Describe alternatives you've considered
It is worth noting that the BFPS relies on the KD-tree construction stage, which will make the BFPS slower than the current implementation when the point cloud scale is smaller than 4000.
Additional context
some references
- Dominant language
- C++
- Stars
- 11.2k
- Forks
- 4.7k
- Avg merge
- 6d 13h
- Merged PRs (30d)
- 10
Getting set up
- No Dockerfile or Docker Compose file
- No pull request template
- Read the contributing guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
More from PointCloudLibrary/pcl
-
kind: bug status: triage
Difficulty 1/5 Under an hour Newbie friendliness 82/100
PointCloudLibrary/pcl#6536 ·
Maintainers usually reply within 3 days
-
Difficulty 2/5 1-3 hours Newbie friendliness 67/100
PointCloudLibrary/pcl#6509 · 1 comment ·
Maintainers usually reply within 3 days
-
kind: bug status: triage
Difficulty 4/5 3-5 days Newbie friendliness 48/100
PointCloudLibrary/pcl#6537 ·
Maintainers usually reply within 3 days
-
[cmake] QHULL/FLANN dll missing when linking single modulePossibly taken @SIDDARTHAREDDY8 claimed this 5 days ago. Openkind: bug module: cmake
Difficulty 3/5 Half a day Newbie friendliness 50/100
PointCloudLibrary/pcl#6522 · 1 comment ·
Maintainers usually reply within 3 days
-
kind: bug status: triage
Difficulty 4/5 3-5 days Newbie friendliness 35/100
PointCloudLibrary/pcl#6395 ·
Maintainers usually reply within 3 days
All issues in PointCloudLibrary/pcl
Similar issues
-
bug
Difficulty 2/5 1-3 hours Newbie friendliness 62/100
nextcloud/passman-android#214 ·
Maintainers usually reply within 1 day
-
Difficulty 1/5 1-3 hours Newbie friendliness 62/100
Maintainers usually reply within 1 day
-
feature wsl2
Difficulty 2/5 1-3 hours Newbie friendliness 80/100
microsoft/WSL#42306 · 3 comments ·
Maintainers usually reply within 1 day
-
2026.11.0 fails to install on Intel macOS: requirements.txt pins cryptography==50.0.2 for Darwin x86_64May be free again A pull request for this issue was closed without being merged. Open
Difficulty 1/5 Under an hour Newbie friendliness 87/100
esphome/esphome#22892 · 1 comment ·
Maintainers usually reply within 1 day
-
bug
Difficulty 2/5 1-3 hours Newbie friendliness 77/100
distante/esphome-components#50 · 1 comment ·
Maintainers usually reply within 1 day