Line–sphere intersection

The three possible line-sphere intersections:
1. No intersection.
2. Point intersection.
3. Two point intersection.

In analytic geometry, a line and a sphere can intersect in three ways: no intersection at all, at exactly one point, or in two points. Methods for distinguishing these cases, and determining equations for the points in the latter cases, are useful in a number of circumstances. For example, this is a common calculation to perform during ray tracing (Eberly 2006:698).

Calculation using vectors in 3D

In vector notation, the equations are as follows:

Equation for a sphere

\left\Vert {\mathbf {x}}-{\mathbf {c}}\right\Vert ^{2}=r^{2}

$\mathbf {c}$ - center point
$r$ - radius
$\mathbf {x}$ - points on the sphere

Equation for a line starting at $\mathbf{o}$

{\mathbf {x}}={\mathbf {o}}+d{\mathbf {l}}

$d$ - distance along line from starting point
$\mathbf {l}$ - direction of line (a unit vector)
$\mathbf{o}$ - origin of the line
$\mathbf {x}$ - points on the line

Searching for points that are on the line and on the sphere means combining the equations and solving for $d$ :

Equations combined

\left\Vert {\mathbf {o}}+d{\mathbf {l}}-{\mathbf {c}}\right\Vert ^{2}=r^{2}\Leftrightarrow ({\mathbf {o}}+d{\mathbf {l}}-{\mathbf {c}})\cdot ({\mathbf {o}}+d{\mathbf {l}}-{\mathbf {c}})=r^{2}

Expanded

d^{2}({\mathbf {l}}\cdot {\mathbf {l}})+2d({\mathbf {l}}\cdot ({\mathbf {o}}-{\mathbf {c}}))+({\mathbf {o}}-{\mathbf {c}})\cdot ({\mathbf {o}}-{\mathbf {c}})=r^{2}

Rearranged

d^{2}({\mathbf {l}}\cdot {\mathbf {l}})+2d({\mathbf {l}}\cdot ({\mathbf {o}}-{\mathbf {c}}))+({\mathbf {o}}-{\mathbf {c}})\cdot ({\mathbf {o}}-{\mathbf {c}})-r^{2}=0

The form of a quadratic formula is now observable. (This quadratic equation is an example of Joachimsthal's Equation .)

ad^{2}+bd+c=0

where

$a={\mathbf {l}}\cdot {\mathbf {l}}=\left\Vert {\mathbf {l}}\right\Vert ^{2}$
$b=2({\mathbf {l}}\cdot ({\mathbf {o}}-{\mathbf {c}}))$
$c=({\mathbf {o}}-{\mathbf {c}})\cdot ({\mathbf {o}}-{\mathbf {c}})-r^{2}=\left\Vert {\mathbf {o}}-{\mathbf {c}}\right\Vert ^{2}-r^{2}$

Simplified

d={\frac {-({\mathbf {l}}\cdot ({\mathbf {o}}-{\mathbf {c}}))\pm {\sqrt {({\mathbf {l}}\cdot ({\mathbf {o}}-{\mathbf {c}}))^{2}-\left\Vert {\mathbf {l}}\right\Vert ^{2}(\left\Vert {\mathbf {o}}-{\mathbf {c}}\right\Vert ^{2}-r^{2})}}}{\left\Vert {\mathbf {l}}\right\Vert ^{2}}}

Note that

\mathbf {l}

is a unit vector, and thus

\left\Vert {\mathbf {l}}\right\Vert ^{2}=1

. Thus, we can simplify this further to

d=-({\mathbf {l}}\cdot ({\mathbf {o}}-{\mathbf {c}}))\pm {\sqrt {({\mathbf {l}}\cdot ({\mathbf {o}}-{\mathbf {c}}))^{2}-\left\Vert {\mathbf {o}}-{\mathbf {c}}\right\Vert ^{2}+r^{2}}}

If the value under the square-root ( $({\mathbf {l}}\cdot ({\mathbf {o}}-{\mathbf {c}}))^{2}-\left\Vert {\mathbf {o}}-{\mathbf {c}}\right\Vert ^{2}+r^{2}$ ) is less than zero, then it is clear that no solutions exist, i.e. the line does not intersect the sphere (case 1).
If it is zero, then exactly one solution exists, i.e. the line just touches the sphere in one point (case 2).
If it is greater than zero, two solutions exist, and thus the line touches the sphere in two points (case 3).

References

David H. Eberly (2006), 3D game engine design: a practical approach to real-time computer graphics, 2nd edition, Morgan Kaufmann. ISBN 0-12-229063-1

This article is issued from Wikipedia - version of the 2/3/2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Line–sphere intersection

Calculation using vectors in 3D

See also

References