Bridson算法：如何优雅地随机撒点

Poisson Disk Sampling

2024年，数学家们用近1000页证明了几何Langlands猜想，而2007年Robert Bridson仅用一页纸就解决了计算机图形学中随机撒点的难题。在程序生成森林时，我们常遇到树木重叠的问题，Poisson disk sampling正是解决这一问题的关键。Bridson算法通过网格划分和活性列表，高效生成互不重叠的随机点。文中还探讨了两种优化技巧：利用父子点关系排除无效角度，以及调整距离分布参数c来平衡密度与随机性。此外，文章还介绍了动态半径下的Stippling效果，以及Scott A. Mitchell提出的确定性算法，后者在保证最大性和均匀性的同时，完全摒弃了拒绝采样。