 Okay, so welcome to today's rendering lecture. This is going to be unit 4. We will have two parts in it. So one, the first part will be spatial acceleration structures and the next part will be tone mapping. I will hold the next three lectures. So this one and two more and then I'll take it over again. So spatial acceleration structures. So where are we? The rendering pipeline, as it was shown in the first lecture, so we start with a 3D scene, performs some kind of light simulation, generate an image out of it that's going to be displayed. So spatial acceleration structures are central to the light simulation because they increase the efficiency of ray shooting. So as you heard last time, ray-based methodologies, so from geometric optics, are mainly employed to enable photorealistic rendering. And in this work, you have to shoot a lot of rays. So usually in the order of million to billion. And if you can cut down the computational cost of this procedure, then you will gain significant speed ups. So to summarize, so generally the Monte Carlo method uses ray shooting to sample the integrand of the rendering equation, as shown in the last time. So usually you have to compute the closest intersection with the scene. So this is equivalent to computing the local visibility. So how far does it travel through the scene before it hits its first object? And this is usually very expensive for a large amount of scene objects, because if you start with one ray and you want to check, does it intersect any of my scene set triangles, then if you have millions of triangles, then each ray has to check all the millions of triangles, which one is the first that intersect. If you have millions of rays, you see that this is a quadratic explosion, and you will not converge in any reasonable time to a high quality image. So the naive approach would be just to determine the intersection with each object. So the object could now be usually triangles can also be non-linear surface patches or whatever you want to use. So if you just go through all the objects, one after the other and check which one is the closest, you have to go through all the objects, so it's a linear approach. So the complexity is over n. A better approach would be to reorganize all the objects in your scene, say the triangles, in some kind of spatial hierarchy. So that I know that say in the left half of this room are these triangles in the right half of these triangles. And then if I have a ray that I know that it only travels through one half of the room, then it can, evidably, discard half of the triangles in my scene and don't need to intersect against them. So this approach, I mean it's a bit more sophisticated than that, leads then to a sub-linear complexity. So eventually it gets close to the rhythmic. So, I mean this is a very old topic. So this popped up very soon when ray tracing was used. So there are many methodologies that were looked into and two main techniques, say, are considered the state of the art. So there are KD trees and the other are bounding volume hierarchies. So a KD tree subdivides the space itself. So your scene is situated in a surrounding space, three-dimensional. You then cut this space into pieces. As can be seen in this example on the right hand side, here the space in which the object resides is just a square. And each object is just a point. And as you see with recursive subdivision of the space, you group the objects together in a spatially local volumes. And if you the right side gives you the subdivision of the space itself and where the object's lying those, but each split of the space can be seen as a construction of a binary tree. So you start off, have the root node, which is the whole space, then you try to find some kind of good cut through the space so that approximately half of the objects are in one half and half of the objects and the other. So it doesn't make sense to start off with the whole volume and then separate a very small part from it. Because every ray has to start its traversal of the tree at the root node. And then it has the decision, am I in the peak volume or do I have to check the small volume too? If you have a lot of small volumes, then this is inefficient again. So what you want to do is to place or to get the criteria that you are not going to have to intersect a lot of triangles as far up in the three years possible. So in this example, the first cut, the vertical cut through the whole space, subdivides the objects approximately in half. So that half of the objects are left of the cut, half of the objects are right of the cut. So this would be a cut plane through the volume, but it's the same procedure. And then you recursively subdivide the parts, so the two sub volumes that you generated with the first cut. Also try again to have half of the objects there, half of the objects there. And you continue with this procedure until you have one object per volume. I mean, of course, you can also terminate earlier. So if you are okay with having 100 triangles in each leaf node of the tree, then you have to check through all these 100 triangles if you enter the subspace. But the main advantage you gain with this is that if you have some ray through this volume, then you can do very quick checks against the subspaces. So you know that all the subspace here are rectangles in a volume. They would be boxes and you can do very quick intersection test against boxes. And if you know that you're not going to intersect the box, which is one test, but there are thousands of triangles in this box, then you can immediately discard all these triangles for your real intersection test. So you only have to check the triangle intersections in those boxes that you checked beforehand that you intersect. And you can imagine that if you have huge areas that you don't intersect, you gain a lot of speed because you don't do unnecessary work. So KT3s subdivide the space. And then you have to, and then in the sub-volumes, the objects life. Another approach, a bounding volume hierarchies, there you group the objects together. So you take, you start with the triangles, and then you say, I put close triangles into groups. And then you again build up a tree structure, but this tree structure now depends on the triangles. So the fundamental unit there is a triangle, not a subspace of your whole scene volume. So now they have advantages and disadvantages, otherwise you would only take the better one. So KT3s, they are usually faster for traversal on the CPU. Here I mean a multi-core CPUs, but they have usually a larger amount of nodes, and they have duplicate references. Because if we go back to this example, here we have points. Okay, a point can, does not have a spatial extent. But if you imagine that you have triangles and you cut through the whole volume, then it could be that you cut through triangles. And then you have two possibilities. Either you just add the triangle to both volumes, so you get duplicate references. That means your triangle discard is less efficient, because you have to check against this triangle if you're in the left or in the right half. Or you cut the triangle itself and add one half there, one half there. But cutting a lot of scene content is computationally expensive. So this would then degrade the performance of the KT3 generation. Bounding volume hierarchies are very popular for GPUs and multi-core architectures, so the CUNE-Fi for example. So they got more attention in recent research, because most of the current work tried to implement. So the spatial hierarchy generation on GPUs or other highly parallel architectures. They are also easier to update, because imagine you have a moving object inside your scene. A KT3 cuts the whole volume apart, and then if you have an object moving from one sub volume to another, you would have to update the whole KT3, because you don't really have a grasp on at which level you have to edit it. Bounding volume hierarchies on the other side, they group objects together. So there you can just, you have the option of ignoring dynamic complication, because say you have two objects and B that are close together. So you generate your Bounding volume hierarchy, so they are grouped together at some level of the three. And if they then move apart, the grouping is not influenced. The only thing that happens is that the Bounding volume that holds both groups gets larger and larger. So what happens is that your spatial hierarchy gets more inefficient, because say a lot of empty spaces generated in between object and B. So raise the travel exactly through the gap between them, they would still have to check A and B. If you would then update your Bounding volume hierarchy to acknowledge that they are spatially separated, then they would be cut at a, they would be put into different branches of the three at a different level. But you don't have to do that. So in Bounding volume hierarchies, dynamic scenes just degrade your performance, but don't invalidate your whole hierarchy. Because in KT trees, if you move from one sub volume to the other, you have to update this in the whole tree. And this could be quite complicated, because traversing the tree for higher than the next scene can be very costly. And another advantage for Bounding volume hierarchies is that every object is only in one tree leaf. I mean, this is naturally because it's constructed that tree. But a negative point of them are that the nodes can spatially overlap. So if you put two triangles that are close by each other into different nodes of the Bounding volume hierarchy, then you still generate the box around them to do a fast intersection test. But if the triangles are, say, right next to each other, then a simple box will have some overlap. So the Bounding volume hierarchy can be inefficient if you generate a lot of boxes with content in it that overlap to a large extent.