Poisson-Disk Sampling: Bridson's Algorithm (2D) |…

What is Poisson-Disk Sampling?

Poisson-disk sampling is a method for generating a set of points that are both uniformly distributed across a given area and well-separated from each other. This technique ensures no two points are too close, which is crucial for creating natural-looking textures or patterns in computer graphics.

The algorithm was popularized by Robert Bridson through his paper 'Fast Poisson Disk Sampling in Arbitrary Dimensions,' published in 2007.

How Does Bridson's Algorithm Work?

Bridson's algorithm begins by placing a single point at the center of the sampling area. It then iteratively adds new points within an annulus (ring-shaped region) around existing points, ensuring that each candidate point is sufficiently far from all previously placed points.

The algorithm uses a minimum-distance rejection test to ensure that no two points are closer than a specified distance r. This process continues until the desired number of points or the entire area is filled.

live demo · related simulation● LIVE

Why Does Poisson-Disk Sampling Matter?

Poisson-disk sampling is essential in computer graphics for generating realistic textures and patterns, such as clouds, grass, and fire. It ensures that elements are not too close to each other, which would otherwise create an unnatural appearance.

In addition, it is used in various applications like game development, scientific visualization, and even urban planning simulations.

Real-World Applications

Poisson-disk sampling has numerous practical applications. For example, in video games, it can be used to place trees or rocks in a way that looks natural without overlapping.

In scientific visualization, it helps in rendering complex data sets by ensuring that points representing data are evenly distributed and not clustered together.

Frequently asked questions

What is the significance of the minimum-distance r parameter?

The minimum-distance r parameter controls how close any two generated points can be. A larger value results in more space between points, while a smaller value leads to denser sampling.

How does Poisson-disk sampling differ from simple random sampling?

Simple random sampling places points randomly within the area, which often results in clustering and gaps. Poisson-disk sampling ensures that no two points are too close, leading to a more uniform distribution.

Can Poisson-disk sampling be used in 3D?

Yes, Bridson's algorithm can be extended to three dimensions for generating 3D point distributions. This is particularly useful for applications like volumetric rendering or terrain generation.

What are some limitations of Poisson-disk sampling?

While effective, Poisson-disk sampling can be computationally expensive and may not always produce the most optimal distribution, especially in large areas. It also requires careful tuning of parameters like r and k to achieve the desired result.

Try it live

Everything above runs in your browser — open Poisson-Disk Sampling: Bridson's Algorithm (2D) and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.

▶ Open Poisson-Disk Sampling: Bridson's Algorithm (2D) simulation