6
$\begingroup$

Given I know two sphere's centre coordinates and their radius.

Let's say both spheres travels in some direction in a straight line.

At t=0, sphere 1 is at (0, 0, 0) and sphere 2 is at (50, 0, 0), their radius is both 30.

At t=1, sphere 1 is at (100, 0, 0) but sphere 2 is at (-50, 0, 0).

How do I check if sphere 2 have passed through sphere 1? (Just touching also count as "passed through").

By just touching, I mean the path the two spheres took touched but didn't overlap.

I can imagine the volume of the two spheres gouging out a capsule, and if this capsule encompasses any portion of the other capsule, then sphere 2 have gone through sphere 1 (true), other wise false.

But I don't know how to verify if a portion of a volume is in another volume.

Scrappy visual of what I'm saying: enter image description here

One sphere travels from yellow to grey, another travel from maroon to purple, how do I tell if the two paths overlap at some point.


Update:

Emac have provided an amazing break down of the problem, but I have failed to extend it to more complex scenarios.

Take this scenario:

enter image description here

All spheres have a radius of 0.5.

The centre coordinates of Red and Blue spheres at time t=0 are at (5, 2, 4) and (1, 3, 6) respectively.

At t=1, the red sphere remained stationary, and the blue sphere have travelled to (6, 2, 3.5).

Examine this images, where I have lined up the camera with the end and start position of the blue sphere (final position of blue sphere is now green):

enter image description here

We can see clearly that the path of the blue sphere will intersect the red sphere at some point in time.

I attempted Emac's answer on this scenario. In my mind, the formula should still work. The derivative of the squared distance between two points in 3D space, then solving for the minimum of that formula seems like a universal solution to all these scenarios, but when I applied the formula, I got t = (4, 0, -2), and I can't make sense of a time vector. I thought perhaps I needed to find the magnitude of this time vector, and that will be my answer, but it returned a time larger than 1, which also doesn't make sense.

To go even further, what if both spheres are both in motion, and they each move diagonally through space, eventually grazing each other at some point. Their radius must be accounted, intersection does not mean full overlap.

$\endgroup$
7
  • $\begingroup$ Welcome to MSE! <> In your example, both spheres are moving along the same axis, in opposite directions. Are you asking more generally about the centers and velocities are known (and arbitrary) at some instant? $\endgroup$ Sep 30, 2023 at 14:29
  • $\begingroup$ Do the spheres travel at a fixed speed? Or do you have more information on their speed? $\endgroup$
    – Trebor
    Sep 30, 2023 at 14:31
  • 1
    $\begingroup$ Two spheres, with radii $r_1$ and $r_2$ respectively, intersect at time $t=T,$ if and only if the distance between the two spheres' centres at time $t=T$ is $\leq r_1 + r_2.$ $\endgroup$ Sep 30, 2023 at 15:31
  • 4
    $\begingroup$ Intersection of the "capsules" is necessary but not sufficient to show that the spheres touched. For example, suppose one sphere travels from $(0,0,0)$ to $(50,0,0)$ and the other travels from $(50,0,0)$ to $(100,0,0)$, and both spheres have radius $10$. The distance between spheres is constant and they never touch, but the capsules certainly intersect at $(50,0,0)$ and nearby points. $\endgroup$
    – David K
    Sep 30, 2023 at 16:02
  • 4
    $\begingroup$ It would be helpful to include in your update how you obtained t = (4, 0, -2), because the formula proposed by emacsdrivesmenuts is actually a ratio of two scalar products, which should not return a vector. $\endgroup$
    – svavil
    Oct 1, 2023 at 7:16

2 Answers 2

16
$\begingroup$

First of all, your problem is actually 1-dimensional, because the $y$ and $z$-coordinates of either ball will be zero at any time. As the balls are approaching each other, they will always intersect!

But let's do the 3-dimensional calculation, anyway. Name the entities:

