hanm2019 / bucket-based_farthest-point-sampling_cpu

the CPU implementation of bucket based farthest point sampling, achieves 7-81x speedup than the conventional implementation

Bucket-based Farthest point sampling for largest-scaled point clouds

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.

Importance

There is a better repo for implementing bucket-based_farthest point sampling on the single-thread CPU.

BUILD

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.

USAGE

./baseline  num_sample_point filename
./kdtree num_sample_point filename
./kdlinetree tree_high num_sample_point filename

Cite

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}
}

Resources

1. the GPU implementation of FPS
2. the reference paper: QuickFPS: Architecture and Algorithm Co-Design for Farthest Point Sampling in Large-Scale Point Clouds

bucket-based_farthest-point-sampling_cpu's Issues

Marvelous work with imperfect code style

Recently I'm working on implementing FPS algorithms in single-thread CPU program.

This work shows an excellent performance compared to the majority of other implementations.

However, I inspect all of the codes and notice that the code style is terrible. It's generally hard to port the code to other applications directly. For example:

• Hard-coded float type for coordinates.
• Hard-coded dimension as 3.
• Abuse of macros.
• Not found any of C++17 features, even though the paper has mentioned that C++17 is used.

I have revised most of the codes with C++17 Standard to my Python Package fpsample with several benchmarks. I think my revised code in https://github.com/leonardodalinky/fpsample/tree/main/src/bucket_fps/_ext may help to refactor.