Poisson Disc Sampling

GPU-accelerated generation of 2D points with a guaranteed minimum distance between them. Returns a GPUBuffer of vec2<f32> points. Useful for object placement, texture sampling, blue noise generation, and procedural content placement.

Usage

import { poissonDisc } from './poisson-disc';

const result = await poissonDisc(device, {
  width: 100,
  height: 100,
  minDistance: 2.0,
  seed: 42,
  maxPoints: 10_000
});

const pointBuffer = result.points; // GPUBuffer of vec2<f32>
const count = result.count; // number of points generated
result.destroy();

API

poissonDisc(device, options?)

Returns a Promise<PoissonDiscResult>. This is a one-shot operation — call it, get the result, use the buffer.

Option	Type	Default	Description
width	number	100	Domain width
height	number	100	Domain height
minDistance	number	2.0	Minimum distance between points
seed	number	(random)	RNG seed for reproducible results
maxPoints	number	10_000	Upper bound for buffer allocation
candidatesPerPoint	number	30	Candidates tested per active point per iteration
maxIterations	number	500	Maximum iterations before stopping

result.points

GPUBuffer containing vec2<f32> values (8 bytes per point). Usage: STORAGE | COPY_SRC | COPY_DST.

result.count

The number of points actually generated. Use this to know how much of the buffer is valid.

result.destroy()

Releases internal GPU buffers (grid, active list, counters). The points buffer is not destroyed — it's yours to use and destroy when done.

Algorithm

This implements a GPU-accelerated variant of Bridson's algorithm:

1. Grid setup — Divide the domain into cells of size minDistance / sqrt(2). This guarantees each cell contains at most one point, enabling fast spatial lookup.

2. Seed — Place an initial point at the domain center.

3. Iterate — For each active point, generate candidatesPerPoint random points in the annulus between minDistance and 2 * minDistance. For each candidate:

   • Check the 5×5 neighbourhood of grid cells for distance violations
   • If valid, atomically claim the grid cell (compare-exchange) and add the point
   • Add newly accepted points to the next iteration's active list

4. Converge — Repeat until no active points remain (all candidates were rejected).

The GPU parallelism comes from evaluating many active points and their candidates simultaneously. Atomic compare-exchange on the grid ensures correctness when multiple threads try to claim the same cell.

WGSL loading

The default import uses Vite's ?raw suffix:

import shaderSource from './poisson-disc.wgsl?raw';

If you're not using a bundler, load via fetch:

const shaderSource = await fetch(new URL('./poisson-disc.wgsl', import.meta.url)).then((r) =>
  r.text()
);

Modifying

Extend to 3D

To generate 3D points:

• Change vec2<f32> to vec3<f32> in points buffer and grid lookups
• Use a 3D grid: cell_size = minDistance / sqrt(3)
• Sample candidates in a spherical shell instead of a 2D annulus
• Check a 5×5×5 neighbourhood instead of 5×5

Variable density

To vary the minimum distance across the domain:

• Pass a density texture as an additional binding
• In the is_valid function, sample the density at the candidate position and use it to modulate min_distance
• This lets you create denser sampling in some areas (e.g., near a character) and sparser in others

Use the output buffer for instanced rendering

The points buffer can be bound directly as a vertex buffer or storage buffer in a render pipeline:

@group(0) @binding(0) var<storage, read> points: array<vec2f>;

@vertex
fn vs(@builtin(instance_index) instance: u32) -> @builtin(position) vec4f {
  let pos = points[instance];
  // Transform to clip space...
}

Change the point data layout

To add extra data per point (radius, category, color), increase the point struct size and modify the points buffer layout. For example, change array<vec2f> to array<vec4f> where .xy is position, .z is radius, and .w is category.