從一維索引到三維坐標(biāo)的高效映射

在高性能計算場景，例如體素光線追蹤器中，數(shù)據(jù)存儲和檢索的效率至關(guān)重要。將空間數(shù)據(jù)存儲在字典中（如 data["4,16"]）并使用字符串作為鍵雖然直觀，但字符串與坐標(biāo)之間的轉(zhuǎn)換以及字典本身的性能開銷，在大規(guī)模數(shù)據(jù)處理時會成為瓶頸。將數(shù)據(jù)扁平化存儲在有序數(shù)組（或列表）中，并通過數(shù)學(xué)運(yùn)算將一維索引映射到多維坐標(biāo)，是實(shí)現(xiàn)性能優(yōu)化的關(guān)鍵策略。

二維坐標(biāo)轉(zhuǎn)換基礎(chǔ)

理解三維轉(zhuǎn)換之前，我們先回顧二維空間中的索引轉(zhuǎn)換。對于一個寬度為 width 的二維網(wǎng)格，給定一個一維索引 i，其對應(yīng)的 (x, y) 坐標(biāo)可以這樣計算：

• x 坐標(biāo)是索引 i 除以 width 的余數(shù)，因?yàn)樗砹嗽诋?dāng)前行中的位置。
• y 坐標(biāo)是索引 i 除以 width 的整數(shù)商，因?yàn)樗砹水?dāng)前是第幾行。

這可以通過以下Python函數(shù)實(shí)現(xiàn)：

import math

def index_vec2(i: int, width: int):
    """
    根據(jù)寬度將一維索引轉(zhuǎn)換為二維 (x, y) 坐標(biāo)。

    參數(shù):
        i (int): 一維索引。
        width (int): 網(wǎng)格的寬度。

    返回:
        tuple: 對應(yīng)的 (x, y) 坐標(biāo)。
    """
    x = math.floor(i % width)
    y = math.floor(i / width)
    return x, y

例如，在一個4x4的網(wǎng)格中，索引3對應(yīng) (3, 0)，索引4對應(yīng) (0, 1)。這個函數(shù)只需要寬度信息，因?yàn)楦叨瓤梢酝ㄟ^索引的范圍隱式確定。

三維坐標(biāo)轉(zhuǎn)換的挑戰(zhàn)

將上述邏輯擴(kuò)展到三維空間時，我們需要考慮深度（z軸）。對于一個寬度為 width、高度為 height 的三維網(wǎng)格，給定一個一維索引 i，我們需要計算其對應(yīng)的 (x, y, z) 坐標(biāo)。

一個常見的錯誤嘗試是直接將二維邏輯疊加：

