快速 nbody 算法/解决方案（使用 OpenGL/C++/??）

Question

我正在从事一个（C ++，OpenGL）项目，在这个项目中，我需要有大量的粒子相互影响，如果我没错的话，这被称为nbody问题。有人知道如何解决这样的算法吗？

我知道Barnes-Hut算法，也许我可以研究一下OpenCL，但我想知道您是否使用其他解决方案。

我将创建的代码将会有很多：

for(int i = 0; i < num_particles; ++i) {
  for(int j = i+1, j < num_particles; ++j)
     dist = distance(particles[i],particles[j]);
     if(dist > limit) {....}
  }
}

亲切的问候， Pollux

- pollux

Answer 1

这就是数据结构，如八叉树派上用场的地方。它们可以将O(N^2)循环减少到O(N*log(N))，代价是失去了一点精度。

- Justin Ardini

Answer 2

Kd树非常适合查找最大距离内的所有对象（在此情况下为粒子）。如果树是平衡的，查找的时间复杂度为O(log n)。

- Staffan

---

谢谢Staffan！您是否知道一些关于这样数据结构的好书籍？ - pollux

查看Mark de Berg等人的《计算几何》（Computational Geometry）[http://www.amazon.com/Computational-Geometry-Applications-Mark-Berg/dp/3642096816/ref=sr_1_1?ie=UTF8&s=books&qid=1280350460&sr=8-1]。这是一本很好的介绍计算几何的书，内容包括Kd树、四叉树和Delaunay三角剖分等。您可以在亚马逊上浏览目录。 - Staffan

Answer 3

如果你想在许多相对简单的体上拥有巨大的计算能力，那么就要了解nvidia CUDA并在GPU着色器单元上进行工作。这可以比使用支持多线程的四核CPU获得更高的性能。

- Piotr Müller

Answer 4

这里有一个链接：GPU Gems 3。它是用CUDA编写的，但很容易移植到openCL。

然而，这个版本计算了N²/2次相互作用，这可能不是你想要的。

- Calvin1602

Answer 5

将1024x512像素区域按4x4像素盒进行划分，为每个盒子分配15个粒子单元，仅计算排斥力的12k粒子，对于Intel HD-400（具有12个计算单元，通过opencl api）而言，不超过8ms即可完成：

for(each particle) // this part unfolded on N workitems of opencl
for(each neighboring box) {       
     for(each particle in selected box)
     {
         dist = distance(particles[i],particles[j]);
         if(dist < limit) {/* sqrt, mult, div, add, sub */}
      }
}

因此，空间划分和使用OpenCL可以显著提高速度。如果不进行划分，暴力算法需要44毫秒，这对于低端集成GPU和单通道慢速内存来说已经不错了。

同时，与第二个CPU并行使用可以帮助减少0.5毫秒至0.1毫秒的时间，但由于内存在后台成为瓶颈，效果有限。

- huseyin tugrul buyukisik