流体模拟中高效遍历单个数组索引范围的优化方案

我在做3D流体模拟开发的时候，碰到了一个头疼的问题：用连续数组存储粒子时，频繁的邻域搜索操作直接拖慢了整个模拟的运行速度。试了好几种方法后，终于找到一个效果特别好的优化方案——基于立方单元格划分的粒子原地排序策略，分享给有同样需求的开发者：

核心实现逻辑 #

• 空间预划分：把整个3D粒子空间切割成等大的立方单元格（建议把单元格尺寸设置成你需要的邻域搜索半径大小，这样后续只需要遍历目标粒子所在单元格+周围26个单元格，就能覆盖所有可能的邻域粒子）
• 原地排序粒子：遍历所有粒子，计算每个粒子所属的单元格索引，然后以此为排序键对粒子数组执行原地排序。排序完成后，同一个单元格内的粒子会在数组中形成连续的区间
• 区间快速遍历：为每个单元格记录对应的数组起始索引N_begin和结束索引N_end（采用左闭右开的区间[N_begin, N_end)）。之后要访问某个单元格内的所有粒子时，直接遍历数组的这个区间即可，完全不需要再做复杂的空间距离判断

举个直观的例子：如果单元格N对应的粒子在数组中是从索引120到185的位置，那我们只需要记录N_begin=120、N_end=185，后续遍历这个单元格的粒子时，直接用for (int i = N_begin; i < N_end; i++)循环就能快速拿到所有粒子，效率拉满！

方案核心优势 #

• 内存友好：原地排序不需要额外开辟大内存存储粒子副本，对内存紧张的场景特别友好
• 性能提升显著：邻域搜索从全局遍历变成了小范围的区间遍历，粒子数量越多，性能提升越明显，完美解决大量邻域搜索的性能瓶颈

内容的提问来源于stack exchange，提问作者patatahooligan