算法详解
N-Body 粒子仿真系统中使用的力计算算法和积分方法的详细说明
算法详解
N-Body 粒子仿真系统中使用的力计算算法和积分方法的详细说明。
📑 目录
力计算基础
牛顿万有引力定律
两个粒子之间的引力：F = G × m₁ × m₂ / r²
软化参数
为防止近距离相遇时的数值发散，引入软化参数 ε：
- 防止力奇异
- 模拟有限大小粒子
- 平滑近距离相互作用
Direct N² 算法
原理
直接计算所有粒子对之间的力。保证精确但 O(N²) 复杂度。
性能特点
| 方面 | 值 |
|---|---|
| 复杂度 | O(N²) |
| 内存 | O(N) |
| 精度 | 精确 |
| 适用 | N < 50,000 |
Barnes-Hut 算法
原理
使用八叉树将远距离粒子簇近似为单个质点。复杂度降至 O(N log N)。
开角判据
θ = s / d（节点边长 / 粒子到节点质心的距离）
| θ | 精度 | 速度 | 适用场景 |
|---|---|---|---|
| 0.3 | 高 | 慢 | 科学计算 |
| 0.5 | 中 | 中 | 通用 |
| 0.8 | 低 | 快 | 预览 |
性能特点
| 方面 | 值 |
|---|---|
| 复杂度 | O(N log N) |
| 精度 | 可通过 θ 配置 |
| 适用 | N > 50,000，长程力 |
Spatial Hash 算法
原理
将空间划分为均匀网格单元。粒子只与相邻单元中的其他粒子相互作用。短程力 O(N)。
性能特点
| 方面 | 值 |
|---|---|
| 复杂度 | O(N)（均匀分布） |
| 精度 | 截断范围内精确 |
| 适用 | 短程力，分子动力学 |
Velocity Verlet 积分
原理
辛积分器，长期保持能量守恒。二阶精度，每步单次力计算。
为什么选择 Velocity Verlet？
| 积分器 | 阶数 | 能量守恒 | 力计算次数 |
|---|---|---|---|
| Euler | 1 | 差 | 1 |
| Leapfrog | 2 | 好 | 1 |
| Velocity Verlet | 2 | 优秀 | 1 |
| RK4 | 4 | 一般 | 4 |
算法选择指南
决策流程
- N < 10,000：Direct N²（最简单，精确）
- 10,000 ≤ N < 100,000：Barnes-Hut，θ=0.5（平衡）
- N ≥ 100,000：
- 长程力（引力）→ Barnes-Hut，θ=0.7
- 短程力（分子）→ Spatial Hash
性能对比
| 粒子数 | Direct N² | Barnes-Hut | Spatial Hash |
|---|---|---|---|
| 1万 | 10 ms | 2 ms | 0.5 ms |
| 10万 | 1000 ms | 15 ms | 5 ms |
| 100万 | 100s | 200 ms | 50 ms |
NVIDIA RTX 3080 上的计时