Why does push_back give a segmentation error?

Question

About the project:

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).

Here is the method responsible for converting the BVH root node into an array:

BvhNode bvhNode; //global variable

BvhNode* putNodeIntoArray() {

    int size=bvhNode.getNumberOfNodes();
    BvhNode nodesArray[size];

    int current_index = 0;
    vector<BvhNode> tempNodes;

    tempNodes.push_back(bvhNode);
    BvhNode current_node;

    while (!tempNodes.empty()) {
        current_node = tempNodes.at(0);

        tempNodes.erase(tempNodes.begin());
        nodesArray[current_index] = current_node;

        if(!current_node.isLeaf)
        {
            tempNodes.push_back(current_node.children.at(0)); // Segmentation error occurs here!
            tempNodes.push_back(current_node.children.at(1));
        }

        current_index++;
    }

    return nodesArray;
}

About the problem:

I don't know why, but it gives me a segmentation error, when I want to push_back the first child to the tempNodes vector (the exact place can be seen by the comment above). It seems to me current_node.children.at(0) does not exist, but actually it exists according to the debugger. I tried to write reference (&) operator: tempNodes.push_back(&current_node.children.at(0));, but in this case it is giving me weird coordinates to the objects. I tried to define the variables in the function as globals - trying to avoid scope problems -, as well as defining the current_node variable as a pointer. Unfortunately none of them gave me better results.

Here is my BvhNode class, if it helps:

class BvhNode {

public:
    BBox bBox;
    int depthOfNode;
    vector<BvhNode> children;
    int order;
    bool isLeaf;
    bool createdEmpty = false;
    vector<glm::vec3> primitiveCoordinates;

    BvhNode() {}
    BvhNode(BvhNode *pNode) {}

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

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

---

Update 1:

I updated the method according to the comments. So I changed the type of the returning value to vector insted of BvhNode*. The algorithm works fine until it reaches the process of putting the leaf nodes into the std::vector. So when it starts to putting the last level of the graph to the vector, it gives me this error:

Program received signal SIGSEGV, Segmentation fault.
0x00007fbda4d69c01 in __GI___libc_free (mem=0x555be3a9dba0) at malloc.c:3123
3123    malloc.c: No such file or directory.

I managed to put seven nodes (meaning all depth levels of the tree except the level of leaves) into the vector. I also tried to run valgring, but actually valgrind does not give me any error, not like in CLion.

This is my modified method. I commented the place of segmentation fault and the fixes.

    BvhNode bvhNode;

    vector<BvhNode> putNodeIntoArray() {

        int size=bvhNode.getNumberOfNodes();

    // FIX:  I modified the array into an std::vector
        vector<BvhNode> nodesArray(size);  

        int current_index = 0;
        vector<BvhNode> tempNodes;

        tempNodes.push_back(bvhNode);   
        BvhNode current_node;

        while (!tempNodes.empty()) {
            current_node = tempNodes.front();// Segmentation error!!
            tempNodes.erase(tempNodes.begin());

            nodesArray.at(current_index)=current_node;
            nodesArray.at(current_index).children.clear();


// FIX: I also modified this not to iterate through leaves' children, because they don't exist.
            if(!current_node.children.empty())  
            {
                tempNodes.push_back(current_node.children.at(0));
                tempNodes.push_back(current_node.children.at(1));
            }
            current_index++;
        }
        return nodesArray;
    }

Answer 1

Actually the problem was in the creation of the Bvh Tree. Because I wanted to reach the children in the form of 2*i+1 and 2*i+2, I was using a method to make the binary tree full (every level has maximum number of nodes). In this method I had to push empty nodes to the tree.

I was creating the empty node like this:

BvhNode emptyNode;

instead of this:

BvhNode *emptyNode = new BvhNode();

So, when the method finished, the lifetime of the emptyNode was ended. And that caused the segmentation fault.

Moreover, there was also a problem, that I stored the BvhNode by value during the creation of the flat binary tree as Balázs Kovacsis pointed out. This option made the app much slower and it was another potential place to cause segmentation fault.

Answer 2

Your vectors store the BvhNodes everywhere by value. This means that every time you push_back a node, its copy constructor is called, which in turn copies the children vector member inside the node, which copies its own elements etc. This basically results in complete subtrees being copied/freed every time you insert or erase a node.

This in turn can result in memory fragmentation, which can eventually cause a vector reallocation to fail and cause a segfault.

Without the full code, I can recommend these 2 things:

1. Store the children as (smart) pointers instead of by value

2. Create a custom allocator for the vectors to enable a more fine-grained debugging, and check for allocation failures