Let $P_n$ be the position of ball $n$ at $t=0$, and let $v_n$ be the speed vector. This means that the length of $v_n$, denoted $|v_n|$ gets bigger when the respective ball is moving faster. And the direction of $v_n$ is the direction of travel as $t$ increases. More specifically, $v_n = P_n(t=1) - P_n(t=0)$.

Then, as the balls are travelling, there is a unique$^1$ time $t$ when their distance is at a minimum. The balls intersect each other iff the distance at that point is smaller than $r_1+r_2$, the sum of their radii.

So the trajectory of ball $n$ is:

$$ b_n: P_n + tv_n \tag 1 $$ and their distance at time $t$ is:

$$ d(t) = |b_1(t)-b_2(t)| = |P_1-P_2+t(v_1-v_2)| \tag 2 $$ where $|\cdot|$ denotes Euclidean distance. To find the minimum, we could differenciate $d$ and find it's minimum, but $d$ has a nasty square-root in it. The time $t$ at which $d$ attains its minimum is the same like where $d^2$ attains its minimum$^2$, so we can analyze $d^2$ instead:

$$\begin{align} d^2(t) &= (P_1-P_2+t(v_1-v_2))^2\\ &= (P_1-P_2)^2 + 2t(P_1-P_2)(v_1-v_2)+t^2(v_1-v_2)^2 \tag 3 \end{align}$$ Differentiating $(3)$ with respect to $t$: $$ \frac{\mathrm d}{{\mathrm d}t}d^2(t) = 2(P_1-P_2)(v_1-v_2) +2t(v_1-v_2)^2 \tag4 $$ So $d$ has a minimum if $(4)$ vanishes: $$ t=-\frac{(P_1-P_2)(v_1-v_2)}{(v_1-v_2)^2} \tag5 $$ Notice these are vectors, so one cannot cancel out $v_1-v_2$. Also, the denominator is non-zero except in the parallel case$^1$ where $v_1=v_2$ or when both balls are sitting still.

Then plug this into $(1)$ to find the positions and thus their distance at time / position of closest approach.

Dropping in the numbers: $$\begin{align} P_1=(0,0,0) &\qquad v_1 = (100, 0, 0) \\ P_2=(50,0,0) &\qquad v_2 = (-100, 0, 0) \\ P_1-P_2=(-50,0,0) &\qquad v_1-v_2 = (200, 0, 0) \\ (P_1-P_2)(v_1-v_2)=-50\cdot200 &\qquad (v_1-v_2)^2 = 200^2 \\ \end{align}$$

yields $t$ according to $(5)$ $$ t=-\frac{(-50)\cdot200}{200^2}=\frac{50}{200} = 1/4 \tag6 $$

Then plug that $t$ into $(1)$:

$$\begin{align} b_1(t=1/4)&=(25,0,0)\\ b_2(t=1/4)&=(25,0,0) \end{align}$$

so we have a complete hit, no matter how big the balls are! And as I already said above, the problem is 1-dimensional...

