  Scanning devices often produce point clouds exhibiting highly uneven
distributions of point samples across the surfaces being captured. Different
point cloud subsampling techniques have been proposed to generate more evenly
distributed samples. Poisson-disk sampling approaches assign each sample a cost
value so that subsampling reduces to sorting the samples by cost and then
removing the desired ratio of samples with the highest cost. Unfortunately,
these approaches compute the sample cost using pairwise distances of the points
within a constant search radius, which is very costly for massive point clouds
with uneven densities. In this paper, we revisit Poisson-disk sampling for
point clouds. Instead of optimizing for equal densities, we propose to maximize
the distance to the closest point, which is equivalent to estimating the local
point density as a value inversely proportional to this distance. This
algorithm can be efficiently implemented using k nearest-neighbors searches.
Besides a kd-tree, our algorithm also uses a voxelization to speed up the
searches required to compute per-sample costs. We propose a new strategy to
minimize cost updates that is amenable for out-of-core operation. We
demonstrate the benefits of our approach in terms of performance, scalability,
and output quality. We also discuss extensions based on adding
orientation-based and color-based terms to the cost function.
