A few questions regarding raytracing
Sidney Richards
I'm doing a maths project on raytracing (not programming at the moment, but
that's next). Since I'm a hobby C++ programmer, I got more from reading
sources then say, for instance, the Foley & Van Dam book. Another added
problem is I'm going to school in a non english speaking country, therefor
the math terms are a bit confusing as well. Anyway, I'll get to the point.
From several sources I found the equation to calculate T in Ray = Start + t
* Direction is (for spheres):
(x1^2 + y1^2 + z1^2 )*T^2 + (x1 * (x0 - a) + y1 * (y0 - b) + z1 * (z0 - c))
* 2T + ((x0 - a)^2 + (y0 - b)^2 + (z0 - c)^2 - r^2 ) = 0
Where:
x0, y0, z0 = coordinates of the starting point of the ray
x1, y1, z1 = the coordinates of the direction
a, b, c = the coordinates of the center of a sphere
r = radius of sphere
This seemed to be correct when compared to the internet sites. So I decided
to put it to the test and calculate the intersection at the first pixel in
an image (1, 1) with the following (very arbitrary) variables:
x0, y0, z0 = (10, 5, 2) -> I assume this is the point from which the ray
originates. I assume you could use any kind of values, though I am a bit
unsure.
x1, y1, z1 = (1, 1, 1) -> I assume this is where you fill in the coordinates
of the current pixel on the image. I leave the z value constant through out
the process (I again assume), and I use 1,1 as the first pixel in an image
a, b, c = (50, 60, 40) with radius 10-> Just chose a big sphere, quite far
away from the viewpoint so I wouldn't "miss it" so to speak.
Now, when I fill this data in I would expect there to be no intersection
(after all, x = 50 for the sphere centre is far aways from x = 1 for the
direction). Anyway, this is what I got:
(1^2 + 1^2 + 1^2 )*T^2 + (1 * (10 - 50) + 1 * (5 - 60) + 1 * (2 - 40)) * 2T
+ ((10 - 50)^2 + (5 - 60)^2 + (2 - 40)^2 - 10^2 ) = 0
Yielding the quadratic formula:
3T^2 - 266T + 5969 = 0
Discriminant = B^2 - 4 * A * C = (-266)^2 - 4 * 3 * 5969 = -872
A negative discriminant means there are no real solutions for T and the ray
doesn't intersect at point (1, 1).
Now for the questions.
1. This is the way I did it to test if it worked. First of all, the numbers
I've been using seem rather large. Should I be scaling them down?
2. Secondly, as I said, the variables are very arbitrary. Does my starting
point have to be between certain values? Does the Z axis of the direction
vector need to be a certain value? etc. etc.
3. If T is indeed positive, and I calculate X with X = Xstart + T * Xdir .
Will the point be a point *on* the sphere? How can I calculate the distance
from that point to the center of the sphere?
4. I've seen some people use "normals", and others not. I know how to
calculate a normal, but could anyone explain to me what the use is, and most
importantly, should I be using it above?
Any help would really really be appreciated, especially if you could explain
to me why I've been doing stuff wrong, or why something has to be done,
since I'm in a bit of a jam here.
Cheers,
Sidney Richards
Kevin Goodsell
very carefully, but it looks like you are making some mistakes. Let me start
at the beginning.
First, the coordinate system. This could be set up just about any way you
are comfortable with, and I'm not sure if there is really a fixed standard.
The way I do it is this: the screen lies in the x-y plane with the origin at
the lower left corner. The y axis increases upward, the x axis increases to
the right, and the z axis increases into the screen. The coordinates are
scaled so that the screen is 1 unit wide, and usually less than 1 unit tall
(this is because the screen is wider than it is tall, and the scaling must
be the same in both directions, otherwise objects will be stretched out).
This makes the lower right corner of the screen (1, 0, 0).
The viewpoint (which is also the origin of an eye ray) is in the negative z
space, so it might be at a point like (0.5, 0.35, -3). In fact, I think I've
used those exact coordinates at times.
Rays need not originate at the viewpoint, however. In fact, they can (and
do) originate virtually anywhere. For example, an eye ray may start at the
view point and intersect a reflective object. This creates a new ray (the
reflected ray) with it's origin at the point of intersection.
For simplicity, assume that the pixel location (0, 0) is at the bottom left
of the screen, although it's actually the top left. This makes it easier to
map screen coordinates to coordinates in the ray traced scene. To actually
do the mapping, y is replaced with (y_max - y), otherwise the image appears
upside down.
Okay, so now to get down to the actual calculations. An eye ray will start
at the viewpoint. We'll call the coordinates x0, y0 and z0. The direction of
the ray is calculated from the pixel location and this origin. For pixel
(xp, yp), we calculate xs = xp/screen_width and ys = xp/screen_width, where
screen_width is the width of the screen in pixels. zs is 0. (xs, ys, zs) is
the location of the pixel in the ray traced world's coordinates ('s' for
screen). Note that 1) xp/screen_width makes the screen one unit wide, since
xp will range from 0 to screen_width - 1, and 2) yp is also divided by
width, *NOT* height, so that the vertical and horizontal scaling will match.
zs is 0 because the screen is in the x-y plane, where z=0.
Given the two points we have now (the origin and the screen coordinates) we
can define a line (or ray). We already have the origin (x0, y0, z0). We just
need the direction (xd, yd, zd). This is given by subtracting the origin
from the screen coordinates, so xd = xs-x0, yd = ys-y0, and zd = zs-z0. Now
we have a ray defined by a starting point (x0, y0, z0) and a direction (xd,
yd, zd). Note that it is usually recommended that the direction be
normalized.
The next task is to find where this ray intersects with objects in the world
by testing it against each object. Since we are interested in the sphere
case here, I'll describe it next.
A sphere is defined by its center and radius. We'll refer to the center as
(xc, yc, zc) and the radius as r. The formula for this sphere is
(x - xc)^2 + (y - yc)^2 + (z - zc)^2 = r^2
or
(x - xc)^2 + (y - yc)^2 + (z - zc)^2 - r^2 = 0
The formula for the ray is just the parametric formula for a line in 3
space:
x = x0 + xd*t
y = y0 + yd*t
z = z0 + zd*t
The next step is to substitute these equations into the equation of the
sphere:
((x0 + xd*t) - xc)^2 + ((y0 + yd*t) - yc)^2 + ((z0 + zd*t) - zc)^2 - r^2 = 0
The goal at this point is to solve for t. The smallest positive value of t
is the first intersection point, which is usually the only one we care
about. Only positive values of t are considered, because a negative value
for t gives a point that is behind the ray's origin.
To solve for t, we want to get the equation into the form
A*t^2 + B*t + C = 0
so that we can apply the quadratic formula. This is just a matter of
multiplying then collecting terms.
((x0 + xd*t) - xc)^2
= (x0 + xd*t)^2 - 2*xc*(x0 + xd*t) + xc^2
= x0^2 + 2*x0*xd*t + xd^2*t^2 - 2*xc*x0 - 2*xc*xd*t + xc^2
The y and z terms expand out the same way. The last term (- r^2) is left
alone for now. Next, we collect terms:
(xd^2 + yd^2 + zd^2)*t^2 +
(2*x0*xd - 2*xc*xd + 2*y0*yd - 2*yc*yd + 2*z0*zd - 2*zc*zd)*t +
(x0^2 - 2*xc*x0 + xc^2 + y0^2 - 2*yc*y0 + yc^2 + z0^2 - 2*zc*z0 + zc^2 -
r^2) = 0
The preceding equation shows how the terms break up into the A, B, and C
components. Simplifying a little, we get:
A = xd^2 + yd^2 + zd^2
B = 2*(xd*(x0 - xc) + yd*(y0 - yc) + zd*(z0 - zc))
C = (x0 - xc)^2 + (y0 - yc)^2 + (z0 - zc)^2 - r^2
Now we can plug these into the quadratic equation. Remember that these are
all known values: (x0, y0, z0) is the origin of the ray, (xd, yd, zd) is the
direction of the ray, (xc, yc, zc) is the center of the sphere, and r is the
radius of the sphere.
There are a few tricks remaining. If the ray direction has been normalized,
then A = 1, and it can be ignored. If B^2 - 4*C is less than zero, there is
no intersection. If it is greater than zero then there are two intersections
corresponding to two different values of t. The one we are interested in is
the smallest one that is positive. If both are negative, the entire sphere
is behind the ray origin. If only one is negative, then the ray originated
inside the sphere.
That's pretty much it.
As an example, let's put a sphere at (0.5, 0.5, 5) with a radius of 1 and
put the view point at (0.5, 0.5, -5). Assume the current pixel is a little
above the center of the screen, so that the screen coordinates are (0.5,
0.5, 0). This gives the ray a direction of (0, 0, 5) which is normalized to
(0, 0, 1). Plugging these in for B and C (A is 1, as expected) above gives:
B = 2*(0*(0.5 - 0.5) + 0*(0.5 - 0.5) + 1*(-5 - 5)) = -20
C = (0.5 - 0.5)^2 + (0.5 - 0.5)^2 + (-5 - 5)^2 - 1^2 = 99
So from the quadratic formula we get:
t0 = (20 + sqrt(20^2 - 4*99))/2 = 11
t1 = (20 - sqrt(20^2 - 4*99))/2 = 9
t1 is the smaller value. Plugging it back into the equations for a line
gives:
x = x0 + xd*t = 0.5 + 0*9 = 0.5
y = y0 + yd*t = 0.5 + 0*9 = 0.5
z = z0 + zd*t = -5 + 1*9 = 4
So the intersection occurred at (0.5, 0.5, 4). It is easy to verify that
this is a point on the sphere. The other intersection would be at (0.5, 0.5,
6), on the other side of the sphere.
I hope that's helpful, considering how long it took me to type. ;)
-Kevin
Sidney Richards wrote in message <9g5hqi$g8t$1...@news1.xs4all.nl>...