TU Wien Rendering #19 - Space Partitioning 1

Okay, so welcome to today's rendering lecture. This is going to be unit four. 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 Karai takes 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, perform some kind of light simulation, generate 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 generally, the Monte Carlo method uses ray shooting to sample the integrand of the rendering equation as shown the last time. So usually you have to compute the closest intersection with the scene. This is equivalent to computing the local visibility. So how far does a ray 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 scenes, say 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 they intersect. If you have millions of rays, you see that this is a quadratic explosion and you will not converge at 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 nonlinear 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 o. 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 are these triangles. And then if I have a ray that I know that it only travels through one half of the room, then I can immediately discard half of the triangles in my scene and don't need to intersect against them. So this approach, I mean it's bit more sophisticated than that, leads them to a sublinear complexity. Usually it gets close to logarithmic. 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 one 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. And 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 objects reside 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 objects lie in 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 are in 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 big 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 tree as 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. In 3D 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 and 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 subspaces here are rectangles in a volume they would be boxes. And you can do very quick intersection tests against boxes. And if you know that you are not going to intersect a 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 KT trees subdivide the space and then in the sub volumes the objects lie. Another approach, 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. Now they have advantages and disadvantages, otherwise you would only take the better1. So KD trees, they are usually faster for traversal on the CPU here, I mean 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 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 1/2 there, 1 half there. But cutting a lot of scene content is computationally expensive, so this would then degrade the performance of the KD3 generation. Bounding volume hierarchies are very popular for GPUs and multi core architectures. So the Xeon Phi, for example. So they got more attention in recent research because most of the current work tried to implement 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 KD Tree cuts the whole volume apart. And then if you have object moving from one sub volume to another, you would have to update the whole KD tree 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 A and B that are close together. So you generate your bounding volume hierarchy so they are grouped together at some level of the tree. 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 space is generated in between object A and B. So rays that travel exactly through this 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 put into different branches of the tree at a different level. But you don't have to do that. So in bounding volume hierarchies, dynamic themes just degrade your performance. But don't invalidate your whole hierarchy, because in KD 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 a highly dynamic scene can be very costly. 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 way. 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 those 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.