Calculate if vector intersects sphere

Question

I have a 3D world and I have a gun who's position is defined by X,Y,Z which fires a bullet in a straight line with a direction defined by X, Y, Z towards a target who position is defined by X,Y,Z with a spherical bounding volume.

How can I calculate if the bullet intersects the sphere?

Answer 1

Does the bullet fly in a straight line or is there gravity in some direction? Assuming a straight line, that the weapon's position is $(X_1,Y_1,Z_1)$, the velocity of the bullet is $(V_x, V_y, V_z)$, the center of the sphere is $(X_2,Y_2,Z_2)$, and the radius of the sphere is R, then the bullet's path is given by $x= X_1+ V_xt$, $y= Y_1+ V_yt$, $z= Z_1+ V_zt$ and the sphere by $(x- X_1)^2+ (y- Y_2)^2+ (z- Z_2)^2= R^2$. Put the x, y, z equations of the bullet into the sphere equation and solve the quadratic equation for t. If there is no positive, real solution, the bullet misses the sphere. If there is a double positive root the bullet grazes the sphere, and if there are two positive solutions, the bullet passes through the sphere. (If there is one positive and one negative solution, the weapon's position is inside the sphere!)

Answer 2

Let $G(X_1,Y_1,Z_1)$ be the weapon's center, $S(X_2,Y_2,Z_2)$ be the sphere's center and $U(u,v,w)$ the shooting direction.

The set of points $P_t$ that belong to the trajectory are described thus:

$$\cases{x=X_1+tu\\y=X_2+tv\\z=X_3+tw} \ \ \ \ \text{for some real} \ t$$

It suffices to express that the distance $SP_t$ is below the sphere's radius $R$ to have an impact on it, or that the square $SP^2$ is below $R^2$:

$$(X_1+tu - Y_1)^2+(X_2+tv - Y_2)^2+(X_3+tw - Y_3)^2 < R^2.$$

Expanding, one obtains that there must exist values of $t$ such that

$$\tag{1}a t^2 + bt + c < 0 \ \text{with} \ \cases{a=u^2+v^2+w^2\\b=-2(u(X_1-Y_1)+v(X_2-Y_2)+w(X_3-Y_3))\\c=(X_1-Y_1)^2+(X_2-Y_2)^2+(X_3-Y_3)^2-R^2}.$$

A necessary and sufficient condition (i.e., the bullet hits the target) for this to hold is that the discriminant is positive:

$$\tag{2}D= b^2 - 4 ac > 0 $$

Then it suffices to plug in (2) the values obtained in (1) to get the final condition.

Pseudo-code:

Read all the necessary data X1,Y1,Z1 (gun) X2,Y2,Z2 (target's center), R (radius) (u,v,w) shooting direction
a=u^2+v^2+w^2;
b=-2*(u*(X1-Y1)+v*(X2-Y2)+w*(X3-Y3));
c=(X1-Y1)^2+(X2-Y2)^2+(X3-Y3)^2-R^2;
d=b^2-4*a*c;
if d>0
hit=1
else hit=0;

(of course, this code can be made more efficient, but readability is important too).

Answer 3

Suppose the line passes through the point $\mathbf{P}$ and is in the direction of the unit vector $\mathbf{U}$. Then its parametric equation can be written $$ \mathbf{L}(t) = \mathbf{P} + t\mathbf{U} $$ Suppose the sphere has center $\mathbf{C}$ and radius $r$. Then a point $\mathbf{X}$ lies on the sphere if $\|\mathbf{X} - \mathbf{C}\|^2 = r^2.$ For any vector $\mathbf{V}$, we know that $\|\mathbf{V}\|^2 = \mathbf{V} \cdot \mathbf{V}$, where the dot denotes a vector dot product. So, the equation of the sphere can be written as $$ (\mathbf{X} - \mathbf{C}) \cdot (\mathbf{X} - \mathbf{C}) = r^2 $$ At points of intersection, we have $$ \big(\mathbf{L}(t) - \mathbf{C}) \cdot (\mathbf{L}(t) - \mathbf{C}\big) = r^2 $$ Using the equation for $\mathbf{L}(t)$ from above, this gives $$ \big(\mathbf{P} + t\mathbf{U} - \mathbf{C}) \cdot (\mathbf{P} + t\mathbf{U} - \mathbf{C}\big) = r^2 $$ $$ \text{i.e.} \quad (\mathbf{P} - \mathbf{C}) \cdot (\mathbf{P} - \mathbf{C}) -r^2 + 2t\mathbf{U} \cdot (\mathbf{P} - \mathbf{C}) +t^2 (\mathbf{U} \cdot \mathbf{U})=0 $$ Solve this quadratic for $t$.

Pseudocode is as follows. It assumes that $+, -, *$ operators have been overloaded to work on 3D points/vectors:

// C = center of sphere
// r = radius of sphere
// P = point on line
// U = unit vector in direction of line

Q = P - C;
a = U*U;      // should be = 1
b = 2*U*Q
c = Q*Q - r*r;
d = b*b - 4*a*c;  // discriminant of quadratic

if d <  0 then solutions are complex, so no intersections
if d >= 0 then solutions are real, so there are intersections

// To find intersections (if you want them)
(t1,t2) = QuadraticSolve(a, b, c);
   if t1 >= 0 then P1 = P + t1*U;   // first intersection
   if t2 >= 0 then P2 = P + t2*U;   // second intersection

We ignore negative values of $t1$ and $t2$ because these correspond to points behind the shooter.