opened
madmann91
username_0
This PR implements a Binned SAH BVH builder, based on "On fast Construction of SAH-based Bounding Volume Hierarchies", by I. Wald. The existing Kd-tree/BVH implementation has been kept intact for comparison purposes. It can be enabled again by defining the preprocessor symbol `OLD_KD_TREE`.

I have only the provided test scene to measure performance, and I cannot really tell if there's a measurable performance improvement because:

 - More than 40% of the time is spent in small functions like `vecSub`. Ray traversal is only 4% of the execution time. Thus, even if this made traversal infinitely faster, not much of an improvement would be visible. This is due to the way you organized your code, as most of those small functions are in separate compilation units and unavailable for the inliner. You have basically two options to fix this problem: Use LTO (on my machine it multiplies performance by almost 3), or move these small functions their respective header file with the `static inline` qualifiers to avoid linking problems (I would recommend going that route, as it gives you more control over what is inlined and what isn't, and doesn't blow up your compilation times).
To enable LTO, you can bump your CMake requirement to something more modern (e.g. 3.4) and use the following:
```set_property(TARGET c-ray PROPERTY INTERPROCEDURAL_OPTIMIZATION TRUE)```
Note that this _will not_ work on old CMake versions (e.g. 2.8 will not enable LTO for gcc). If you want to use LTO but stick to an old CMake version, you need to append `-flto` to both the linker and compiler flags for gcc (old versions of gcc might not support LTO).

 - The second problem is that the test scene you provide has around 10 meshes that each have their own BVH, but have all to be traversed sequentially, completely nullifying the benefit of using an acceleration data structure altogether. I recommend to either merge those meshes, or to build a top-level BVH that has per-mesh BVHs as leaves. The code in this PR is designed to be able to do that, as only bounding boxes and centers are required to build a BVH (so it works for any primitive type, including other BVHs).

Finally, there's a large optimization potential that's not taken advantage of, namely early exit for shadow rays. For that, I have added a `TODO` that suggests to add a `tMin` and `tMax` to your rays, so that you can actually cull nodes more efficiently during traversal (because shadow rays can exit the traversal loop early, upon the first intersection found in the given `[tMin, tMax]` range). This in general gives a 20% performance boost when implemented correctly. This PR does not implement  this feature, as it would break the compatibility with the existing acceleration data structure.
Binned SAH BVH builder
issue
created
VKoskiv
username_1
This is so cool! I'm evaluating it right now, I'll post my comments shortly. Looking great at first glance!
comment
created
VKoskiv
username_1
Okay, I'm speechless here. I just quickly threw in the `INTERPROCEDURAL_OPTIMIZATION` flag to my `CMakeLists.txt` to test it out, and **what**? The `hdr.json` scene rendered 60% faster than ever before.
I *had* tried adding `-flto` to the **linker** flags before, resulting in a slightly smaller binary, but this is just an incredible boost in performance from such a small change.

I'm still exploring this PR, but I can already tell you you've made my year with this. I am ecstatic!
comment
created
VKoskiv
username_1
You are more than welcome to implement this, changing the existing data structures as you see fit.

I'd love to know which tools you used for profiling as well. I've used the sampling profiler that comes with Xcode (built on DTrace), but apparently I wasn't that good at interpreting the results, as I had no idea it was as bad as you've shown it to be. 😄 
I think I just failed to identify the massive amount of function call overhead.

I think the  plan going forward would be something like this:

- For now, I'll tweak the `CMakeLists.txt` file to require `v2.9` and set the `INTERPROCEDURAL_OPTIMIZATION` flag as a stopgap until the heavy functions are inlined in code. As is, just adding that flag boosts performance by ~60% while only slightly increasing build times.
- Remove the old KD-tree implementation. It's much slower than your  BVH implementation, so I don't see a reason to preserve it beyond just comparing the performance. We can just checkout an older version to compare performance going forward.
- Implement early exit for shadow rays

What an incredible PR, thanks so much for helping out!
comment
created
VKoskiv
username_1
@username_0 If it's okay by you, I would like to tag you in the README as a contributor.
comment
created
madmann91
username_0
I use `perf` for profiling. It's pretty low-level, but it can perform sampling and can return statistics for cache misses, number of instructions executed, and so on. It's also not intrusive, and has very little overhead, compared to other approaches like `gprof`. To sample an executable, use `perf record <prog> <args>` (where `prog` and `args` are the program name and its command line arguments, respectively), and to show the result use `perf report`. To get statistics, use `perf stat <prog> <args>`. You might want to compile in `RelWithDebInfo` to get valuable annotations in the `perf` report, otherwise you'll only see assembly without line info.

Thank you for the attribution request, I'm fine with it. In any case it's going to be visible on GitHub's contributors page.
comment
created
madmann91
username_0
I'd be curious to know what is the performance difference between the new BVH implementation and the old one on more complicated scenes. Do you have some figures? And maybe also, do you have any complicated (ideally only one mesh, but highly tessellated and with a non-uniform primitive distribution, like e.g. Sponza) test scene that I could play around with?
comment
created
VKoskiv
username_1
@username_0 I'll do a lot more testing in the coming days. The most complex scene I have right now is the stormtrooper scene that you see in the readme, but that one also has the meshes separate, and no top-level acceleration structure of course. So I guess that feature is what should be tackled next.
You can download the stormtrooper scene [here](https://vkoskiv.com/c-ray/releases/troopers.zip) if you want. And if you do end up making changes to scenes, or new scenes, then use the `scripts/bundler.py` to package them up like that zip in the download link.
I'll keep you posted on the performance metrics I measure once I have them.
comment
created
lycium
username_2
I'm also blown away by your generosity here, @username_0! Checked out your bvh project, it looks very impressive :)
comment
created
madmann91
username_0
@username_2 Thank you! It's not much really. This project looked interesting, so I thought I'd just contribute a bit.
comment