Premium
Fast Out‐of‐Core Octree Generation for Massive Point Clouds
Author(s) -
Schütz Markus,
Ohrhallinger Stefan,
Wimmer Michael
Publication year - 2020
Publication title -
computer graphics forum
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.578
H-Index - 120
eISSN - 1467-8659
pISSN - 0167-7055
DOI - 10.1111/cgf.14134
Subject(s) - octree , computer science , point cloud , out of core algorithm , sort , noise (video) , set (abstract data type) , point (geometry) , sampling (signal processing) , computer graphics (images) , parallel computing , core (optical fiber) , throughput , algorithm , computational science , computer vision , mathematics , geometry , database , image (mathematics) , telecommunications , filter (signal processing) , wireless , programming language
We propose an efficient out‐of‐core octree generation method for arbitrarily large point clouds. It utilizes a hierarchical counting sort to quickly split the point cloud into small chunks, which are then processed in parallel. Levels of detail are generated by subsampling the full data set bottom up using one of multiple exchangeable sampling strategies. We introduce a fast hierarchical approximate blue‐noise strategy and compare it to a uniform random sampling strategy. The throughput, including out‐of‐core access to disk, generating the octree, and writing the final result to disk, is about an order of magnitude faster than the state of the art, and reaches up to around 6 million points per second for the blue‐noise approach and up to around 9 million points per second for the uniform random approach on modern SSDs.