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.
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!
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
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).
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…
Oh cool! Glad you’re finding it useful.
See also this outstanding HTML5 implementation which I think is easier to understand and visualize : http://bl.ocks.org/mbostock/dbb02448b0f93e4c82c3
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.