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.