基于相交外接球体的3D空间分箱粒子碰撞计数优化问询

你已经实现了立方体空间分箱来统计粒子碰撞，现在要切换为立方体的外接球体分箱，同时避免球体相交带来的复杂度，可以基于现有立方体分箱逻辑做以下适配优化：

1. 立方体分箱预筛选 + 球体条件二次过滤 #

保留原立方体分箱的核心逻辑，通过预筛选减少需要检查的粒子对，再用外接球条件做二次过滤，避免全量粒子遍历：

核心步骤： #

• 沿用原代码的立方体索引计算逻辑，先把所有粒子归类到对应立方体分箱中；
• 对每个粒子，除了检查同立方体内的粒子，还要遍历相邻立方体的粒子（2D是8个相邻立方体，3D是26个）——因为外接球体覆盖范围超出自身立方体，相邻立方体的粒子可能落在当前立方体的外接球内；
• 对候选粒子对，额外判断两者是否属于同一个外接球体：计算粒子到立方体中心的距离，是否小于等于外接球半径（2D半径为 (cube_size * √2)/2，3D为 (cube_size * √3)/2）。

示例代码（2D）： #

import math

cube_size = 1.0
# 2D立方体外接圆半径
sphere_radius = (cube_size * math.sqrt(2)) / 2

# 原立方体分箱索引计算逻辑
def get_cube_index(x, y):
    xi = math.floor(x / cube_size)
    yi = math.floor(y / cube_size)
    return (xi, yi)

# 存储分箱后的粒子：key为立方体索引，value为粒子列表
particle_bins = {}
for particle in all_particles:
    idx = get_cube_index(particle.x, particle.y)
    particle_bins.setdefault(idx, []).append(particle)

collision_count = 0
checked_pairs = set()  # 避免重复检查同一对粒子

for (xi, yi), current_particles in particle_bins.items():
    # 当前立方体中心坐标
    current_center = ((xi + 0.5)*cube_size, (yi + 0.5)*cube_size)
    
    # 1. 处理当前立方体内的粒子对
    for i in range(len(current_particles)):
        p1 = current_particles[i]
        dist_p1_to_current = math.hypot(p1.x - current_center[0], p1.y - current_center[1])
        if dist_p1_to_current > sphere_radius:
            continue  # p1不在当前立方体的外接球内，跳过
        for j in range(i+1, len(current_particles)):
            p2 = current_particles[j]
            dist_p2_to_current = math.hypot(p2.x - current_center[0], p2.y - current_center[1])
            if dist_p2_to_current > sphere_radius:
                continue
            # 计算碰撞概率并统计
            pair_id = tuple(sorted((p1.id, p2.id)))
            if pair_id not in checked_pairs:
                if compute_collision_prob(p1, p2) > collision_threshold:
                    collision_count += 1
                checked_pairs.add(pair_id)
    
    # 2. 处理相邻立方体的粒子对
    # 2D相邻立方体索引（8个方向）
    neighbor_indices = [
        (xi-1, yi-1), (xi-1, yi), (xi-1, yi+1),
        (xi, yi-1),                (xi, yi+1),
        (xi+1, yi-1), (xi+1, yi), (xi+1, yi+1)
    ]
    for neighbor_idx in neighbor_indices:
        if neighbor_idx not in particle_bins:
            continue
        neighbor_particles = particle_bins[neighbor_idx]
        neighbor_center = ((neighbor_idx[0] + 0.5)*cube_size, (neighbor_idx[1] + 0.5)*cube_size)
        
        for p1 in current_particles:
            # 检查p1是否在相邻立方体的外接球内
            dist_p1_to_neighbor = math.hypot(p1.x - neighbor_center[0], p1.y - neighbor_center[1])
            if dist_p1_to_neighbor > sphere_radius:
                continue
            for p2 in neighbor_particles:
                pair_id = tuple(sorted((p1.id, p2.id)))
                if pair_id in checked_pairs:
                    continue
                # 检查p2是否在相邻立方体的外接球内
                dist_p2_to_neighbor = math.hypot(p2.x - neighbor_center[0], p2.y - neighbor_center[1])
                if dist_p2_to_neighbor > sphere_radius:
                    continue
                if compute_collision_prob(p1, p2) > collision_threshold:
                    collision_count += 1
                checked_pairs.add(pair_id)

2. 扩展粒子的球体归属标记，复用分箱结构 #

基于原立方体分箱，给每个粒子额外标记它所属的外接球体（因为球体相交，一个粒子可能属于多个相邻立方体的外接球），但只需要标记当前立方体和相邻立方体的外接球（更远的球体不可能覆盖该粒子）：

• 不需要重构分箱逻辑，仅在原立方体分箱完成后，为每个粒子生成一个「所属球体索引列表」（即当前立方体索引+相邻立方体索引）；
• 统计碰撞时，按球体索引遍历粒子对，避免重复计算——同一粒子对可能出现在多个球体中，用checked_pairs集合去重即可。

3. 缩小相邻立方体遍历范围，减少无效检查 #

根据粒子在立方体内的相对位置，动态缩小需要检查的相邻立方体范围：

• 2D场景：如果粒子靠近当前立方体的右下角，那么仅需要检查右下、右、下三个方向的相邻立方体，其他方向的外接球不可能覆盖该粒子；
• 3D场景同理，根据粒子在x/y/z轴上的位置（靠近立方体的最小/最大边界），过滤掉不可能覆盖该粒子的相邻立方体，减少候选粒子对的数量。

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