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.