Optimizing LBVH‐Construction and Hierarchy‐Traversal to accelerate kNN Queries on Point Clouds using the GPU

Jakob, J.; Guthe, M.

Optimizing LBVH‐Construction and Hierarchy‐Traversal to accelerate kNN Queries on Point Clouds using the GPU

Files

v40i1pp124-137.pdf (1.75 MB)

Date

2021

Authors

Jakob, J.
Guthe, M.

Publisher

Abstract

Processing point clouds often requires information about the point neighbourhood in order to extract, calculate and determine characteristics. We continue the tradition of developing increasingly faster neighbourhood query algorithms and present a highly efficient algorithm for solving the exact neighbourhood problem in point clouds using the GPU. Both, the required data structures and the NN query, are calculated entirely on the GPU. This enables real‐time performance for large queries in extremely large point clouds. Our experiments show a more than threefold acceleration, compared to state‐of‐the‐art GPU based methods including all memory transfers. In terms of pure query performance, we achieve over answered neighbourhood queries per millisecond for 16 nearest neighbours on common graphics hardware.

        @article{10.1111:cgf.14177
,
journal = {Computer Graphics Forum},
title = {{Optimizing LBVH‐Construction and Hierarchy‐Traversal to accelerate kNN Queries on Point Clouds using the GPU
}},
author = {Jakob, J. and 
Guthe, M.
},
year = {2021
},
publisher = {© 2021 Eurographics ‐ The European Association for Computer Graphics and John Wiley & Sons Ltd
},
ISSN = {1467-8659
},
DOI = {10.1111/cgf.14177
}
}