游戏Octree导航故障：Morton Code节点插入位置错误求助

游戏开发中使用Octree并采用Morton Code（Z序）实现导航功能，但节点始终被插入到错误位置，无法定位问题根源。更换过基于查找表的Morton Code实现、改用非Morton的插入方法，问题依然存在。以下是关键代码片段及排查记录，请求技术协助：

关键代码片段 #

1. Morton支持数组初始化与映射表构建 #

static Utils()
{
    thresholds[0] = Consts.Lod0Range;
    for (int i = 1; i <= Consts.MaxLod; i++)
        thresholds[i] = thresholds[i - 1] * 2f;
    for (int i = 0; i < 3; i++)
    {
        morton256[i] = new uint[256];
        for (uint j = 0; j < 256; j++)
            morton256[i][j] = SpreadBits(j, i);
    }
    for (int x = 0; x < 2; x++)
        for (int y = 0; y < 2; y++)
            for (int z = 0; z < 2; z++)
                MortonMapping[x * 4 + y * 2 + z] = (int)(MortonEncode(new Vector3Int(x, y, z)) & 0b111);
}

private static uint SpreadBits(uint x, int offset)
{
    uint result = 0;
    for (int i = 0; i < 8; i++)
    {
        result <<= 3;
        result |= ((x >> (7 - i)) & 1) << offset;
    }
    return result;
}

2. Morton编码实现 #

public static ulong MortonEncode(Vector3Int vector)
{
    if (vector.x < 0 || vector.y < 0 || vector.z < 0)
        throw new System.Exception("Negative morton");
    ulong answer =
    morton256[0][(vector.x >> 16) & 0xFF] |
    morton256[1][(vector.y >> 16) & 0xFF] |
    morton256[2][(vector.z >> 16) & 0xFF];
    answer = answer << 24 |
    morton256[0][(vector.x >> 8) & 0xFF] |
    morton256[1][(vector.y >> 8) & 0xFF] |
    morton256[2][(vector.z >> 8) & 0xFF];
    answer = answer << 24 |
    morton256[0][(vector.x) & 0xFF] |
    morton256[1][(vector.y) & 0xFF] |
    morton256[2][(vector.z) & 0xFF];
    return answer;
}

3. 从Morton Code获取指定层级的子节点本地索引 #

[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int MortonIndexForLevel(int level, ulong mortonIndex)
{
    return (int)(mortonIndex >> (level * 3)) & 0b111;
}

4. 从索引转换为子节点相对父节点的本地位置 #

[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static Vector3Int FlatIndexToVector(int realIdx)
{
    return new Vector3Int((realIdx & 4) >> 2, (realIdx & 2) >> 1, realIdx & 1);
}

5. 递归插入逻辑（初始版本） #

//coords are relative to world 0,0,0 measured in smallest possible node size
public void Insert(byte lod, Vector3Int coords, NativeArray<ushort> data)
{
    EnsureSpace(coords);
    Chunk chunk = !data.IsCreated ? null : new Chunk(data);
    ulong idx = Utils.MortonEncode(coords - beginCorner); //Substract beginCorner of octree in order to localize coords

    //Debug section, no logic here
    Vector3 center = FromGlobalCoords(coords) + Vector3.one * (1 << lod) * lod0ChunkSize / 2;
    Debug.DrawLine(lastPos, center, Color.white, 4000000, false);
    lastPos = center;
    Debug.Log("Insert " + _root.Lod + ", " + lod + ", " + idx + " at: " + coords + ", " + (coords - beginCorner) + ", " + FromGlobalCoords(coords) + ", " + beginCorner + ", " + (chunk == null ? "empty" : "ok"));
    Debug.Log(Utils.ToMortonString(idx));

    InsertRecursive(_root, new Node(lod, chunk), idx, beginCorner, FromGlobalCoords(beginCorner));
}

private void InsertRecursive(Node parent, Node value, ulong idx, /*debug param*/ Vector3Int coords, /*debug param*/ Vector3 lastCenter)
{
    byte lod = (byte)(parent.Lod - 1);
    int curIdx = Utils.MortonIndexForLevel(lod, idx);

    //Debug section, no logic here
    Vector3Int localCoords = Utils.FlatIndexToVector(Utils.MortonMapping[curIdx]);
    coords += localCoords * (1 << lod);
    Vector3 center = FromGlobalCoords(coords) + Vector3.one * (1 << lod) * lod0ChunkSize / 2;
    if (idx == 12582911)
    {
        Debug.Log("Go down: " + parent.Lod + ", " + localCoords + ", " + coords + ", " + center + ", " + FromGlobalCoords(coords));
        Debug.DrawLine(lastCenter, center, Color.Lerp(Color.green, Color.blue, lod / 10f), 4000000, false);
    }

    if (lod == value.Lod)
    {
        parent[curIdx] = value;
        return;
    }
    if (parent[curIdx] == null)
        parent[curIdx] = new Node(lod);
    InsertRecursive(parent[curIdx], value, idx, coords, center);
}

调试截图 #

白色线条为服务器端Octree按Z序发送的数据接收顺序的真实位置：

排查记录 #

编辑1：更换Morton Code实现 #

测试了基于查找表（LUT）的Morton Code实现，问题仍未解决。

编辑2：改用非Morton的插入方法 #

更换插入逻辑，直接通过坐标比较确定子节点索引，问题依然存在：

public void Insert(byte lod, Vector3Int coords, NativeArray<ushort> data)
{
    EnsureSpace(coords);
    Chunk chunk = !data.IsCreated ? null : new Chunk(data);
    ulong idx = Utils.MortonEncode(coords - beginCorner); //Substract beginCorner of octree in order to localize coords

    //Debug section, no logic here
    Vector3 center = FromGlobalCoords(coords) + Vector3.one * (1 << lod) * lod0ChunkSize / 2;
    Debug.DrawLine(lastPos, center, Color.white, 4000000, false);
    lastPos = center;
    Debug.Log("Insert " + _root.Lod + ", " + lod + ", " + idx + " at: " + coords + ", " + (coords - beginCorner) + ", " + FromGlobalCoords(coords) + ", " + beginCorner + ", " + (chunk == null ? "empty" : "ok"));
    Debug.Log(Utils.ToMortonString(idx));

    InsertRecursive(_root, new Node(lod, chunk), idx, Vector3Int.zero, coords - beginCorner);
}

private void InsertRecursive(Node parent, Node value, ulong idx, Vector3Int parentCorner, Vector3Int coords)
{
    byte lod = (byte)(parent.Lod - 1);
    int curIdx = Utils.MortonIndexForLevel(lod, idx);

    Vector3Int parentCenter = parentCorner + Vector3Int.one * (1 << lod);
    int index = 0;
    if (coords.x >= parentCenter.x)
        index |= 4;
    if (coords.y >= parentCenter.y)
        index |= 2;
    if (coords.z >= parentCenter.z)
        index |= 1;

    Debug.Log("Indexes: " + index + ", " + curIdx + "\n" + Convert.ToString(index, 2).PadLeft(3, '0') + "\n" + Convert.ToString(curIdx, 2).PadLeft(3, '0'));

    if (lod == value.Lod)
    {
        parent[index] = value;
        return;
    }
    if (parent[index] == null)
        parent[index] = new Node(lod);
    InsertRecursive(parent[index], value, idx, parentCorner + Utils.FlatIndexToVector(index) * (1 << lod), coords);
}

内容的提问来源于stack exchange，提问作者Robert Ostrowski-Jagoda