Research

PixelPie: Maximal Poisson-disk Sampling with Rasterization

"PixelPie: Maximal Poisson-disk Sampling with Rasterization"
Cheuk Yiu Ip (University of Maryland), M. Adil Yalçin (University of Maryland), David Luebke (NVIDIA), Amitabh Varshney (University of Maryland), in High Performance Graphics 2013, July 2013
Research Area: 3D Graphics
Author(s): Cheuk Yiu Ip (University of Maryland), M. Adil Yalçin (University of Maryland), David Luebke (NVIDIA), Amitabh Varshney (University of Maryland)
Date: July 2013
Download(s):
Video (YouTube)Slides (PPS)Code (SourceForge)
 
Abstract: 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.