如何高效检测移动3D位置进入固定尺寸的新区块？

我用Pygame编写了一个基于CPU的光线追踪引擎，它通过让光线每次循环沿速度方向移动1单位，检测整数位置的体素。最近我添加了区块（chunk）来提升性能，每个固定尺寸区域内的体素存储在一个容器中，优先读取该容器。例如：若区块大小为16，位置(0, -16, 32)的区块会存储从该位置到(16, 0, 48)的所有数据。有效区块存储在以起始角元组为索引的字典中，结束角可通过加上区块大小得到。数据结构示例如下：

chunks = {
    (0, 0, 0): None,
    (64, 0, 32): None,
    (-96, 48, 16): None,
    (-128, -96, 0): None,
}

我发现区块扫描的开销过大，大部分卡顿源于位置检查与对齐到区块大小以获取对应索引：光线每次移动时，我需检查它是否进入了另一个区块并获取其数据。例如，若光线以速度(1, 1, 1)从位置(-0.5, 0.25, 0)移动到(0.5, 1.25, 1)，现在需要获取区块(0, 0, 0)的数据。目前光线循环的代码示例：

pos = (0, 0, 0)
chunk_min = (0, 0, 0)
chunk_max = (0, 0, 0)
chunk_size = 16
chunk = None
while True:
    if pos[0] < chunk_min[0] or pos[1] < chunk_min[1] or pos[2] < chunk_min[2] or pos[0] > chunk_max[0] or pos[1] > chunk_max[1] or pos[2] > chunk_max[2]:
        pos_min = ((self[0] // chunk_size) * chunk_size, (self[1] // chunk_size) * chunk_size, (self[2] // chunk_size) * chunk_size)
        pos_max = (pos_min[0] + chunk_size, pos_min[1] + chunk_size, pos_min[2] + chunk_size)
        chunk = chunks[pos_min] if pos_min in chunks else None

    # Do things with the data in chunk, advance pos by -1 or +1 on at least one axis, and break out of the loop when tracing is over

该循环每像素运行数十次，总计数千次，每次检查必须非常高效，否则FPS会大幅下降。我通过缓存上一个区块的边界，仅在光线位置超出边界时切换区块，获得了一定性能提升，但边界检查本身仍有开销，位置对齐到区块大小的操作开销更大。请问如何以最优方式实现？检测位置进入新立方体区域的最低开销操作是什么？

1. 位运算替代除法乘法（区块大小为2的幂时） #

如果区块大小是2的整数次幂（比如16=2^4），用位运算计算区块起始位置的速度远快于整数除法和乘法：

chunk_size = 16
chunk_shift = 4  # 等于log2(chunk_size)，16对应4

# 计算当前位置对应的区块起始坐标
x, y, z = pos
new_chunk_idx = (
    (int(x) >> chunk_shift) << chunk_shift,
    (int(y) >> chunk_shift) << chunk_shift,
    (int(z) >> chunk_shift) << chunk_shift
)

Python中负数的位运算会保留符号，比如(-1 >> 4)结果为-1，左移4位后得到-16，正好符合负坐标区块的起始位置要求。

2. 简化区块切换逻辑 #

放弃多条件的边界检查，直接对比当前位置的区块索引与上一次的索引是否一致：

x, y, z = 0.0, 0.0, 0.0
chunk_size = 16
chunk_shift = 4
current_chunk_idx = None
chunk = None

while True:
    # 计算当前位置的区块索引
    new_chunk_idx = (
        (int(x) >> chunk_shift) << chunk_shift,
        (int(y) >> chunk_shift) << chunk_shift,
        (int(z) >> chunk_shift) << chunk_shift
    )
    # 仅当索引变化时才切换区块
    if new_chunk_idx != current_chunk_idx:
        current_chunk_idx = new_chunk_idx
        chunk = chunks.get(new_chunk_idx, None)
    
    # 处理体素、移动pos等逻辑
    # ...

这种方式把6次边界比较简化为1次元组对比，开销显著降低。

3. 预计算区块跨越点，减少检查次数 #

不要每移动1单位就检查一次，而是计算光线到达下一个区块边界的时间，一次性移动到边界处：

x, y, z = pos
dir_x, dir_y, dir_z = dir  # 单位化后的光线方向向量
chunk_size = 16
chunk_shift = 4

# 初始化当前区块
current_chunk_idx = (
    (int(x) >> chunk_shift) << chunk_shift,
    (int(y) >> chunk_shift) << chunk_shift,
    (int(z) >> chunk_shift) << chunk_shift
)
chunk = chunks.get(current_chunk_idx, None)

while True:
    cx_min, cy_min, cz_min = current_chunk_idx
    cx_max = cx_min + chunk_size
    cy_max = cy_min + chunk_size
    cz_max = cz_min + chunk_size

    # 计算到达各轴区块边界的时间
    t_x = (cx_max - x)/dir_x if dir_x > 0 else (cx_min - x)/dir_x if dir_x < 0 else float('inf')
    t_y = (cy_max - y)/dir_y if dir_y > 0 else (cy_min - y)/dir_y if dir_y < 0 else float('inf')
    t_z = (cz_max - z)/dir_z if dir_z > 0 else (cz_min - z)/dir_z if dir_z < 0 else float('inf')

    # 移动到最近的边界
    t_min = min(t_x, t_y, t_z)
    x += dir_x * t_min
    y += dir_y * t_min
    z += dir_z * t_min

    # 更新区块
    current_chunk_idx = (
        (int(x) >> chunk_shift) << chunk_shift,
        (int(y) >> chunk_shift) << chunk_shift,
        (int(z) >> chunk_shift) << chunk_shift
    )
    chunk = chunks.get(current_chunk_idx, None)

    # 终止条件判断
    # ...

这种方法把区块检查从每步一次变为每次跨区块一次，大幅减少总检查次数，适合长距离追踪的光线。

4. 用单独变量替代元组访问 #

元组的索引访问速度慢于单独变量，把pos、current_chunk_idx拆成独立变量：

# 替代 pos = (x, y, z)
x, y, z = 0.0, 0.0, 0.0
# 替代 current_chunk_idx = (cx, cy, cz)
cx, cy, cz = 0, 0, 0

直接使用x、y、z比pos[0]、pos[1]、pos[2]的访问效率更高。

5. 缓存区块查找结果 #

用LRU缓存存储最近访问的区块，避免重复从字典中查找：

from functools import lru_cache

@lru_cache(maxsize=64)
def get_chunk(chunk_idx):
    return chunks.get(chunk_idx, None)

# 循环中使用
chunk = get_chunk(new_chunk_idx)

缓存能降低字典查找的开销，尤其适合光线频繁在少量区块间移动的场景。

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