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

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]);
开发者_如何学Go     if(dist > limit) {....}
  }
}

Kind regards, Pollux

---

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

---

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.

---

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

---

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.

---

Division of 1024x512 pixel area by 4x4 pixel boxes, allocating 15 cells for particles in each box, having 12k particles with only exclusion forces to compute, took no more than 8ms for an Intel HD-400 (has 12 compute units, via opencl api) for:

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 */}
      }
}

so space partitioning and using opencl certainly increases speed. Without partitioning, brute-force took 44ms which isn't bad for a low-end integrated-gpu with single channel slow memory.

Also using a second the cpu concurrently, helps about 0.5ms - 0.1ms but because of memory being bottlneck in background.