How to calculate the miss links in a BVH tree?

Question

I am creating an OpenGl based ray tracer for polygon models. To accelerate the application I am using BVH-trees. Because there is no recursion in GLSL, I decided to find an other way to traverse the bounding boxes, sent to the fragment shader as shader storage buffers.

I would like to implement that kind of way:Traversal of BVH tree in shaders

Actually I don't really understand how to calculate the hit and miss links during the construction of the tree. Hit and miss links help the program to navigate to the next node (bounding box) during the traverse, whether it is intersected or not missed.

Until now I created the method to construct the tree, as well as I can also put the tree into a simple array. I have depth-first implementation to flatten the tree into the array.

Here are the depth-first, tree flattening methods:

FlatBvhNode nodeConverter2(BvhNode node, int& ind){
    FlatBvhNode result = FlatBvhNode(node.bBox.min, node.bBox.max, ind, node.isLeaf,                            
    node.indices);
    return result;
}

void flattenRecursion(const BvhNode &bvhNode, vector<FlatBvhNode>& nodes, int& ind) {
    ++ind;
    nodes.push_back(nodeConverter2(bvhNode, ind));

    if (!bvhNode.isLeaf) {
        flattenRecursion(*bvhNode.children.at(0), nodes, ind);
        flattenRecursion(*bvhNode.children.at(1), nodes,ind);
    }
}

vector<FlatBvhNode>* flatten(const BvhNode& root) {
    vector<FlatBvhNode>* nodesArray=new vector<FlatBvhNode>;
    nodesArray->reserve(root.countNodes());

    int ind=0;
    flattenRecursion(root, *nodesArray, ind);

    return nodesArray;
}

I have to calculate the following "links" :

The image is from: source. The image shows the different linkings. So, for example the ray intersects a bounding box (Hit links), we can move to the next node in the array. This is all right as I have depth-first traversal. The problem is coming when I have to move to the sibling or even to the parent's sibling. How can I implement these linkings / offsets? I know I should create and indices but how to do this with depth-first tree construction.

Any help is appreciated.

Answer 1

I do not have an answer about a depth-first tree, but I have figured out a way to do that if your tree is a heap. So here is some code in GLSL I used

int left(in int index) { // left child
    return 2 * index + 1;
}

int right(in int index) { // right child
    return 2 * index + 2;
}

int parent(in int index) {
    return (index - 1) / 2;
}

int right_sibling(in int index) { // a leaf hit or a miss link
    int result = index;
    while(result % 2 == 0 && result != 0) {
        result = parent(result);
    }
    return result + 1 * int(result != 0);
} 

I am using this and it works with a pretty reasonable speed. The only problem I have is that loop, which slows the performance. I would really like to have a constant complexity expression in that function.