Poisson Disk Sampling

This repository contains a single file, header-only, no-dependencies, C++ library for generating Poisson disk samplings in an arbitrary number of dimensions. The implementation uses the techniques reported in the paper Fast Poisson Disk Sampling in Arbitrary Dimensions published by Robert Bridson in 2007. In fact, the implementation in this library is based on the public domain example code provided by the author.

All code in this repository is released under the MIT license.

Contributions

This repository contributes the following improvements compared to the public domain code released by the original author:

• The code is in a single file and has no dependencies other than the standard library.
• The code is flexible in that results can be retrieved as a user-defined vector type (see examples below).
• The code is tested (see test folder and section below).
• The code is in a namespace (thinks::poisson_disk_sampling)

Cloning

This repository uses git submodules, which means that it needs to be cloned with the --recursive flag in order to initialize the submodules.

git clone --recursive https://github.com/thinks/poisson-disk-sampling.git

Note that the submodules are only used for building tests and examples.

Usage

Poisson disk sampling aims to generate a set of samples within a bounded region such that no two samples are closer than some user-specified radius. Let us first show a simple example.

#include <array>
#include <vector>

#include <thinks/poisson_disk_sampling/poisson_disk_sampling.h>

std::vector<std::array<float, 2>> Foo()
{
  namespace pds = thinks::poisson_disk_sampling;

  // Input parameters.
  constexpr auto radius = 3.f;
  const auto x_min = std::array<float, 2>{{ -10.f, -10.f }};
  const auto x_max = std::array<float, 2>{{ 10.f, 10.f }};

  // Samples returned as std::vector<std::array<float, 2>>.
  // Default seed and max attempts.
  const auto samples = pds::PoissonDiskSampling(radius, x_min, x_max);
  return samples;
}

The code snippet above generates a set of points in the 2D range [-10, 10] separated by a distance (radius) of 3 units. The image below visualizes the results (generated using a simple python script). On the right-hand side the radius has been plotted to illustrate the distance separating the points. Here it is "clear" that each circle contains only a single point.

There are two additional parameters of the PoissonDiskSampling function: seed and max_sample_attempts. The seed parameter is used to generate pseudo-random numbers in a deterministic way. Changing the seed gives slightly different patterns. The max_sample_attempts controls the number of attempts that are made at finding neighboring points for each sample. Increasing this number could lead to a more tightly packed sampling in some cases, at the cost of computation time. Both seed and max_sample_attempts have reasonable default values so they need not always be specified. The images below illustrate the effect of varying seed and max_sample_attempts.

By default the samples are returned as a std::vector<std::array<F, N>>, where the inner type std::array<F, N> has the same type as that used to specify the region bounds (see example above). In some cases it is useful to have the samples returned as a different type. There are two ways of doing this. First, we can explicitly provide our vector type together with a traits type, as in function Foo in the snippet below. The second way of doing it is to specialize the thinks::poisson_disk_sampling::VecTraits template for our vector type, as in function Bar below.

struct Vec3
{
  float x;
  float y;
  float z;
};

struct Vec3Traits
{
  typedef float ValueType;

  static constexpr auto kSize = 3;

  static ValueType Get(const Vec3& v, const std::size_t i)
  {
    return *(&v.x + i);
  }

  static void Set(Vec3* const v, const std::size_t i, const ValueType val)
  {
    *(&v->x + i) = val;
  }
};

namespace thinks {
namespace poisson_disk_sampling {

template<>
struct VecTraits<Vec3>
{
  typedef float ValueType;

  static constexpr auto kSize = 3;

  static ValueType Get(const Vec3& v, const std::size_t i)
  {
    return *(&v.x + i);
  }

  static void Set(Vec3* const v, const std::size_t i, const ValueType val)
  {
    *(&v->x + i) = val;
  }
};

} // namespace poisson_disk_sampling
} // namespace thinks

std::vector<Vec3> Foo()
{
  namespace pds = thinks::poisson_disk_sampling;

  constexpr auto radius = 3.f;
  const auto x_min = std::array<float, 3>{{ -10.f, -10.f, -10.f }};
  const auto x_max = std::array<float, 3>{{ 10.f, 10.f, 10.f }};
  
  // Explicitly passing in our own traits class.
  const auto samples = 
    pds::PoissonDiskSampling<float, 3, Vec3, Vec3Traits>(
      radius, x_min, x_max);
  return samples;
}

std::vector<Vec3> Bar()
{
  namespace pds = thinks::poisson_disk_sampling;

  constexpr auto radius = 3.f;
  const auto x_min = std::array<float, 3>{{ -10.f, -10.f, -10.f }};
  const auto x_max = std::array<float, 3>{{ 10.f, 10.f, 10.f }};

  // No need to explicitly specify traits here.
  const auto samples = pds::PoissonDiskSampling<float, 3, Vec3>(
    radius, x_min, x_max);
  return samples;
}

Tests

The tests for this distribution are written in the Catch2 framework. The Catch2 framework is included as a submodule in this repository.

Running the tests using CTest is simple. In a terminal do the following (and similar for Debug):

$ cd d:
$ git clone git@github.com:/thinks/poisson-disk-sampling.git D:/pds
$ mkdir build-pds
$ cd build-pds
$ cmake ../pds
$ cmake --build . --config Release
$ ctest . -C Release

For more detailed test output locate the test executable (thinks_poisson_disk_sampling_test.exe) in the build tree and run it directly.