We present PixelPie, a highly parallel geometric formulation of the Poisson-disk sampling problem on the graphics pipeline. Traditionally, generating a distribution by throwing darts and removing conflicts has been viewed as an inherently sequential process. In this paper, we present an efficient Poisson-disk sampling algorithm that uses rasterization in a highly parallel manner. Our technique is an iterative two step process. The first step of each iteration involves rasterization of random darts at varying depths. The second step involves culling conflicted darts. Successive iterations identify and fill in the empty regions to obtain maximal distributions. Our approach maps well to the parallel and optimized graphics functions on the GPU and can be easily extended to perform importance sampling. Our implementation can generate Poisson-disk samples at the rate of nearly 7 million samples per second on a GeForce GTX 580 and is significantly faster than the state-of-the-art maximal Poisson-disk sampling techniques.

This work shows how to leverage the modern graphics hardware functions (shaders/depth culling) to solve a popular computer graphics problem, the Poisson-disk distribution. Poisson-disk distributions are highly desired in many computer graphics applications, such as anti-aliasing, stochastic ray tracing, object placement, and global illumination.

We present PixelPie, an alternative, simpler, technique that leverages the rasterization hardware on modern many-core GPUs to carry out this process in a highly parallel fashion. Unlike previous work, PixelPie does not rely on hierarchical data-structures for efficiency. Instead, its simplicity allows it to efficiently leverage the highly-optimized graphics pipeline on GPUs. Figure 2 presents a overview of PixelPie. We use the graphics pipeline to perform 1) dart throwing and 2) conflict removal in parallel.

• We throw random darts into empty regions by rasterizing them as circular disks into a depth map. We cast the problem of conflict checks as an occlusion detection problem. We use the depth test feature of the GPU to perform this efficiently.
• We read the depth map to identify and remove the occluded disks. The unoccluded disk centers become part of the final sample set. We iterate this process on the empty regions to attain maximal coverage.

• We present a simple algorithm, PixelPie, for generating Poisson-disk distribution by casting it as an occlusion-culling problem using programmable shaders and rasterization.
• PixelPie efficiently leverages the highly-optimized and parallel graphics operations on the modern GPUs. We attain maximal sampling coverage with a small number of iterations.
• PixelPie is easily extensible to importance sampling by simply changing the radii of the disks based on the underlying importance map.
• We present angular distribution of nearest neighbors to quantify the bias of a Poisson-disk distribution. We show how subpixel-centered samples can substantially reduce the bias for discrete sampling approaches.

      

PixelPie can generate high-quality uniform Poisson-disk distribution at a rate of 6.8 million samples per second.

We show the results of importance sampling in the following figure. (a) shows the importance sampling of a quadratic gradient by PixelPie. (b-g) show a comparison of PixelPie against Kalantari and Sen's serial and discrete dart throwing approach. Each example contains approximately 20K points. While both approaches produce samples of similar quality, our GPU parallel PixelPie approach runs 400 times faster than Kalantari and Sen's serial approach on a CPU. PixelPie samples were generated on a GTX 580 with 2048 square textures. Their results were generated on a Core i7 2.8 GHz CPU. We select the Smaller Disk option at the boundaries between different importance regions. The importance maps are provided by Kopf et al.

We have shown how to use the programmable graphics pipeline to generate 2D maximal Poisson-disk distributions. The key to our approach, PixelPie, is to identify and remove conflicting darts by culling occluded disks. Our implementation leverages the optimized graphics functions of the modern GPU to perform parallel dart-throwing and conflict-removal in large batches. PixelPie can be extended to perform importance sampling by programming the geometry shader to emit disks of different radii. We have also presented angular distribution of nearest neighbors to quantify the bias of Poisson-disk distributions. We have introduced subpixel-centered samples to substantially reduce this bias for discrete sampling approaches. Our experiments have shown that PixelPie can produce maximal Poisson-disk samples at the rate of nearly 7 million samples per second on a GeForce GTX 580. The surprising insight of our work is that hardware-oriented solutions can significantly outperform the computational geometric state-of-the-art algorithms for Poisson-disk sampling by a factor of 4 or more with no perceptible difference in quality. Our approach indicates that modern geometry and tessellation shaders have the potential to significantly accelerate proximity-driven geometry computations.

• PixelPie: Maximal Poisson-disk Sampling with Rasterization
  C.Y. Ip, M.A. Yalçın, D. Luebke, and A. Varshney. High-Performance Graphics, 2013

This work has been supported in part by the NSF grants: CCF 05-41120, CMMI 08-35572, CNS 09-59979 and the NVIDIA CUDA Center of Excellence. Any opinions, findings, conclusions, or recommendations expressed in this article are those of the authors and do not necessarily reflect the views of the research sponsors.