Coding Adventure: Optimizing a Ray Tracer (by building a BVH)

Trying to speed up the ray tracer (from a previous coding adventure) so that we can render some more intricate scenes!

Links:
● Get early access to new videos and projects by supporting on:

Chapters:
00:00 Intro
00:30 Triangle-Test Debug View
03:34 Bounding Boxes Inside of Bounding Boxes
04:41 Building a BVH
07:41 Traversing the BVH
09:13 GPU-Friendly Data
15:32 Converting Recursion to Iteration
18:06 Box-Test Debug View
21:42 Increasing the Depth of the BVH
25:11 Distance Test and Child Ordering
31:47 The Surface Area Heuristic
37:19 Speeding up the Construction
38:57 32-Byte Nodes
42:20 Transformations
45:10 Supporting Multiple Models
48:45 Some Tests and Final Thoughts

[griffinschreiber]

"Just recursively split the children in half" is my new favorite Sebastian Lague quote.

[theothetorch]

"But sometimes, I suppose, one has to prioritise the computer's happiness over one's own."

[TilghmanReiss]

I’ve never been so excited to watch an hour long coding adventure before

[x]

> I want to measure our inefficiency so that we can track improvements to it

what a philosophy

[wesplybon]

18:10 the arm waves in the reflection was so real 😂

[greenguy]

"Where we left off a year or so ago" dealt me 1d6 of psychic danage

[curtreyes]

For your next coding adventure you should try some multiplayer sync stuff if you haven't already. I recently have gone down a rabbit hole of different types of network sync models and there is still a lot of nuance that is left ambiguous in even the most detailed blog posts. Something that I would personally love to see.

[sietzethebest]

OMG you've found the blog of my thesis supervisor (JBikker)! My thesis is related to BVHs so this video is a treat to watch :)

[Gwilo]

these coding adventures get more and more complex. I reckon Sebastian's working on something big, but first has to learn every technique to its fullest before starting and then finishing it

[Xaer]

I hear the "hello everyone" and I drop anything just to watch it. 10/10 dropped my phone on a lake.

[hestojam]

Very impressive results, bravo.
I keep being in awe by how you manage to make things work first, then optimize it in a structured way and without getting weighted down by premature optimizations and such.

[seanloughran]

That was awesome. One of the structures I've used in the past when I have all the data ahead of time is a Sort-Tile-Recursive (STR) R*Tree. You sort the data in space first, then build the tree from the bottom up. The result is a very well balanced tree that is extremely quick to query. You then set the maximum number of children in a leaf, so you get even performance. I don't know if the query times would speed up that much after your final iteration, but my guess is, the build time would be infinitely quicker. As always, just an extremely informative and entertaining video!

[GeorgeTsiros]

My absolute favorite part of your videos is that the tone of your voice is like you are _smiling_ while speaking.
I do not know why, normally I would consider it condescending, but from you it sounds _honest_
People who code well are rare. Equally rare are people who can explain well. People who can do _both_ are exceedingly rare. You deserve every bit of praise you get.

[jaccobikker]

Very nice video. Nice illustration of the BVH concepts! Greets, Jacco.

[sebastianmestre]

Hey Sebastian, cool video!

There's a slightly different approach that would let you try every possible cut in the SAH without too much additional cost.

Right now you're evaluating each cut by looping over all the triangles (O(N*K) cost for N triangles and K cuts), but this does not take advantage of previous evaluations.

Imagine you sorted the triangles along one of the axis, then computed and stored the bounding box of each prefix and each suffix of the triangle list. Now you can evaluate each cut in constant time (child A corresponds to a prefix of the list and child B to a suffix).

Sorting has cost O(N log N), but then you can try all the cuts along that axis in O(N) time. Overall, the cost is O(N log N), which should be much better than O(NK) for large values of K.

Here is an outline of the general approach:

sort tris along the x axis
prefixes = array of length n
prefixes[0] = bounding box of tri[0]
for i = 1 to n-1, assign prefixes[i] = bounding box union of prefixes[i-1] and tri[i]
suffixes = arraay of length n
suffixes[n-1] = bounding box of tri[n-1]
for i = n-2 to 0, assign suffixes[i] = bounding box union of suffixes[i+1] and tri[i]
for i = 1 to n-1, the cost is i*surfaceArea(prefixes[i-1]) +

As described, the idea involves performing three sorting operations at each node of the tree, but this is not strictly necessary. If you sort all the triangles along the three axis just once at the top level, it's possible to preserve the order as you go down the tree construction algorithm. This might be too complicated to implement while keeping the code readable, though.

[calebgilbertyt]

I fell asleep watching this video and I'm not even joking, you have the calmest voice and I wouldn't trade it for anything!

[toara]

Can't wait for more fluid simulation next!

[bejoscha]

Your detailed explanation style is very much appreciated. It's often a tiny "practical" thing between "the theory" and "the final program" which is the biggest coding hurdle to overcome. Your videos are great to overcome these hurdles and learn how to approach such problems in general. Important skills well taught.

[suriMusiq]

Your visualizations are immensely beautiful and helps understand complex concepts like BVH. I am not lying when I said, I read this and implemented this myself, but I don't believe this is what my understanding was! Much love to your work <3

[FisheySauce]

The exploratory nature of your videos is why I will spend an hour of my life the next available moment I have watching your channel. I love learning, and as a non programmer and you just make it so fun and easy to understand. Thank you for the knowledge and enthusiasm you give me to keep knowing more. :)