Final Project: Poisson Disk Sampling

  • Introduction

    2006 paper "A Spatial Data Structure for Fast Poisson-Disk Sample Generation", and combined this sampling method with PBRT.

    Best-candidate algorithm is great, but it runs in O(N^2) time. Poisson-disk distributions have execellent blue noise characterictic, but they are regard as too computationally expensive to generate in real time. Tiling may be a solution, but it produces the unwanted artifacts. This paper presents two algorithms to generate Poisson-disk distributions in O(N logN) time and O(N) time respectively,

  • Implementation

    I only implemented the O(N) algorithm, this algorithm only samples points in the available boundary, therefore it is extremly fast. Basically, I followed the sudo code in the technical report, and accelerated the algorithm using the uniform gird. The size of the gird is 4r, therefore when I sample a points, I only need to examine the points in the neighboring eight grids.

  • Result

    Result pattern image:

    (In Intel Core 2 Quad 2.4G CPU)

    20,000
    2,000,000
    Poisson Disk
    171ms
    1578ms

    PBRT Images:

    #1. Left is Poisson-disk sampling, right is low discrepancy sampling (8 samples per pixel)

    #2. Buddha. Left is Poisson-disk sampling, right is low discrepancy sampling (32 samples per pixel)