Intro to Graphics 19 - Ray Tracing

well hello everyone and thank you for joining us for another lecture for introduction to computer graphics today our topic is drum roll ray tracing yeah so we we started talking about different rendering algorithms we landed on rage racing so we're gonna spend some time on ray tracing today and and next time as well uh so we're gonna we're gonna finish up our discussion on rendering by talking about all sorts of stuff that is sort of related to ray tracing so today i'm saying the topic is retracing but mostly we're going to be talking about ray intersections um i'm also going to talk about other other stuff that's related to ray tracing that's that's our topic all right so uh let's start with remembering remember this what we're trying to do is that we're trying to render an image using a camera that we're seeing through this this um the screen and we have a whole bunch of triangles in the scene and we're going to be using raytracing to render that image all right so for any point on the screen we're going to be generating a ray that originates from the camera and goes through that point and i'm going to trace that ray and find out which of our scene primitives it hits if if anything and if it hits anything then we're going to shade that point and we're going to set that set the color of that pixel to that point and we'll be done right so that's that's raytracing in a nutshell and that's what we're going to be doing but let's start with red red so what's array array is a point or an origin so it has a position let's let's call it origin of the ray and it also has a direction so array is defined by a point and a direction for for the purpose of computer graphics array mathematically speaking is just going to be half a line right so in that sense you can think of this as the the structure that defines this half a line right so it's start it starts at this position and it goes in in this direction right so half a line this half mathematically speaking you can think of this as a position and a direction and that position and direction sort of defines this this whole half line over here right for any point on this ray any point on this ray let's call it x we can write x as a combination of this position and direction right so starting from this position if i start from this position p if i go along the direction of d enough i can reach this point x right so if i were to write this position x as a combination of these two i'd say i start with this position p that's the ray origin and i travel along direction d by the magnitude of t t is just some scalar value that tells me how far i need to go from p to reach x so often times people think about this t as the distance between this position p and this position x right and it can be the distance only if this d is a unit vector if it's a unit vector then t is the distance right if d is not a unit vector that t just tells me how many multiples of d i have to go to reach x starting from point b when t is positive when t is positive we're going to be on on this side of the ray i would say we're going to be in front of the ray right in this side of the array so we're going to be on the mathematical ready uh actually i believe mathematical array also includes um the point where t is equal to zero so at this point where t is equal to zero this term cancels this term cancels out so we're left with p we're going to be exactly at the ray origin and if t is negative then we're going to be on the back side of the ray we're going to be i often refer to this as we're going to be behind the array right so x is going to be sort of behind right on the backside of the array if t is negative uh but oftentimes when we're doing ray tracing we're going to be interested in positions that are going to be in front of the array that are going to be represented with t values that are that will be positive not even zero often times we're not interested in things that are at t is equal to zero because if i have this ray you know i'm at this position anyway i will be interested in stuff that is in that direction but not exactly at this point right so we're going to be interested in stuff that's going to be t greater than zero all right so what am i going to do with this red i have this ray what am i going to do with it i'm going to take this ray and i'm going to see if this ray let's say this ray that i generated from my camera and going through a sample on my screen i'm going to check if this ray intersects with any of the objects in my scene right that's what i'm going to use this ray for so the next thing to look at of course now that we have a proper definition of what the ray is the next thing to look at is to see how we can compute intersections of this ray with our scene objects right so very intersections let's start with the the simplest thing like we're going to be intersecting this ray with let's say surfaces right uh remember when we talked about surfaces the one of the first things that we mentioned was implicit surfaces right so let's start with the definition of implicit surfaces and how we can handle implicit surfaces using ray tracing implicit surfaces are not easy to render using rasterization all right with rasterization we were taking triangles we're projecting triangles but if i have an implicit surface that is defined by a function like this rasterizing this is very very hard actually i don't even know if it's possible like in some specific cases we might be able to do that but in general no that's one of the reasons why our rasterizers that run our gpus will be just rendering triangles right but with raytracing we can actually easily handle implicit surfaces so all i got to do is to make sure that a point on the ray can be represented using this function so if there exists a point on the ray that satisfies this function that satisfies the definition of an implicit surface then that point on the ray is also a point on the surface that means my ray intersects with that implicit surface right so that's all i got to do is to write this equation that's a that's a point on the right and check if if these two equations can be satisfied that is if i take this if i take this x and replace it with with this form that is if i can write this that means that my ray intersects with with this implicit surface that is if there exists any t value if there exists any t value such that this equation is satisfied that means that my ray is intersecting with the implicit surface that means it's a hit okay but if this equation is not satisfied if it's always non-zero uh for all possible t values if that is the case then i'm going to say that no that there's no hit that means that my ray is not intersecting with the implicit surface simple enough right so you can literally take any implicit surface definition and use this approach to find ranger section intersections with the implicit surface uh although although implicit surfaces can have quite complicated functions here so figuring this out as simple as it might seem can be a little bit tricky so let's see an example of this with a relatively simple implicit surface definition that is actually used quite often with ray tracing that is going to be an implicit sphere so let's take a look at race sphere intersection using implicit definition of a sphere all right so an implicit sphere of course has this this function so what's the function for implicit sphere what's the sphere function you must have seen this a million times we have even talked about this earlier like x squared plus y squared plus z squared minus r squared is equal to zero that's the uh sphere equation right but i like the vector form i like the vector form of this equation i like writing it like this that x dot product with itself x being a vector dot product of itself minus r squared is equal to zero i find it more intuitive but this is specifically a sphere that is at the origin right if the sphere is not at the origin that is if its centered position is is not the origin of my coordinate frame then this equation will turn into this equation right this is this is the scary question that i i like looking at but i like this because like any position x on the sphere will of course satisfy this equation but i like writing it this way because i find it quite intuitive and if this doesn't look intuitive to you let me make this intuitive for you right so i i would like you all to like vector equations because if you write things in vector form and if you understand those vector forms i you will see that there are a lot more intuitive than the scalar equations written for 3d objects so for this equation any position x satisfies this equation right so what is the position x position x you can think of this as a vector from the origin towards a point on the surface right so what's the what is this vector from the origin to a point x on the sphere it's x minus c right simple enough good so tell me what is the definition of a sphere a sphere is a collection of points that are that are equal distance away from the origin right just collection of points that are equal distance away from the origin so any vector starts from the origin goes to a point on the surface any vector should have a constant length that length is the radius of the sphere right so i can i can write a sphere like this right this whatever this vector is so x is the position on the sphere minus the origin the length of this vector has to be a constant that's the radius of the sphere right simple enough so what is this length length of a vector line to a vector by definition is the dot product of that vector with itself square root right so this is the length of a vector that's the definition of a lack of a vector and and this if i take this the square of both sides i'm going to get this right that product a vector by itself is equal to r squared well guess what it is exactly this equation so this is this is what this equation says not nothing else so if you really understand what this equation says it's really really intuitive right that that's why like vector equations also there are a lot more compact than the scalar forms so okay let's put all this stuff away we're going to talk about ray intersections with a sphere so i let's say that i have a ray and that ray goes through a point on the sphere i'm gonna call that point x and i would like to be able to find that point x and i would like to be able to check if this ray intersects with the sphere at all right so the equation the parametric equation for x any point x along this ray i can write it like this right we talked about this x is equal to p plus sum t times d right so that's for any point along this red so if i take this and put it up here and replace all x's with p plus t i am going to get this equation simple enough all right so next step what i'm going to do is i'm going to take these components with with t and move them to the side i'm just blowing them around nothing else and if you expand this if you do this this dot product component by component dot product multiplication you if you expand this you get this equation all right so what do we see what do we see here in terms of t in terms of t i see at the all the way here there's a t squared term there's a t term and there is a constant term so this looks like a polynomial of t a polynomial of degree two so this is a quadratic polynomial of t right so what does that mean a quadratic polynomial you must have seen this in the uh when you're where you're investigating a quadratic polynomials in math classes a quadratic polynomial is equal to zero so this is going to have at most two roots right so there's going to be two different t values two different values for t that might satisfy this equation so maybe there's going to be no root that no t value satisfies this in in this case that will mean that our ray does not intersect with the sphere or that might be up to two different t values that will satisfy that will satisfy this equation and if you look at this this geometrically it makes perfect sense because if i have a ray that goes through a sphere l the ray will go into the sphere from this point and it will come out of the sphere from the other end right so there's going to be another t value where this ray is going to come out that will correspond to another point so what does that mean if i have a single value if i have a single root that would mean that these two x and x prime points that's actually one point that means my ray is is tangent to the sphere that's what it means okay so it makes perfect sense that we are getting a quadratic polynomial here as our solution because there are two roots so we should expect to get a quadratic polynomial for a sphere because of that because there are two roots and and we did so everything is good so let's simplify the notation of this just a little bit so i'm going to call this term a it's just a scalar right dot product of d by itself it's it's going to give me a scalar value i'm going to call that a i have another dot product here to the p y and c that's i'm going to call that that scalar value b and the remaining scalar value that's also another scalar value that i'm going to call it c so it goes into this very very familiar form for a quadratic polynomial a t squared plus bt plus c is equal to zero so what's the solution for t most of you should know this this by heart by now that's the typical quadratic formula that's minus b plus minus square root of delta uh with 2 divided by 2a and delta is equal to b squared minus 4ac right so this is the the standard quadratic formula this is the solution of any quadratic equation and we can easily use this to solve our problem so what is this what this is going to do is it's going to give us the t values where our ray will be intersecting the sphere and if i know the t values i can find x right if i know t i already have my ray formulation that i already know my rate origin and rate direction so i can easily compute the position x that's on this this sphere surface so that's all i need to know i just need to know the t value so um but here's the thing my ray may or may not intersect with the sphere how would i know if the ray intersects with the sphere i will know by looking at this delta right so delta here has to be positive or zero it cannot be negative for us to have a real root if delta is negative then i'm going to have an imaginary root but in this particular problem i don't care about imaginary numbers that's all i care about is real values for for t imaginary values of t i have no idea what that means geometrically so i don't care about that so if delta is negative i don't have a root i don't have a real root anyway so that means my rate is not intersecting with the sphere so if delta is negative i am going to say that there is no hit right there is no real value of t where this ray is going to intersect with the sphere that means i could not find the real solution for this equation if delta is equal to zero or a positive value then i will say that i found a hit that and i know that my ray intersects with the sphere and depending on the value of delta i may have one or two intersections right so um depending on the delta i can say that my array intersects with either one point that's going to be tangent to the sphere or the ray goes through the sphere that means there'll be two roots but there are two solutions right now i need to figure out which is the one that i want because this is plus minus which one do i pick actually in this case the answer is quite easy in this case i will always want to pick the one with negative here the reason for that is if i look at the other one the other one um the other intersection that x prime that is going to always have this this positive version and why is that now the closest hit point the the one that's closer to the ray origin is going to have a smaller t value right a smaller t value if you look at these two equations the only difference is the sign over here this minus and this is plus obviously and i know that square root of delta which is a positive value this is a positive number and a is also positive you know what is a a is uh this guy right this this guy that is the dot product of the dot product of d with itself that means it's the length of d squared the square of the length of d well the length of d is obviously positive square of its length well square of any number is positive so it's that's definitely positive in fact in most cases this d is going to be a unit vector and if it's a unit vector its length is one so the square of its length is one so a is in most cases going to be 1. so this is going to give me a smaller t value than this one so this is going to give me a larger t value this is going to give me a smaller t value so if my ray origin is outside of the sphere if my ray origin is outside of the sphere then this one with minus is going to give me the very first hit the very first intersection of the ray with the sphere and this one is going to give me the next intersection right and if i if i'm rendering a sphere and i want to see what's outside of the surface then i will always be using this one always be using this one i will never be using this one except if my ray origin is inside the sphere and i want to see what is inside inside this sphere surface i'm inside this first surface um i'm inside the sphere and i'm looking at this here surface from the inside and i want to see that the inside part of the sphere surface in that case i'm going to be using this guy right but for most applications i won't care about that part i will only care about the outside surface of the sphere so i will be using this one let me answer before you ask uh for the project we will be interested in the outside of spears and we will be using this one for the upcoming raytracing project all right so um yeah that's that's about it this is the entire sphere intersection it's just an implicit surface we took the definition of a ray and we put it inside the sphere equation and we did the math and we figured out where the roots were and we found out which root we're interested in and there it is and if i if i know t then i can compute this point x easily and i can compute the surface normal at that point x right at the surface normal at that point x is going to be in the same direction as x minus c right that the vector from the center to the point x on the surface is going to be my surface normal vector for the sphere so um i found the position i found t that means i found x that means i could find i could compute the surface normal and i have everything i need to start doing my shading right most probably for most applications anyway i haven't told you how to compute the texture coordinates but it's uh it's a whole other thing uh that depends on how you're mapping the texture so don't worry about that all right so this is ray sphere intersections simple enough not too hard right let's take a look at one more thing before we we continue let's take a look at another implicit surface that's going to be a simple implicit surface it's going to be the great plane intersection so in this case i have a plane that's defined by this normal so does anybody remember the vector equation for a plane it's going to be this guy the implicit equation for a plane is going to be x dot product by n minus c is going to be zero so that's the emphasis equation for any plane any infinite plane and what i'm interested in is finding the intersection of array computing the intersection of array with this plane and finding where this this ray intersects with the plane all right so we're going to do the exact same trick so my ray equation parametric equation any points x along the ray defined by p plus td i'm just going to take this i'm going to put it inside the implicit equation for a plane and that gives me this formula all right and here t is the only unknown i know everything else i know p i'm d i know n i know c i know everything else i just don't know t and as you can see in this case this is a linear equation right there's nothing complicated here i don't need the quadratic formula even this is linear and just uh move things around with some very simple algebra you can actually find that t is supposed to be this all right simple enough all right there's one caveat here there's one little thing that you kind of need to be careful about does how do i know whether or not my ring intersects with this play right so it seems like this always intersects right there's always a solution there isn't always a solution there's a very specific case where the ray will not be intersecting that's right the ray will not be intersecting with the with the plane that is when this denominator is zero right if this is zero then i'm not that t is going to be infinity right so that's that's not gonna fly yeah that means my brain is not intersecting with the plane so what do i do what does that mean d and n if i take the dot product and that's zero that means these two vectors are perpendicular to each other right so that means that i have a ray that is perpendicular to the plane normal its direction is perpendicular to the plane normal so this ray will not be intersecting with the plane right and if that is not the case i just need to check that special case if that's not the case i'm going to say yes it intersects it intersects with the plane and at this t value whatever that t value is right simple enough very very simple right it's a lot simpler than all right it's it is simpler than the sphere equation maybe not a lot simpler the sphere equation was relatively simple as well so but this is even linear i only have one one root and that makes perfect sense because array cannot intersect with a plane more than once right it makes no sense uh so geometrically it makes no sense so it it's perfectly understandable that i'm getting a linear equation here and i'm getting a single root 14. good all right actually there's something a little bit simpler than this even that is if this plane is not just an arbitrary plane but it is an axis aligned plane if this is an x to the line plane that means my surface normal here my plane normal is either x direction y direction or z direction or negative x negative y together e right so let's say that is z so let's say that this is my plane normal zero zero one and c can be any value i don't care about c it just means it's just going to determine where the the plane is it's its altitude if you will and that n is my uh surface normal so what happens in this case in this case the dot product simplifies a little bit right because i have zero zero one so this dot product of p dot n will give me just the z component of p and this is going to give me just the z component of d right so it's going to be just this fairly fairly simple now i want to just spend a minute here just talk about what this means geometrically what's the what's the meaning of this now if i'm interested in the z component of d it is this magnitude here like if i just take the z component of d it is this vector right this kind of small vector this big and c minus p z is going to give me where this plane is in in the z coordinate and where this point is and the difference between the two is going to give me this length so this whole length divided by this length is going to tell me how many times of this length i need to go until i go from this point all the way down to the plane right so i'm just dividing it by that magnitude and of course that's going to give me the t value so that's the geometric interpretation of what's going on here all right so um planes infinite planes and spheres are two of the very few implicit surfaces that are commonly used for with ray tracing because they're they're very very useful and they're also fairly easy to handle with with ray tracing they are used in practice but the the most common primitive that we will be using for rendering with or without rage racing is going to be triangles right so the more interesting bit here is how do you compute intersections of triangles with with rays because that's going to be the main operation that we will be using when we're rendering triangular meshes and since we're representing most objects using triangular meshes this is the operation that we will be doing very very often in a in a ray tracer this is a very old problem it's been around as long as ray tracing has been around back in the 80s when people were very much interested in raytracing this operation was expensive just doing this was very expensive computationally expensive and you're doing a lot of this too i have a lot of triangles in my scene i need to check intersections of rays with my triangles so i'm doing this operation a lot of times when i'm rendering so this is an operation that i really really really needed to optimize uh that's why people looked into this a lot and they figured out actually many ways of computing this and many optimized ways of computing this and i have no intention of going through all of them but i'm just going to give you the intuition of how this works just one way of how you could compute this as a but i want to give you this disclaimer that are there are many ways of computing this and with different advantages and disadvantages uh one of the most popular ones use this idea so if i have a triangle if i have a triangle using these three vertices of that triangle in space these three vertices will define a [Music] a plane right so what i can do is i can compute the intersection of this ray with the plane that is defined by these three vertices right and if i if i i know how to do this right we just talked about this all i want you to know is the the normal of this triangle and i can compute the normal of a triangle by you know take two edges two edges do a cross product that will give you the normal direction right and i can fit it in the plane equation to get the constant c so i can easily build the plane equation the implicit plane equation from three vertex positions of a given triangle and if i have a plane equation then i can easily do the right plane intersection and i find out where the hit point is but that doesn't tell me that my rate intersects with the triangle it only tells me that where the ray intersects with the plane with the infinite plane after that i need to check whether that intersection point x here is inside that triangle that's all i need to check um and one way of doing this is computing the barycentric coordinates of x inside that plane so it turns into a 2d problem now because now that now we're on this on this plane so you can convert this into a 3d problem and take you can look at it as a 2d problem and in that 2d problem i have a point on this plane and i'm checking whether or not that point is inside the triangle and for any point on this plane i can compute the very centered coordinates we talked about percentage coordinates we talked about how they correspond to the areas defined by different top triangles using those areas that's one way of computing the percentage coordinates i can compute the paracentric coordinates and then by looking at the very centric coordinates i can tell whether or not the point is inside the triangle um because if any of the percentage coordinates components if any of them are outside of the the range 0 and 1 that means my point is going to be outside of the triangle if all of them are between 0 and 1 that means my point is inside the triangle right so that's one way of doing right triangle intersection and it's a very very common way of doing right triangle intersection there are different variants of this as i said people try to optimize this quite a bit over the years that i believe the the most optimal version includes only one division operation because division is more expensive than other operations especially back in the day it was considerably expensive it moves that division all the way to the end of ray triangle intersection and you have to do the division only if you know that the triangle intersected with the ray just to find the intersection position and its very sensory coordinates anyhow that's one way of drawing a one actually quite popular way of doing right triangle intersection i'm skipping the mathy details over here because i don't think that those math details are that important i just want you to understand the general idea of how you would approach a problem like this right and the way you do that is finding the section with a plane and then check if that intersection is inside the triangle right that's all i want you to get out of this entire discussion all right so that's the right triangle intersection and if i can do a ray triangle intersection since i'm representing anything as triangles i can render anything right all right let's see let's see how we do that all right we're doing great racing i have a camera i have there's an image that i want to generate so what do i do with ray tracing for each pixel sample for each pixel sample let's say this guy this guy for each pixel sample i am going to be generating array and then i'm going to be tracing that right so let's let's not call it a pixel sample let's call it an array right because that pixel sample will will define array that this way specifically so let's call it ready for each ray i'm going to find the closest primitive right so how am i going to do that i'm going to you know i'm going to look at my scene i'm going to find the the hit points but but the the important thing here is that i need to find the the closest one all right that's that's the important bit here and once i find the closest one in this case it's going to be this red sphere once i find the closest one i'm going to shade that closest one and that's how i can find the color that corresponds to this pixel all right so for each ray find the closest perimeter um okay this is a little hmm how am i going to do that well the simplest thing you can do is just look at all primitives and see which ones intersect with the ray right so just find the closest primitive i can convert it to a for loop right for each primitive for each primitive what am i going to do for each primitive i'm going to check if the ray intersects with the primitive for each primitive if the array intersects with the primitive oh i also need to make sure that it is the closest one because i'm going to look at all of these right i'm going to look at all of them and and then i also need to check okay if i found a hit is this the closest hit because i might be looking at these spheres in any order i don't i don't know what order i'm going to be looking at in this for loop so i need to do this this loop and look at all the primitives and um for each one that intersects with my ray i'm going to check if it is the closest hit and if it is the closest hit i'm going to record it and keep it somewhere i'm going to keep looking at all the other primitives and after only after this loop is completed that's when i know that yes i found the closest hit now that i found the closest hit now i can shade it all right so that's how this is going to work i'm repeating this and i'm explaining this sort of slowly because this is exactly what we are going to be implementing for our upcoming projects right so i i know this may sound trivial to some of you now that i've explained it but i'm going to repeat it again because this is what you will be implementing so here's what we're doing for each ray and for a given ray let's say i'm going to be looking at each and every one of my primitives in the project that's going to be a set of spheres i'm going to be looking at each one of my primitives and then if the ray intersects with that primitive i'm gonna check if it is the closest it or if one of the earlier primitives had a closer hit if it had a closer hit i don't care if it is the closest hits so far i'm gonna keep a record of this and when i'm done when i when i'm done looking at all of the primitives that's when i know that i found the closest hits and that's what i'm ready to shade so when you find a closest primitive you need to you need to take a note of what that is i need to know what that point is and what the surface normal at that point is and and all those details everything that i will need to be able to shade that point that's what i'm going to be saving okay now in this example i have two spheres fairly simple right for the projects we're not going to have too many spheres that's going to be fine too but in general in general i might have quite a lot of primitives is there a faster way of doing doing this yes there is because we need a faster way because um in in a scene i oftentimes i'm not going to have just two spheres or just two objects just two primitives in a typical scene i'm gonna have millions and millions of primitives right and um you know imagine their in production scenes even in scenes that are used for video games too and for real-time rendering on the gpu you'll have a ton of triangles right so if i were to do this for loop in this brute force manner look at each and every primitive and i do that for every ray how many rays do i have even like one of the lowest resolution screens that we use today let's say it's 1080p in 1080p you have more than a million pixels right and in 4k you'll have a lot more so you have so many you you had millions of rays and you had millions of primitives million times million is this was what this thing looks like this is not going to finish anytime soon this is going to be massively slow this brute force way of doing weight racing is going to be massively slow so no we cannot do that and that's what we're not doing this uh we're doing things that are uh better than this that's going to be about ray tracing acceleration it's a very very important topic for ray tracing this is how we have ray tracing that actually runs in reasonable time and we're going to call these acceleration structures or space partitioning structures because they will be working with partitioning the space let's let's talk about those ah so here's my problem i have a scene with a bunch of spheres more than one all right all right i i didn't sorry i didn't have the patience to actually draw a million spheres here but just as imagine that this is a very large number i know this is not a very large number but let's use your imagination that this is a very large number a lot of spheres um now here's the thing i if i want to do this brute force computation that i want to check the intersection of my ray with all of these spheres that is going to take a long time but but if i know where these spheres are maybe i can take a shortcut for example if i know that these spheres just spin in a box i put all these years in a box or actually i can i built a box that will contain all of my spears if my ray does not intersect with the box if my rig does not intersect with the box it cannot possibly intersect with any of the spheres right i mean all my spheres are contained inside this box so if the array does not intersect the box then it is not going to intersect with any of my spheres so and this is the kind of shortcut that we're going to be using for accelerating ray tracing um and the kind of box that i would like to use is a special box that is going to be an axis align bounding box a bounding box meaning that it is bounding everything in the scene and it is axis aligned that is uh each one of these six planes that form the the ends of my box they are going to be axes aligned planes right and there's a good reason for using axle line planes for defining this axis align bounding box because we just talked about this a few minutes ago i can easily do a raid plane intersection but if my plane is an axis aligned plane then great plane intersection simplifies quite a bit and a exit line boundary box is just six six plane intersections so computing the range sections with an extra line bounding box is just going to be six plane intersections i'm skipping the details of exactly how to do this because that that's the whole point that i would like you to get the difficult part is just doing the six plane intersections and then you sort of sort all the t values that you get and you figure out whether or not ray intersects with the bounding box it's fairly easy to do after you do the right plane intersections so with six axis aligned plane intersections which is actually very cheap right we talked about this it's very simple axis of line plane intersection is very simple so this axial line bounding box intersection with array is a very fast operation very cheap operation and i can fit millions of spheres inside this bounding box and uh you know that simplifies my brain intersections with my scene that contains millions of spheres only if the ray does not intersect with the box right if the ray intersects with the box then i'm in trouble okay um maybe it wasn't a great idea to put all of my spheres into one box right maybe that was not the best idea i have millions of spears or millions of primitives and i dumped them all inside one box that was not the best idea so how about how about we put some spheres in in one boundary box and the rest of the spheres in another boundary box so i can i can just do two box intersections instead of one box intersection still you know it's relatively cheap it's just box intersections and i have you know fewer spheres per box so it's even for the better actually even better than that i can take these two boxes and i can put them inside a larger bounding box that contains both of them what about boxes and boxes that's exactly what it is so i can just have a box here that contains everything and if my rate intersects with this box that's when i'm going to go in and check the smaller boxes right so that brings us to a very very popular acceleration structure used for ray tracing uh today that is a bounding volume hierarchy bounding volume hierarchy is just a hierarchy of axis aligned bounding boxes bbh there are other acceleration structures used in ray tracing which were very very popular in the past but today when we think about ray tracing almost always we use some form of bbh there are different versions of bbh so that's by far the most popular acceleration structure that we use today with the bounding volume hierarchy what we have is a box that contains my entire scene everything i just put my millions of primitives inside this box everything lives inside there and if my ray does not intersect with it that means it doesn't intersect with anything in my scene i can just throw away that ray go to the next ray very cheap very fast i'm done if the raid intersects with it then i'm going to look at the boxes inside this box right so the box is inside this box i'm going to check both of them if it is if it doesn't intersect with let's say the blue one blue one's gone i don't have to look at the blue one ever again if it doesn't intersect with the green one either then i'm done but if it intersects with one of them or or both of them it might then i'm gonna have to go in and look at the boxes inside there right uh and and then i'm gonna be looking at those boxes and you know this can go down as far down as it needs to and in the end in the end this is going to define a what looks like a binary tree to be fair this doesn't have to be a binary tree but it forms a tree structure like this oftentimes when people say bvh they mean the bvh that forms a binary tree but it doesn't have to be a binary tree there are cases where we use trees that are not binary trees like this that is trees that have more than two nodes that is boxes that contain more than two boxes inside but anyhow this is the general structure of a dvh it's just a tree structure most acceleration structures actually are going to be some sort of tree structures you know we're going to be traversing some sort of tree and bbh is today the most popular acceleration structure we use for for ray tracing just to reiterate the way this is going to work is that if i have a ray i'm first going to check if there intersects with this root bounding box if it does then i'm going to check its two child nodes if it intersects with with one of them then i'm going to go down and check it's it's child knowledge child node all the way down to a leaf node that leaf node is going to contain the original derivatives whatever my primitives are if there are spheres it's going to contain spheres if there are a bunch of triangles it's going to contain a bunch of triangles right and if i have a single object that has a million triangles in it i'm just going to take a single object i'm going to split it into pieces like this such that each one of my leaf bounding boxes leaf level at the very bottom leaf level bounding boxes will contain about a handful of triangles only how do you sign up group them is their strategy i am not going to talk about this that's a that's a big topic actually there are good ways of building the structure there are bad ways of building the structure if you build this in a very very bad way actually your acceleration structure will still probably help a little bit but it's not going to help as much but if you build this structure carefully and i'm not explaining you what careful means if you build this carefully and not necessarily optimally but you know close to optimal way uh i i keep using the word optimal although i don't quite like using the word optimal because optimality is not really well defined in this in this problem if you if your data structure if your dbh is good then your ray tracer will perform very few gray triangle intersections in the end very few how many about on average it will perform only a handful of ray triangle intersections yeah that true so i have millions and millions of triangles and i'm gonna be testing let's say four of them before i find before i find the hit because when you think about it in a scene that i have a ray that hits an object that object that the ray will hit just one of its triangles right array will not hit all of the triangles of an object it's going to hit one triangle maybe two triangles maybe one triangle on the back side as well but if you traverse the structure in a careful manner you can find the closest one you can immediately find the closest one or you can find the closest one earlier than the other ones by first building it carefully and then traversing it carefully you can avoid the extra unnecessary cost of looking at all the other triangles which will return false when you try to do intersection tests so you can skip all that you can only find you can only look at triangles that have a high possibility of intersecting with the ray and they're they're not that many triangles that will have high probability of intersecting with a with a given ray and if you build your data structure carefully you can avoid all that computation but to be able to do that you're gonna have to do a whole bunch of great box intersections right if i'm only doing a handful of ray triangle intersections that means i'm doing a whole bunch of raid box intersections yeah so that's the the cost but i am building a hierarchy here so so this this becomes a logarithmic search problem right uh so in logarithmic time you can find the triangles that can possibly intersect with array so the the whole complexity of ray tracing can be reduced significantly using this how do you build this that's a whole topic of its own and i am not planning to get into this yeah there are different strategies for for building the street you can build it from bottom up or top down there are different strategies but there are methods that especially for bbhs we can today we can build them very very fast and we can maybe not get the the best possible bbh but we get a reasonably high quality bh but we can build them super fast that building a higher quality bbh that would give you a better performance is not worth it because it will take a longer time to build that higher quality bh as i said it's a big topic and that's why i'm not getting into the details of that all right so this is where i'm going to end this conversation as i said there are different data structures actually last year my students and i proposed an alternative data structure to bvhs that performs faster than ddhs also takes up less memory and this year we talked about how to implement this in hardware so it really outperforms any kind of bbh so there's still research going on in this topic is what i'm trying to tell you and there are different data structures that are not necessarily deviations but pbhs are today the most popular data structures used for accelerating ray tracing all right that's where i'm ending this conversation but don't worry about the project we're not going to be implementing a bbh we're not going to have that many spheres to render so don't worry about it all right let's move on to our next topic which is going to be gpu ray tracing with hardware acceleration this is not going to be acceleration structure this is a hardware acceleration it's a topic that i thought that i must at least mention and in today's gpus today's modern gpus we have hardware hardware units that are designed for ray tracing even though this gpu by and large is designed for rasterization there exists hardware units nvidia calls them rt cores ray tracing cores that are designed for doing ray tracing specifically so we talked about the rasterization pipeline on the gpu we said we had a vertex shader at the output of that goes to rasterizer and the rasterizer calls our fragment shaders so we have programmable vertex shader and programmable fragment shader and between we have this hardware unit that does the rasterization for us right and this entire pipeline is run by the gpu hardware so with this um modern gpus we also have hardware ray tracing support so that creates a bit of a more complicated pipeline for ray tracing there's a way generation shader that is a programmable shader stage that you write the code that generates the rays and that's sent to an acceleration structure traversal that is going to be a bbh it's going to be traversing the bbh sort of automatically and then it's going to send possible intersection tests to our intersection shader um some any hit shader for handling semi-transparent objects and it doesn't find anything any hit it's going to call this this shader if it finds a hit it's going to call this closest hit shader so this this pipeline is quite a bit more complicated but that's that's what it's needed for doing ray less like a pipeline more like a washing machine okay uh yeah it is it is more complicated because like over here with rasterization we just feed in our triangles and coming from one end and our pixels come out the other end here with ray tracing we want to use ray tracing for doing all sorts of different things not just for handling the primary visibility like we're going to be using it's next time we're going to talk about it we're going to be using it for computing shadows we're going to be using it for computing reflections for all that stuff we need this more flexible pipeline that can actually do other things that this rasterization pipeline won't be able to do right that's why it's a more complicated machinery here but i am not planning to cover this topic in detail in this course this is where i'm going to stop talking about it but i just wanted to i just have to mention that this exists and if you guys are interested in that please do check it out but although it is not going to work on the current webgl versions that are supported but maybe in some future version of webgl we might have raytracing support today we do not have it only some graphics api is supported all right so this is hardware accelerated ray tracing but that's not the only way of implementing ray tracing on the gpu we can implement as software that does ray tracing and if you're writing a software it's it's software so you don't need hardware support for that to work right because it is going to be software and i want to briefly touch this because this is exactly how we will be implementing ray tracing in our upcoming project we're going to be implementing a software ray tracer on the gpu and people have done this in the past a lot before we had raid racing hardware batteries and support on gpu people still do that for all sorts of things that that's why i want to briefly touch on how how something like this can be done so here's the thing with rage racing this is the this is what i'm doing right i i pick samples on the screen i send rays that go through these samples i trace them i find intersections with triangles maybe one triangle maybe more whatever intersections i find and then i shade that point and i do that for all of the pixel samples that i have so that i can form my image right that's the idea but that's without hardware support this is kind of hard to do so how are we going to do that if we don't have hardware support for weight tracing but we only have support for rasterization how are we going to trick our gpu to do software ray tracing instead of rasterization here's that now we're going to do rasterization but we don't care about that rasterization all we want is i want some shader to run for each pixel basically for each pixel on my screen i want to run a shader and inside my shader i'm going to have a software implementation of ray tracing okay so here's what i do i just draw a quad on the screen and i render this quad using rasterization and that quad is just large enough to cover the entire screen okay so when i do that and i rasterize a quad it's going to have very few vertices right and that when i rasterize it my rasterizer is going to call my fragment shader as many times as i have pixels now i can do whatever it is that i want inside this fragment shader right i can do whatever i want inside that fragment shader and it is inside this fragment shader i will be implementing my ray tracer right so my raytrace is going to run inside this fragment shader the project is implemented such that this vertex shader uh with the help of interpolation and rasterization will generate the primary rays for us so once once we get the fragment shader to fragment shader is going to have array array that corresponds to that corresponding pixel and then we run our software ray tracer inside this fragment shader and that's going to render our final image that let's say it looks like this right so this is how we are going to be implementing ray tracing on the gpu so so in that case i use my visualization pipeline but i didn't do it i didn't use it for anything useful i just used it for rendering a screen size quad right i could actually make use of the rasterization pipeline and i can handle the primary visibility using rasterization so if i have these two triangles in my scene i can render those two triangles using rasterization and and then i'm going to get the pixels that correspond to those triangles on the screen and and and that's where i'm going to have my fragment reader and inside my fragment reader i'm going i can run my ray tracer so if i do that uh it's going to be more like this like this is full ray tracing like i generate primary rates and then i generate secondary rates for reflections refractions globalization whatever if i use rasterization then i'm going to be handling my primary visibility using rasterization so i don't need that primary ray and i can start my ray tracing exactly at this point right i can start my ray tracing at this point which is where my fragment shader will be called and i can run my ray tracer inside my fragment shader to all the secondary effects to handle the secondary effects like reflections refractions shadows and so forth so in the in the upcoming project about retracing we're going to have two rendering modes one of them is going to just render a screen size quad and render everything using ray tracing the other one is going to handle primary visibility using rasterization and the secondary effects like reflections and shadows will be handled using ray tracing right so um that's where i'm going to stop for today next time around i'm going to spend some time and talk about how we can handle shadows and reflections using ray tracing so that's going to be our next topic that being said i think you can start looking into our next project and start implementing the next project right away before waiting for our discussion on shadows and and reflections well at least the parts the the primary visibility part uh you can implement the rest is going to be relatively simple anyway so most of the information that you need for implementing our next project we've already talked about all right but this is where i'm going to stop today um thank you and take a look at the project i hope you're going to enjoy it i certainly enjoyed it good luck with that and i'll talk to you next time

Channel: Cem Yuksel

Views: 1,260

Keywords:

Id: gGKup9tUSrU

Length: 65min 12sec (3912 seconds)

Published: Tue Nov 02 2021