Hierarchical additive poisson disk sampling

In proceedings of Vision, Modeling and Visualization, The Eurographics Association, 2018
 

Abstract

Generating samples of point clouds and meshes with blue noise characteristics is desirable for many applications in rendering and geometry processing. Working with laser-scanned or lidar point clouds, we usually find region with artifacts called scan- lines and scan-edges. These regions are problematic for geometry processing applications, since it is not clear how many points should be selected to define a proper neighborhood. We present a method to construct a hierarchical additive poisson disk sampling from densely sampled point sets, which yield better point neighborhoods. It can be easily implemented using an octree data structure where each octree node contains a grid, called Modifiable Nested Octree [Sch14]. The generation of the sampling amounts to distributing the points over a hierarchy (octree) of resolution levels (grids) in a greedy manner. Propagating the distance constraint r through the hierarchy while drawing samples from the point set leads to a hierarchy of well distributed, random samplings. This ensures that in a disk with radius r, around a point, no other point upwards in the hierarchy is found. The sampling is additive in the sense that the union of points sets up to a certain hierarchy depth D is a poisson disk sampling. This makes it easy to select a resolution where the scan-artifacts have a lower impact on the processing result. The generated sampling can be made sensitive to surface features by a simple preprocessing step, yielding high quality low resolution poisson samplings of point clouds.

Images

Bibtex

@INPROCEEDINGS{DieckmannSampling,
     author = {Dieckmann, Alexander and Klein, Reinhard},
      title = {{Hierarchical additive poisson disk sampling}},
  booktitle = {Vision, Modeling and Visualization},
       year = {2018},
  publisher = {The Eurographics Association},
   abstract = {Generating samples of point clouds and meshes with blue noise characteristics is desirable for many
               applications in rendering and geometry processing. Working with laser-scanned or lidar point clouds,
               we usually find region with artifacts called scan- lines and scan-edges. These regions are
               problematic for geometry processing applications, since it is not clear how many points should be
               selected to define a proper neighborhood. We present a method to construct a hierarchical additive
               poisson disk sampling from densely sampled point sets, which yield better point neighborhoods. It
               can be easily implemented using an octree data structure where each octree node contains a grid,
               called Modifiable Nested Octree [Sch14]. The generation of the sampling amounts to distributing the
               points over a hierarchy (octree) of resolution levels (grids) in a greedy manner. Propagating the
               distance constraint r through the hierarchy while drawing samples from the point set leads to a
               hierarchy of well distributed, random samplings. This ensures that in a disk with radius r, around a
               point, no other point upwards in the hierarchy is found. The sampling is additive in the sense that
               the union of points sets up to a certain hierarchy depth D is a poisson disk sampling. This makes it
               easy to select a resolution where the scan-artifacts have a lower impact on the processing result.
               The generated sampling can be made sensitive to surface features by a simple preprocessing step,
               yielding high quality low resolution poisson samplings of point clouds.}
}