如何将 BVH 节点 object 转换为简单数组？

Question

我正在开发 Opengl ray-tracer，它能够加载 obj 文件并 ray-trace 它。我的应用程序使用 assimp 加载 obj 文件，然后使用着色器存储 objects 将所有三角形面（顶点和索引）发送到片段着色器。基本结构是将结果从片段着色器渲染到四边形。

当我加载更大的 obj-s（超过 100 个三角形）时，计算机需要花费很多时间来完成交集，所以我开始创建一个 BVH-tree 来加快这个过程。我的 BVH 根据 AABB 中包含的三角形面的平均中值递归地将 space 分成两个 axis-aligned-bounding-boxes。

我成功构建了 BVH 树结构（CPU），现在我想将它转换为一个简单的数组，然后将它发送到片段着色器（到着色器存储缓冲区）。

这是我的 BVH class 的结构。

class BvhNode {

public:
    BBox bBox;
    vector<BvhNode> children;
    bool isLeaf;
    int depthOfNode;

    vector<glm::vec3> primitiveCoordinates;

    BvhNode() {}

    ~BvhNode() {}

    BvhNode(vector<glm::vec3> &primitiveCoordinates) {
        this->primitiveCoordinates = primitiveCoordinates;
    }

    void buildTree(vector<glm::vec3> &indicesPerFaces, int depth) {...}

    glm::vec3 calculateCenterofTriangle(glm::vec3 vec, glm::vec3 vec1, glm::vec3 vec2) {...}

    glm::vec3 getCoordinatefromIndices(float index) {...}

    BBox getBBox(vector<glm::vec3> &indices) {...}
};

但首先我想把它转换成一个简单的数组，因为 GLSL 不支持指针。我读过关于二叉树可以转换成数组的内容（当然如果树是完整的）。我正在拔头发。如何遍历整个节点，包括 children 以及如何用空节点完成它（以完成完整二叉树的定义）？我开始编写如下所示的方法，但是当我将 nodes 变量声明为全局变量时出现分段错误。不知道为什么。

vector<BvhNode> nodes; // it is a global variable

void putNodeIntoArray(BvhNode node) {

    nodes.push_back(node.children.at(0));
    nodes.push_back(node.children.at(1));
}

我想，当我创建树时，我需要以某种方式在每个节点中签名，即左侧和右侧 children 开始的位置。

感谢任何帮助。

Answer 1

在数组中布置二叉树节点的一种方法是：对于树中的所有节点，如果给定节点的数组索引为 i，则其子节点位于索引 2i + 1 和 2i + 2（描述更完整 here）。

假设你有一个 complete tree，你可以通过简单的广度优先遍历将你的树写入数组：

在伪代码中：

int current_index = 0;
node[] array = new node[2^n];
q nodes;
q.add(root);
while (!q.empty) {
   node current_node = q.front()
   array[current_index] = current_node;
   if (current_node.left != null)
      q.add(current_node.left);
   if (current_node.right != null)
      q.add(current_node.right);
   current_index++;
}

如果您的树不完整（可能不会，但这取决于您的 BVH 实现），您需要稍微修改它以正确跟踪每个节点应该进入的索引。它将也浪费space，如上面link所述。

除了按广度优先顺序布置节点，还可以（更有效地）按深度优先顺序布置它们，如 基于物理的渲染 中所述here。

如何将 BVH 节点 object 转换为简单数组？

How to convert a BVH node object into a simple array?

c++

arrays

raytracing

aabb

bounding-volume