泊松盘采样

2024 年，一个由 9 名数学家组成的团队发布了一份长达近 1000 页的几何朗兰兹猜想的巨大证明。这是纯数学领域的最高成就，我承认我永远无法理解他们所证明的陈述，更不用说证明本身了。与此完全相反的是，2007 年，罗伯特·布里德森 (Robert Bridson) 发表了一篇一页纸的论文，被引用了近 1,000 次，只需不到 10 分钟即可完全理解。它为计算机图形和模拟中常见的问题提供了一个简单的解决方案：随机放置事物，但不要太靠近。假设您正在尝试按程序生成一片森林，并且需要一种放置树木的方法。普通随机采样的问题很明显：有些树会相互重叠！我们需要的是能够设置任意两棵树之间的最小距离。遵守此规则的树分布称为泊松盘分布。我们可以尝试一种简单的拒绝采样方法，即抛出随机飞镖并拒绝落在任何其他点的最小距离内的任何点，但如果没有更聪明的数据结构，则需要线性时间来检查每个样本的碰撞，并且拒绝率很快就会接近 1。布里德森的算法为我们提供了一种有效的方法来做到这一点。 Bridson 算法假设点之间所需的最小距离是 r r r 并且我们正在 dd d 维空间中工作。 Bridson 算法如下：将空间划分为边长为 r d \frac{r}{\sqrt{d}} d ​ r ​ 的网格。这保证了每个网格单元内部最多可以有一个点。初始化一个活动列表，从空间中均匀选择一个随机点。当active非空时：从active中均匀随机选择一个元素p p p。对以 p p p 为中心、内半径 r r r 和外半径 2 r 2r 2 r 的圆环均匀采样最多 k k k 次。如果找到有效的泊松盘样本，则使用网格进行有效的碰撞检测，将其添加到活动状态并选择一个新的 p p p 。如果在 k k k 次尝试中未找到有效点，则从 active 中删除 p p p 。 Bridson 建议设置 k = 30 k = 30 k = 30 。对环面进行均匀采样的最简单方法是生成一个随机单位向量 v ⃗ ∈ R d \vec{v} \in \mathbb{R}^d v ∈ R d 和从区间 [ 1 2 d , 1 ) \left[\frac{1}{2^d}, 1\right) [ 2 d 1 ​ , 1 ) 中均匀选择的数字 x x x ，然后你的最终样本是2 r x 1 / d ⋅ v ⃗ 2rx^{1/d}\cdot\vec{v} 2 r x 1/ d ⋅ v 。几年前，我制作了一个视频来解释其原理。在二维中，选择一个单位向量相当于选择一个角度 θ ∈ [ 0 , 2 π ) \theta \in [0, 2\pi) θ ∈ [ 0 , 2 π ) 。在更高维度中，您可以对向量进行归一化，其中每个分量都是从正态分布中采样的。改进 我发现 Bridson 算法有两个简单的改进，可以大大减少生成相同数量的点所需的迭代次数。第一个适用于二维，但第二个也适用于更高维度。让我们从二维改进开始。考虑算法何时放置点 p p p，然后对其环进行采样以获得新点 q q q。我们称 p p p 为 q q q 的父级。这些点之间的关系存储了有价值的信息。当我们不可避免地对以 q q q 为中心的环面进行采样时，我们不需要考虑整个角度范围，因为它们内的点太接近 p p p 。该范围由下图中的虚线表示。虽然视觉直觉很容易掌握，但将其转化为公式是一项乏味的三角学练习。我就不讲细节了，并在没有证据的情况下声称由虚线形成的圆锥体以角度 α \alpha α 为中心，其宽度为 2 β 2\beta 2 β 其中 α = atan2 ⁡ ( p y − q y , p x − q x ) , β = min ⁡ ( arccos ⁡ ∣ p − q ∣ 2 + 3 r 2 4 r ⋅ ∣ p − q ∣ , arccos ⁡ ∣ p − q ∣ 2 r ) 。 \begin{align*} \alpha &= \operatorname{atan2}(p_y - q_y, p_x - q_x), \\ \beta &= \min\left(\arccos\frac{|p-q|^2+3r^2}{4r \cdot |p-q|}, \arccos\frac{|p-q|}{2r}\right)。 \end{align*} α β ​ = atan2 ( p y ​ − q y ​ , p x ​ − q x ​ ) , = min ( arccos 4 r ⋅ ∣ p − q ∣ ∣ p − q ∣ 2 + 3 r 2 ​ , arccos 2 r ∣ p − q ∣ ​ ) 。 ​ 这个公式唯一有趣的部分是 β \beta β 方程中出现的最小值。这说明了环面的内圆或外圆可以限制圆锥体的事实，具体取决于 p p p 和 q q q 之间的距离。我们必须选择最小值以保证圆锥体和环面的交点完全包含在圆内。注意当点之间的距离跨越 3 ⋅ r \sqrt{3} \cdot r 3 ​ ⋅ r 时，圆锥体的边界点如何从外圆跳到内圆。最小值中的第一项是与外圆的交角，第二项是与内圆的交角。实现