Fast nbody algorithms / solutions (with opengl/c++/??)

Question

Dear reader,

I'm working on a (c++, opengl) project where I need to have lots of particles which influence eachother, if I'm correct this is called a nbody problem. Does someone knows what solutions there are for algorithms like this.

I know the barnes hut algorithm and maybe I can peek around openCL, though I'm not just wondering if you maybe used other solutions.

The code which I'll create will have lots of:

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) {....}
  }
}

Kind regards, Pollux

Answer 1

This is where data structures like Octrees come in handy. They can reduce your O(N^2) loops to O(N*log(N)), at the expense of losing a tiny bit of accuracy.

Answer 2

If you want to have a HUGE computation power on lot of quite simple bodies - get interested in nvidia CUDA and doing your work on GPU shader units. This can give you more performance even comparing to quad-core CPUs with multithreading

Answer 3

Kd-trees are ideal for finding all objects (particles in this case) at a maximum distance. If the tree is balanced look ups are O(log n).

Answer 4

There you go : GPU Gems 3. It's in CUDA, but easily portable to openCL.

However, this version computes the N²/2 interactions, which you maybe don't want.