How to establish a quadratic equation for the intersection of rays / spheres?

Question

I study math for the ray tracer, but I do not follow the transition that is made in almost every article I read on this subject. This is what I have:

Formula for the scope:

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

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

The formula for the line is:

X + DxT, Y + DyT, Z + DzT

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

Substituting the line components in the spherical equation, we obtain:

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

I follow everything up to this point (at least I think I’m doing it), but then every text I read makes a transition from this to a quadratic equation without explaining it (this is copied from one of the sites, so the terms slightly 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 a quadratic formula, but I don’t understand how they get into the quadratic equation from the above formulas. I suppose that only part of the general mathematical knowledge that I had long forgotten, but googling for "How to set up a quadratic equation" also brought nothing.

I would really like to understand how to get to this step before moving on, because I don’t like writing code that I don’t quite understand.

Answer 1

From here:

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

Expand the three squares, so you have a long expression:

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

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

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

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

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

Answer 2

A detailed description of each step; hope this makes things crystal clear. The equation for a three-dimensional sphere:

(xa)^2 + (yb)^2 + (zc)^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.

Parametric equations for the beam:

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

where <xo, yo, zo> is the beam source, and <xd,yd,yd> is the direction of the camera beam.

To find the intersection, we want to see which points on the ray coincide with the points on the sphere. Therefore, we substitute the equation of the ray in the equation of the sphere:

(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] * 1 = 0 

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

• 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:

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

Part B^2 - 4AC is called the "discriminant." Depending on the value of the discriminant, we obtain 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 zero, then the ray intersects the sphere at exactly 1 point (it exactly touches the sphere).

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

If the discriminant indicates that there is no solution, then everything is ready! The ray does not cross the sphere. If the discriminant indicates at least one solution, you can decide for t determine the intersection point. These two solutions:

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

A smaller solution is the point at which the ray first enters the sphere.