In this segment, we are going to review ray-object intersections. We have already dealt with most of the topics here in the previous lecture. But for completeness, since they are very basic to develop a ray tracer, we'll continue talking about them here. Since we already have some basic background, I'll go over it relatively quickly. Remember the outline of the ray tracer. In the previous segment, we generated the eye rays through the camera pixel. In this segment, we are doing the second step, which is finding the hit points for intersecting a ray with the scene. First let's consider ray-sphere intersection. In your ray tracer, we asked you to do spheres and triangles. The formula from a ray has an origin point P_0, and it has a direction P_1 as well as the distance along the ray, t. The sphere is given by the standard equation which is that the distance squared from the center is given by R square. And we want to find the intersection points. So, the first step we will do, as on all of these ray surface intersections, is substitute the ray equation for the sphere, so substitute P_0 plus P_1*t into P for the sphere. So making that substitution, we get the formula shown here. The only unknown is the distance along the ray, t. Everything else is known from the properties of the ray and the sphere. Looking at this equation, you can easily see that it's in fact a quadratic equation. And we can find the coefficients of the various quadratic, linear and constant terms. Once we've done that, it's a simple matter of solving a quadratic equation, which all of you are familiar with from high school algebra. There are many possibilities that can arise from looking at the discriminant of this equation. So you should definitely check the discriminant first. First let's consider the value at the bottom of the slide. If the discriminant involves complex roots, so the discriminant is negative, then you should not take the square root in solving the quadratic equation. What it means physically is that there is no intersection between the ray and the sphere. On the other hand, if you have two real, positive roots then the ray intersects the sphere twice, and this is in fact the canonical case. You pick the smaller positive root. If both roots are the same, the ray is tangent to the sphere, and of course in all ray tracing there is an interesting question of how do you handle these kinds of numerical degenerate cases like tangents. You can do whatever you think is reasonable. If there is one positive and one negative root, then the ray is inside the sphere which can happen if you have things like refractions. Once you've found the intersection point, you also need the normal for calculating the reflected direction, and this is useful for many other tasks as well. For a sphere, it's really easy, so the normal at a point is just the direction from the center. If this is my sphere, I have a point here, normal is just along the direction from the center. So therefore, you just take the difference P - center, which will give you this direction, and you normalize it. So much for ray-sphere intersection. The next thing you need to implement is ray-triangle intersection. There are, of course, many ways of doing this. It's a topic that's seen lot of research. One approach we will consider here is to intersect the ray with the plane in which the triangle lies. Then check if the intersection point is inside the triangle. First, we need the equation for a plane. And in order to find the equation for the plane, you first need the normal to the triangle. So the normal really comes out of the plane of the triangle, and it can be given by a cross product, so you can consider C - A as one vector. So this is really the vector AC. And you can consider B - A as another vector. In fact, that's what's done here, C - A cross B - A, the whole thing normalized. The plane equation essentially says that the normal dot product with any tangent vector in the plane. So P - A is the tangent vector, is equal to 0. That can also be written in this form, that the dot product of any point with the normal is the same as the dot product of any other point, such as the vector A. We now combine it with the ray equation. And again, this involves a process of substitution. So you substitute P = P_0 + P_1 * t in the plane equation. So you take the vector P here, you substitute P_0 + P_1 * t here and you do this dot product. This is now a linear equation for t, which can be solved here, and this is the formula you get for the solution for t. Of course, if P_1 dot N is equal to 0, which means the ray is parallel to the plane, there is no intersection, but otherwise there is an intersection. Of course, once you intersect the ray with the plane, the question is, is the intersection point actually inside the triangle or outside the triangle? Doing that calculation is a fascinating subject, and for general polygons, you have the shooting test. You can shoot the ray in the plane of the polygon to infinity. If it intersects an odd number of times, the ray is inside the polygon, and even number of times, it's outside. However, what we do is: We use barycentric coordinates, as we discussed in the last lecture, which is also useful to parameterize the point, which can have benefits in interpolating coordinates, such as texture coordinates. The barycentric coordinates are like this, where a point P is given by weights alpha A, beta B, gamma C, where the alpha, beta and gamma are all non-negative weights and they sum to 1. So, it's an affine combination of the coordinates A, B and C. These are known as barycentric coordinates of the point P. Given these barycentric coordinates, I want to check if the ray lies inside the triangle, so I have my hypothesis for the point P, which is where the ray intersects the plane, and I'm going to find alpha, beta and gamma to say P lies inside the triangle. Subtracting A from here, and noting that A can also be written as alpha A + beta A + gamma A, because alpha + beta + gamma = 1, we get the expression shown here. And just to see the algebra, so I have P - A here, and on this side, what I do is I subtract - (alpha * A) - (beta * A) - (gamma * A). The alpha * A term of course cancels. What we are left with is beta * (B - A), gamma * (C - A). And that's exactly the terms here. So we can solve the system of simultaneous equations. Remember that there are 3 coordinates X, Y, Z in which these equations have to hold, but one of the cases becomes degenerate, because we are operating in a plane. Nevertheless we can solve for beta and gamma and then we just check if you have beta and gamma both lying in the 0 to 1 range. And alpha = 1 - beta - gamma must also lie in 0 to 1 and that condition is that beta + gamma < 1. So alpha also lies between 0 and 1. If this is true, the point is in the triangle. Otherwise it's not. Just want to say a brief word about other primitives although it is not required for the assignment. Some of you may be interested in exploring different types of primitives. And so there are well defined intersection test for cones, cylinders, ellipsoids, boxes, especially bounding boxes and general planar polygons. And it was one of the most active topics in the early days of ray tracing. Next, I want to show you a slide on ray-scene intersection, just to make this explicit. At the top level, we have the intersection call for ray and scene. And I define the minimum distance, the minimum distance to the intersection, which is what the intersection actually is, starts out at infinity, and I haven't hit any objects. Then what I do is loop for each object in the scene. t is the intersection of the ray with that object, so t is the distance of the ray to that object. If t > 0, that's a positive distance for intersection. And most importantly, t < mindist. So if the current intersection is less than the previous intersection, or less than infinity, if there was no previous intersection, then I simply set mindist to t, and set the hitobject to the object. Now, when I go back in the loop for the next object, I'll again check if it's less than the previously closest intersection. Finally, I have an intersection given by mindist and hitobject. And that structure maintains things like the normals, the texture coordinates. And this may already have been computed when I have the intersection at t. So this is essentially how you do ray-scene intersection. It's very important to have this loop and see which object has the minimum intersection distance. The next topic we're going to study briefly is ray tracing transformed objects. Here we have an optimized ray-sphere test, for example. But now we want to trace against an ellipsoid. This is something that you will actually consider in homework 3. Of course you could define a new ray-ellipsoid intersection routine, but that may be inefficient, because your ray-sphere routine is optimized. Instead what you do is apply the inverse transform to the ray, then use ray-sphere. And this also helps with instantiation, when you have a number of cars in the traffic jam, you just have to use the same object with different transforms. Or you have spheres, ellipsoids, other shapes that can be achieved by a transform. You don't need to have a separate ray-ellipse intersection routine. Of course, there is nothing that's specific about spheres and ellipsoids. I've just used that example because a transform of a triangle still leaves it a triangle, but the sphere actually changes shapes. However, the general idea is the same. You consider a general 4x4 transform matrix M, which can be implemented using matrix stacks much the same way you did it in homework 2. You apply the inverse transform M^(-1) to the ray. Remember that the ray consists of two parts, the origin and the direction. The inverse transform must be applied to both parts. The origin is a location which is stored in homogeneous coordinates, and you can nicely apply the inverse transform. The direction is a vector, which means that the homogeneous coordinate is 0. And that is very important. Don't miss that. If the homogeneous coordinate is zero, the main activity is that translations will not act on the vector, and in fact if you translate the location of a ray only the origin changes; the direction does not. So that's the correct behavior. You do the standard ray-surface intersection, and then finally you have to transform the intersection back to the actual coordinates. The intersection point p that you computed in this transformed space, now you apply Mp. So first you apply an inverse to the ray, do the intersection and then to the point, you apply Mp. And normals you know, transform differently, so you use M inverse transpose * n. We talked about that in normal transforms. Once you've found the point and normal in both coordinates, you can do your standard lighting calculation.