Procedural Object Placement with Variable-Radius Poisson Disk Sampling and noise

When generating large procedural worlds, placing objects believably is harder than it looks.

Trees shouldn’t overlap. Rocks shouldn’t clump unnaturally. Buildings need breathing room. And ideally, all of this should be controllable, performant, and compatible with procedural generation.

A few years ago, while working on procedural world generation for my game, I ran into exactly this problem i.e. placing objects of varying sizes, driven by noise, with zero overlap.

This post is a write-up of how I approached that problem, what didn’t work, and the solution I ended up shipping.

The Problem

At a high level, I wanted to:

• Place objects procedurally across a 2D surface

• Allow each object to have a different radius

• Guarantee no overlap

• Retain a natural, non-grid-like distribution

• Be able to bias density using noise or gameplay logic

Classic Poisson disk sampling gives you a nice "even but random" distribution but it assumes a fixed minimum distance between points. That assumption breaks down immediately when object sizes vary.

Why Standard Poisson Disk Sampling Falls Short

Traditional Poisson disk sampling works by enforcing a single global minimum distance between samples. That’s great if every object is the same size.

But once you introduce variable radii:

• A small object can sit comfortably near another small object

• A large object needs more space

• The minimum distance is no longer constant

You can try to cheat by inflating everything to the maximum radius but that leads to:

• wasted space

• overly sparse distributions

• loss of detail where small objects should be dense

In short: the distance constraint needs to be local, not global.

Idea: The Radius Is the Constraint

Instead of thinking in terms of "points with a minimum distance" I reframed the problem as:

Each object has a radius, and no two objects' influence circles may overlap.

That seems obvious in hindsight, but it changes how you structure the algorithm.

Instead of asking:

"Is this point at least D away from others?"

You ask:

"Does this object’s radius overlap with any existing object’s radius?"

That means overlap tests become:

distance(p1, p2) >= r1 + r2

Once you accept that, the rest of the system can be built around it.

Adding Noise-Driven Density

Uniform distributions are fine but procedural worlds benefit from variation.

To control where objects want to appear, I introduced procedural noise as a placement bias, not as a hard rule.

The workflow became:

1. Sample a candidate position

2. Use noise to decide:

   • whether something should exist here

   • what size it should be

3. Attempt to place the object

4. Reject it if it overlaps anything already placed

This approach has a few nice properties:

• Designers can control density using noise parameters

• The same system works for trees, rocks, structures, etc.

• Rejection sampling naturally enforces spacing

Making It Fast Enough

Naively checking every new object against every existing object doesn’t scale.

To keep this practical, I used spatial partitioning (a simple grid) to reduce overlap checks to nearby cells only. Each placed object is inserted into the grid cells it overlaps, and new candidates only test against objects in those cells.

This keeps placement costs roughly constant, even as object count grows.

The result is a system that:

• scales well

• is deterministic when needed

• works in real time or during world generation

Results in Practice

This sampler ended up being flexible enough to use across multiple contexts:

• natural object scattering

• terrain decoration

• gameplay-relevant structures

Because object size, noise bias, and placement constraints are all decoupled, it’s easy to tune without rewriting the algorithm.

I eventually cleaned up the implementation and published it here:

https://github.com/bensanmorris/poisson_disk_sampler

A couple of videos of it in action are here:

And here:

Final Thoughts

Procedural generation lives in the space between theory and messy reality. Algorithms rarely work out-of-the-box once real constraints enter the picture.

This wasn’t about inventing a new sampling technique it was about adapting a known idea to solve a real production problem.

If you’re working on procedural placement and have ever fought with clumping, overlaps, or over-uniform distributions, I hope this gives you a useful angle of attack.