I'm rolling the world!

Sorry, I couldn't think of a relevant title for this post. This post is all about maths. So, if you hate maths, just look somewhere else. I'm not boasting or anything here, just bored only.

(David, you love Quadratics right? Well, here are some Quadratics for you!)

Right, do you remember about my post about ray tracing. Yeah, I tried implementing it, but it was too buggy, so I scrapped the project. The most simplest thing to ray-trace is a sphere. It's very simple to trace a line through a sphere. But, let's represent a sphere with a circle for simplicity okay.

Okay, a circle can be represented by this equation:
1) (x-x₀)²+(y-y₀)²-r²=0
where x₀ and y₀ represents the coordinate of the center of the circle in the Cartesian Plane.

I'm won't go through the details on why the circle's equation is like what I've typed above. If you know Pythagoras' theorem and the Cartesian grid, you should probably have a little understanding on how it's defined.

Next, the equation to represent a line. Here, I'll use vectors.
2) P=L+Dt
where
P is the (x,y) coordinate that lies on the line
L represents the line origin point (the line's starting point)
D is the direction of the line. This is a unit vector (a 1-unit long vector)
t is a scalar value. It's sort of like the distance from point P to L₀

So, now, how do we check whether a line intersects with a given circle? First, we derive two formulas from equation 2.

3) x=L_x+D_x t
4) y=L_y+D_y t

If the line were to intersect the circle, there will be at least 1 coordinate that will satisfy both the circle equation and the line equation. Equations 3 and 4 are just to find the x and y components of the resulting vector P.

Anyway, let's plug those two babies into the circle equation:
5) (L_x+D_x t - x₀)² + (L_y+D_y t - y₀)² - r²=0

You're gonna hate what's coming up next. Now, you've got to expand it. Remember the (a-b)² expansion rule? Hopefully you do because it's one very important rule. Well, Same goes for the (a+b)² and all his cousins. Okay, you know what I mean right?

(a-b)²=a²-2ab+b²

By applying that into equation 5, you'll get a very big mess...
6) ( (L_x+D_x t)² - 2(L_x+D_x t)(x₀) + x₀² ) + ( (L_y+D_y t)² - 2(L_y+D_y t)(y₀) + y₀² ) - r² = 0

This is one hard thing to type out in HTML man. Phew... got that down. Now, expand it some more to get an even bigger mess!!!

7) (L_x² + 2L_xD_xt+D_x²t² -2x₀L_x - 2x₀D_xt+x₀²) + (L_y² + 2L_yD_yt+D_y²t² - 2y₀L_y - 2y₀D_yt + y₀²) - r² = 0

Starting to hate Maths already? Well, too bad. That's not the end of the horror.

Now, introducing the Quadratic equation:

8) Ax² + Bx + C = 0
Now, instead of x, we need to find t.
So, equation (8) will be rewritten as

8) At² + Bt + C = 0

To fill up the quadratic equation, we need the values of A, B and C. Where do we get such values? Do we like wish upon a star for it to come out? Do we dig underground to look for it? Not really. All you need to do is take equation (7) and factorise out t² and t. After that, the remaining terms will be C.

So, factorising, you'll get:

(D_x² + D_y²)t² + (2L_xD_x + 2L_yD_y - 2x₀D_x - 2y₀D_y)t + (L_x² + L_y² - 2x₀L_x - 2y₀L_y + x₀² + y₀² - r²) = 0

You should now be able to see clearly which is A, B and C.
A = (D_x² + D_y²) = 1
Mind you, the direction vector is a unit vector. This is just the Pythagoras' way of finding the length of the direction vector. In the end, you'll always get 1 for A (so long as the direction vector is a unit vector. Remember that)

B = (2L_xD_x + 2L_yD_y - 2x₀D_x - 2y₀D_y)
C = (L_x² + L_y² - 2x₀L_x - 2y₀L_y + x₀² + y₀² - r²)

Introducing, another pain in the ass (sorry David, I know how much you love Quadratics).

Now, that's the wonderful quadratics formula to solve for the value of "t". (Just substitute the "x" in the above equation with t)

Now, plug in the values that we have just obtained for A, B and C into a,b and c in the above equation and solve for t.

Once you have the value(s) of t, plug it into equation (3) and (4) to get the x and y coordinates of the intersection point(s).

One tip, by using the discriminant, b² - 4ac, you can determine how many intersection points are there.

If...
b² - 4ac = 0, there's only 1 intersection point
b² - 4ac > 0, there are 2 intersection points, thus, 2 possible values for t
b² - 4ac < 0, no intersections.

Here's an example:


Anyway, here's how to do it. Let's try with the red line. The starting point of the line (the origin of the line, L) is (-5,-5). The direction is actually supposed to be 1 over square root of 2 (1/sqrt(2)). 0.707 is just approximation.

The circle's center is at (2,2) and has a radius of 2. So, we got everything we need. Let's crank it up using the formulas above. First, let's get A, B and C!!
A=1 (direction vector is 1 unit long)
B= (2L_xD_x + 2L_yD_y - 2x₀D_x - 2y₀D_y)
So, B=-19.796

C = (L_x² + L_y² - 2x₀L_x - 2y₀L_y + x₀² + y₀² - r²)
So, C=94.

FYI, my calculations may be wrong. This is really one complicated formula, and because I'm always very careless, mistakes may occur. If you think I may be wrong, just ignore it. This won't appear in your Math syllabus.

Okay, let's find the discriminant:
b² - 4ac = 15.88
And 15.88 > 0, so there are two intersections, as shown by the image above.

The value of t would be:
t=[19.796+sqrt(15.88)]/2 = 11.89
t=[19.796-sqrt(15.88)]/2 = 7.91

Now, slap the values of t into equation (3) and (4) to get the x,y values of the intersection points and you'll get

(3.4, 3.4)
(0.59, 0.59)

Those are the intersection points of the line and the circle. Remember, that's just an approximation. So, it's not 100% accurate, there's about 1% margin of error.

So, I hope you get it. It's interesting, no? You can try it out with the blue line.