快速nbody算法/解決方案（用OpenGL/C++ /？）

我工作的一個（C++，OpenGL的）項目中，我需要有很多的顆粒，其影響海誓山盟，如果我是正確的，這是被稱爲人身問題。有人知道這樣的算法有什麼解決方案。快速nbody算法/解決方案（用OpenGL/C++ /？）

我知道巴恩斯小屋算法，也許我可以窺視周圍的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) {....} 
    } 
}

親切的問候，北河三

來源

2010-07-28 pollux

Kd-trees非常適合在最大距離發現的所有對象（在這種情況下，顆粒）。如果樹是平衡的，查找ups是O(log n)。

來源

2010-07-28 20:02:25 Staffan

Thanks Staffan！你也許知道一些關於這樣的數據結構的好書嗎？ – pollux 2010-07-28 20:47:22

查覈[計算幾何]（http://www.amazon.com/Computational-Geometry-Applications-Mark-Berg/dp/3642096816/ref=sr_1_1?ie=UTF8&s=books&qid=1280350460&sr=8-1）由Mark de Berg等人這是計算幾何的一個很好的介紹，有Kd-trees，quadtrees和delaunay三角剖分等。您可以瀏覽亞馬遜的TOC。 – Staffan 2010-07-28 20:57:55

這是像Octrees數據結構派上用場。他們可以將您的O(N^2)環路減少到O(N*log(N))，但會損失一點精度。

來源

2010-07-28 19:58:59

如果您想有很多非常簡單的身體龐大的計算能力 - 讓感興趣的NVIDIA CUDA，做您的GPU着色單元工作。這可以給你更多的表現甚至比較四核CPU多線程處理

來源

2010-07-28 20:01:19

你去那裏：GPU Gems 3。它在CUDA中，但很容易移植到openCL。

然而，這個版本計算N²/ 2交互，你可能不想要。

來源

2010-07-29 07:54:40 Calvin1602

由4x4像素框劃分1024x512像素區域，爲每個盒子中的粒子分配15個單元，其中12k個粒子僅具有排除力計算，對於英特爾HD-400（12個計算單元不超過8ms，通過opencl API）：

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肯定會提高速度。沒有分區，蠻力耗時44ms，這對於具有單通道慢速內存的低端集成GPU來說並不壞。

而且使用第二CPU的同時，幫助大約爲0.5ms - 爲0.1ms但由於在背景內存爲bottlneck。

來源

2017-03-19 18:34:19

快速nbody算法/解決方案（用OpenGL/C++ /？）

回答

相關問題