将一维数组索引高效转换为三维坐标的教程

从一维索引到三维坐标的高效映射

在高性能计算场景，例如体素光线追踪器中，数据存储和检索的效率至关重要。将空间数据存储在字典中（如 data["4,16"]）并使用字符串作为键虽然直观，但字符串与坐标之间的转换以及字典本身的性能开销，在大规模数据处理时会成为瓶颈。将数据扁平化存储在有序数组（或列表）中，并通过数学运算将一维索引映射到多维坐标，是实现性能优化的关键策略。

二维坐标转换基础

理解三维转换之前，我们先回顾二维空间中的索引转换。对于一个宽度为 width 的二维网格，给定一个一维索引 i，其对应的 (x, y) 坐标可以这样计算：

• x 坐标是索引 i 除以 width 的余数，因为它代表了在当前行中的位置。
• y 坐标是索引 i 除以 width 的整数商，因为它代表了当前是第几行。

这可以通过以下Python函数实现：

import math

def index_vec2(i: int, width: int):
    """
    根据宽度将一维索引转换为二维 (x, y) 坐标。

    参数:
        i (int): 一维索引。
        width (int): 网格的宽度。

    返回:
        tuple: 对应的 (x, y) 坐标。
    """
    x = math.floor(i % width)
    y = math.floor(i / width)
    return x, y

例如，在一个4x4的网格中，索引3对应 (3, 0)，索引4对应 (0, 1)。这个函数只需要宽度信息，因为高度可以通过索引的范围隐式确定。

三维坐标转换的挑战

将上述逻辑扩展到三维空间时，我们需要考虑深度（z轴）。对于一个宽度为 width、高度为 height 的三维网格，给定一个一维索引 i，我们需要计算其对应的 (x, y, z) 坐标。

一个常见的错误尝试是直接将二维逻辑叠加：

def incorrect_index_vec3(i: int, width: int, height: int):
    """
    错误的将一维索引转换为三维 (x, y, z) 坐标的尝试。
    此函数中y坐标在Z层切换时不会归零。
    """
    x = math.floor(i % width)
    y = math.floor(i / width) # 这里的y计算是错误的
    z = math.floor(i / (width * height))
    return x, y, z

让我们通过一个 4x4x4 的立方体（总共64个元素）来模拟迭代，观察 incorrect_index_vec3 函数的输出：

从输出可以看出，当 z 坐标从0变为1时（即从一个 width * height 的平面切换到下一个平面），y 坐标并没有像预期的那样从0重新开始计数，而是继续递增。这是因为 y = i / width 的计算没有考虑到 z 层的边界，它将整个一维数组视为一个非常高的二维平面，导致 y 值不断累积。

纳米搜索

纳米搜索：360推出的新一代AI搜索引擎

30

查看详情

正确的三维坐标转换逻辑

为了解决 y 坐标的问题，我们需要分层计算。基本思想是：

1. 确定 Z 坐标： z 坐标表示当前元素位于第几层（平面）。每一层包含 width * height 个元素。因此，z 可以通过将一维索引 i 除以 (width * height) 的整数商来获得。
2. 确定当前层内的剩余索引： 在确定了 z 坐标后，我们需要知道当前元素在它所属的 z 层中的相对索引。这可以通过将 i 对 (width * height) 取模来获得。
3. 确定 Y 坐标： 在当前 z 层内，y 坐标表示当前元素位于第几行。每一行包含 width 个元素。因此，y 可以通过将当前层内的剩余索引除以 width 的整数商来获得。
4. 确定 X 坐标： 在当前 z 层内的当前行中，x 坐标表示当前元素位于第几列。这可以通过将当前层内的剩余索引对 width 取模来获得。

使用 divmod 函数实现

Python的 divmod(a, b) 函数非常适合这种场景，它会同时返回 a 除以 b 的整数商和余数，从而避免了重复的除法和取模运算，使代码更简洁高效。

def index_vec3(i: int, width: int, height: int):
    """
    将一维索引高效转换为三维 (x, y, z) 坐标。

    参数:
        i (int): 一维索引。
        width (int): 网格的宽度。
        height (int): 网格的高度。

    返回:
        tuple: 对应的 (x, y, z) 坐标。
    """
    # 1. 计算 z 坐标和当前 z 层内的剩余索引
    # z = i // (width * height)
    # remainder = i % (width * height)
    z, remainder = divmod(i, width * height)

    # 2. 在当前 z 层内，计算 y 坐标和当前行内的剩余索引
    # y = remainder // width
    # x = remainder % width
    y, x = divmod(remainder, width)

    return x, y, z

示例验证

让我们再次使用 4x4x4 的立方体，并使用 index_vec3 函数验证其输出：

# 模拟迭代一个 4x4x4 的立方体
width = 4
height = 4
depth = 4 # 实际上不需要深度来计算，但它定义了总大小
total_elements = width * height * depth

print("使用正确的 index_vec3 函数，4x4x4 立方体的索引映射：")
for i in range(total_elements):
    x, y, z = index_vec3(i, width, height)
    print(f"索引 {i:2d} -> ({x},{y},{z})")

部分输出如下：

...
索引 12 -> (0,3,0)
索引 13 -> (1,3,0)
索引 14 -> (2,3,0)
索引 15 -> (3,3,0)  # 第一层 (z=0) 结束
索引 16 -> (0,0,1)  # 第二层 (z=1) 开始，y 归零
索引 17 -> (1,0,1)
索引 18 -> (2,0,1)
索引 19 -> (3,0,1)
索引 20 -> (0,1,1)
索引 21 -> (1,1,1)
...
索引 31 -> (3,3,1)  # 第二层 (z=1) 结束
索引 32 -> (0,0,2)  # 第三层 (z=2) 开始，y 归零
...

可以看到，当 z 坐标增加时，y 坐标正确地从0开始计数，这符合我们的预期。

注意事项与总结

• 效率： 这种基于整数除法和取模的数学方法避免了字符串操作和字典查找的开销，提供了极高的性能。divmod 函数在底层通常被优化，进一步提升了效率。
• 内存： 将数据存储在扁平数组中通常比使用嵌套结构或字典更节省内存，尤其是在处理大量同质数据时。
• 维度扩展： 这种分层计算的思路可以很容易地扩展到N维空间。例如，对于四维空间，你可以在计算 z 之后，进一步计算 w 坐标和 w 层内的剩余索引，然后重复 y 和 x 的计算。
• 坐标系约定： 本文的坐标系约定为X轴最快变化，Y轴次之，Z轴最慢。如果你的数据存储顺序不同（例如，Y轴最快变化），则需要相应调整计算公式。

通过掌握这种一维索引到多维坐标的映射技术，开发者可以构建出更高效、更节省资源的计算系统，这在游戏开发、科学模拟和高性能图形渲染等领域具有重要意义。

以上就是将一维数组索引高效转换为三维坐标的教程的详细内容，更多请关注php中文网其它相关文章！