 Some detail on bonding volume hierarchy. So, I mean, you take the object, say the triangles and group them somehow together. I mean, there are a lot of ways to do that. This is a combinatorial explosion. So you cannot just say, test each possibility and check which is the best one. So usually, this is seen dependent. So you don't know in beforehand which bonding volume hierarchy would give you the best performance. Because it could be that through the light propagation, light very seldomly enters, say, one half of the room. Because there is a wall with only a small hole. If you do not know that, then you would treat both rooms with the same priority and put them very high up in the tree hierarchy. But if light only travels very seldomly to half of the room, then you could make one huge note for only half of the room. And spend all your detail on the thing where actually something happens. So the same usually dictates what kind of hierarchies optimal. But this doesn't make too much sense to take this into account. Because if you have to run the light simulation to know what is the most optimal spatial hierarchy, then you have done the light simulation already. So you need to use some kind of heuristic that works for general scenes and build a hierarchy that optimizes this heuristic. And the most popular one is the surface area of heuristic where you compute a cost for the whole hierarchy and try to find the one with the lowest cost. And here, just to quickly show the formula, you can read this in detail in the references I provide on the last slide of the lecture. But here you sum up two components. So the costs of the inner nodes of the trees and the costs of the leaf nodes. Because as we already know, the object, so the triangles are in the leaf node of the tree. So all the intermediate nodes are just different groupings. So from fine to coarse. But they do not contain content. So they just say if I hit a bounding box of some intermediate node, then it tells me year my next level are these two bounding boxes continue with them. Then you check the next two bounding boxes in this volume and continue recursively until you hit all the leaf nodes that are appropriate. So that lie along your ray. And the costs. So there is a inner cost associated with getting from one bounding box to the bounding boxes that lie in it. And the cost of the leaf nodes, which are also the sexual costs of the triangles themselves. So see in this formula is the cost of checking which bounding boxes are appropriate for continuing through the tree. And the cost for the leaf node is the same for it. The TN is the cost for the triangle intersections. And now the heuristic enters via the surface areas of objects. Because the main assumption in this heuristic is that you have that race lie randomly in your scene. So you don't know in beforehand in which direction light will travel. So you just assume a random rate is tribution. And then you check how probable is it that a hit certain objects. So objects with a small surface area are less probable, larger triangles are more probable. And what you want to do is that you give very good groupings. As a groupings that have a high chance that you actually hit something in them or that you can exclude a lot of this. And this is here shown as a ratio of the surface areas. So AN is the surface area of node N. This is the volume of the bounding box which has a certain surface. And it's also dictates how probable is it that I hit this bounding box. And then you have the surface area of the root, so the level above. So I have my own bounding box at a certain level of the tree and my root that contains me is a larger bounding box that at least has the extent of my current one. But what you want to do is that you want to minimize this cost so that you want to have a large surface area of the root but a small surface area of your current bounding box. Because this means that you can exclude a lot of volume in the space. So if you're going through a huge bounding box and you want to decide where do I have to continue, then the smaller the continuation is, the more descriptive it is where the same content is. And then you want to have a small bounding box that is the same as the one for the final leaf nodes where the triangles are. And now you try to build a whole hierarchy that optimizes this cost. So this is not that you can decide at every level or at every level you decide what is the best ratio here that I can achieve. And then this gives you how your grouping has to be done. And there are different heuristics in the recent literature that take some more information of the scene into account. So for example, the surface area heuristic not only assumes random redistribution in the scene, but also assumes that they are infinitely long. So that they just travel through the whole scene and are not blocked by objects. This is taken into account with more sophisticated heuristics and there are references on this. And so, yeah, I have a dynamic scene, then the bound box can get larger. Yes, one object moves away. So a leaf node can be larger than its root because the two objects move from the bottom and so that leaf gets larger. Now you have to account for that. So you would have to update. You would have to propagate this information up the tree. Otherwise, it would fail, so to say, because if you do not hit the root node, yeah. I mean, this you have to propagate up, but it's the way of the propagation is clear. So it's just a grouping upwards till you have contained even with the dynamic update what's happening. But with KD trees, this is not so easy because the space itself is activated. So you have to somehow determine where is the object moving to in which other part of the tree, which is not simple because it could be that it moves into another leaf node. But the leaf node could be split already at the very top level of the tree. So to find the other leaf node where your KD tree object moves into, you have to go up and down the whole tree. So this is much more costly, much more complicated. Here you just propagated upwards till it's okay. So, I mean, the surface area of heuristic is just that, a heuristic, but it's still expensive to compute the optimal tree for that. So there is not necessarily a unique solution with the minimal surface area of heuristic, but there is one. And since this is expensive, there are also methods how to approximate. So not to develop a hierarchy with the optimal cost, but with one that's good enough for the purpose. And usually this is a trade off. So the more time you invest to build your spatial hierarchy, the better its quality gets. And in turn, the more efficient the light simulations. So if you don't spend a lot of time to build your hierarchy, you have bad quality, inefficient rate or virtual during the global illumination simulation. You are actual rendering takes longer. But if you spend more time on the hierarchy, then it has better properties for a propagation. So your lighting simulation is more efficient and it's faster. But you see that there is some kind of trade off. So I mean, if I and usually this is encoded and or start again, usually depends on how complex your light simulation is. So if I want to trace say 1000 rays, then the cost of this is very, very low. So I just need a, I can live with a very approximated hierarchy. So the hierarchy quality can be very bad, but because I shoot so less rays, I will not feel the difference too much. But if I shoot rate counts in the billions, then even a small increase in optimality of the hierarchy will give you significant gains in your rendering time. So what you see here in this graph, this I just showed that you get a feeling what are different methods there. I put the reference to the actual method to the actual paper where this is from right next to it. So what you see here are different methods on how to generate bounding volume hierarchies with the surface area heuristic. So as you see the blue line, the SPVH has very low call or start again. So what you see here is on the x axis, the number of rays that you will shoot in your light thing simulation. So that means that the more you go to the right, the more complex the light simulation is, the more quality you want of the final rendering, the deeper you go into reflection and reflection levels, things like that. On the other hand, on the y axis, you see how many rays the lighting simulation can trace per second. So that means that the higher you go up the y axis, the faster your lighting simulations. And now you have to find some trade off. So SPVH constructs very good spatial hierarchies, but it's also very slow. That means that for lighting simulation that only use a few million rays, the performance is very bad. Because most of the time is taken to build a spatial hierarchy. So the press, the edge, it takes longer to build the hierarchy than to do the actual rendering, which doesn't make too much sense. But if you go into the into one, the other is for computing your final image, then it starts to pay off because you have a very high performance. So you can trace in this example on the hardware, 400 million rays per second. BL, BVH, HL, BVH, on the other hand, is a method to quickly get a spatial hierarchy that's not very optimal. So you see that for scenes with only a few million rays, you already get close to the final performance. 200 million rays per second, and you are much faster than SPVH here. But the more rays you shoot, the more you are heard by the missing optimality of your hierarchy. And it's that there is some kind of sweet spot around 10 giga rays where SPVH gets actually better than HL, BVH. And in this paper, they propose another method that is faster to construct. So you see it in the green dotted line. So you quickly, it already gives a significant performance, increasements, even for smaller simulation. So already at 100 million rays, you are better than HL. And you get, but you get quickly close to the performance of SPVH. So this is in this paper, this shows that, yeah, they found a very good intermediate method that's only a bit less optimal than the state of the art before. So I advise you to look into this paper. You see a lot of interesting things there. So how to port BVH, a construction on the GPU, parallelization issues, and other smart tweaks. So I give you a literature. So in PBRD, it's the chapter four. And since this is inherently a geometrical problem, so you want to know where are triangles in the scene, the same hierarchies can also be used for collision detection. Because for collision detection, if you want to know, could two objects collide, then you have to be spatially near to each other. So if I know that they are far apart already in the, through the bounding boxes of the tree, then I can ignore this and not compute the exact intersection between them. And there are several papers here. So the work of IngoVide, more or less, started this whole business in this thesis. And then I also give some recent papers that usually looking to how to do this fast in the GPU. So this is more or less the current trend now. There are also upcoming works to do the same on this Intel, many core architecture, so the Xeon file. Good. This concludes the first part of this lecture. Are there any questions? If not, then I continue with something completely different now. I mean, this is a very technical topic. If you want to implement it, then you have to look into the papers anyhow, because I cannot layout here all the issues with coding. I mean, it would be super boring. And on the other hand, it's also the surface area heuristic in itself has proved worthful. But I mean, there are a lot of different approaches. So approximation of this small part, approximation of this small part. So there are many papers that focus on different partial problems in the whole in the whole research problem. So going through a lot of literature is also suboptimal because due to the rapidly increasing hardware capabilities, the tunnel is also quite fast. So things that were super smart approaches say four years ago, do not cut it anymore because GPUs now have completely different functionality and can do certain aspects more efficiently. So this is a rapidly developing topic since years already. So if you want to implement that, have a look at the current literature. There are a few standard papers like the one of the of IngoVide, which have lasting contributions, but mostly in between are small optimizations that are focused on things that are perhaps not relevant anymore. Okay, good. Let's put this.