views:

461

answers:

2

I'm researching the math for a ray tracer, but I'm not following a transition that is made in just about every article I've read on the subject. This is what I have:

Formula for a sphere:

(X - Cx)^2 + (Y - Cy)^2 + (Z - Cz)^2 - R^2 = 0

Where R is the radius, C is the center, and X, Y, Z are all the points in the sphere.

Formula for a line:

X + DxT, Y + DyT, Z + DzT

where D is a normalized direction vector for the line and X, Y, Z are all the points on the line, and T is a parameter for some point on the line.

By substituting the components of the line into the sphere equation, we get:

(X + DxT - Cx)^2 + (Y + DyT - Cy)^2 + (Z + DzT - Cz)^2 - R^2 = 0

I follow everything up to that point (at least I think I do), but then every tutorial I've read makes a jump from that to a quadratic equation without explaining it (this is copied from one of the sites, so the terms are a little different from my example):

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 - Sr^2

I get how to then solve for T using the quadratic formula, but I don't understand how they get to the quadratic equation from the above formulas. I'm assuming that's just some piece of common math knowledge that I've long since forgotten, but googling for "How to set up a quadratic equation" hasn't really yielded anything either.

I'd really like to understand how to get to this step before moving on, as I don't like writing code I don't fully grasp.

+6  A: 

From here:

(X + DxT - Cx)^2 + (Y + DyT - Cy)^2 + (Z + DzT - Cz)^2 - R^2 = 0

Expand the three squared terms, so you have a long expression:

X^2 + Dx^2T^2 + Cx^2 + 2XDxT - 2XCx - 2DxTCx + ...... = 0

(This is due to using the formula (x+y+z)^2 = x^2 + y^2 + z^2 + 2xy + 2xz + 2yz)

Then group so you have factors of T^2, T, and 1:

(....)T^2 + (....)T + .... = 0

These factors are the A,B,C given above. This is a quadratic equation for T, and can be solved using the quadratic formula.

interjay
That clears things up. I wish they would have just said that in at least one of the articles. Perhaps it was a given, though. Thanks!
Mike Pateras
+4  A: 

Here's a detailed walkthrough of each step; hopefully this will make things crystal clear. The equation for a three-dimensional sphere is:

(x-a)^2 + (y-b)^2 + (z-c)^2 = r^2

with <a, b, c> being the center of the sphere and r its radius. The point <x, y, z> is on the sphere if it satisfies this equation.

The parametric equations for a ray are:

  • X = xo + xd*t
  • Y = yo + yd*t
  • Z = zo + zd*t

where <xo, yo, zo> is the origin of the ray, and <xd,yd,yd> is camera ray's direction.

To find the intersection, we want to see what points on the ray are the same as points on the sphere. So we substitute the ray equation into the sphere equation:

(xo + xd*t - a)^2 + (yo + yd*t - b)^2 + (zo + zd*t - c)^2 = r^2

which expands to:

  (xd^2 + yd^2 + zd^2) * t^2 +
  [2[xd * (xo - a) + yd * (yo - b) + zd *(zo - c)]] * t +
  [(xo - a)^2 + (yo - b)^2 + (zo - c^)2 - r^2]
  = 0

Notice that this is a quadratic equation in the form At^2 + Bt + C = 0, with:

  • A = (xd^2 + yd^2 + zd^2)
  • B = [2[xd * (xo - a) + yd * (yo - b) + zd *(zo - c)]]
  • C = [(xo - a)^2 + (yo - b)^2 + (zo - c^)2 - r^2]

We can apply the general quadratic formula for an unknown variable, which is:

t = [-B +- sqrt(B^2 - 4AC)] / 2A

The B^2 - 4AC portion is called the "discriminant". Depending on the value of the discriminant, we will get zero, one, or two solutions to this equation:

  • If it is less than zero, the solution is an imaginary number, and the ray and sphere do not intersect in the real plane.

  • If it is equal to zero, then the ray intersects the sphere at exactly 1 point (it is exactly tangent to the sphere).

  • If it is greater than zero, then the ray intersects the sphere at exactly 2 points.

If the discriminant indicates that there's no solution, then you're done! The ray doesn't intersect the sphere. If the discriminant indicates at least one solution, you can solve for t to determine the intersection point. The two solutions are:

t_1 = [-B + sqrt(B^2 - 4AC)] / 2A
t_2 = [-B - sqrt(B^2 - 4AC)] / 2A

The smaller solution is the point at which the ray first hits the sphere.

John Feminella
I wish I could mark two questions as the answer, as this is truly an awesome response. While the other one addresses the question a little more directly, this really helps put what I'm trying to do into better perspective, and I really appreciate it. Thank you very much for your time and help, John.
Mike Pateras
Note: If one of the two solutions is negative and the other is positive, that tells you that the ray originates from _inside_ of the sphere. (You have to travel "backwards" to find one intersection point and "forwards" to find the other.)
John Feminella
@John: Surely there's only one point if it originates from within the sphere? ..or do you mean that if you went backwards from the point of origin of the ray you'd also exit the sphere?
Jon Cage
@Jon: If the ray originates from within the sphere, then there'll be two points of intersection, but the two `t` solutions will have opposite signs. This is easy to visualize if you think of `t` as measuring time and `f(t)` of tracing out a line over time. If the point indicated by `f(0)` is inside the sphere, that means that at some point prior to `t = 0` (negative `t`) it was outside the sphere. At a future point (positive `t`) it will be outside again.
John Feminella