"Poisson disk sampling through disk packing" by Guanghui Liang, Lin Lu et al.

Article Title

Poisson disk sampling through disk packing

Authors

Guanghui Liang, School of Computer Science and Technology, Shandong University, Jinan 250101, China.
Lin Lu, School of Computer Science and Technology, Shandong University, Jinan 250101, China.
Zhonggui Chen, Department of Computer Science, Xiamen University, Xiamen 361005, China.
Chenglei Yang, School of Computer Science and Technology, Shandong University, Jinan 250101, China.

Keywords

disk packing, image stippling, Poisson disk sampling, power diagram

Abstract

Poisson disk sampling is an important problem in computer graphics and has a wide variety of applications in imaging, geometry, rendering, etc. In this paper, we propose a novel Poisson disk sampling algorithm based on disk packing. The key idea uses the observation that a relatively dense disk packing layout naturally satisfies the Poisson disk distribution property that each point is no closer to the others than a specified minimum distance, i.e., the Poisson disk radius. We use this property to propose a relaxation algorithm that achieves a good balance between the random and uniform properties needed for Poisson disk distributions. Our algorithm is easily adapted to image stippling by extending identical disk packing to unequal disks. Experimental results demonstrate the efficacy of our approaches.