Poisson Disk Generator

Wow, haven’t posted here in a while. Glad to see my web hosting fees are going to good use! πŸ™‚

Anyway. These days, I’m working on improving the shadow algorithm we use for our game. One of the common ways to improve the perceived quality of PCF shadows is to use a rotating Poisson Disk filter, but generating those coefficients was always a challenge. Not anymore…

In the past I’ve used the sample code from a paper called “A Spatial Data Structure for Fast Poisson-Disk Sample Generation”, but that command-line tool isn’t exactly intuitive. Still, I usually manage (after a few tries) to get a set of sampling points that work for my needs, and move on. Of course, the next time I need sample points, I don’t remember how I made the tool work and I waste my time again.

I’ve wanted to make a tool to generate Poisson disk coefficients for a long time, but never took the time to do it — the usual references found via Google aren’t exactly what I call “accessible”.

Fast-forward to last friday: I hit the jackpot, completely by accident. A remarkably simple generation algorithm (“Fast Poisson Disk Sampling in Arbitrary Dimensions”), totally easy to understand, and someone else already wrote the code in C#? Ok, I know what I’m doing this weekend. πŸ˜‰

After a bit of futzing around (I haven’t done C# in a while, this was a good excuse to restart!), here are the results:

Poisson Disk Generator screenshot

Finally, an easy way to generate those coefficients, and you can visually spot-check the resulting coverage. Don’t like the coverage? One click and you have a new set of coefficients, in ready-to-paste-in-your-shader form. How cool is that?

You can download the tool + source code here. There are no external dependencies besides the .NET 2.0 framework.

Let me know if you can find ways to improve it, or if it’s been useful to you.

PS: In case you don’t get it, “Poisson” means “Fish” in french. With apologies to SimΓ©on-Denis Poisson

21 Responses to “Poisson Disk Generator”


  • Dude! Averaging one post per year! πŸ˜€

  • Yeah, it’s pretty pathetic. Hey, at least I’m trying πŸ™‚

  • Thank you, a really nice tool!
    Maybe it would be better to use dots instead of commas in the floating point values (0.198124f instead of 0,198124f). That would reduce the copy and paste work to use the generated poisson disk in shader code.

  • Caph, the tool uses the language settings you have set in Windows (actually it’s not me, it’s the default formatting behavior of System.Text.StringBuilder). If you look at the screenshot, you’ll see I get dots on an English system πŸ™‚

    In Windows 7, you can change the separator by going in Control Panel | Region and Language, select the Format tab and click Additional Settings. From there, in the Numbers tab, you can change the Decimal symbol to whatever you need.

  • *Doh*
    Thank you, I didn’t know that. πŸ™‚

  • aeolusengine.blogspot.com

    Just dropping a note to say thanks! This is very useful. πŸ™‚

  • Cheers, saved me a good chunk of time. πŸ™‚

  • Thanks for your nice tool, used it for a DepthOfField effect.

    Changed the output to produce GLSL code(dot instead comma, no trailing “f”, separate declaration for each index).

    Here’s the function i changed(ugly but works for me):
    ——————————
    private void generateButton_Click(object sender, EventArgs e)
    {
    CurrentPoints = UniformPoissonDiskSampler.SampleCircle(new Vector2(0, 0), 1,
    (float)minimumDistanceCtl.Value,
    (int)pointsPerIterationCtl.Value);

    StringBuilder sb = new StringBuilder();
    sb.AppendFormat(“{0} point{1} generated with a minimum distance of {2}:”,
    CurrentPoints.Count, CurrentPoints.Count > 1 ? “s” : “”,
    (float)minimumDistanceCtl.Value);
    pointsGeneratedLbl.Text = sb.ToString();

    sb = new StringBuilder();
    sb.AppendFormat(“const int NUM_TAPS={0};”, CurrentPoints.Count);
    sb.Append(Environment.NewLine);
    sb.AppendLine(“vec2 poisson[NUM_TAPS];”);
    sb.Append(Environment.NewLine);
    for (int i = 0; i < CurrentPoints.Count; ++i)
    {
    Vector2 p = CurrentPoints[i];
    sb.AppendFormat("poisson[{2}] = vec2({0}# {1});", p.X, p.Y, i);
    sb.Append(Environment.NewLine);
    }
    String result = sb.ToString();
    result = result.Replace(",", ".");
    result = result.Replace("#", ",");
    poissonCoefficients.Text = result;
    poissonCoefficients.SelectAll();
    previewPanel.Invalidate();
    }

    ——————————

  • Thanks Martin! StringBuilder is the one responsible for introducing commas (it adds dots when your system is set as English), but I realize now I should have explicitly used dots because that’s what the shader compiler expects regardless of your locale. I’ll keep this in mind next time…

  • Amazing, just what I needed a couple of weeks ago πŸ™‚

    What’s the license btw, can I steal it and add it to my homebrew editor? I’ll leave the original About box in, of course πŸ™‚

  • My licensing terms are simply “don’t be a dick”. You can do whatever you want with the code, just don’t claim that you wrote it yourself, and don’t blame me if it doesn’t work. If you break it, you get to keep both pieces.

    This is essentially the MIT or BSD license shrunk down to two phrases. πŸ™‚

    Cheers!

  • So DBAD (Don’t Be A Dick) license! I like it, cheers! πŸ˜€

  • Very usefull, it would be even better if the diameter of the disc should be setted (will modify this to my needs when I’ll have a C# edi).
    Thanks for sharing!

  • The generated coordinates are around a normalized disc, I just scale them by the actual radius of my shadow samples (0.5f, 2.0f, whatever) in my shader code so I don’t have to change them once I have found a suitable dither pattern.

    Cheers!

  • Hi, Thanks a lot for your effort. I have two questions(this is even before I played with your code but…):
    1. Can I use your code for a domain bigger than [0,1]x[0,1]x[0,1]? do I need to do any transformations? or can you code do that just by giving length x width x height of the domain?
    2. What if I have holes in the domain?

    Thank you.

    Venu

  • Hi Venu, sorry for the late reply.

    As I said in the previous comment, the disk is normalized (i.e. between -1 and 1) so you can scale it to whatever size you need without affecting the quality of the distribution (which is what I do when I used this for shadow filtering code, combined with a 2D rotation of the disk at each pixel to further hide the pattern). I guess you could add exclusion areas to the generated points, but then you won’t have a Poisson distribution. For my uses, the whole point (ha!) is to emulate higher-order filtering without making the dither pattern too apparent.

    In any case the source code is there, feel free to change it to something more suitable for you πŸ™‚

    Cheers!

  • Hello!
    I have added some new features to your tool and uploaded it here:
    http://2dbros.com/projects.html

  • Hey Dudeson, that’s awesome! Glad to see it was useful.

    Perhaps I should put this tool on github…

    Cheers!

  • Just wanted to drop a big Thank You! Searched a lot for a quick tool to generate poisson disk kernels, and your work comes very handy. Thanks so much πŸ˜€

  • Hey A-Bomb, if you like my generator, you should look at the one from Bart Wronsky: https://bartwronski.com/2014/09/05/updated-poisson-like-generator-with-gui-and-more/

    Cheers!

Leave a Reply