def incorrect_index_vec3(i: int, width: int, height: int):
    """
    錯誤的將一維索引轉(zhuǎn)換為三維 (x, y, z) 坐標(biāo)的嘗試。
    此函數(shù)中y坐標(biāo)在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 函數(shù)的輸出：

從輸出可以看出，當(dāng) z 坐標(biāo)從0變?yōu)?時（即從一個 width * height 的平面切換到下一個平面），y 坐標(biāo)并沒有像預(yù)期的那樣從0重新開始計數(shù)，而是繼續(xù)遞增。這是因?yàn)?y = i / width 的計算沒有考慮到 z 層的邊界，它將整個一維數(shù)組視為一個非常高的二維平面，導(dǎo)致 y 值不斷累積。

四維時代AI開放平臺

四維時代AI開放平臺

66

查看詳情

正確的三維坐標(biāo)轉(zhuǎn)換邏輯

為了解決 y 坐標(biāo)的問題，我們需要分層計算?；舅枷胧牵?/p>

1. 確定 Z 坐標(biāo)： z 坐標(biāo)表示當(dāng)前元素位于第幾層（平面）。每一層包含 width * height 個元素。因此，z 可以通過將一維索引 i 除以 (width * height) 的整數(shù)商來獲得。
2. 確定當(dāng)前層內(nèi)的剩余索引： 在確定了 z 坐標(biāo)后，我們需要知道當(dāng)前元素在它所屬的 z 層中的相對索引。這可以通過將 i 對 (width * height) 取模來獲得。
3. 確定 Y 坐標(biāo)： 在當(dāng)前 z 層內(nèi)，y 坐標(biāo)表示當(dāng)前元素位于第幾行。每一行包含 width 個元素。因此，y 可以通過將當(dāng)前層內(nèi)的剩余索引除以 width 的整數(shù)商來獲得。
4. 確定 X 坐標(biāo)： 在當(dāng)前 z 層內(nèi)的當(dāng)前行中，x 坐標(biāo)表示當(dāng)前元素位于第幾列。這可以通過將當(dāng)前層內(nèi)的剩余索引對 width 取模來獲得。

使用 divmod 函數(shù)實(shí)現(xiàn)

Python的 divmod(a, b) 函數(shù)非常適合這種場景，它會同時返回 a 除以 b 的整數(shù)商和余數(shù)，從而避免了重復(fù)的除法和取模運(yùn)算，使代碼更簡潔高效。

def index_vec3(i: int, width: int, height: int):
    """
    將一維索引高效轉(zhuǎn)換為三維 (x, y, z) 坐標(biāo)。

    參數(shù):
        i (int): 一維索引。
        width (int): 網(wǎng)格的寬度。
        height (int): 網(wǎng)格的高度。

    返回:
        tuple: 對應(yīng)的 (x, y, z) 坐標(biāo)。
    """
    # 1. 計算 z 坐標(biāo)和當(dāng)前 z 層內(nèi)的剩余索引
    # z = i // (width * height)
    # remainder = i % (width * height)
    z, remainder = divmod(i, width * height)

    # 2. 在當(dāng)前 z 層內(nèi)，計算 y 坐標(biāo)和當(dāng)前行內(nèi)的剩余索引
    # y = remainder // width
    # x = remainder % width
    y, x = divmod(remainder, width)

    return x, y, z

示例驗(yàn)證

讓我們再次使用 4x4x4 的立方體，并使用 index_vec3 函數(shù)驗(yàn)證其輸出：

# 模擬迭代一個 4x4x4 的立方體
width = 4
height = 4
depth = 4 # 實(shí)際上不需要深度來計算，但它定義了總大小
total_elements = width * height * depth

print("使用正確的 index_vec3 函數(shù)，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) 結(jié)束
索引 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) 結(jié)束
索引 32 -> (0,0,2)  # 第三層 (z=2) 開始，y 歸零
...

可以看到，當(dāng) z 坐標(biāo)增加時，y 坐標(biāo)正確地從0開始計數(shù)，這符合我們的預(yù)期。

注意事項與總結(jié)

• 效率： 這種基于整數(shù)除法和取模的數(shù)學(xué)方法避免了字符串操作和字典查找的開銷，提供了極高的性能。divmod 函數(shù)在底層通常被優(yōu)化，進(jìn)一步提升了效率。
• 內(nèi)存： 將數(shù)據(jù)存儲在扁平數(shù)組中通常比使用嵌套結(jié)構(gòu)或字典更節(jié)省內(nèi)存，尤其是在處理大量同質(zhì)數(shù)據(jù)時。
• 維度擴(kuò)展： 這種分層計算的思路可以很容易地擴(kuò)展到N維空間。例如，對于四維空間，你可以在計算 z 之后，進(jìn)一步計算 w 坐標(biāo)和 w 層內(nèi)的剩余索引，然后重復(fù) y 和 x 的計算。
• 坐標(biāo)系約定： 本文的坐標(biāo)系約定為X軸最快變化，Y軸次之，Z軸最慢。如果你的數(shù)據(jù)存儲順序不同（例如，Y軸最快變化），則需要相應(yīng)調(diào)整計算公式。

通過掌握這種一維索引到多維坐標(biāo)的映射技術(shù)，開發(fā)者可以構(gòu)建出更高效、更節(jié)省資源的計算系統(tǒng)，這在游戲開發(fā)、科學(xué)模擬和高性能圖形渲染等領(lǐng)域具有重要意義。

以上就是將一維數(shù)組索引高效轉(zhuǎn)換為三維坐標(biāo)的教程的詳細(xì)內(nèi)容，更多請關(guān)注php中文網(wǎng)其它相關(guān)文章！