Strolle: Raytracing 2 million triangles in real-time!
Hi there,
Together with u/mrDzejkop we're improving a raytracer we've implemented from scratch for our game \- and while it's still very much work-in-progress, we thought it might be nice to share how it's going :-)
As of a few days ago, our engine is able to trace in real time - 2560x1440 x 60 FPS on my laptop's GTX 1050 Ti - the following image:
... which consists of two million triangles!
As usually, the magic here lays in avoiding doing as much work as possible, for which we've employed a data structure called LBVH \- tl;dr it groups the entire scene into consecutively smaller boxes (called bounding boxes):
Nefertiti Bust, how it looks like from BVH's point of view
Those nested boxes form a tree (with triangles being the leaves and bounding boxes being the nodes), which allows for the raytracer to quickly discard large parts of geometry simply by checking whether a particular pixel "hits" given box.
Say, if pixel at coordinates (5,5) doesn't hit the top-level bounding box, then there's no point in checking any of the two million triangles inside the box! (and when a pixel "hits" some bounding box, we recursively check its children-boxes, children-children-boxes etc.)
(on the image above, the whiter the pixel, the more nested in the tree it is.)
Similarly, this scene:
... gets the following BVH tree:
... and, if we zoom-in on a particular bunny, we get:
Our raytracer is pretty much still a toy at this point, but nonetheless one can play:
... and, of course:
The source code is available here, for the curious people:
https://github.com/Patryk27/strolle
There's no documentation at this point (no 0.0.1-alpha release either, still lots of things to left to implement), but Strolle is integrated with Bevy (and the examples are Bevy-based), so if you want to play around, you should be able to figure out the way :-)
Technical-wise we'd like to give shout out to rust-gpu! -- thanks to them, we could (relatively easily!) write the entire raytracer (including shaders) in Rust.
Now, for people interested in some raytracing meat:
\- we're using LBVH, but for now we've only got a naive CPU-based implementation \- it will serve us as a reference point when when we'll go full-GPU on generating the tree,
\- building LBVH for Nefertiti Bust takes around 850 ms on my machine (i7-8750H, single-threaded, even without radix tree); for smaller scenes it usually takes less than a few milliseconds / less than a millisecond,
\- so far we're building LBVH for the entire scene at once (though HLBVH looks promising),
\- we're traversing the tree using explicit stack (like stack: [usize; 16] \+ stack_pos: usize), with one trick: instead of allocating this array in Rust code (that is, instead of doing let mut stack = [0; 16]), we utilize workgroup shared memory (so we've got #[spirv(workgroup)] stack: [usize; 16 * x * y]); it's a few percent faster this way (possibly because the memory doesn't have to get zeroed out each time),
\- while our game from before uses roped BVH, we've found out that it becomes slower than stack-based iteration above around 512 triangles (possibly because using ropes means you can't prioritize left/right children),
\- we've got a multi-shader setup:
- pass #1 (compute shader) generates rays, checks collisions and stores colliding triangle ids into a separate buffer (basically
hits: &mut [Option<TriangleId>; screen width * screen height]), - pass #2 (compute shader) takes those hits, compares them with lights (to generate shadows), loads materials and generates RGB colors,
- pass #3 (vertex + compute shader) takes the texture generated above, performs debanding and renders stuff into the final color attachment that gets displayed on the screen,
- we've started with one mega-shader and just splitting it into separate steps improved performance by around 50% (possibly due to lower register pressure, although I haven't investigated it thoroughly),
\- I've compared traversing performance of LBVH & SAH -based trees and, perhaps amazingly, e.g. for the bunny model, LBVH generated a tree that's faster to process (for the raytracer) than the one created by SAH; I haven't tested it for bigger scenes though, since even multi-threaded SAH already takes \~2 minutes for the bunny model (50k triangles, I think?), so I can't imagine generating a tree for 2 million triangles this way.
Well, that's all thoughts for now - if you have any questions, feel free to ask :-)