将八叉树转换为数组时如何正确分配索引？

Question

我正在尝试将一个八叉树展平成一个数组，以便我可以将它传递给 GPU。我想从我的八叉树中获取数据，将其加载到 Voxel 结构的向量中，然后将其发送到 GPU。我在开始时将 2 个体素插入到八叉树中。这些是我的插入函数：

template<typename T>
Octree<T>::Octree(glm::vec3 position, float octreeSize, int depth) : root(position, 1.0f), depth(depth), octreeSize(octreeSize), transform(1.0f)
{
    insert(glm::vec3(0.5, 0.1, 0.7f), true);
    insert(glm::vec3(-0.5, -0.1, -0.7f), true);
    transform = glm::translate(transform, glm::vec3(0, 0, 5));
}

template<typename T>
void Octree<T>::insert(glm::vec3 pos, T data)
{
    root.subdivide(pos, data, depth, 1.0f);
}

template<typename T>
int Octree<T>::Node::getIndexOfPosition(glm::vec3 lookupPosition, glm::vec3 nodePosition) const
{
    int index = 0;
    index |= lookupPosition.y > nodePosition.y ? 4 : 0;
    index |= lookupPosition.x > nodePosition.x ? 2 : 0;
    index |= lookupPosition.z > nodePosition.z ? 1 : 0;

    return index;
}


template<typename T>
void Octree<T>::Node:: subdivide(glm::vec3 targetPos, T value, int divDepth, float parentSize)
{
    int subdivIndex = getIndexOfPosition(targetPos, position);
    if(children.empty())
    {
        for(int i = 0; i < 8; i++)
        {
            glm::vec3 newPos = position;
            float sizeModifier = parentSize * 0.5f;
            if ((i & 4) == 4)
                newPos.y += sizeModifier;
            else
                newPos.y -= sizeModifier;

            if ((i & 2) == 2)
                newPos.x += sizeModifier;
            else
                newPos.x -= sizeModifier;

            if ((i & 1) == 1)
                newPos.z += sizeModifier;
            else
                newPos.z -= sizeModifier;
            Node newNode(newPos, sizeModifier);
            children.push_back(newNode);
        }
    }

    if (divDepth > 0)
    {
        //std::cout << "Subdividing" << std::endl;
        children[subdivIndex].subdivide(targetPos, value, divDepth - 1, parentSize*0.5f);
    }
    else
    {
        children[subdivIndex].data = value;
    }
}

我的体素结构：

struct Voxel
{
    Voxel(): pIndex(-1), index(-1), pos(90000.f), col(0.f) { for (int & i : cIdx) i = -1; }
    int cIdx[8]; // The indexes of the child nodes in the vector
    int index;   // The current index of this voxel within the vector
    int pIndex;
    glm::vec4 pos;
    glm::vec4 col;
};

目前我正在按预定顺序遍历我的八叉树，我递归地遍历每个子节点（如果有的话），将当前体素子索引设置为当前索引，然后对所有子节点执行相同操作.最后，一旦我们位于树的底部或者我们没有子节点，将该节点推送到 GPU 并将子节点的父索引设置为当前索引。这是我的功能：

template<typename T>
int
Octree<T>::Node::fillShaderVector(std::vector<Voxel> &voxelData, glm::mat4 octTransform, float octSize, int index) const
{
    Voxel voxel;
    if (isInternal())
    {
        int i = 0;
        for (auto child: children)
        {
            // I think this is where we have issues
            voxel.cIdx[i] = index;
            index = child.fillShaderVector(voxelData, octTransform, octSize, index);
            i++;
        }
    }

    voxel.pos = glm::vec4(position, 1.0);
    // Store size as the 4th element in the vector
    voxel.pos.w = voxelSize;
    voxel.col = glm::vec4(1.0);
    voxel.index = index;

    voxelData.push_back(voxel);
    index++;

    if (isInternal())
    {
        for(int i : voxel.cIdx)
            voxelData[i].pIndex = voxel.index;
    }

    return index;
}

template<typename T>
bool Octree<T>::Node::isInternal() const
{
    return !children.empty();
}

这正确地遍历了节点，我能够为每个体素获得正确的索引，但是我似乎无法正确设置父索引。

示例输出（为了简洁起见，我删掉了很多，它从 0..56 开始 Parent: -1 意味着没有父节点，即应该只是根节点，而 child: -1 , 表示它是叶节点):

