Intersection of sphere with triangle containing moving vertices

Question

First off, apologies if I cannot properly articulate my question in the most formal way. However, I believe my question should be simple enough to grasp anyhow.

In $\mathbb{R}^3$, I would like to determine the time of contact, if any, between:

• An unmoving unit sphere, whose center is at the origin
• A triangle, each of whose vertices follow independent, linear motion from $t = 0$ to $t = 1$. In other words, each triangle vertex has a start and end position, which are linearly interpolated by $t$.

The sphere may touch the triangle on a vertex, an edge, or on the triangle's surface. Vertex testing is simple enough as it's analogous to static line segment-sphere intersection.

For edge testing, parameterizing a line-sphere intersection test by $t$ appears to lead to solving a degree 4-polynomial, which isn't ideal. I believe that doing the same for triangle surface testing (parameterizing a sphere-plane intersection with $t$) would lead to solving a 6-degree polynomial.

Would there be any applicable non-analytical methods to approximate the intersection (other than directly approximating the polynomial roots)? Or maybe there is an analytical method that I'm not thinking of. In addition, would further constraining the motion of the triangle potentially simplify a solution?

Answer 1

OP: "would further constraining the motion of the triangle potentially simplify a solution?"

(1) Because the triangle vertices follow independent paths, the shape of the triangle is changing over time. If the triangle's shape were fixed, and it translates only, then there are existing algorithms:

David Eberly, "Intersection of Moving Sphere and Triangle." Geometric Tools link. PDF download.

"This document describes how to compute the first time of contact and the point of contact between a (solid) sphere and triangle, both moving with constant linear velocities."

---

         
          ^{Fig.4. Predicted contact time and point for a sphere and triangle, each moving with constant linear velocity.}

---

(2) If the triangle shape is fixed, but its motion is unconstrained, then the 3D shape is known as a swept surface, in your case in fact a ruled surface. I am not finding an exact match to your problem, but perhaps it is implied by work such as this:

Seong, Joon-Kyung, Ku-Jin Kim, Myung-Soo Kim, Gershon Elber, and Ralph R. Martin. "Intersecting a freeform surface with a general swept surface." Computer-Aided Design 37, no. 5 (2005): 473-483. Journal link.

"We present efficient and robust algorithms for intersecting a rational parametric freeform surface with a general swept surface. "