均匀采样与低差异序列：从 Halton 到 Hammersley 到球面采样

均匀采样与低差异序列：从 Halton 到 Hammersley 到球面采样

在计算机图形学、3D 渲染和蒙特卡洛积分等领域，均匀采样 是一个重要的概念，直接影响结果的质量和效率。本文将深入解读如何通过 Halton 和 Hammersley 序列生成均匀采样点，并将这些采样点映射到球面，生成适合 3D 场景的均匀分布点。

1. 什么是 Halton 和 Hammersley 序列？

1.1 Halton 序列

Halton 序列 是一种低差异序列，通常用于生成多维空间中均匀分布的采样点。与伪随机采样不同，Halton 序列在采样过程中能够避免点的堆积现象，使得生成的点更加均匀。

生成 Halton 序列的核心是 基数逆序小数 的概念：

• 给定一个整数 ( n ) 和一个基数 ( b )，将 ( n ) 表示为 ( b ) 进制（如二进制、三进制等）。
• 将该 ( b ) 进制的数字逆序，并将其每一位权重按照小数点后的位置进行累加，得到一个小数值。

例如，在二进制下：

• ( n = 3 )，对应二进制 11，其逆序小数为 ( 0.1 + 0.01 = 0.75 )。

1.2 Hammersley 序列

Hammersley 序列 是 Halton 序列的扩展，通常用于采样固定数量的点。在 Hammersley 序列中，第一维直接使用 ( n / N )（( N ) 是总采样数），其余维度沿用 Halton 序列。

Hammersley 序列比 Halton 序列更高效，特别是当我们需要一个固定数量的点时。

2. 从代码看 Halton 和 Hammersley 序列

以下代码展示了如何生成 Halton 和 Hammersley 序列：

import numpy as np

PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53]

def radical_inverse(base, n):
    val = 0
    inv_base = 1.0 / base
    inv_base_n = inv_base
    while n > 0:
        digit = n % base
        val += digit * inv_base_n
        n //= base
        inv_base_n *= inv_base
    return val

def halton_sequence(dim, n):
    return [radical_inverse(PRIMES[dim], n) for dim in range(dim)]

def hammersley_sequence(dim, n, num_samples):
    return [n / num_samples] + halton_sequence(dim - 1, n)

核心函数解析：

1. radical_inverse(base, n)：

   • 实现 Halton 序列中基数逆序小数的生成。
   • 输入一个整数 ( n ) 和基数 ( b )，返回 Halton 序列在该维度的值。

2. halton_sequence(dim, n)：

   • 使用前 dim 个素数作为基数，生成 Halton 序列的一个点。

3. hammersley_sequence(dim, n, num_samples)：

   • 第一个维度直接设置为 ( n / \text{num_samples} )。
   • 其余维度使用 Halton 序列。

示例：

print(halton_sequence(2, 3))  
# 输出：例如 [0.75, 0.333...]

print(hammersley_sequence(2, 3, 10))
# 输出：例如 [0.3, 0.75]

3. 从平面采样到球面采样

为了生成 3D 场景中均匀分布的点，我们需要将 Hammersley 序列扩展到球面上。这涉及到将二维采样点映射到球面坐标系。

以下是实现代码：

def sphere_hammersley_sequence(n, num_samples, offset=(0, 0), remap=False):
    u, v = hammersley_sequence(2, n, num_samples)
    u += offset[0] / num_samples
    v += offset[1]
    if remap:
        u = 2 * u if u < 0.25 else 2 / 3 * u + 1 / 3
    theta = np.arccos(1 - 2 * u) - np.pi / 2
    phi = v * 2 * np.pi
    return [phi, theta]

映射逻辑解析：

1. u, v 的生成：

   • 使用 Hammersley 序列生成二维平面上的采样点。

2. theta 和 phi 的计算：

   • ( \theta )：极角，范围为 ([- \pi/2, \pi/2])。通过计算 ( u ) 的反余弦值映射到球面。
   • ( \phi )：方位角，范围为 ([0, 2\pi])，直接通过 ( v ) 的线性映射生成。

3. 偏移和重映射：

   • 偏移 offset 用于平移采样点的位置。
   • remap 允许对 ( u ) 进行非线性变换，使得点分布更加均匀。

4. 示例：生成球面上的采样点

以下是如何使用 sphere_hammersley_sequence 生成球面上的采样点：

for i in range(10):
    phi, theta = sphere_hammersley_sequence(i, 10)
    print(f"Point {i}: phi={phi}, theta={theta}")

5. 应用场景

1. 蒙特卡洛积分：

   • Halton 和 Hammersley 序列生成的低差异点集，适合在多维空间中进行数值积分。

2. 3D 渲染：

   • 均匀分布的球面采样点可用于光线跟踪中的采样，或环境光遮蔽（Ambient Occlusion）计算。

3. 物理模拟：

   • 在球面上生成均匀分布的采样点，可用于模拟粒子系统或散射效果。

6. 总结

本文展示了如何生成 Halton 和 Hammersley 序列，并将其扩展到球面采样。在 3D 渲染和蒙特卡洛方法中，均匀分布的采样点至关重要。这种基于低差异序列的采样方法，不仅高效，而且能显著提升结果的质量。

通过上述代码，你可以快速生成均匀分布的球面采样点，并将其应用到实际项目中。希望本文对你有所帮助！ 😊