topic Re: Stack overflow with Custom BVH builder in Intel® Embree Ray Tracing Kernels

Stack overflow with Custom BVH builder

shocker_0x15 — Wed, 26 Aug 2020 07:52:29 GMT

Hi,

I'm now trying to use custom BVH builder with rtcBuildBVH.
I attached the program files I used.

Embree 3.11.0
Visual Studio 2019 16.7.2
Core i9 9900K
Windows 10 Pro 1909

It succeeds to build custom BVHs with low/medium quality settings but sometimes fails due to stack overflow or produces a BVH with overusing primitive list size when using high-quality builder.

Steps to reproduce:

Download Amazon Lumberyard Bistro 3D model from https://casual-effects.com/data/
Sorry for the huge file for repro.
Build the attached program with Release build (the issue happens also with Debug).
Execute the program with the path to Exterior\exterior.obj as the command line argument.
I see the stack overflow exception during rtcBuildBVH().
The attached picture is the call stack window in Visual Studio.

I allocated 100% extra space for spatial splitting, I see the stack overflow with above settings but sometimes see that the build itself finishes but it produces primitive reference list of size over 200% of the original primitive list size (like 500% - 1000%).

I have several questions:

Is there my mistake or is this a known bug?
If I do the above experiment but with multiple threads (by specifying "threads=0" at rtcNewDevice()), it succeeds to build but it gets small amount of leaf node creations with 0 primitives, is this expected behavior?

Thanks

Re: Stack overflow with Custom BVH builder

shocker_0x15 — Wed, 26 Aug 2020 07:57:36 GMT

I reused Embree's internal splitting function but with own types as splitPrimitive function.

Re: Stack overflow with Custom BVH builder

BenthinC_Intel — Wed, 26 Aug 2020 14:42:25 GMT

Looking at it right now...

Few things I noticed so far:

I don't get a crash on my machine with your code but the BVH build process simply gets stuck and never finishes.

Rendering the exterior obj file with Embree's viewer tutorial and the spatial split builder seems to work fine. Cmd line I've used:

viewer.exe -i ..\..\..\lumberjack\Exterior\exterior.obj -verbose 2 --rtcore quality=high,max_spatial_split_replications=2

Also when I replace the splitting function in your code with the simple version from our bvh_builder tutorial it works as well. I guess the new splitting function is somehow causing the BVH build process getting stuck but I don't know why yet.

Re: Stack overflow with Custom BVH builder

BenthinC_Intel — Wed, 26 Aug 2020 17:18:16 GMT

Few more remarks:

I take back my previous comment of the app being stuck in and endless loop on my machine. It seems it finishes but it just takes a very long time. Probably a combination of the app and Embree being run in DEBUG mode on my system and using only a single thread.

About your questions:

Do you infer the 500-1000% increase from the number of splitPrimitives()? That is misleading as Embree can call the splitFunction many more times than the number of input primitives.

Under certain conditions our spatial split builder can create empty leaves, so a small number of those is not surprising.

Re: Stack overflow with Custom BVH builder

BenthinC_Intel — Wed, 26 Aug 2020 17:20:55 GMT

BTW: That's what I get one my machine (used maxDepth=32,maxLeafSize=8).

Start loading assimp scene: ..\..\..\Exterior\exterior.obj ... done.
Generate RTCBuildPrimitive's ... done.
buildArgs.primitiveCount 2837137
buildArgs.primitiveArrayCapacity 5674274
Build BVH ... done.
InternalNode::create(): 381669
LeafNode::create(): 1145004 (null: 35)
splitPrimitives(): 156214674
Convert BVH ... done.
Calculate Statistics ... done.
SAH Cost: 83.7197
Num Primitives: 2837137
Num Primitive References: 3744814 (132.0%)
Num Internal Nodes: 381669
1 children: 11
2 children: 1
3 children: 4
4 children: 381653
Num Leaf Nodes: 1144969
Min/Max/Mean Num Leaves: 1 / 8 / 3.3
Min/Max Depth: 4 / 25

Re: Stack overflow with Custom BVH builder

shocker_0x15 — Wed, 26 Aug 2020 17:52:12 GMT

Thanks for checking the app.

> Do you infer the 500-1000% increase from the number of splitPrimitives()?

No, the percentage comes from the number of primitive references in the end, so it corresponds to: Num Primitive References: 3744814 (132.0%)

I try to increase the stack size from the default to 4MiB, it succeeds to build with HQ settings (200%).
However your last reply gave me a hint and I noticed that the maximum depth setting seems stupidly large... I got a success with maximum depth == 32

I got more questions:

Does custom BVH builder deterministically build a BVH even with multi-threading from the viewpoint of tree structure?
What does sahBlockSize argument mean? Is this something like the number of bins during object/spatial splitting?

Re: Stack overflow with Custom BVH builder

BenthinC_Intel — Wed, 26 Aug 2020 18:21:12 GMT

The standard SAH builder is deterministic in a multi-threaded environment but the spatial split builder is not. When the number of possible spatial splits exceeds the spatial split budget in a given subtree, the build algorithm will fill up the limited spatial split budget aggressively using multiple threads, which introduces non-deterministic splitting at this point.

sahBlockSize is used when computing the SAH of potential splits. For example in

https://github.com/embree/embree/blob/master/kernels/builders/heuristic_binning.h

line 359-373 the value blocks_shift is used which is basically log(sahBlockSize). If you build for example a 4-wide BVH you get a better quality BVH if you use a block size of 4.

Re: Stack overflow with Custom BVH builder

shocker_0x15 — Wed, 26 Aug 2020 18:28:05 GMT

Thanks for the fast reply.

I understand the determinism and will see the code to understand what the block size is.

I'm not sure why I saw over use the split budget in certain conditions but I guess it is the result of multi-thread racing with bad argument (max depth == 1024) and it will not happen with the current setting (max depth == 32).

Therefore I'll make this issue resolved.

Thanks for the support!