@zakkster/lite-poisson-disc

Variable-radius, zero-GC, allocation-free Poisson-disc sampler for 2D.

One allocation at construction. No new Float32Array per frame. No object graphs. No GC pauses inside your animation loop. Spatially-varying minimum distance — density follows whatever function you hand it.

import { createVariablePoissonSampler2D } from '@zakkster/lite-poisson-disc';

const sampler = createVariablePoissonSampler2D({
  width: 800, height: 600,
  // Bigger discs in the centre, smaller at the edges:
  radius: (x, y) => {
    const dx = x - 400, dy = y - 300;
    const d = Math.sqrt(dx * dx + dy * dy);
    return 6 + 24 * (d / 500);
  },
  minRadius: 6, maxRadius: 30,
  k: 30,
});

sampler.fill();

// Read straight out of the backing Float32Array — no copies, no objects.
const xy = sampler.samples;
const r  = sampler.radii;
for (let i = 0; i < sampler.count; i++) {
  drawCircle(xy[i * 2], xy[i * 2 + 1], r[i]);
}

// Reuse for the next effect — zero allocation:
sampler.reset();
sampler.fill();

Contents

• Why · Install · Quick start
• How it works
• Case study: variable-density particle field
• API reference
• Benchmarks
• Testing (for clients & QA)
• Browser & engine compatibility
• Edge cases & guarantees
• FAQ · License

Why

Existing JavaScript Poisson-disc samplers do one of two things, both of which are wrong for animation loops:

1. Allocate a fresh sampler per call. The constructor creates a grid, a queue, a results array, and a handful of internal arrays — all of it garbage the moment fill() returns. At a few thousand samples per frame that's a megabyte or two of GC pressure every time.
2. Return points as [number, number][]. Every sample is a fresh two-element array. The renderer reads them, copies the coordinates into its own buffer, then drops the objects on the floor.

Both patterns are fine for a one-shot static scatter. Neither survives a 60 fps loop that re-samples on resize, parameter change, or per-frame.

flowchart LR
    subgraph N["Naive path (every competitor on npm)"]
        direction TB
        N1[new PoissonDiskSampling]
        N2[allocates grid, queue,<br/>active list, results array]
        N3[fill returns Array of pairs]
        N4[caller copies into render buffer]
        N5[everything becomes garbage]
        N1 --> N2 --> N3 --> N4 --> N5 -.->|GC pressure<br/>frame stalls| N1
    end
    subgraph L["lite-poisson-disc path"]
        direction TB
        L0[createVariablePoissonSampler2D<br/>once, at scene init]
        L1[reset count = 0]
        L2[fill writes into<br/>Float32Array views]
        L3[caller reads .samples<br/>directly — no copy]
        L0 -.->|reused forever| L1
        L1 --> L2 --> L3 -.->|no garbage| L1
    end

@zakkster/lite-poisson-disc owns its grid, active list, and output buffers as Int32Array / Float32Array. Construction allocates once. The hot path (step, fill) does indexed-store operations only. The output is the same Float32Array the algorithm uses internally — you can pipe it straight into a draw call.

It's also the only library on npm (that I can find) that does variable-radius sampling and keeps zero allocation pressure in the reuse path.

What this is not

• Not the fastest single-shot fixed-radius sampler. fast-2d-poisson-disk-sampling is ~2× faster on raw throughput for a one-off fixed-radius scatter and you should use it if that's your whole use case (see benchmarks). lite-poisson-disc trades that headline number for variable radius, near-zero steady-state allocation, and an incremental step() API.
• Not a triangulator / not a Voronoi library. It returns a point cloud. Pair with d3-delaunay if you need topology.
• Not 3D. 2D only. 3D may land in a future version if there's demand.

Install

npm i @zakkster/lite-poisson-disc

ESM-only. Zero dependencies. Ships TypeScript definitions alongside the source.

import {
  createVariablePoissonSampler2D,
  estimateMaxSamples2D,
} from '@zakkster/lite-poisson-disc';

You can also drop src/index.js into your project directly — it's one file, ~250 lines.

Quick start

import { createVariablePoissonSampler2D } from '@zakkster/lite-poisson-disc';

