Ray-sphere Intersection
We've seen how to form a ray following the trajectory of the mouse, but that's only half the solution to making a renderer interactive. We must also see what that ray hits and where. This is collision detection. There are algorithms for intersecting a ray with a triangle. Modern games on ultra settings can render 10 million triangles per frame. But detecting collisions with that many is far too expensive.
A faster method is to collide not with a detailed trimesh but simpler proxy geometry like a bounding box or a bounding sphere. Let's examine intersecting a bounding sphere first, because it's less involved.
First, we observe the fact that a point \(\mathbf{p}\) is on a sphere of radius \(r\) if it satisfies the implicit equation of a sphere:
Note that the sum on the left-hand side is dot product. We can therefore rewrite the equation like so:
These equations apply only if the sphere is centered at the origin. If it's positioned elsewhere, we must translate it to the origin:
Second, we observe that a point \(\mathbf{p}\) on the ray that starts at \(\mathbf{o}\) and points in direction \(\mathbf{d}\) must satisfy this parametric equation:
We want to find a point that is both on the ray and on the sphere, so we combine the two equations:
Before we can act on this, we need to establish a property of the dot product. We've seen binomial expansion applied to the multiplication of sums of scalars. Does it also apply to the dot product of sums of vectors? Let's expand out such an expression and then regroup the terms:
The dot product does indeed distribute over vector addition. To expand out our combined equation, we must sum these combinations of dot products:
| \(\mathbf{o}\) | \(t \times \mathbf{d}\) | \(-\mathbf{c}\) | |
| \(\mathbf{o}\) | \(\mathbf{o} \cdot \mathbf{o}\) | \(\mathbf{o} \cdot \mathbf{d} \times t\) | \(-\mathbf{c} \cdot \mathbf{o}\) |
| \(t \times \mathbf{d}\) | \(\mathbf{o} \cdot \mathbf{d} \times t\) | \(\mathbf{d} \cdot \mathbf{d} \times t^2\) | \(-\mathbf{c} \cdot \mathbf{d} \times t\) |
| \(-\mathbf{c}\) | \(-\mathbf{c} \cdot \mathbf{o}\) | \(-\mathbf{c} \cdot \mathbf{d} \times t\) | \(\mathbf{c} \cdot \mathbf{c}\) |
Let's group these terms: one includes \(t^2\), four include \(t\), and four are constants. This grouping lets us rewrite the sum as a quadratic equation of \(t\):
We've moved \(r^2\) into \(c\) to put the equation in standard form. The only unknown is \(t\). We solve for it using the quadratic equation:
The value \(t\)—if there is one—is a scalar that tells us how far along the ray the intersection occurs. The ray may never hit the sphere, may hit it exactly once, or may hit it twice. We examine the discriminant \(b^2 - 4ac\) to determine the number of intersections. If it's negative, there are none. If it's 0, there's one. If it's positive, there are two.
Cast a ray in this renderer and rotate the scene to see how the ray intersects the sphere. Achieving only a single intersection is nearly impossible because making a ray tangent requires more precision than we can achieve with the mouse.
All that remains is to turn this math into a reusable function with more helpful variable names.
Place this function in lib/intersect.ts.