5
\$\begingroup\$

I have code for circle-circle intersection. But I need to expand it to 3-D. How do I calculate:

  • Radius and center of the intersection circle of two spheres
  • Points of the intersection of a sphere and a circle?

Given two spheres (sc0,sr0) and (sc1,sr1), I need to calculate a circle of intersection whose center is ci and whose radius is ri.
Moreover, given a sphere (sc0,sr0) and a circle (cc0, cr0), I need to calulate the two intersection points (pi0, pi1)
I have checked this link and this link, but I could not understand the logic behind them and how to code them.

I tried ProGAL library for sphere-sphere-sphere intersection, but the resulting coordinates are rounded. I need precise results.

\$\endgroup\$
  • \$\begingroup\$ I had some confusion if you were looking for sphere-sphere or sphere-circle collision. I answered as though you were looking for sphere-sphere. \$\endgroup\$ – CiscoIPPhone May 28 '14 at 17:55
  • \$\begingroup\$ Can you clarify? What do you want to get out of the intersection method? Circles overlap areas, spheres overlap volumes. Are you wanting the intersects method to return a volume? \$\endgroup\$ – MichaelHouse May 28 '14 at 18:48
  • \$\begingroup\$ @Byte56 I want to calculate the coordinates of intersections \$\endgroup\$ – padawan May 28 '14 at 18:50
  • \$\begingroup\$ @cagirici There are an infinite number of points where two spheres intersect. This is why I'm asking you to clarify. There's no specific coordinate. \$\endgroup\$ – MichaelHouse May 28 '14 at 18:51
  • \$\begingroup\$ @Byte56 I mean, the equation of the circle of intersection. \$\endgroup\$ – padawan May 28 '14 at 18:52
14
\$\begingroup\$

Sphere-Sphere Intersection

Let's start with the more obvious one - sphere-sphere. It's almost identical to the circle-circle case in 2D. We can project down on any plane containing the line between the spheres' centers to get an identical 2D picture:

Reducing the problem to 2D

Here the first sphere has center c_1 and radius r_1, the second c_2 and r_2, and their intersection has center c_i and radius r_i. Let d = ||c_2 - c_1||, the distance between the spheres.

Edge Cases:

As was pointed out previously, if r_1 + r_2 < d then there is no intersection at all. The spheres have a separation between them.

If r_1 + r_2 == d, then the intersection is a single point, located a distance of r_1 on the line from c_1 to c_2, or: c_i = c_1 + (c_2 - c_1) * r_1/d

This can also happen from the other side, if d + min(r_1, r_2) = max(r_1, r_2). In this case, the single point of intersection lies on the larger sphere, at c_i = c_larger + (c_smaller - c_larger) * r_larger/d

Finally, if one circle is entirely encompassed within the other, such that d + min(r_1, r_2) < max(r_1, r_2), then once again there is no intersection.

Edge case examples

Typical intersections

Okay, now the meaty bit.

Let's define c_i = c_1 + h * (c_2 - c_1), for some value of h. Note that h can be negative or greater than one in the case where one circle encompasses the center of the other. Fortunately, the signs will "just work," so we don't need to add any special case logic for this condition.

The remaining, interesting cases

We can express r_1 and r_2 in terms of r_i, h, and d using Pythagorean Theorem, then solve the system of equations to find h:

$$\require{cancel} \begin{array}{r|l} (hd)^2 + r_i^2 = r_1^2 & \left((1-h)d\right)^2 + r_i^2 = r_2^2\\ h^2d^2 - r_1^2 = -r_i^2 & \left(1 - 2h + h^2 \right)d^2 - r_2^2 = -r_i^2 \end{array}\\ \begin{align} \cancel{h^2d^2} - r_1^2 &= d^2 - 2hd^2 + \cancel{h^2d^2} - r_2^2\\ 2hd^2 &= d^2 + r_1^2 - r_2^2\\ h &= \frac 1 2 + \frac {r_1^2 - r_2^2} {2 d^2} \end{align}$$