// Once, at renderer init:
const sampler = createVariablePoissonSampler2D({
  width: canvas.width,
  height: canvas.height,
  radius: (x, y) => densityField(x, y),   // your function, called per candidate
  minRadius: 4,
  maxRadius: 24,
  k: 30,                                  // Bridson's recommendation
});

// Per resize / parameter change:
sampler.reset();
sampler.fill();

// Read the result:
const pts = sampler.samples;              // Float32Array, interleaved [x, y, x, y, ...]
const rs  = sampler.radii;                // Float32Array, one radius per point
const n   = sampler.count;

ctx.beginPath();
for (let i = 0; i < n; i++) {
  ctx.moveTo(pts[i * 2] + rs[i], pts[i * 2 + 1]);
  ctx.arc(pts[i * 2], pts[i * 2 + 1], rs[i], 0, Math.PI * 2);
}
ctx.fill();

Spreading work across frames

If fill() would block too long (saturating a large domain at small radii can take 50–80 ms), use step() to amortise:

const sampler = createVariablePoissonSampler2D({ /* ... */ });

function frame() {
  if (!sampler.done) sampler.step(200);   // generate up to 200 samples this frame
  drawCurrentState(sampler);
  requestAnimationFrame(frame);
}

step(n) generates up to n samples and returns the actual number produced. When sampler.done flips true the active list is exhausted.

Deterministic output

Pass any () => number PRNG returning [0, 1). Pair with @zakkster/lite-random for a seeded, allocation-free sfc32:

import { sfc32 } from '@zakkster/lite-random';

const rng = sfc32(1, 2, 3, 4);
const sampler = createVariablePoissonSampler2D({
  width, height, radius, minRadius, maxRadius,
  random: rng,
});

Same seed + same params = byte-identical output. Useful for replay, deterministic procgen, golden-master tests.

How it works

The algorithm

Bridson's "Fast Poisson Disk Sampling in Arbitrary Dimensions" (2007), with one twist: the minimum-distance constraint is allowed to vary per point. A candidate at distance d from a neighbour is accepted iff d ≥ max(rcandidate, rneighbour) — i.e. the larger of the two discs has to fit. Classic fixed-radius Poisson is the special case where all radii are equal.

flowchart TB
    A[Pick first sample at random<br/>add to grid + active list]
    B{Active list empty?}
    C[Pick random parent from active list]
    D[Try k candidates at distance<br/>r..2r around the parent]
    E{Any candidate<br/>passes the disc test?}
    F[Add to samples / grid /<br/>active list]
    G[Retire parent<br/>swap-pop the active list]
    H((Done))

    A --> B
    B -- no  --> C --> D --> E
    E -- yes --> F --> B
    E -- no  --> G --> B
    B -- yes --> H

Memory layout

flowchart TB
    subgraph BB["One allocation at construction"]
        direction LR
        S["samples : Float32Array<br/>capacity * 2<br/>[x0, y0, x1, y1, ...]"]
        R["radii : Float32Array<br/>capacity"]
        G["grid : Int32Array<br/>gridCols * gridRows<br/>cell → sample index, -1 = empty"]
        A["activeList : Int32Array<br/>capacity"]
    end
    HOT["Hot loop (step / fill)<br/>indexed stores only<br/>no allocation"] -.-> BB

