0

我正在开发一个 Opengl 光线追踪器，它能够加载 obj 文件并对其进行光线追踪。我的应用程序使用 assimp 加载 obj 文件，然后使用着色器存储对象将所有三角形面（顶点和索引）发送到片段着色器。基本结构是将结果从片段着色器渲染到四边形。

当我加载更大的 obj-s（超过 100 个三角形）时，计算机需要很长时间才能完成交点，因此我开始创建 BVH-tree 以加快处理速度。我的 BVH 根据 AABB 中包含的三角形面的平均中值，递归地将空间分成两个轴对齐的边界框。

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

这是我的 BVH 类的结构。

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 不支持指针。我读过关于可以将二叉树转换为数组的信息（当然，如果树是完整的）。我正在拔头发。我如何遍历整个节点，包括子节点，当然还有如何用空节点完成它（以实现完整二叉树的定义）？我开始编写如下所示的方法，但是当我将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));
}

我想，当我创建树时，我需要以某种方式在左右孩子开始的每个节点上签名。

任何帮助表示赞赏。

4

1 回答 1

1

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

在此处输入图像描述

假设您有一个完整的树，您可以使用简单的广度优先遍历将树写入数组：

在伪代码中：

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 实现），你需要稍微修改它以正确跟踪每个节点应该进入的索引。它也会浪费空间，因为在上面的链接中描述。

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

于 2020-05-06T12:01:42.577 回答