Fast Uniform Poisson-Disk Sampling in C#

Updated July 26th : Added a circle sampling method.

This appears to be tool-class weekend! Here’s another that I just finished up.

I’ve been wanting uniform poisson-disk distribution generation code for ages, ever since I started working with shadow map filtering in October 2006. I had difficulty decrypting the whitepapers that popped in the first results of Google at the time, so I just gave up for a little bit until… well… someone did a simple implementation for me to grab.

Thankfully, it happened!

The fine gentlemen at Luma labs (Herman Tulleken is credited for the class I converted) released a Java, Python and Ruby implementation of uniform and non-uniform poisson-disk sampling. It’s based on an oddly straightforward whitepaper by Robert Bridson at the UBC (in Canada!).

It took me under an hour to make it work in C#. This will prove very useful in my PCF filtering code, and I will be using it immediately in a Depth-of-Field shader I’m working on.

poisson disk 1poisson disk 2
poisson disk 3poisson disk 4
circle basedcircle based 2

Download

UniformPoissonDiskSampler.cs (4 kb – C# class)

This one uses Vector2’s from the SlimDX namespace, but it would be easy to just replace them with XNA Vector2’s or TV3D TV_2DVECTOR’s.

The original Java code used a non-static class, I decided to make it static and use structures for settings and state. This will reduce garbage if it’s used repeatedly, and since I send the structures as references, it’s just as fast as instance variables. I feel it’s a bit cleaner too.

The pointsPerIteration parameter defaulted to 30 in the original code, I did this too and it works well. You can reduce it to have potentially less dense distributions but much faster generation, or make it higher to make sure the whole space is filled.

Again, I won’t post a sample because the class usage is as simple as can be : it returns a List<Vector2> in the specified domain.

Enjoy!

7 thoughts on “Fast Uniform Poisson-Disk Sampling in C#”

  1. Hi,

    I understand poisson-disk is useful for object placement or surface modifications, but can’t I figure out why it’s useful for blurring code. Any insights on this?

    Thanks, Peter

  2. Hi Peter,

    Poisson-disk is usually the best method for Percentage Closer Filtering, I’ve seen it used in many articles as a “rotated poisson-disk grid”. First time I’ve heard about it was an in article of the “Programming Vertex & Pixels Shaders” book by W. Engel.
    [Edit] Looks like the original source is in ShaderX³, an article by Jason Mitchell called “Poisson Shadow Blur” : http://books.google.com/books?id=DgMSb_10l7IC&lpg=PA403&dq=poisson%20shadow%20blur%20ShaderX3&pg=PA403

    This ATi presentation about depth-of-field shaders also uses Poisson-Disk to do its circle of confusion kernel : http://ati.amd.com/developer/gdc/Scheuermann_DepthOfField.pdf (page 14).

  3. Hi,

    Thank you for sharing this piece of code. It is quite handy in several situations.
    I modified it little so that minimum distance can vary along the sampling region: it can be specified as a scalar field defined over the sampling region (i.e. a fonction Vector2 => float).

    (As I use Unity engine, I also changed few minor things like Vector2 implementation)
    here are the sources. I though it was worth the sharing…

  4. Thanks, this code is useful. Saves me the trouble of implementing the algorithm myself.

    It would be awesome to take it one step further. Use this algorithm as the basis for an infinite Poisson disk distribution suitable for real time procedural content generation.

    There is a straight forward algorithm for that described here:
    http://graphics.cs.kuleuven.be/publications/LD06AWTCECC/LD06AWTCECC_paper.pdf

    The algorithm you wrote here is perfect for generating the colored corners, edges and tiles. The tiles are pre calculated once, and after that they can be used to generate a pseudo infinite Poisson disk sampler in real time suitable for procedural content generation.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.