CUDA particles 算例文档的内容

难点主要在于粒子之间的作用力是局部的，如何避免不必要的计算。

1. 空间划分：需要矩形网格划分，用于邻近粒子搜索。
2. 每个网格中央的粒子需要处理3*3*3个网格，每个粒子都与一个网格绑定。

用原子操作生成网格

方法一：

网格包含两个数组（假设了每个单元包含粒子数的最大值）

• gridCounters: 存储每个单元中粒子的数量。
• gridCells：存储每个粒子的索引。

一个核函数

• updateGrid：更新网格数据，每个粒子占用一个线程，将自己的索引写入对应的单元。

注：如果我们不确定每个网格单元会有多少粒子，那么我们可以先遍历一遍，计算出粒子数，然后再遍历一遍粒子，将粒子的索引写入对应数组。算例scan能算出索引。

方法二

不需要原子操作的算法。

两个数组
particleHash
cellStart

两个核函数
calcHash
findCellStart

1. 通过calcHash算出一个粒子的Hash值，哈希值对应着一个单元。
2. 将粒子的哈希值存储在particleHash数组中，数组中的元素是一个二元组：(单元哈希，粒子索引)。
3. 通过哈希排序将particleHash数组排序。(排序方法：CUDPP中的fast radix sort方法)
4. 通过函数findCellStart查找那些网格单元是有粒子分布的。
5. 为了增强粒子的连续性，将进行计算

其他方法：KNN(暴力求解)，kd-tree(d叉树)