we use an approximate KD-Tree to divide the point clouds into multi-buckets and use two geometry inequality to reduce the distance computation times and the data which need to load from memory
we achieve 42ms on CPU for 50k points (generate 4K sample points )
we present the CPU implementation and GPU implementation of bucket-based farthest point sampling.
There is a better repo for implementing bucket-based_farthest point sampling on the single-thread CPU.
cmake -B build -DCMAKE_BUILD_TYPE=Release
cmake --build build --config Release
then, three executable files are generated:
-
baseline: the conventional implementation of FPS, used for performance baseline.
-
kdline: bucket-based farthest point sampling, each bucket contains multiple points. high performance
-
kdtree: bucket-based farthest point sampling, each bucket contains one point.
./baseline num_sample_point filename
./kdtree num_sample_point filename
./kdlinetree tree_high num_sample_point filename
Please kindly consider citing this repo in your publications if it helps your research.
@article{han2023quickfps,
title={QuickFPS: Architecture and Algorithm Co-Design for Farthest Point Sampling in Large-Scale Point Clouds},
author={Han, Meng and Wang, Liang and Xiao, Limin and Zhang, Hao and Zhang, Chenhao and Xu, Xiangrong and Zhu, Jianfeng},
journal={IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems},
year={2023},
publisher={IEEE}
}
@inproceedings{han2023fusefps,
title={FuseFPS: Accelerating Farthest Point Sampling with Fusing KD-tree Construction for Point Clouds},
author={Han, Meng and Wang, Liang and Xiao, Limin and Zhang, Hao and Zhang, Chenhao and Xie, Xilong and Zheng, Shuai and Dong, Jin},
booktitle={2024 29th Asia and South Pacific Design Automation Conference (ASP-DAC)},
year={2024},
organization={IEEE}
}