如何在物理模拟场景下实时索引邻近3D点并高效更新交互瓦片？

初始构建流程 #

底层采用边长等于截断距离d的3D规则网格作为锚点，天然保证所有距离小于d的粒子对必然落在同一个网格或相邻26个网格范围内，避免全量遍历。

• 先为所有粒子计算所属网格坐标，按网格ID对粒子排序，同一网格内的粒子按x坐标做稳定排序，方便后续分组。
• 每个网格内的粒子按固定Tile大小（如32）拆分成分组，仅将当前网格分组与自身、相邻27个网格的分组两两配对生成候选Tile，过滤掉大量无可能的粒子对组合。
• 对每个候选Tile的行列粒子对逐一计算距离，仅对满足distance(p1,p2) < d且p1全局ID < p2全局ID的对标记为有效，天然避免同一对被重复标记，同时满足无遗漏、无重复的要求。每个Tile额外绑定对应两个分组的网格ID、当前行列粒子的坐标边界框作为辅助数据。
• 全局维护一个Tile总列表，同时为每个粒子维护「所属Tile索引集合」的辅助结构，记录该粒子出现在哪些Tile的行/列中。

增量更新步骤 #

基于粒子每次移动距离远小于d的特性，仅处理边界变化的粒子，无需全量扫描：

• 第一步：遍历所有粒子，仅筛选出移动后网格ID发生变化的粒子，未跨网格的粒子不会产生超出原有27个网格范围的新增邻接对，无需处理。
• 第二步：对每个跨网格的粒子，从其所属的所有原有Tile中移除，对应位置的有效标记直接置为False即可，无需立刻删除Tile。
• 第三步：将跨网格的粒子分配到新网格的对应分组中，仅和新网格的27个相邻网格分组生成新的候选Tile，计算距离后标记有效对，将新Tile追加到总列表中，同步更新粒子的所属Tile索引。
• 第四步：按固定周期（或空Tile占比达到阈值时）执行轻量Tile合并：遍历所有Tile，将有效标记占比低于10%的Tile删除，把其中剩余的有效交互对合并到同网格分组的未满Tile中，仅处理低利用率Tile，无需全量重构。

额外优化点 #

• 规则网格的更新开销远低于八叉树等树状索引，每个粒子的网格归属计算仅需O(1)时间，完全匹配密度恒定、移动幅度小的场景特性。
• 距离计算仅在新增候选Tile时执行，每次更新的计算量和新增/失效的交互对数量完全成正比，无冗余计算。
• 32x32的Tile布尔数组可做位压缩存储，仅需128个32位整数即可容纳，读写和遍历效率远高于普通布尔数组。

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