Optimizing Poisson Disk Sampling: From Bridson to Mitchell

Poisson disk sampling is an essential technique for generating random point sets with a guaranteed minimum distance between elements. The article details Bridson's classic algorithm and introduces optimizations like parental angle exclusion and radial distance tuning to improve efficiency and density. Finally, it discusses Mitchell's modern deterministic approach, which provides a maximal and uniform alternative to traditional rejection-based methods.

Key Points

• Poisson disk sampling creates random distributions where no two points are closer than a specified distance, avoiding the overlapping issues of pure random sampling.
• Bridson's algorithm is the industry standard for efficiency, utilizing a background grid and an active list to sample points in O(N) time.
• The author's parental optimization reduces redundant sampling by calculating and excluding angular ranges already occupied by a point's parent.
• Adjusting the distance distribution exponent 'c' allows for tighter point packing, though it requires balancing density against the visual 'randomness' of the distribution.
• Mitchell's 2022 algorithm represents a significant advancement by being deterministic, maximal, and uniform without relying on traditional rejection sampling.

Sentiment

The overall sentiment is strongly favorable. Commenters largely accept the article's framing and use it as a basis for appreciative remarks, related resources, and technical clarification. The disagreements are mild and mostly concern applicability boundaries rather than rejection of the article's core ideas.

In Agreement

• The visualizations make the algorithm easier to understand and are valuable for graphics learners.
• Poisson disk sampling is a useful way to produce distributions that feel random while avoiding visually unpleasant clustering.
• The article fits naturally into a broader graphics context that includes blue noise, stippling, procedural grass placement, and related sampling demos.
• The post's interactive treatment helps expose implementation behavior that is otherwise hard to reason about from formulas alone.

Opposed

• Some generated patterns can appear to form lines, raising questions about aliasing and whether low-discrepancy approaches may be preferable for some graphics workloads.
• Bridson-style active-list sampling is awkward to express as a purely per-pixel shader, which can push practical implementations toward hashed-cell jitter or specialized GPU methods.
• Poisson disk sampling is not naturally a low-discrepancy sequence because it usually targets a completed set over a region rather than an arbitrary prefix of points.