Rendering Lecture 1 - Spatial Acceleration Structures

This lecture belongs to the computer graphics rendering course at TU Wien. We start from a naive iteration through all triangles, go through basic grid like acceleration and end up with Octrees and BVHs. Various optimisation techniques for building and traversal are discussed.
You can download the slides at www.cg.tuwien.....

[@Nandu2794]

Cannot emphasis how well this is presented! Thank you so much for making this public

[@yuxiang3147]

The clearest explanation on this topic so far!

[@unkindled_dreg]

I was searching for a practical example of acceleration data structure and KD-Tree and stumbled upon this gold mine.
Really enjoyed the lecture.

[@FabriceClosier]

Excellent presentation! One detail about the way you start the traversal of BVH, no need to start outside. A simple additional test on point in bound (the origin of the ray) when testing the tree nodes from root is enough and faster.

[@anatolystrashkevich7621]

Great lecture! Thank you!

[@Ribulose15diphosphat]

The most interesting way of rendering is Portal-rendering (What the Descent engine does). You split the scenery in konvex subpolyhedrons, and begin rendering in the room there the camera is. If you hit a portal, you clip the viewing frustrum agains the portal, and go to the next room. So you can render from back to forth without overdraw. It doesn't need an actual structure, and the traversal time does not depend on the level size (with BSP, and other ones the complexity would be logaritmic)

[@danielkrajnik3817]

amazing presentation, thank you. I'm surprised no mentioning of OpenVDB/NanoVDB?

[@HardCoreCodin]

The presentation quality is pretty good here. But this getting students to have to "learn to run before they can walk" is a giant pedagogical mistake.
Throwing fresh minds eager to learn ray tracing, way into the deep-ends of BVH and SAH as the very first entry lecture, is almost a sure way to loose the majority of them at the very outset. Anyone interested in this could alternatively spend weeks and months without any acceleration structure at all, while still getting interactive/real-time framerates, even on just a single thread CPU - as long as the initial scenes are kept small and simple.
Learning the basics of ray-generation, ray-intersections with spheres, triangles, quads, boxes, doing lighting and shading, including shadows, reflections and even refractions - all way ahead of even thinking about any acceleration structure at all - is very easily achievable and much more satisfying for the students - many more of them would be much more likely to stick around. After the basics are firmly in place, the size and complexity of the scenes can be increased, incrementally - only THEN is the appropriate time to start discussing acceleration strategies.

[@cgtuwien]

Thanks, we'll discuss that as well when preparing the next lecture. However, this part is unlikely to change as we also need to take care of the exercise part (this is primarily a university lecture and was moved to youtube because of corona). The acceleration structure is a topic that is relatively easy to pack as a coding task at the beginning, while we develop other topics. It is taught in that order at least at EPFL (by Jakob) and at Aalto University (by Lehtinen).
Cheers, Adam

[@cgtuwien]

Oh, and another thing. Back then when I took that lecture at Aalto, i think I wouldn't have much motivation to implement BVH after having worked with path tracing already. More interesting things ahead, but I would be missing some basics. But that probably also depends on the type of person you are :)
Adam

[@HardCoreCodin]

@@cgtuwien You'd probably get tired of waiting too long to see a render, the moment you start using anything more than the most basic of scenes. That'd be motivating enough to want to make it faster. Regardless, I think for any kind of educational material, a gradual increment of difficulty is recommended. Making it more difficult than it needs to be at the very beginning, is just raising a barrier to entry higher than it needs to be.

[@HardCoreCodin]

​@@cgtuwien University students have to follow their curriculum as-is regardless. They're also unlikely to raise concerns about it or drop-out at the beginning. So when there are issues with it, the chances of that being surfaced are pretty low.
It's quite different in the online courses world, and especially on CZcams.

[@OmniscientOCE]

I concur.