Question How to handle stack overflow when using recursion with large datasets (BVH)

I am working on a Bounding volume hierarchy (BVH) structure and when building it I get a stack overflow exception, but I am not quite sure how to fix it well.

This is the constructor for the node. BinnedSplit basically just splits the primitives in half and creates a left and right child BVHNode, each getting one half of the primitives. BinCount is set to 8.

Code (CSharp):

1. public BVHNode(BVHNode parent, AABoundingBox bounds, List<IBVHPrimitive> primitives)
2.     {
3.         this.Parent = parent;
4.         this.Bounds = bounds;
5.  
6.         if (primitives.Count > BinCount)
7.         {
8.             BinnedSplit(primitives);
9.         }
10.         else
11.         {
12.             IsLeaf = true;
13.             this.Primitives = primitives;
14.         }
15.     }

I truthfully am not 100% clear on what does and doesn't cause a stack overflow exception. If I am correct, it is when it runs out of memory, not clear though if it is for a specific method, or application wide, or what. Someone said using a while loop would work, but that doesn't make sense to me?

I know I could just stop it much sooner I guess? But that would lower the quality of the BVH and make traversals more expensive.
Any ideas or clarifications?

 

Every time you call a method/function, a new stack frame containing all of the local variables and arguments of the new function is added to the stack. If you are using recursion, the stack will build up for every level "deep" your recursion goes. If your code results in infinite recursion, because you do not have a proper base case for recursion (or even just an extremely "deep" recursion), the program will keep calling your recursive method and adding stack frames until the stack itself gets too large. At this point the stack is considered to be "overflowed". That is what causes a StackOverflowException.

In the small code snippet you shared here, I don't actually see any recursion, but I would guess you have recursion inside the "BinnedSplit" method. Mind sharing the code for BinnedSplit?

 

Ah, got it, yeah, I think my problem is it is too deep.

I don't mind sharing it, but it is kind of long and a bit dense, the important part is at the end of "BinnedSplit" where it creates two nodes, thus calling the constructor that is in my main post, which in turn calls the "BinnedSplit" if the number of primitives is high enough.

Code (CSharp):

1. private void BinnedSplit()
2. {
3.    // Code that calculates which primitives go to the left node and which to the right node.......
4.    //......
5.  
6.     // After primitives have been divided, create the Left and Right child.
7.     // This is where the recursion comes in, this then calls the constructor for the BVHNode posted earilier which then calls BinnedSplit()
8.     LeftChild = new BVHNode(this, bins[splitIndex].allLeftBinBounds, bins[splitIndex].primitivesAllLeft);
9.  
10.         RightChild = new BVHNode(this, bins[splitIndex + 1].allRightBinBounds, bins[splitIndex + 1].primitivesAllRight);
11. }