# TU Wien Rendering #19 - Space Partitioning 1

## Метаданные

- **Канал:** Two Minute Papers
- **YouTube:** https://www.youtube.com/watch?v=Ash4Q06ZcHU
- **Дата:** 30.04.2015
- **Длительность:** 14:17
- **Просмотры:** 7,529

## Описание

This lecture is held by Thomas Auzinger. Space partitioning helps us to alleviate the problem of intersecting a ray of light against every object in the scene. It turns out that we can often throw away half of the objects with every intersection test!

About the course:
This course aims to give an overview of basic and state-of-the-art methods of rendering. Offline methods such as ray and path tracing, photon mapping and many other algorithms are introduced and various refinement are explained. 

The basics of the involved physics, such as geometric optics, surface and media interaction with light and camera models are outlined. 

The apparatus of Monte Carlo methods is introduced which is heavily used in several algorithms and its refinement in the form of stratified sampling and the Metropolis-Hastings method is explained. 

At the end of the course students should be familiar with common techniques in rendering and find their way around the current state-of-the-art of the field. Furthermore the exercises should deepen the attendees' understanding of the basic principles of light transport and enable them to write a simple rendering program themselves.

These videos are the recordings of the lectures of 2015 at the Teschnische Universität Wien by Károly Zsolnai and Thomas Auzinger

Course website and slides → http://www.cg.tuwien.ac.at/courses/Rendering/
Subscribe → http://www.youtube.com/subscription_center?add_user=keeroyz
Web → https://cg.tuwien.ac.at/~zsolnai/
Twitter → https://twitter.com/karoly_zsolnai

## Содержание

### [0:00](https://www.youtube.com/watch?v=Ash4Q06ZcHU) <Untitled Chapter 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 um car takes over again so um spatial acceleration structures so where are we um the rendering pipeline as it was shown in the first lecture so we start with a 3D scene um perform some kind of light simulation generate a image out of it that's going to be displayed so spatial

### [0:46](https://www.youtube.com/watch?v=Ash4Q06ZcHU&t=46s) Spatial Acceleration Structures

acceleration structures are um Central to the light simulation because they increase the efficiency of Ray shooting so as you heard last time um Ray based uh 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 monticola method uses Ray shooting to sample the integrant of the rendering equation as shown 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 a ray um travel through the scene before it hits its first um object and this is usually very expensive for a large amount of SE objects because if you start with one Ray and you want to check does it intersect any of my SC say triangles then if you have millions of triangles then each Ray has to check all the million 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 in any reasonable time to a high quality image so the naive approach would be just to uh determine the intersection with each object so the object could now be usually triangles can also be um 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 um closest you have to go through all the object so it's a linear approach so the complexity is O of n a better approach would be to reorganize all the objects in your seene say the triangles in some kind of spatial hierarchy so that I know that say in the left half of this room is 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 um a bit more sophisticated than that leads then to a sublinear complexity usually it gets close to logarithmic so I mean this is a very old topic so this uh popped up very soon when um rate racing was used so there are many method IES that were looked into and two main techniques say are considered the State ofthe art so one

### [4:08](https://www.youtube.com/watch?v=Ash4Q06ZcHU&t=248s) Kd Trees

are KD trees and the other are bounding volume hierarchies so a kd3 subdivides the space itself so um your scene is situated in a surrounding space threedimensional and you then um cut this space into pieces as can be seen in this example on the right hand side here the space in which the OB objects reside is just a square and each object is just a point and as you see with um recursive subdivision of the space you um group the objects together in a spatially local um volume so 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 um 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 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 and if you have a lot of small volumes then this is inefficient the game so what you want to do is um 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 um 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 um the parts so the two sub volumes that you generated with the first cut and uh also try again to have 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 um rectangles in a volume they would be um boxes and you can do very quick intersection tests against boxes and if the 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 um 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 um 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 kt3 subdivide the space and then you have to um and then in the sub volumes the objects lie another approach uh bounding volume

### [8:37](https://www.youtube.com/watch?v=Ash4Q06ZcHU&t=517s) Bounding Volume Hierarchies

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 threee structure but this three structure now um depends on the triangles so the fundamental unit there is a triangle not a Subspace of your whole scene volume so um now they have advantages

### [9:14](https://www.youtube.com/watch?v=Ash4Q06ZcHU&t=554s) Advantages and Disadvantages

and disadvantages otherwise you would only take the better one so um KD trees they are usually faster for traversal on the CPU here I mean multicore 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 um does not have a special 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 um your um 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 but um cutting a lot of scene content is computationally expensive so this would then degrade the um the performance of The kd3 Generation Um bounding volume hierarchies are very popular for uh gpus and multi-core architectures so the CI for example so they um got more attention in the um in recent research because it is um because most of the current work try to implement um so the spatial hierarchy de generation on gpus or um other highly parallel architectures um 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 a 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 closed 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 uh spatial hierarchy gets more inefficient because say a lot of empty space is generated in between object A and B so tra uh Ray that travel exactly through this gap between them they would still have to check A and B if you would then um 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 tree at a different level but you don't have to do that so in bounding volume hierarchies Dynamic sces just degrade your performance but don't invalidate your whole uh key 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 U could be quite complicated because um traversing the tree for highight dynamic scene can be very costly um I mean due and another Advantage for Bing volume hierarch is that there are um that every object is only in one tree leaf I mean this is naturally because it's constructed that way but a um 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 see right next to each other then a simple box will have some overlap so the abounding volume hierarchy can be inefficient if you generate a lot of boxes with content in it that overlap to a large extent

---
*Источник: https://ekstraktznaniy.ru/video/14990*