Index: 0
Parent: 56
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 1
Parent: 24
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 2
Parent: 24
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 3
Parent: 24
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 4
Parent: 24
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 5
Parent: 20
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 6
Parent: 20
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 7
Parent: 20
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 8
Parent: 20
Children: -1 -1 -1 -1 -1 -1 -1 -1
...
Index: 16
Parent: 19
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 17
Parent: 19
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 18
Parent: 19
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 19
Parent: -1
Children: 11 12 13 14 15 16 17 18
Index: 20
Parent: -1
Children: 4 5 6 7 8 9 10 11
...
Index: 47
Parent: 48
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 48
Parent: -1
Children: 32 33 34 43 44 45 46 47
Index: 49
Parent: 55
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 50
Parent: 55
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 51
Parent: 55
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 52
Parent: 55
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 53
Parent: 55
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 54
Parent: 55
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 55
Parent: -1
Children: 31 32 49 50 51 52 53 54
Index: 56
Parent: -1
Children: 0 25 26 27 28 29 30 31

我的 fillShaderVector 函数有什么问题导致我无法准确填写父索引？

Answer 1

我解决了这个问题，在预订时我将体素推到矢量上，然后我使用它的索引直接修改矢量并成功更新父数据和子数据。

新插入代码

template<typename T>
int
Octree<T>::Node::fillShaderVector(std::vector<Voxel> &voxelData, glm::mat4 octTransform, float octSize, int index) const
{
    Voxel voxel;

    voxel.pos = glm::vec4(position, 1.0);
    // Store size as the 4th element in the vector
    voxel.pos.w = voxelSize;
    voxel.col = glm::vec4(1.0);
    voxel.index = index;

    voxelData.push_back(voxel);
    index++;
    if (isInternal())
    {
        int i = 0;
        for (auto child: children)
        {
            voxelData[voxel.index].cIdx[i] = index;
            index = child.fillShaderVector(voxelData, octTransform, octSize, index);
            i++;
        }
    }
    if (isInternal())
    {
        for(auto c: voxelData[voxel.index].cIdx)
            if(c != -1) voxelData[c].pIndex = voxel.index;
    }

    return index;
}

这导致正确的索引和层次结构

Index: 0
Parent: -1
Children: 1 26 27 28 29 30 31 32
Index: 1
Parent: 0
Children: 2 3 4 5 6 23 24 25
Index: 2
Parent: 1
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 3
Parent: 1
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 4
Parent: 1
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 5
Parent: 1
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 6
Parent: 1
Children: 7 8 9 10 11 12 13 14
Index: 7
Parent: 6
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 8
Parent: 6
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 9
Parent: 6
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 10
Parent: 6
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 11
Parent: 6
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 12
Parent: 6
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 13
Parent: 6
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 14
Parent: 6
Children: 15 16 17 18 19 20 21 22
Index: 15
Parent: 14
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 16
Parent: 14
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 17
Parent: 14
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 18
Parent: 14
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 19
Parent: 14
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 20
Parent: 14
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 21
Parent: 14
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 22
Parent: 14
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 23
Parent: 1
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 24
Parent: 1
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 25
Parent: 1
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 26
Parent: 0
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 27
Parent: 0
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 28
Parent: 0
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 29
Parent: 0
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 30
Parent: 0
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 31
Parent: 0
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 32
Parent: 0
Children: 33 34 51 52 53 54 55 56
Index: 33
Parent: 32
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 34
Parent: 32
Children: 35 36 37 46 47 48 49 50
Index: 35
Parent: 34
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 36
Parent: 34
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 37
Parent: 34
Children: 38 39 40 41 42 43 44 45
Index: 38
Parent: 37
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 39
Parent: 37
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 40
Parent: 37
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 41
Parent: 37
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 42
Parent: 37
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 43
Parent: 37
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 44
Parent: 37
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 45
Parent: 37
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 46
Parent: 34
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 47
Parent: 34
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 48
Parent: 34
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 49
Parent: 34
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 50
Parent: 34
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 51
Parent: 32
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 52
Parent: 32
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 53
Parent: 32
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 54
Parent: 32
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 55
Parent: 32
Children: -1 -1 -1 -1 -1 -1 -1 -1
Index: 56
Parent: 32
Children: -1 -1 -1 -1 -1 -1 -1 -1

将八叉树转换为数组时如何正确分配索引？

How to properly assign indexes when transforming octree into array?

c++

arrays

tree

tree-traversal

octree