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

Question

I am working on an Opengl ray-tracer, which is capable of loading obj files and ray-trace it. My application loads the obj file with assimp and then sends all of the triangle faces (the vertices and the indices) to the fragment shader by using shader storage objects. The basic structure is about to render the results to a quad from the fragment shader.

When I load bigger obj-s (more than 100 triangles), it took so much time for the computer to do the intersections, so I started creating a BVH-tree to speed up the process. My BVH splits up the space into two axis-aligned-bounding-boxes recursively based on the average median of the triangles faces contained in the AABB.

I succeed to build the BVH tree structure (on CPU) and now I want to convert it to a simple array, then send it to fragment shader (to a shader storage buffer).

This is the structure of my 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) {...}
};

But first I would like to convert it to a simple array, as GLSL does not support pointers. I have read about a binary tree can be converted into an array (if the tree is complete of course). I am pulling out of my hair. How can I iterate over the whole node, including children and of course how to complete it with empty nodes (to fulfill the definition of complete binary tree)? I started to write a method seen below, but I got segmentation fault when I declare the nodes variable as global variable. I don't know why.

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));
}

I guess, when I am creating the tree, I need to sign somehow in every nodes, where the left and the right children starts.

Any help is appreciated.

Answer 1

One way to lay out binary tree nodes in an array is: for all nodes in the tree, if a given node has array index i, its children are at indices 2i + 1 and 2i + 2 (described more fully here).

Assuming you have a complete tree, you can write your tree to an array with a simple breadth-first traversal:

In pseudo-code:

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++;
}

If your tree is not complete (which it probably won't be, but it depends on your BVH implementation), you'll need to modify this slightly to correctly track the index each node should go in. It will also waste space, as described in the link above.

Rather than lay out the nodes in breadth-first order, it is also possible to lay them out (more efficiently) in depth-first order as described in Physically Based Rendering here.