Dan's Raytracing Notes, #1
This is the first in a series of a tutorial on ray tracing in an attempt to
get traffic and interest in the subject flowing in the 3d programming echo.
It is written for those with high-school level math. I'll probably include
easier ways to do it in the future using linear algebra, but there are a
lot of people out there like I was when I first started ray tracing who
don't understand any of that stuff.
Basic concepts: Ray tracing is where you build a virtual world out of
"primitives", objects that can be easily represented mathematically, and
find out what would be visible to an eye in that space by drawing rays out
from the eye to see what they hit. It is also possible to go the other way,
drawing rays from light sources back to the eye, but this has (so far) been
impractical in practice, although it theoretically should generate better
images.
To draw the result of all of those rays, you figure that the eye is some
distance in front of a screen, and that a ray goes through every pixel
(dot) on the screen. You find out what objects that ray hits first, and
color the dot the color of that object.
To represent a ray, we've got an origin for it (the eye position), and a
direction. For the notation that follows, I'll show that as "ray.origin"
for the origin and "ray.direction" for the direction.
For clarity, what we'll do is place the observer at (0,0,0), looking at a
virtual screen along the Z axis. The distance of the screen from the
observer is analagous to the lens length on a camera; if you have a lens
length too short (like a wide-angle lens), you'll get "fisheye" looking
images like you see from a wide angle lens, if the lens length is too long
(like a zoom lens), you'll see no depth.
The extreme of a lens too long is a 2d "orthographic" projection; all
possible rays must be parallel, so the Z axis is thrown away.
Anyway, for our first image, we'll take a sphere. Those of you who remember
back to algebra remember that a circle was represented as:
X^2 + Y^2 = radius^2
Or, that all of the points on a circle were such that when plotted on a
Cartesian plane the square of the X coordinate plus the square of the Y
coordinate equaled the radius squared. Nothing new here thus far, and, as a
matter of fact, you could implement a ray tracer in two dimensions like
this:
First off, we need to substitute something for the X and Y terms. Since we
know we want to find how far from the ray origin the ray intersects the
sphere, we need a distance term that we can solve for. For starters, we'll
put the center of the sphere at the origin and put the ray elsewhere,
simplifying the math a little bit:
X = ray.origin.x + distance * ray.direction.x
Y = ray.origin.y + distance * ray.origin.y
radius^2 is something that the world designer gives us, but we know it's a
constant, so now it's a matter of solving for the distance. From grade
school, multiply everything out and make it completely incomprehensible:
radius^2 =
ray.origin.x * ray.origin.x +
2 * ray.origin.x * distance * ray.direction.x +
distance * ray.direction.x * distance * ray.direction.x +
ray.origin.y * ray.origin.y +
2 * ray.origin.y * distance * ray.direction.y +
distance * ray.direction.y * distance * ray.direction.y
Now, solve one side to zero and factor out all of the distances and it
looks remarkably like something solvable using the quadratic equation:
0 =
(ray.direction.x^2 + ray.direction.y^2) * distance^2 +
2 * (ray.origin.y * ray.direction.y *
ray.origin.x * ray.direction.x) * distance +
ray.origin.x * ray.origin.x +
ray.origin.y * ray.origin.y -
radius^2
That is, there's a generic equation that gives us two answers for any
equation that looks like:
A * D^2 + B * D + C = 0
Since we know the ray direction, the ray origin and the radius, those are
all constants, so plugging those constants into this equation (If you need
a reference, any algebra text should do):
- B + or - square root(B - 4 * A * C)
D = -----------------------------------
2 * A
Where:
A = (ray.direction.x^2 + ray.direction.y^2)
B = (ray.origin.y * ray.direction.y *
ray.origin.x * ray.direction.x)
C = ray.origin.x * ray.origin.x +
ray.origin.y * ray.origin.y -
radius^2
If A is zero, then the ray had no direction, so the equation won't solve
correctly. If the term in the square root, "(B - 4 * A * C)", is negative,
then there is no solution to the equation in real numbers and the ray never
intersects the sphere. If everything works out hunky-dory, however, the ray
intersects the sphere at one of the two points (see that "+ or -", do it
both ways and that gives you both points).
The equation for a sphere (rather than a circle) is:
X^2 + Y^2 + Z^2 = radius^2
Your homework for the next installment is to expand this puppy out to three
dimensions, and write a program that puts the ray origin at (0,0,-400), a
screen from (-160,-100,0) to (160,100,0), and a sphere at 0,0 with radius
50, like so:
lens_length = 400
radius = 50
FOR X = -160 TO 160
FOR Y = -100 TO 100
ray.origin.x = 0
ray.origin.y = 0
ray.origin.z = -lens_length
ray.direction.x = X
ray.direction.y = Y
ray.direction.z = lens_length
IF solve for the circle equation had a real answer THEN
PLOT X + 160, Y + 100 COLOR not black
ELSE
PLOT X + 160, Y + 100 COLOR black
ENDIF
END FOR
END FOR
This should fit on a 320 by 200 screen (okay, it's one over, so sue me),
and when done properly will give you a filled circle half the height of the
active screen centered in the screen.
If you get really exotic, you might want to try moving the sphere around by
giving it an origin and subtracting the origin from the initial ray origin
before you check for an intersection.
If I get any response from this, next time we'll see about adding a few
more objects, and then going for shading and reflection.
---------------------------------------------------------------------------
This is part of the Graphics Without Greek collection in the home pages of
Dan Lyke, reachable at danlyke@chattanooga.net