• samples is interleaved x/y for cache-friendly iteration. Hand it to a draw call as-is.
• radii is parallel — radii[i] is the disc radius of the sample at samples[i*2 .. i*2+1].
• grid is a spatial hash sized to cell = minRadius / √2. One cell holds at most one sample (Bridson's guarantee — for the fixed-radius case; the variable-radius variant uses the same grid with an expanded neighbour-search extent of ceil(maxRadius / cellSize) cells).
• activeList is the parent-candidate queue. Failed parents are removed by swap-with-tail.

All four arrays are sized to capacity at construction. Nothing else is ever allocated.

Why hoist the output buffers?

Same reason as vb.count in @zakkster/lite-batch-buffer: property access through this is slower than indexed access into a local typed-array reference. The library exposes samples and radii as getters that return the same backing buffer every time, so you can hoist:

const xy = sampler.samples;       // hoist once
const r  = sampler.radii;
const n  = sampler.count;
for (let i = 0; i < n; i++) {
  // ...uses xy[i*2], xy[i*2+1], r[i]
}

Case study: variable-density particle field

A real-world scene: 1024×768 canvas, particle field with 5× density variation across the domain (sparse at the edges, dense in the centre), re-sampled on every resize / mouse-controlled focal point.

The three approaches

1. Naive — fresh sampler per change:

function onResize() {
  const p = new PoissonDiskSampling({
    shape: [width, height],
    minDistance: 6, maxDistance: 30,
    tries: 30,
    distanceFunction: (pt) => /* density 0..1 */,
  });
  const points = p.fill();                // Array of [x, y] pairs
  particles = points.map(([x, y], i) => ({ x, y, r: p.radii[i] }));
}

Constructor allocs: ~1 MiB. Result array: another ~150 KiB. Object array: another ~250 KiB. All garbage on the next resize.

2. fast-2d-poisson-disk-sampling — fastest, but fixed radius:

const p = new FastPoissonDiskSampling({ shape: [w, h], radius: 12, tries: 30 });
const points = p.fill();

~2× faster than (1) on raw throughput. But: fixed radius only — no density variation. And still allocates per call.

3. lite-poisson-disc — one sampler, reused forever:

// Once:
const sampler = createVariablePoissonSampler2D({
  width: w, height: h,
  radius: densityFn,
  minRadius: 6, maxRadius: 30,
  k: 30,
});

// On every change:
sampler.reset();
sampler.fill();
const xy = sampler.samples;
const r  = sampler.radii;
// draw directly from xy / r — no intermediate object array

Results

Measured on Node 22 / x86-64, median of 5 runs × 20 iterations, fresh process per scenario. Re-run npm run bench on your own hardware.

Scenario A — fixed radius, 1000×1000, r = 8 (saturated to ~9 850 samples)

| Library | ms/call | samples/sec | alloc/call | vs best | |---|---:|---:|---:|---:| | fast-2d-poisson-disk-sampling | 34.93 | 392 K | 1.32 MiB | — | | poisson-disk-sampling | 58.93 | 169 K | 1.26 MiB | 1.69× | | @zakkster/lite-poisson-disc | 60.06 | 164 K | 453 KiB | 1.72× | | @zakkster/lite-poisson-disc (reused) | 58.14 | 169 K | 60.8 KiB | 1.66× |

Scenario B — variable radius, 1000×1000, r = 4..16 (~6 960 samples; fast-2d doesn't support variable radius)

| Library | ms/call | samples/sec | alloc/call | vs best | |---|---:|---:|---:|---:| | poisson-disk-sampling | 71.68 | 161 K | 1.05 MiB | — | | @zakkster/lite-poisson-disc | 75.30 | 92 K | 102.9 KiB | 1.05× | | @zakkster/lite-poisson-disc (reused) | 73.65 | 94 K | 15.8 KiB | 1.03× |

Scenario C — cold start × 60 small samplers (200×200, r = 4 — the particle-effect spawn pattern)

| Library | ms/call | samples/sec | alloc/call | |---|---:|---:|---:| | fast-2d-poisson-disk-sampling × 60 | 329 ms | 405 K | 2.21 MiB | | poisson-disk-sampling × 60 | 534 ms | 181 K | 2.78 MiB | | @zakkster/lite-poisson-disc × 60 (fresh) | 550 ms | 174 K | 1020 KiB | | @zakkster/lite-poisson-disc × 60 (pooled) | 544 ms | 176 K | 1.17 MiB |

Allocation pressure (log scale)

%%{init: {"theme":"dark"}}%%
xychart-beta
    title "Heap allocation per call, KiB (log scale) — lower is better"
    x-axis ["fast-2d (A)", "poisson-disk (A)", "lite reused (A)", "poisson-disk (B)", "lite reused (B)"]
    y-axis "KiB (log)" 1 --> 2000
    bar [1352, 1290, 61, 1075, 16]

The headline: on Scenario B (variable radius, reused) the competitor allocates ~68× more heap per call than lite-poisson-disc. Across a 60 fps loop that's the difference between zero GC pauses and a stutter every few seconds.

Throughput honesty

%%{init: {"theme":"dark"}}%%
xychart-beta
    title "Throughput, K samples/sec — higher is better"
    x-axis ["fast-2d (A)", "poisson-disk (A)", "lite (A)", "poisson-disk (B)", "lite (B)"]
    y-axis "K samples/sec" 0 --> 450
    bar [392, 169, 169, 161, 94]

fast-2d-poisson-disk-sampling is the throughput leader on its supported scenario (fixed radius). lite-poisson-disc matches poisson-disk-sampling on fixed radius and trails it by ~40 % on variable radius — that's the cost of a more conservative variable-radius collision rule (max(r_a, r_b)) and per-candidate radius evaluation. You're trading ~40 % single-shot speed for two orders of magnitude lower allocation. Depending on your app, that's either the best deal in the README or the worst one.

When it matters

| Scenario | Re-sample rate | Without lite-poisson-disc | With lite-poisson-disc | |---|---|---|---| | One-shot scatter at page load | once | irrelevant | irrelevant | | Procgen seed map | per level load | usually fine | fine | | Resizable canvas + density slider | per UI change | GC pause on every tweak | smooth | | Animated focal point (mouse-following density) | every frame | frame stalls inside 30 s | flat heap forever | | Twitch Extension overlay (1 MB / 3 s budget) | per overlay event | too heavy | fits comfortably |

Rule of thumb: if you re-sample more than once per page lifetime, the allocation profile matters more than the per-call ms.

API reference

createVariablePoissonSampler2D(opts) → Sampler

| Option | Type | Description | |---|---|---| | width | number | Domain width. Must be > 0. | | height | number | Domain height. Must be > 0. | | radius | (x, y) => number | Spatially-varying minimum distance. Called once per candidate. Non-finite returns are clamped to minRadius; otherwise clamped to [minRadius, maxRadius]. | | minRadius | number | Global minimum across the domain. Sizes the spatial-hash grid. Must be > 0. | | maxRadius | number | Global maximum across the domain. Sizes the candidate neighbour-search radius. Must be ≥ minRadius. | | k | number | Rejection attempts per active sample. Default 30 (Bridson). Returns above ~30 diminish; below ~10 the result starts looking less uniform. | | random | () => number | RNG returning [0, 1). Default Math.random. Use a seeded scalar PRNG (sfc32, mulberry32) for determinism. | | seeds | ArrayLike<number> | Pre-seeded samples to respect as constraints. Layout: [x0, y0, x1, y1, ...]. Out-of-domain points are dropped. Seed proximity is not validated against other seeds. | | out | Float32Array | Caller-owned output buffer. Must be ≥ capacity * 2 in length. If omitted, the sampler allocates one internally. | | maxSamples | number | Hard cap. Default estimateMaxSamples2D(width, height, minRadius). Determines all internal buffer sizes — no allocation after construction. | | wrap | boolean | Toroidal (wrap-around) domain. Default false. Cannot wrap if maxRadius reaches across the domain. |

Sampler instance

| Member | Type | Description | |---|---|---| | fill() | () => number | Run to completion. Returns total samples generated this call. | | step(n?) | (n?: number) => number | Generate up to n more samples (default 1). Returns the number actually produced. | | reset(random?) | (random?: () => number) => void | Reset state, preserve all buffers. Optionally re-seed the RNG. | | done | boolean | true once the active list is exhausted or capacity is reached. | | count | number | Number of samples currently written. | | capacity | number | Maximum samples the buffers can hold. | | samples | Float32Array | Backing buffer. Stable reference — getter returns the same instance every call. Iterate [0, count * 2). | | radii | Float32Array | Per-sample radius. Stable reference. Iterate [0, count). |

estimateMaxSamples2D(width, height, radius) → number

Conservative upper bound on sample count for a given domain and minimum radius. Uses Bridson's grid density (r/√2) with a +16 safety margin. Pass the result as maxSamples to size internal buffers tightly when you have a fixed budget.

Error conditions

| Situation | Throws | |---|---| | width ≤ 0 or height ≤ 0 | Invalid domain size: width and height must be > 0 | | minRadius ≤ 0 or maxRadius < minRadius | Invalid radius bounds | | radius is not a function | radius must be a function (x, y) => number | | wrap: true with maxRadius ≥ half-domain | maxRadius too large relative to domain for wrap mode | | out.length < capacity * 2 | out buffer length N < required M | | seeds.length is odd | seeds array must have even length (x,y pairs); got N | | seeds.length / 2 > capacity | seed count N exceeds capacity M |

All validation runs at construction time. The hot loop has zero branches that throw.

Benchmarks

Node CLI

node --expose-gc bench/benchmark.js
# or: npm run bench

Runs three scenarios — fixed radius, variable radius, cold-start × 60 — against poisson-disk-sampling and fast-2d-poisson-disk-sampling. Each scenario runs in a fresh child process to keep V8 JIT/IC state from contaminating later scenarios' heap numbers. --expose-gc is required for accurate alloc/call figures.

Output is a coloured table per scenario, with ms/call, samples/sec, alloc/call, and persistent (heap retained after a forced GC — should be ≤ V8 noise for a correct library).

Testing (for clients & QA)

Three levels of verification.

1. Unit tests — "does the library do what it says?"

npm test
# or: node --expose-gc test/poisson.test.js

Runs 36 deterministic assertions covering:

| Group | What's tested | |---|---| | estimateMaxSamples2D | Formula correctness, non-degenerate radius, safety margin | | Construction + validation | Bad domain, bad radius bounds, non-function radius, undersized out buffer, odd-length seeds, oversized seeds | | Basic sampling | Counts > 0, all samples in domain, all pairwise distances satisfy max(r_a, r_b) | | Variable radius | Density follows the radius function (more samples where radius is small); per-sample radii recorded in .radii | | Incremental step() | Generates ≤ N at a time, sums to the same total as fill(), sets done correctly | | Determinism | Same seed + same params = byte-identical samples + radii | | Seeds | Pre-seeded points appear in output; out-of-domain seeds are silently dropped | | Wrap mode | Constraint satisfied across the toroidal seam (distances measured with min-image) | | Buffer ownership / zero-alloc | samples / radii getters return the same instance across many calls; caller-owned out is used in place; reset + fill does not grow the heap (smoke test under --expose-gc) | | Bug regression | The fill() active-list swap (a v0.0.x bug where failed parents weren't being removed correctly) |

A clean run prints 36 passed, 0 failed and exits 0. Any failure prints the assertion plus expected / actual. CI-suitable.

2. Benchmark — "does it perform as claimed?"

npm run bench

Reproduces the case-study tables on your hardware. Exit code is always 0; the signal is the numbers. On any 2021+ machine you should see:

• Scenario A reused: alloc/call < 100 KiB (vs ~1.3 MiB for the other two libs)
• Scenario B reused: alloc/call < 50 KiB (vs ~1 MiB for poisson-disk-sampling)
• persistent near zero (typically a few KiB of V8 churn — not lite-poisson-disc allocations)

Quick npm run reference

| Command | What it does | |---|---| | npm test | Run the 36-test unit suite | | npm run bench | Run the Node benchmark vs. competing libraries | | npm run verify | npm test && npm run bench — the full CI-style check |

Browser & engine compatibility

The library is plain ESM and uses only Float32Array / Int32Array / standard Math. It works everywhere ES2015+ works.

| Target | Library | Demo | |---|---|---| | Chrome / Edge 61+ | ✅ | ✅ | | Firefox 60+ | ✅ | ✅ | | Safari 15+ (iOS 15+) | ✅ | ✅ | | Node.js 14+ | ✅ | — (browser only) | | Bun / Deno | ✅ | — | | Twitch Extensions (Chromium iframe) | ✅ | ✅ |

Twitch Extensions specifically

This library was built with Twitch Extensions' 1 MB total upload / 3 s cold-start budget in mind. Its minified+gzipped footprint is on the order of 2 KB, with no runtime dependencies. One sampler instance owns its buffers for the lifetime of the extension; nothing leaks into the GC's nursery during overlay updates.

Edge cases & guarantees

Behaviours the test suite pins down:

• samples and radii are stable references. Both getters return the same Float32Array instance for the lifetime of the sampler. You can hoist them once at scene init.
• reset() does not zero samples or radii. Old sample data is still there until overwritten. count is reset to 0; only [0, count) is ever meaningful.
• Seed-to-seed proximity is not validated. Seeds are trusted. If you pass two seeds 0.1 px apart, both end up in the output and both block subsequent candidates. Validate your seeds upstream if you care.
• The variable-radius collision rule is max(r_a, r_b). A candidate disc of radius 4 next to a stored disc of radius 16 must clear 16, not the average. This is the conservative choice and the only one that guarantees no overlap when the function is monotone in space.
• radius(x, y) returning a non-finite number is clamped to minRadius. No NaN propagation, no infinite loops. (Infinity from your function gets clamped to maxRadius.)
• The hot loop allocates nothing. Verified empirically (test suite) and by inspection: every variable inside step / fill is a primitive let, every container is an indexed typed-array write. The output buffer is the input buffer.
• done is monotone. Once done flips to true, only reset() can flip it back. step() and fill() on a done sampler return 0 immediately.
• Wrap mode preserves the constraint across the seam. Distances are measured with the toroidal min-image (min(dx, width - dx)) on both axes. The test suite includes a wrap-mode validator.

FAQ

Why no fixed-radius variant? Every other library has one. Because the variable-radius sampler degenerates to fixed-radius when radius is constant, with no measurable overhead — the per-candidate radius lookup is one function call and one clamp, and V8 inlines the lambda. The benchmark shows radius: () => R matches poisson-disk-sampling's fixed-radius path within noise. There's no API to maintain, and one code path means one set of bugs.

How big should maxSamples be? By default, estimateMaxSamples2D(width, height, minRadius), which is a safe upper bound — ceil(2 × W × H / r²) + 16. For a 1000×1000 domain at r=8 that's ~31 KB of buffers. If you want tighter memory and you know your density field doesn't saturate the small-radius regions, pass an explicit maxSamples lower than the default. The library will return done = true when it hits the cap.

Can I have multiple samplers? Yes. They're independent objects with their own buffers. Sharing one sampler across multiple effects is the recommended pattern, though — reset() is cheaper than constructing.

Does the order of samples matter? Samples are in generation order — the first sample is the root, and each subsequent sample is the child of some prior one (active-list parent). This means sample 0 to sample 10 are a connected cluster around the root, not a uniform random subset of the whole point cloud. If you want a uniform subset, sample uniformly from [0, count).

Why is samples interleaved instead of two separate arrays? Cache locality. The renderer reads x and y together, almost always. Interleaved [x0, y0, x1, y1, ...] is one cache line per two points; two separate arrays would be one cache line per four points across two streams.

What PRNG should I use? Anything fast and scalar. Math.random is fine. For determinism use sfc32 or mulberry32 — both fit in a closure with four / one uint32 of state. @zakkster/lite-random ships both, allocation-free. Don't use crypto.getRandomValues for this — it allocates and is 100× slower.

Can I sample on the GPU? Not with this library. GPU-side Poisson via dart-throwing or relaxation is a different algorithm — see Wei 2008. This library is for CPU-side scene-graph / particle-system generation where you want the output back in JavaScript.

Does it work in a Web Worker? Yes. The library has no DOM dependencies. You can build the sample buffer in a worker and postMessage(sampler.samples.buffer, [sampler.samples.buffer]) to transfer ownership — but note that the transfer neuters the original, so you'll need to construct a fresh sampler after each transfer. For zero-copy two-way sharing use a SharedArrayBuffer and pass it as the out option.

Part of the @zakkster ecosystem

Zero-GC, allocation-free utility libraries for performance-critical JavaScript:

• @zakkster/lite-batch-buffer — interleaved vertex buffer for WebGL / WebGPU sprite batchers
• @zakkster/lite-random — seeded scalar PRNGs (sfc32, mulberry32, xorshift)
• @zakkster/lite-ecs — allocation-free entity-component-system
• @zakkster/lite-ease — easing functions, zero allocation
• @zakkster/lite-pointer-tracker — pointer / touch state without garbage

License

MIT © the author