There one twist in the general case though: The balls' closest approach may be at negative $t$, but the balls may still intersect at $t=0$, so we conclude with the following procedure:

  • If the time of closest approach is non-negative, compute the distance of the balls at that time and compare to the sum of radii.

  • If the time of closest approach is negative, compute the distance of the balls at $t=0$ (which is $|P_1-P_2|$ and compare that so the sum of radii.

Similarly, when the time is limited to some interval $[t_1,t_2]$: Solve for $t$ and then sort out the two cases:

  • If the $t$ of closest approach $t\in[t_1,t_2]$, then proceed as usual.
  • If the cloases approach time $t\notin[t_1,t_2]$, then check whether the balls intersect at times $t_1$ or $t_2$.

Alternate Approach without Calculus

When the balls intersect, then there are times $t_1$ and $t_2$ when they kiss. To compute these times, solve

$$ d(t) = r_1+r_2 \tag 7 $$ But it will be easier to square $(7)$ which again gets rid of the square-root:

$$\begin{align} (r_1+r_2)^2 &\stackrel.= d^2(t) \\ &\stackrel{(3)}=(P_1-P_2)^2 + 2t(P_1-P_2)(v_1-v_2)+t^2(v_1-v_2)^2\tag8 \end{align}$$ This is a quadratic in $t$:

  • If $(8)$ has no solutions, the balls miss each other

  • If $(8)$ has one solutions, the balls kiss

  • If $(8)$ has two solutions, the balls kiss at $t_1$ and $t_2$ and intersect for all $t\in[t_1, t_2]$ with closest approach at $(t_1+t_2)/2$ due to symmetry.

  • If $v_1=v_2$ then $(8)$ degenerates (no more depends on $t$), and the situation is static, i.e. balls relative position stays the same and does not change with time.


Footnotes

$^1$Except in the case where the balls are travelling in the same direction at the same speed, or more concretely, if $v_1=v_2$.

$^2$Because $x\mapsto x^2$ is strictly increasing for $x\geqslant0$.

$\endgroup$
7
  • $\begingroup$ My interpretation of the question as asked is that there is an ending time to the motion as well as a starting time. So the "twist" occurs both for closest approach at negative $t$ and for closest approach at $t > t_{\rm end}$. But that is easily accounted for using the tools in this answer. Using the square of the distance is a nice simplification. $\endgroup$
    – David K
    Sep 30, 2023 at 15:56
  • $\begingroup$ @DavidK: Thanks, I extended my answer. $\endgroup$ Sep 30, 2023 at 16:51
  • $\begingroup$ @emacsdrivesmenuts This is awesome, and definitely answer the example I provided in my original question. I have tried myself to extend it to more complex scenarios and have failed. If you can, please see the updated question, I will update my original question with another example scenario. $\endgroup$
    – Sheng
    Oct 1, 2023 at 3:00
  • $\begingroup$ @Sheng: Just drop in the other numbers; all you need is vector subtraction (which is component-wise) and dot product. If you have problems carrying out the calculations, then maybe better start a new question instead of turining this one into a moving target. $\endgroup$ Oct 1, 2023 at 8:24
  • $\begingroup$ Of course, dot product. I studied all this vector stuff 6 years ago while I was in high school, and just multiplied vectors together component by component rather than doing dot product. $\endgroup$
    – Sheng
    Oct 1, 2023 at 14:47
11
$\begingroup$

If the two spheres are centred at $(x_1, y_1, z_1)$ and $(x_2, y_2, z_2)$ at some time $t$, then the distance between their centres is given by the Euclidean distance $\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2 + (z_1 - z_2)^2}$. If you compare this to the sum of their radii, it should give a clear indication of whether they are touching, overlapping or disjoint.

$\endgroup$
11
  • 2
    $\begingroup$ Doesn't answer the question. If the two spheres, in one time step travelled through each other, then simply comparing their distance apart with their radius will not tell me if sphere 1 passed through sphere 2. $\endgroup$
    – Sheng
    Sep 30, 2023 at 14:21
  • 6
    $\begingroup$ You can calculate this value as a function of time, and you can determine its minimum value. $\endgroup$
    – ConMan
    Sep 30, 2023 at 14:26
  • 2
    $\begingroup$ @Sheng Your objection is not very clear. Why doesn't this answer the question? Are you worried that the minimum is difficult to compute (which it isn't because it's basically just quadratic)? Or is it something else? $\endgroup$
    – Trebor
    Sep 30, 2023 at 14:29
  • 1
    $\begingroup$ @Trebor, I might have misunderstood the answer. Calculating distance between two spheres at t = 1 and comparing that to the radius of the two spheres will show that the two spheres are not overlapping. But the path the two spheres took definitely over lapped. I don't know how to expand on this answer to figure out the middle part, i.e. to varify that the two spherical volume overlapped at some time between t = 0 and t = 1 $\endgroup$
    – Sheng
    Sep 30, 2023 at 14:32
  • 5
    $\begingroup$ @Sheng Use $$r_1(t)=r_{1i}+(r_{1f}-r_{1i})t=r_{1i}(1-t)+r_{1f}t$$ and similarly for $r_2(t)$. $\endgroup$
    – user
    Sep 30, 2023 at 14:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .