CODEWITHSUNDEEP
c++visual-c++raytracing
Chez Block
Chez Block

Reputation: 11

Issue with memory leak

I'm trying to create a path tracer that can render meshes but I have an issue trying to build a naive bounding volume hierarchy which will help me traverse the mesh and increase performance. However I encountered an issue where whenever I tried to partition the vertices in a mesh recursively (ultimately building a bvh i guess), it led to a memory leak and linked to a cpp file "new_scalar.cpp" telling me there was a stack overflow.

To try to solve the issue, I created another project where I have a node that stores a vector of float pointers and whenever I call partition, it creates two new nodes with half of the split vector each which sort of simulates the recursive nature of building a bvh. Then I encountered the same issue trying to fix it and I don't understand why.

#include <iostream>
#include <vector>
#include <ctime>

#define print(x) std::cout << x << std::endl;

struct Node {
    std::vector<float*> Numbers;

    Node* LeftNode;
    Node* RightNode;

    void Partition() {
        if (Numbers.size() > 4) {
            // Find center
            float min = HUGE_VALF;
            float max = -HUGE_VALF;

            for (int i = 0; i < Numbers.size(); i++) {
                min = fmin(min, *Numbers[i]);
                max = fmax(max, *Numbers[i]);
            }

            float center = (min + max) * 0.5f;

            // Partitioning
            LeftNode = new Node;
            RightNode = new Node;

            for (int i = 0; i < Numbers.size(); i++) {
                if (*Numbers[i] < center) {
                    LeftNode->Numbers.push_back(Numbers[i]);
                }
                else {
                    RightNode->Numbers.push_back(Numbers[i]);
                }
            }

            LeftNode->Partition();
            RightNode->Partition();
        }
    }
};

struct Object {
    Node* Root;

    void BuildBVH(std::vector<float*> numbers) {
        Root = new Node;
        Root->Numbers = numbers;
        Root->Partition();
    }
};

int main()
{
    srand(std::clock());


    // Initialize vector
    std::vector<float*> numbers;

    for (int i = 0; i < 100000; i++) {
        float* newNumber = new float;
        *newNumber = ((float)(rand() % 1000000) / 1000000.0f) * 2.0f - 1.0f;

        numbers.push_back(newNumber);
    }


    Object object;
    object.BuildBVH(numbers);
}

Upvotes: 1

Views: 442

Answers (2)

Paul Evans
Paul Evans

Reputation: 27567

In your function Partition, you're recursively calling Partition:

 LeftNode->Partition();
 RightNode->Partition();

Whenever you call a function in C++, the return address (and any parameters) are pushed onto the stack. C++ stack sizes vary from a few kilobytes to several megabytes but aren't really made for deep recursion. So you don't want to recursively call Partition 100,000 times. Maybe refactor that into a loop?

Upvotes: 2

Hatted Rooster
Hatted Rooster

Reputation: 36483

You're pushing 100,000 floats to numbers and then call Partition() on those. Partition() calls Partition() for both sides, over and over again (until Numbers is less than 4 which still takes a while) . You're simply overflowing your call stack by recursing too many times.

Side note: Stop using new like this.

Upvotes: 1

Related Questions