h = 1/2 + (r_1 * r_1 - r_2 * r_2)/(2 * d*d)

We can sub this into our formula for c_i above to find the center of the circle of intersections. Then, reversing one of our earlier Pythagorean relations:

r_i = sqrt(r_1*r_1 - h*h*d*d)

So, now we have the center and radius of our intersection. Now we can revolve this around the separating axis to get our full circle of solutions. The circle lies in a plane perpendicular to the separating axis, so we can take n_i = (c_2 - c_2)/d as the normal of this plane.

Our glorious intersection

After choosing a tangent and bitangent t_i and b_i perpendicular to this normal and each other, you can write any point on this circle as:

p_i(theta) = c_i + r_i * (t_i * cos(theta) + b_i sin(theta));

Because of the Hairy Ball Theorem, there's no one universal way to choose the tangent/bitangent to use. My recommendation would be to pick one of the coordinate axes not parallel to n_i, and set t_i = normalize(cross(axis, n_i)), and b_i = cross(t_i, n_i) or somesuch.


Sphere-Circle Intersection

A circle, being flat/2-dimensional, can only intersect with things within its own plane. So, the first thing is: find out where that plane intersects our sphere.

Slice

Given a circle with center & radius c_c and r_c, respectively, in the plane with (unit) normal n, and a sphere with center & radius c_s and r_s...

The plane of the circle cuts the sphere d = dot(n, c_c - c_s) units from the sphere's center. Again, this can be negative if the normal is pointing toward the sphere's center, but the signs will work out.

If abs(d) > r_s then there is no intersection. Our plane passes above/below the sphere entirely.

If there is an intersection, it will be between our original circle and a new one formed where this plane meets the sphere, with center c_p = c_s + d*n.

If d == r_s then this is the sole point of intersection with the plane; otherwise we have a circle whose radius r_p we can find with Pythagorean Theorem:

r_p = sqrt(r_s*r_s - d*d)

And now we've reduced the problem to circle-circle, which we already know how to solve. Checking the distance/radii involved according to the edge cases above will let us take care of the non-intersecting and single point of intersection cases.

Looks familiar

If the two circles do overlap by more than one point, we can use the formulae from the Sphere-Sphere check to find c_i and r_i as before.

Instead of a full circle of intersection points though, we'll have only the two points lying in the plane of the circle.

To express these points, we can define a tangent vector in the plane,

t = normalize(cross(c_p - c_c, n))

Then our intersection points are:

p_0 = c_i - t * r_i

p_1 = c_i + t * r_i

And we're done. :D

I hope that helps!

\$\endgroup\$
  • \$\begingroup\$ Just a little bit off topic. The drawings in your answer are great. Can I ask what software do you use to draw them? PGF/TikZ? \$\endgroup\$ – Milo Yip Jun 30 '14 at 9:27
  • \$\begingroup\$ Thanks, I appreciate that! I drew these in Adobe Illustrator CS3 \$\endgroup\$ – DMGregory Jun 30 '14 at 13:15
  • \$\begingroup\$ why is h = 1/2 + (r_1 * r_1 - r_2 * r_2)/(d*d). I don't understand why you would just randomly add .5, Also what is h at first I though it would be the height but that is r_i \$\endgroup\$ – johnny 5 Jan 27 '17 at 1:34
  • 1
    \$\begingroup\$ @johnny5 I've updated the answer to include the derivation of h. It looks like there was a typo in the original post which I've now fixed - I was missing a 2 in front of the d*d in the denominator. You can think of h as an interpolation weight between c_1 and c_2, chosen so that the center of the ring of intersections occurs at lerp(c_1, c_2, h). r_i is the radius of that ring of intersections. \$\endgroup\$ – DMGregory Jan 27 '17 at 8:00
  • \$\begingroup\$ Thank you, I've looked at a lot of posts on this and yours is the only one I can follow \$\endgroup\$ – johnny 5 Jan 27 '17 at 13:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.