TU Wien Rendering #20 - Space Partitioning 2

Some detail on bounding volume hierarchies. 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 scene dependent. So you don't know beforehand which bounding 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 node for only half of the room and spend all your detail on the thing where actually something happens. So the scene usually dictates what kind of hierarchy is 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 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 objects or the triangles are in the leaf node 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 here 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 an 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 intersection costs of the triangles themselves. So C 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 rays lie randomly in your scene, so you don't know beforehand in which direction light will travel. So you just assume a random rate distribution and then you check how probable is it that I 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 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 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 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 go into 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 scene content is. The same is done 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. 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 ray distribution 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, yep, if I have a dynamic seam, then the bounding box can get larger. Yes, because one object moves away. So a leaf node can be larger than its root because the two objects move apart from Another 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, I mean this, you have to propagate up, but 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 subdivided. 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 KT3 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 propagate it upwards till it's okay. So I mean the surface area heuristic is just that, the 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 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 simulation is. So if you don't spend a lot of time to build your hierarchy, you have bad quality inefficient ray traversal during the global illumination simulation. So your actual rendering takes longer. But if you spend more time on the hierarchy then it has better properties for ray 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 it depends on how complex your light simulation is. So if I want to trace say 1,000 rays, then the cost of this is very, very low. So I just need, 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 ray 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 I just showed that you get a feeling what are different methods? I put the reference 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 quality. Or start again. So what you see here is on the X axis, the number of rays that you will shoot in your lighting 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 refraction 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 simulation is. And now you have to find some trade off. So SPVH constructs very good spatial hierarchies, but is also very slow. That means that for a lightning simulation that only use a few million rays, the performance is very bad because most of the time is taken to build the spatial hierarchy. So for spdh, 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 1 Tera rays 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 their hardware, 400 million rays per second. Hlbvh, 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. So 200 million rays per second and you are much faster than SPVH here. But the more rays you shoot, the more you are hurt by the missing optimality of your hierarchy. So that means that there is some kind of sweet spot around 10 gig arrays where SPVH gets actually better than HLPVH. 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 significant performance increasements even for smaller simulations. So already at hundred million rays you are better than hl, 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 here how to port pvh, construction of the gpu, parallelization issues and other smart tricks. So I give you the literature. So in pbrt it's the chapter four and since this is inherently a geometrical problem, so you want to know where are triangles in a 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 they have to be spatially near to each other. So if I know that they are far apart already through the bounding boxes of the tree, then I can ignore this and not compute the exact intersection between them. And then there are several papers here. So the work of Ingo Walt more or less started this whole business in his thesis. And then I also give some recent papers that usually look into how to do this fast on 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 Phi. 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 lay out 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 turnover 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 ingowt, which have lasting contributions, but mostly in between are small optimizations that are focused on things that are perhaps not relevant anymore. Okay, good, that's for this.