In this segment, we're going to consider ray-surface intersection, which is really the heart of a raytracer. Ray-surface intersection was one of the main initial research areas, as a result of which there are now optimized routines for a variety of different primitives: triangles, spheres, cubes, etc. Notice that different types of rays may need different types of information. For shadow rays, you just need intersection or no intersection. If you do find an intersection, it doesn't even need to be the closest intersection. For primary rays, you want the point of intersection, the materials at that point, the normal at that point, the texture coordinates at that point. In this segment, we'll try to work out examples for a triangle, for a sphere, and talk about polygons and general implicit surfaces. Let's first talk about ray/sphere intersection, which is one of the most canonical cases. First, we need to have a way of defining the ray, as well as a way of defining the sphere. The ray is defined like this. You have an origin, P0, and you have a direction, P1. t is a parameter along the ray that starts from zero and is positive, corresponds to the distance along the ray. The sphere is measured with respect to the central location C. So P - C for any point in the sphere: the dot product with itself which is the length squared has to be equal to r squared where r is the radius. What we want to find is what is the location of these intersection points. The way we do it, and the way we do all of the ray sphere intersections, all of the ray surface intersections, is to substitute the ray equation into the equation for the sphere. So in this case, P is equal to P0 plus P1(t). I will substitute that into the equation for the sphere. So P0 + P1(t) - C. Okay? And now I want the dot product with itself to be equal to r squared. So let me just reprise that equation. We substituted the ray formula in the sphere, and we said P0 + P1 t - C dot product with itself has to be equal to r squared. This is simple, and what we are solving for is the distance along the ray t. So we know the other parameters. We know P0 and P1 for the ray. We know the central location C for the sphere, as well as the radius r squared. Simplifying, we'll see that the t terms will give you t squared here, and so you have t squared that gets multiplied by p1 dot product with P1. Then we have the t terms. So P1 dot product with (P0 - C). (P0 - C) dot product with P1. And so we'll have the t terms. P1. Which will take a dot product with (P0 - C). Then we have the constant term, which is (P0 - C) dot product with itself, minus r squared is equal to 0. So this will be P0. I've just written it out again on the slide. This is simply a quadratic equation which we have to solve for t. Depending on what the roots of the quadratic equation reveal, we have many different cases that correspond to physically, to different ways in which the ways in which a ray and a sphere can intersect. First let's consider the case where you have 2 real positive roots. Of course this will depend on the value of the discriminant, as is standard in quadratic equations. So the ray-sphere intersection routine should first check the discriminant. If you have 2 positive roots, it means the ray intersects the sphere like this. And in that case, you pick the smaller positive root. If both roots are the same, that means the ray intersect the sphere only once, which means it is tangent to the sphere. If you have 1 positive and 1 negative root, that means you are inside the sphere. So the negative part is this intersection, the positive part is here. And in this case, what you want to do is pick the positive root because a ray does not have t less than 0. And if you have complex roots, that means there is no intersection between the ray and the sphere. So before you try to solve this equation, you should check to make sure that the discriminant is positive. Finally you've solved the equation for the t which results in an intersection point. Then you need to find what the actual intersection point in physical coordinants is. That symbol you substitute back into the equation for the rate P0 + P1 t where you use the value of t you just solved for. You may also need to know the surface normal at the point of intersection. This is useful for a variety of different tasks such as shading. In the case of the sphere, you know that the normal lies on the direction from the point to the center of the sphere. And so that's just P - C, normalized. Having discussed spheres, let's come now to another commonly used primitive, which is triangles. And in homework 3, you will have to do spheres and triangles. There are many different ways to intersect a ray with a triangle, and if you search for it online, you'll come up with many different solutions. It's really one of the most fundamental problems, because triangles are the most commonly used primitive, so you want to make that fast. In this lecture we'll consider first a general ray polygon intersection routine and then we'll talk about a check if this intersection point is actually inside the triangle. First let's consider a triangle like this. The 3 vertices of the triangle are A B and C. You want to know what the normal to this triangle is, so let me just write it down. So you have the normal and this will be given by, you can consider any two directions in the triangle. So you have C - A and B - A. It can be given by C - A, cross product, with B - A. I have just normalized the cross product here. The next question is what is the equation for a plane. You may remember this from high school geometry: essentially the normal dot product with any vector in the plane has to be zero. So if you consider any point P in the plane, which is any point P in the triangle. Here is the P, then if you consider the vector P minus A, it lies along the plane; the normal with that is zero. So n . (P - A) is zero, which is the same as saying tha P . n - A . n is equal to zero. Next, you want to combine this with a ray equation. So the ray is again given by P0 + P1 t. We've just substituted that in the plane equation, so (P0 + P1 t) . n is equal to A . n. Now you notice that this is a linear form, so t is multiplied by P1 dot n, and on the other side, you have (A dot n) - (P0 dot n). And if you put this all together, you'll get, solve for t is (A dot n) - (P0 dot n), divided by (P1 dot n). Notice that if P1 dot n is equal to 0, this is not defined, and that occurs when the ray P1 direction is orthogonal to the normal direction, so that means the ray lies in the direction of the plane, and in that case, of course, it doesn't intersect it. However in the common case and in the most general case you will find a ray plane intersection. That's only half the problem. You still need to find if the intersection point is inside the triangle. There are many possibilities for doing this, and you can do this for triangles and general polygons. Let me briefly say what you would do for a general polygon. One approach to this is to consider your general polygon something like this. It does not need to be convex and you have a point here. You don't know whether it is inside or outside. So I draw a line from this point to infinity along any direction, doesn't matter, it could be here. Could be here. If it intersects an even number of times, the point is outside the polygon. If it intersects an odd number of times, notice that in this case it has 3 intersections, in this case it has 1, then it is inside. So. odd is in and even is out. However, for the case of triangles we actually find the intersection parametically using what are known as barycentric coordinates with respect to the triangle vertices. This is useful in a number of other applications such as texture. If I show the triangle here A, B, and C are the vertices of the triangle. Alpha, beta, and gamma correspond to the weights of the point P for A,B, and C respectively. They are normalized so that alpha + beta + gamma is equal to 1. This is known as the barycentric coordinates for a triangle. A point P will be given by alpha A, plus beta B, plus gamma C, where they sum to one. And furthermore it's a convex combination which means that alpha, beta and gamma are all positive. So now the question is, how do we solve for this? It's simply a system of simultaneous equations. So I can subtract A from P and I can get beta into B-A, plus gamma into C-A. What I've done in order to do this is as follows. I went here and I subtracted A. But remember that alpha + beta + gamma is equal to 1. So this is equal to A and to alpha + beta + gamma. The alpha A time then cancels against the alpha A time here, and becomes beta times (B - A), gamma into (C - A). I can now try to solve this under the condition that 0 is less than beta is less than 1. Same for gamma, and they sum to less than 1. So alpha + beta + gamma is equal to 1. And I will do this with my intersection point. I have enough equations. I have actually 3 equations for the 3 coordinates of P. But since we are talking about a planar region, 1 of those becomes degenerate. I have enough equations to determine beta and gamma, from the 2 simultaneous equations. So far we've spoken about spheres and triangles. Much of the early work in raytracing dealt with other primitives. So it focused on a variety of ray primitive tests for things like cones, cylinders and ellipsoids. Ray box intersection tests were especially studied and optimized. This is useful for bounding boxes, and general planar polygons were considered. Many, many other surfaces were considered. You can pick up a raytracing book and you'll find many ray surface intersection routines. To make it simple in homework 3, we've just asked for spheres and triangles, but in practice, there are intersection routines with many different primitives. One final aspect of raytracing and ray surface intersections, is intersecting with a transformed object. So, consider a common situation, where you have an optimized ninth ray sphere intersection test in homework 3, but you want to trace the ray to intersect with an ellipsoid. Because, I took my sphere and I scaled it and squashed it and stretched it so it's now an ellipsoid. Very well, I could go look up the ray ellipsoid intersection routines or the general ray quadric surface intersection routines. However, this is not appropriate in the sense that it requires a lot of code. It may not be as efficient as the ray sphere intersection. Fortunately, there's a way around this. Instead of intersecting the ray with the transformed sphere or ellipsoid, I apply the inverse transform to the ray, then intersect it with the original shape and transform it back. This allows for many different things, so one of the things it allows for is instancing: I can take my sphere, make different egg-shape ellipsoids and intersect the ray with all of them. I can also create new types of shapes in homework 3. Although the intersection points are rays and spheres and triangles. I can have ellipses, and in this way, more interesting shapes. So let's talk about the mathematics for ray transformed surface intersection. So, let's first consider the ray. And I'm going to call it R. And then, I'm going to consider the object, which I'm going to call P. And let's call a transform, which is M, is my matrix. So P will go to MP and I want to intersect the ray and MP. Instead what I say is that I create a new ray which is R' which is equal to the inverse transform applied to the original ray. Remember that the ray contains an origin and a direction. The origin is in homogeneous coordinates and is a 4 vector. It's a point. The direction is a vector, and so the homogeneous coordinate is 0. If I'm translating an object, I apply the inverse translation to the ray, which inverse translates the origin, but has no effect on the direction. Once I have this, I am really computing the intersection between R' and the original object p. After I've done this and computed this intersection point - let's call it P star so let's call if P' star actually. I then apply the matrix M on this point. So, I apply the matrix M on the intersection point and that gives me my intersection point in the actual world. So, let's go over this and homework 3 you should support general transform stacks just as you do in homework 2. You consider a general 4 by 4 transform. You apply the inverse transform to the ray. So, the locations are stored and transformed in homogenous coordinates. The vectors, the ray directions, have homogeneous coordinates are set to zero so there is no action because of translations. You do the standard ray surface intersection as modified and then you transform the intersection back to the actual coordinates so you apply the transformation matrix M. The normals transform as m inverse transpose times n, that's very important. And finally you do the lighting, you recompute the distances. It's not very different. Suppose you wanted to do a transformation like rotation not about the origin, but about some point in space. You first reverse transform the translation to bring it to the center, do the rotation and then forward transform back. This is the same idea, you first apply the inverse transform to the ray, you do the intersection and then you apply the forward transform to the intersection.