01 Sep 2018

Part 1: Ray tracing: Computing ray-circle intersections

Part 2: Ray tracing: Computing ray-circle intersections

I'm currently making my way through Ray tracing in One Weekend (now also available for free) and its 500 lines of C++ code. Being a bit rusty on the math side, these posts serve as my notes and supplement the book.

In this post I focus on the mechanics of 2D line-circle intersection. This technique is required in order to trace a ray from the eye, or camera position, through a pixel on the screen, or image plane, and into the scene. As the ray travels through the scene, we want to determine whether it hits, or intersects with, the circle, or scene object, and if so at which positions. These positions determines the image plane's color at that pixel.

I start out with line-circle intersections in 2D because it's simpler to visualize and because once the scalar math is worked out, it generalizes nicely to 3D and vector math. To develop a visual intuition for the math, I found it helpful to play with the equations in Wolfram Alpha and similar sites.

In 3D space, the process is nicely illustrated in the Wikipedia article on ray tracing.

For a gentle introduction to the topic of ray tracing, I recommend watching Disney's short Practical Guide to Path Tracing and the the Painting With Light conference talk.

A circle may be defined in terms of the position of its center and its radius. To start simple, assume the circle is centered around the origin at \((0,0)\). In this case, the circle equation, or circle on standard form as it's also called, is: $$x^2 + y^2 = r^2$$ The way to read the circle equation is that for any \((x,y)\), if \(x^2 + y^2 = r^2\) holds true, then the point is on the circle, otherwise it's not. The circle equation follows from the Pythagorean theorem, or distance formula. In order to visualize the relationship between the circle equation and the Pythagorean theorem, consider a point \((x,y)\) on the circle shown below:

For this right-sided triangle, \(\sqrt{x^2 + y^2} = r\) holds true. By squaring both sides we get rid of the square root and end up with the circle equation.

Instead of a circle centered at \((0,0)\), it may be centered at any point \((c_x, c_y)\): $$\begin{eqnarray*} (x - c_x)^2 + (y - c_y)^2 = r^2 & & \textrm{or} & & \sqrt{(x - c_x)^2 + (y - c_y)^2} = r \end{eqnarray*}$$ As an example, imagine the circle's center being to the right and up with respect to origin. For the circle equation to still hold true, \((x,y)\) points on the circle must have greater values of \(x\) and \(y\) than when the circle was centered at origin.

To keep the following examples short, they assume the circle is centered at \((0,0)\) such that \(c_x\) and \(c_y\) from the circle equation may be ignored.

Circle equation in hand, if provided with a point \((x,y) = (-3,4)\) on a circle, and assuming the circle is centered around origin, the circle equation can be determined: $$\begin{eqnarray*} x^2 + y^2 = r^2\\ (-3)^2 + 4^2 = r^2\\ 9 + 16 = r^2\\ 5 = r \end{eqnarray*}$$ meaning this circle's equation is $$x^2 + y^2 = 5^2$$

Comparing the distance of a point to the center of a circle defined by \(x^2 + y^2 = 5^2\), any point may be determined as either inside, outside, or on the circle: $$\begin{eqnarray*} (2,-3): \sqrt{2^2 + (-3)^2} = \sqrt{13} \approx 3.6 & & \textrm{\{inside circle\}}\\ (1,5): \sqrt{1^2 + 5^2} = \sqrt{26} \approx 5.1 & & \textrm{\{outside circle\}}\\ (-4,-3): \sqrt{(-4)^2 + (-3)^2} = \sqrt{25} = 5 & & \textrm{\{on circle\}}\\ \end{eqnarray*}$$

For additional explanation, refer to this video.

Assuming a circle \(x^2 + y^2 = r^2\) and a line \(y = ax + b\), both on their standard form (if not, we first must bring those on standard form), three possible intersection scenarios exists:

As an example, let's go with the circle \(x^2 + y^2 = 3^2\) and the line \(y = -x + 3\). If the two intersect, it implies that for some same value of \(x\) and for some same value of \(y\), plugging those values into both equations, they each hold true. It doesn't imply that the left side of one equation equals the right side of the other, but that the left and right side of each equation by itself holds true.

At a point of intersection, the value of \(x\) and the value of \(y\) in the two equation are the same. Thus, either \(y = -x + 3\) or \(x = -y + 3\) of the line equation may be plugged into the circle equation. Plugging in \(y\) results in $$x^2 + (-x + 3)^2 = 3^2$$ The goal of plugging one equation into the other is that instead of one circle equation with two variables (\(x\) and \(y\)), out comes one quadratic equation with one variable (\(x\)): $$\begin{eqnarray*} x^2 + (-x + 3)(-x + 3) = 3^2 & & \textrm{\{expand \(y = -x + 3\)\}}\\ x^2 + x^2 - 3x - 3x + 9 = 9 & & \textrm{\{multiply out parenthesis\}}\\ x^2 + x^2 - 3x - 3x = 0 & & \textrm{\{subtract 9 from both sides\}}\\ 2x^2 - 6x = 0 & & \textrm{\{simplify\}} \end{eqnarray*}$$ Solving a quadratic equation of the standard form \(ax^2 + bx + c = 0\) for \(x\) means determining values of \(x\) for which \(y = 0\). In other words, determining where the quadratic equation intersects the \(x\) axis.

Depicted graphically, the line, circle, and quadratic equations are shown below. Visually, it's easy to confirm that the solutions to the quadratic equation are \(x_1 = 0\) and \(x_2 = 3\):

Solving algebraically, the standard method involves plugging the coefficients of \(ax^2 + bx + c\), that is \(a\), \(b\), and \(c\), into the equation below, with \(d\) being the discriminant: $$\begin{eqnarray*} x = \dfrac{-b \pm \sqrt{d}}{2a} \textrm{, where \(d = b^2 - 4ac\)} \end{eqnarray*}$$ The discriminant signals which of the three intersection scenarios to expect. If \(d = 0\), then one solution, or intersection, exist as the square root term disappears from the equation. If \(d > 0\), two solutions, or intersections, exist as the square root term must be both added and subtracted. If \(d < 0\), no solution, or intersection, exist as calculating the square root of a negative number is undefined:

$$d = (-6)^2 - 4(2)(0) = 36$$ Calculating the discriminant on its own, without plugging it into the larger equation, is useful only as a means to determine the number of solutions. For the actual solutions, the points of intersection, the larger equation is needed: $$\begin{eqnarray*} x_1 = \dfrac{-(-6) + \sqrt{36}}{2(2)} = \dfrac{6 + 6}{4} = \dfrac{12}{4} = 3\\ x_2 = \dfrac{-(-6) - \sqrt{36}}{2(2)} = \dfrac{6 - 6}{4} = \dfrac{0}{4} = 0 \end{eqnarray*}$$ Finally, plugging the two values of \(x\) into either equation gets us the corresponding values of \(y\). The line equation is the simplest of the two: $$\begin{eqnarray*} y_1 = -x_1 + 3 = -0 + 3 = 3\\ y_2 = -x_2 + 3 = -3 + 3 = 0 \end{eqnarray*}$$ and so the points of intersection of the line and the circle are at \((0,3)\) and \((3,0)\).

For additional explanation on calculating the discriminant and points of intersection, refer to this and this video.

At first sight, the math introduced in this post may not seem all that relevant or important. After all, most high school students are taught these subjects. The true power, however, become apparent in the next post where the techniques are generalized from 2D to 3D (to any dimension, actually) and from scalars to vectors. 3D and vectors are what's needed for ray tracing.