Poisson Disk Sampling

The primary characteristic of a Poisson Disk distribution is its blue noise spectral profile. In frequency analysis, blue noise has most of its energy concentrated at high frequencies, meaning points repel each other. This results in a visually pleasing, natural randomness without low-frequency clumps or obvious grid-like structure, making it ideal for object placement, stippling, and dithering.

The algorithm's core constraint is a user-defined minimum separation distance (r) between any two sample points. This enforced spacing prevents points from being too close, eliminating the visual artifacts and impractical placements caused by clustering. The distance is typically uniform, but adaptive algorithms can vary it based on local density for more complex distributions.

The canonical efficient implementation is Bridson's algorithm (2007). It operates in O(N) time by:

• Maintaining an active list of candidate points.
• Using a background grid to accelerate spatial queries.
• For each active point, generating k random candidates in an annulus around it (between r and 2r).
• Accepting candidates that satisfy the minimum distance from all existing points. This structure makes it vastly more efficient than naive dart-throwing approaches.

Within the hard constraint of the minimum distance, the point placement is maximally random. Unlike a jittered grid, there is no underlying lattice. The process is stochastic, and each run produces a different, valid configuration. This balances the need for uniform coverage with the organic variability required for realistic procedural generation of forests, starfields, or terrain features.

Poisson Disk Sampling is critical for creating believable virtual environments:

• Object Placement: Distributing trees, rocks, or buildings naturally across a terrain.
• Sampling Integration: Generating sample points for Monte Carlo integration in rendering (e.g., ambient occlusion, depth of field) to reduce noise.
• Texture Synthesis: Seeding points for generating cellular textures or Voronoi patterns.
• Sensor Simulation: Placing virtual LiDAR or camera viewpoints for comprehensive scene coverage.

A Poisson Disk sample set produces a high-quality Voronoi diagram where all cells are relatively uniform in size and shape, avoiding long, thin cells. The dual Delaunay triangulation of these points results in triangles with near-equilateral angles, which is optimal for finite element analysis and mesh generation. This geometric quality is a direct result of the blue noise property.

A geometric partitioning of a plane into regions based on distance to a set of seed points. Each region contains all points closer to its seed than to any other. In procedural generation, it's used to create:

• Cellular patterns for terrain, textures, and biome distribution.
• Natural-looking object placement when combined with Poisson Disk seeds.
• Efficient spatial indexing for queries.

Key Relationship: The seed points for a Voronoi diagram are often generated using Poisson Disk Sampling to ensure evenly spaced, non-overlapping regions.

The algorithmic creation of game assets, environments, or levels automatically using rules, noise functions, or other generative systems. PCG encompasses:

• Terrain and level generation using algorithms like Perlin Noise or Wave Function Collapse.
• Asset placement, where Poisson Disk Sampling is a key technique for distributing objects like trees or rocks without artificial clustering.
• Rule-based systems for constructing complex structures like buildings.

Poisson Disk Sampling is a core spatial distribution algorithm within the broader PCG toolkit.

A gradient noise function developed by Ken Perlin that generates natural-looking, coherent randomness. It's a fundamental building block for:

• Procedural terrain heightmaps to create realistic mountains and valleys.
• Texture generation for clouds, marble, wood grain, and fire.
• Adding natural variation to parameters like object scale or color.

Contrast with Poisson Disk: While Perlin Noise creates continuous, smooth value fields, Poisson Disk Sampling generates discrete point sets. They are often used together—e.g., using a noise field to modulate the density of a Poisson sample.

A constraint-solving algorithm for procedural generation that creates locally coherent output by iteratively placing elements based on predefined adjacency rules. It's used for:

• Generating tile-based levels and architecture.
• Texture synthesis from example images.
• Creating large, consistent outputs from small input samples.

Comparison: Unlike the random-but-even distribution of Poisson Disk, WFC is deterministic from constraints. It's used for different PCG subproblems—logical layout vs. spatial distribution.

A simulation technique for training machine learning models by systematically varying environmental parameters (textures, lighting, object properties) to improve robustness and facilitate sim-to-real transfer. Key aspects:

• Visual randomization: Changing colors, textures, and lighting conditions.
• Dynamic randomization: Varying physics parameters like friction and mass.
• Object distribution: Using algorithms like Poisson Disk Sampling to randomize the positions and types of objects in a training scene, preventing overfitting to a specific layout.

A spectral characteristic of a point set where high-frequency components are emphasized, minimizing low-frequency artifacts and visual clumping. Poisson Disk Sampling produces blue noise distributions.

Technical Properties:

• Anti-aliasing: Blue noise patterns are excellent for stochastic sampling in rendering, reducing structured aliasing artifacts.
• Perceptual quality: Appears more naturally random to the human eye than white noise (uncorrelated) or regular grids.
• Applications: Beyond object placement, it's used for dithering, ray tracing sample distributions, and rendering filters.