Maximum call stack size exceeded - BVH_Build_Recursive

[RealTecWare]

Hy erichlof,

I have tested the .obj example up to woolly-mammoth-skeleton.obj (Triangles: 99,998), if I used the 100,000 Triangles example stanford-buddha.obj I get the error, that the call stack size is exceeded (BVH_Recursive_Acc_Structure.js - BVH_Build_Recursive).

I have used a test from 2ality.com - Call Stack Size
The snippet:

var computeMaxCallStackSize = (function() {
  return function() {
    var size = 0;
    function cs() {
      try {
        size++;
        return cs();
      } catch(e) {
        return size + 1;
      }
    }
    return cs();
  };
}());

And get following number of stack depth:

• Safari (12.0 13606.2.11): 36254
• Vivaldi (2.0.1309.37) 64bit: 27946
• Firefox (62.0.3): 26196 64bit: 25960
• Chrome (69.0.3497.100) 64bit: 13951
• Opera (56.0.3051.36) 64bit: 13951
• Edge (17.17134) 64bit: 11289

[erichlof]

Hi @RealTecWare
Thank you for the error report and thanks for the link to Call Stack Size calculator - that is helpful! I was searching for something like that on the internet, but only got StackOverflow help/answers as results. I somehow missed your link!

Now about the errors, I recently found that the recursive BVH builder is finicky when it comes to object dimensions. If the scaling of the object is not within a certain range with respect to the overall scene dimensions, the recursive builder will go on and on, never correctly splitting the current triangles in the current workList into 2 groups, left and right, and thus never successfully spawning 2 smaller child bounding boxes from the parent bounding box.

I did try to mitigate this with trial and error, which is why I have the exact 'model settings' that you can comment and uncomment for the appropriate model you are trying to load. I'm curious, did the Buddha model crash on your machine, using my tested dimensions settings for that Buddha model?

I am actively looking for a way to make the builder more robust to these different scaling situations. As I mentioned before on another thread in this repo, this builder is the most complex 300-or so lines of code I have ever attempted using and maintaining in a project. For months I had to go line by line, trying to understand it fully. I understand most of it, but the line 'step = (stop-start)/24' grid sizing that keeps going down as the builder steps through the levels of hierarchy I still don't fully grasp. ;-) This is where things go wrong and the recursive builder just keeps spinning its wheels until it exceeds the call stack size. Different numbers substituted for the '24' in that above equation crash certain models and scales, and perform fine on others - it's hit or miss.

Thanks again, I'll update if I make any progress.
-Erich

[RealTecWare]

I try to mitigate this with trial and error, which is why I have the exact 'model settings' that you can comment and uncomment for the appropriate model you are trying to load. I'm curious, did the Buddha model crash on your machine, using my tested dimensions settings for that Buddha model?

Hy Erich,

I tested it with your information and set the model settings and with the necessary scaling of the model it works very nice, so I think the my issue is fixed by this.

Hope the callstack snippet helps you :)

Thanks for your fast answer 👍

-Fabian

[erichlof]

@RealTecWare ,
Glad to hear you got it working! Yes if the model dimensions are not within a certain window, the recursive builder spins its wheels until it crashes. I'm still trying to determine the boundary condition where it succeeds up to that boundary, and beyond which it fails. Hopefully in the future I can make the builder less fragile and less prone to this kind of catastrophic error.

I'm also about to dive into writing a LBVH which uses Morton codes and bit manipulations inside the fragment shader (now available with WebGL 2.0 support from three.js). Instead of recursively building on the CPU beforehand, it basically builds and re-builds the entire acceleration structure from scratch every animation frame on a GPU texture, so you can have arbitrary morphing and animating triangle geometry, as in real-time games. That builder will be even more complex than the current one (ha), but I'll at least give it a try.

Thanks again!
-Erich

[erichlof]

@RealTecWare
Hi Fabian,
Just wanted to give you a progress update on the BVH builder. I removed the recursive builder that was crashing, and in its place a created an iterative version. When I was new to BVH builders, the recursive one was more intuitive code-wise but was prone to crashing as you saw. With the iterative version, I had to create and maintain a stack and stack pointer, then the builder goes down left branches (stackptr ++) and then back up the right branches (stackptr --). It took a lot of trial and error to make it behave correctly, but now it is much more robust! You should have no problem rotating, translating, or scaling a model upon loading it with the objLoader provided by the three.js library - the builder should just do its thing and work now. :)

new Iterative builder demo

When I see that you have read this, I might close out this issue if that's ok with you - the recursive builder has been removed.
Take care,
-Erich