Swept Sphere vs Linesegment
Kasper Fauerby presented this excellent article on how to collide moving
ellipsoids with triangles: https://www.peroxide.dk/papers/collision/collision.pdf.
After colliding the swept ellipsoid with the inside of the triangle
he goes on to explain how to test for the collision with the three points of the
triangle. This test leads to a quadratic formula of the known form of
\[
At^2 + Bt + C = 0 \label{eq:standard-quadratic-form} \tag{1}
\]
He also explains that we arrive at the same quadratic form for testing the swept
ellipsoid against the sides (linesegments) of the triangle.
However, what the parts \(A, B\) and \(C\) are in case of the
sphere vs. linesegment test is not being derived in the paper. This article tries to fill that gap.
The premise
Let us look at what is going on again:
The sphere is travelling along its velocity vector \(v\).
At a time \(t_{0}\) the sphere will hit the linesegment. At that time the distance
of the center \(C(t_{0})\) of the moving sphere to the line will be smaller than the radius
\(r\) of the sphere.
In our case the distance from
Point \(C(t_{0})\) towards the line will be:
\[
distance = \Vert C(t_{0}) - (P_{1} +s\vec{d})\Vert, s \in \mathbb{R}
\]
\(\vec{d}\) is the direction-vector of the
line that is formed of the two vertices \(P_{1}\) and \(P_{2}\).
We also know that we are dealing with a unit-sphere so
the distance when the sphere is about to hit must be \(1\):
\[
1 = \Vert C(t_{0}) - (P_{1} +s\vec{d})\Vert
\]
Now, we rewrite it by taking the squared distance. That
way we can get rid of the square root that we would have to
to deal with when calculating the length of \(C(t_{0}) - (P_{1} +s\vec{d})\):
\[
1^2 = \Vert C(t_{0}) - (P_{1} +s\vec{d})\Vert^2 \Leftrightarrow 1 = \sqrt{\left(C(t_{0}) - (P_{1} +s\vec{d})\right) \cdot \left(C(t_{0}) - (P_{1} +s\vec{d})\right)}^2
\]
\[
\Leftrightarrow 1 = \left(C(t_{0}) - (P_{1} +s\vec{d})\right) \cdot \left(C(t_{0}) - (P_{1} +s\vec{d})\right) \label{eq:initial-distance} \tag{2}
\]
Down to the detail
So far so good. Now we have two unknowns in the equation: The scalars \(t_{0}\) and \(s\).
\(t_{0}\) is the value we want to have in the end. This is the ultimate goal. So how
to get rid of, or rather, replace \(s\)? Well, we make another drawing that will
hopefully give us more information (it will!):
We see that we can represent \(s\) as the sum of the projections of the vectors \(C - P_{1}\)
and \(t_{0}\vec{v}\) onto the line-direction vector \(\vec{d}\):
\[
proj_{\vec{d}}(C - P_{1}) = \frac{\vec{d} \cdot (C - P_{1})}{\vec{d} \cdot \vec{d}}
\]
\[
proj_{\vec{d}}t_{0}\vec{v} = \frac{\vec{d} \cdot t_{0}\vec{v}}{\vec{d} \cdot \vec{d}}
\]
\[
\Rightarrow s = \frac{\vec{d} \cdot (C - P_{1})}{\vec{d} \cdot \vec{d}} + \frac{\vec{d} \cdot t_{0}\vec{v}}{\vec{d} \cdot \vec{d}}
\]
Beautiful! Now, we’re left with just one unknown, namely \(t_{0}\). Just what we want.
Substituting \(s\) into \eqref{eq:initial-distance} yields:
\[
1 = \left\Vert \ C(t_{0}) - P_{1} - \left(\frac{\vec{d} \cdot (C - P_{1})}{\vec{d} \cdot \vec{d}} +
\frac{\vec{d} \cdot t_{0}\vec{v}}{\vec{d} \cdot \vec{d}}\right)\vec{d} \ \right\Vert^2
\]
Also, the point \(C(t_{0})\) is just \(C + t_{0}\vec{v}\). So let us substitute
that as well and expand it:
\[
1 = \left\Vert \ C + t_{0}\vec{v} - P_{1} - \frac{\vec{d} \cdot (C - P_{1})}{\vec{d} \cdot \vec{d}}
\vec{d} - \frac{\vec{d} \cdot t_{0}\vec{v}}{\vec{d} \cdot \vec{d}}\vec{d} \ \right\Vert^2 \label
{eq:main-equation} \tag{3}
\]
Let us focus on the right part of the equation. One way of getting hold of all these parts of the term
is to organize it so that it becomes clear that it is a binomial:
\[
\left\Vert \left( \vec{v} - \frac{\vec{d} \cdot \vec{v}}{\vec{d} \cdot \vec{d}}\vec{d} \right)t_{0} +\left( (C-P_{1}) - \frac{\vec{d} \cdot (C-P_{1})}{\vec{d} \cdot \vec{d}}\vec{d} \right) \right\Vert^2
\]
which now can be seen as:
\[
A^2t_{0}^2 + 2ABt_{0} + B^2
\]
when expanded. So we do just that and locate
\({\color{#00aaff} A}, {\color{lime} B}\) and \({\color{#bb0000}C}\) of the standard quadratic form \eqref{eq:standard-quadratic-form}:
\[
{\color{#00aaff} \left\Vert \ \vec{v} - \frac{\vec{d} \cdot \vec{v}}{\Vert \vec{d} \Vert ^2} \vec{d} \ \right\Vert^2} t_{0}^2
+{\color{lime}2 \left(\vec{v} - \frac{\vec{d} \cdot \vec{v}}{\Vert \vec{d} \Vert ^2} \vec{d} \right)}t_{0} {\color{lime}\Biggl( (C-P_{1}) - \frac{\vec{d} \cdot (C-P_{1})}{\Vert \vec{d} \Vert ^2} \vec{d}\Biggr)}
+{\color{#bb0000}\left\Vert \ (C-P_{1}) - \frac{\vec{d} \cdot (C-P_{1})}{\Vert \vec{d} \Vert ^2}\vec{d} \ \right\Vert^2}
\]
\[
\begin{equation}
\begin{split}
{\color{#00aaff}A} &= \left\Vert \ \vec{v} - \frac{\vec{d} \cdot \vec{v}}{\Vert \vec{d} \Vert ^2}\vec{d} \ \right\Vert^2 = \Vert \vec{v} \Vert ^2 - 2\vec{v} \frac{\vec{d} \cdot \vec{v}}{\Vert \vec{d} \Vert ^2}\vec{d} + \frac{(\vec{d} \cdot \vec{v})^2}{\Vert \vec{d} \Vert ^4} \Vert \vec{d} \Vert ^2 = {\color{#00aaff}\Vert \vec{v} \Vert ^2 - \frac{(\vec{d} \cdot \vec{v})^2}{\Vert \vec{d} \Vert ^2}} \\
{\color{lime}B} &= 2 \left(\vec{v} - \frac{\vec{d} \cdot \vec{v}}{\Vert \vec{d} \Vert ^2} \vec{d} \right) \cdot \Biggl( (C-P_{1}) - \frac{\vec{d} \cdot (C-P_{1})}{\Vert \vec{d} \Vert ^2} \vec{d}\Biggr)
= {\color{lime}2\vec{v} \cdot (C-P_{1}) - 2\frac{\vec{d} \cdot \vec{v}}{\Vert \vec{d} \Vert ^2}\vec{d} \cdot (C-P_{1})} \\
{\color{#bb0000}C} &= \left\Vert \ (C-P_{1}) - \frac{\vec{d} \cdot (C-P_{1})}{\Vert \vec{d} \Vert ^2}\vec{d} \ \right\Vert^2
= {\color{#bb0000}(C-P_{1})^2 - \frac{\left(\vec{d} \cdot (C-P_{1})\right)^2}{\Vert \vec{d} \Vert ^2}}
\end{split}
\end{equation}
\]
Putting it all together, replacing \eqref{eq:main-equation} with our re-arranged form. We also bring the \(1\)
over to the other side and make it part of \({\color{#bb0000}C}\) as it is independent from \(t_{0}\):
\[
{\color{#00aaff}\left(\Vert \vec{v} \Vert ^2 - \frac{(\vec{d} \cdot \vec{v})^2}{\Vert \vec{d} \Vert ^2}\right)}t_{0}^2 +
{\color{lime}\left(2\vec{v} \cdot (C-P_{1}) - 2\frac{\vec{d} \cdot \vec{v}}{\Vert \vec{d} \Vert ^2}\vec{d} \cdot (C-P_{1})\right)} t_{0}
+{\color{#bb0000}(C-P_{1})^2 - \frac{\left(\vec{d} \cdot (C-P_{1})\right)^2}{\Vert \vec{d} \Vert ^2} - 1} = 0
\]
Then, we multiply both sides with \(\Vert \vec{d} \Vert ^2\) in order to get rid of the divison and compress
\({\color{#bb0000}C}\) a bit more:
\[
{\color{#00aaff}\left (\Vert \vec{v} \Vert ^2 \Vert \vec{d} \Vert ^2 - (\vec{d} \cdot \vec{v})^2 \right)} t_{0}^2 +
{\color{lime}\left (2\vec{v} \cdot (C-P_{1})\Vert \vec{d} \Vert ^2 - 2(\vec{d} \cdot \vec{v})(\vec{d} \cdot (C-P_{1})) \right)} t_{0}
+{\color{#bb0000}\left(\Vert C-P_{1} \Vert ^2 - 1\right)\Vert \vec{d} \Vert ^2 - \left(\vec{d} \cdot (C-P_{1})\right)^2} = 0
\]
We have arrived at what Fauerby’s paper presents for \(A, B\) and \(C\). Well. Almost! You may have
noticed that both terms \({\color{#00aaff}A}\) and \({\color{#bb0000}C}\) have flipped signs. I honestly have no idea why that is! I though it is due to
the fact that he used a vector from \(C\) towards \(P_{1}\) whereas this article uses the inverted vector
(from \(P_{1}\) to \(C\)). The projection onto \(\vec{d}\) would be
a negative value if we take the vector from \(C\) to \(P_{1}\). However, I still arrived at the same terms
as derived above. If I figure this out at some point I will edit this section.
The final step: Do we actually hit the linesegment?
Moving on, we now can easily use the well known formula to get \(t_{0}\):
\[
t_{1/2} = \frac{-b \pm \sqrt{b^2-4ac}}{2a}
\]
So if the resulting \(t\) is smaller than the one we got from the previous test (swept-ellipsoid vs. triangle’s points)
then we know that the ellipsoid collides with the infinite line at time \(t_{0}\). So the
last thing to do is to check if that collision takes place within the line-segment. I am just paraphrasing
Fauerby’s paper here, just to setup the stage for what we have to do.
The scalar \(s\) must be within \([0, 1]\). If it is \(< 0\) the collision takes place before \(P_{1}\).
If \(s\) > \(1\) then the ellipsoid collides after \(P_{2}\). Thus we use our \(t_{0}\) we just computed
and calculate \(s\):
\[
s = \frac{\vec{d} \cdot (C - P_{1})}{\vec{d} \cdot \vec{d}} + \frac{\vec{d} \cdot t_{0}\vec{v}}{\vec{d} \cdot \vec{d}}
\]
In Fauerby’s paper \(s\) is called \(f_{0}\). Also, again, we see that he uses the “negative” projection of \(P_{1} - C\) onto
\(\vec{d}\).
Anyways, if \(s\) is within the range \([0, 1]\) then we have a collision with one of the triangles’s sides at point
\[
P_{1} + s\vec{d}
\]
after the ellipsoid has travelled a distance of
\[
t_{0}\Vert \vec{v} \Vert
\]
And that’s it! See you in the next one. Cheers!
Thanks
I’d like to thank David Eberly for replying to a question I had about his book 3D Game Engine Design where I
spotted an error. Only one hour after I had written him an email I got his response back with the clarification.
That is quite some customer support for a book that is a quarter of a century old by now!
Also, thank you to my former professor, Dr. Ruckert, who clarified an algebraic question I had.
Thanks to Daniel Gibson, who took the time to adjust the colors of the equation so that they are
distinguishable for people with color-blindness.
And, of course, thanks to Kasper Fauerby for the original text. I wish we had more such excellent papers
that present concepts in such a concise and clear way.
BibTex
@article{ eggers-michael_2025,
author = Eggers, Michael,
title = Swept Ellipsoid vs. Linesegment,
year = 2025
}
Download BibTeX