Tangent Plane to 3 Spheres?
Dov Sherman
I'm having problems with an equation I've been trying to work out
for use in object modelling for raytracing. I've taken it to all
my math professors and none of them can work it. Maybe you folks can.
Imagine three spheres with centers (X1, Y1, Z1), (X2, Y2, Z2),
and (X3, Y3, Z3) with radii R1, R2, and R3 and we know that no
sphere completely engulfs another.
Now we take a plane and lay it on top of the spheres so that it is
tangent to the spheres and intersects with each sphere at only one point
on the sphere. There are eight possible planes but only two
of them do not pass in between the spheres.
The question is: How do I find the points of intersection between
the planes and the spheres?
I've been struggling with this for weeks. Any help is greatly
appreciated.
--- Dov Sherman
GRS0...@Stat.Appstate.Edu
Jim Roth
In article <1msaak...@lester.appstate.edu>, GRS0...@CONRAD.APPSTATE.EDU (Dov Sherman) writes...
>I'm having problems with an equation I've been trying to work out
>for use in object modelling for raytracing. I've taken it to all
>my math professors and none of them can work it. Maybe you folks can.
>Imagine three spheres with centers (X1, Y1, Z1), (X2, Y2, Z2),
>and (X3, Y3, Z3) with radii R1, R2, and R3 and we know that no
>sphere completely engulfs another.
>Now we take a plane and lay it on top of the spheres so that it is
>tangent to the spheres and intersects with each sphere at only one point
>on the sphere. There are eight possible planes but only two
>of them do not pass in between the spheres.
>The question is: How do I find the points of intersection between
>the planes and the spheres?
I don't see an obvious closed form solution, but it would be easy
to obtain the one parameter family of planes tangent to two
of the spheres, and use a nonlinear root finding method to select the
pair of planes you want tangent to the third sphere. Parameterizing by
angle around the line passing thru the centers of the two spheres will
bound the unknown on the interval [0,2 pi], and this could be taken
advantage of to get a reliable, rapidly convergent solution.
The fact that there are 8 planes in general shows that there will
be an 8'th order function and there is no closed form these in
general. (The solution would be complex in case the one of the circles
contains one of the others...)
- Jim
Scott Brown
>Imagine three spheres with centers (X1, Y1, Z1), (X2, Y2, Z2),
>and (X3, Y3, Z3) with radii R1, R2, and R3 and we know that no
>sphere completely engulfs another.
>Now we take a plane and lay it on top of the spheres so that it is
>tangent to the spheres and intersects with each sphere at only one point
>on the sphere. There are eight possible planes but only two
>of them do not pass in between the spheres.
>The question is: How do I find the points of intersection between
>the planes and the spheres?
Let Ci be the center <Xi, Yi, Zi> of sphere i. WLOG say
C1 = <0,0,0>.
If the plane is tangent to sphere i at a point Di on each
sphere, the lines CiDi are all normal to the plane(s) you seek.
Hence they are parallel. Say CiDi = Ri*U (scalar product), where
U = <U1,U2,U3> lies on the unit sphere in three-space. Thus we have
(1) |U| = 1.
Then if v is the vector from D1 to D2 and w from D1 to D3, you
are looking for the plane satisfying
v x w = k*U where x and * denote vector and scalar product resp..
That is, the plane you seek contains vectors v and w and is
normal to the radius CiDi. Note that
(2) k = |vxw|.
This leads to the vector equation
(3) k*U = (R2-R1)(U x C3) + (R3-R1)(U x C2) + (C2 x C3).
Here I am using the fact that C1 = <0,0,0> to simplify somewhat.
This yields a system of five equations, (1), (2) and the three
components in (3), in unknowns U1, U2, U3 and k. Note that this
is an overdetermined system, suggesting that solutions need
not always exist, which is of course the case (if the centers
are collinear and the middle sphere has a large radius while
the other two are small, for example). The resulting system
is kind of a mess, but with patience and a lot of paper it
looks manageable. I'll leave the details to you, ASCII isn't
suitable for writing it out here.
Scott
constraint equation for U, U1^2 + U2^2 + U3^2 = 1, to eliminate
Mark
>Imagine three spheres with centers (X1, Y1, Z1), (X2, Y2, Z2),
>and (X3, Y3, Z3) with radii R1, R2, and R3 and we know that no
>sphere completely engulfs another.
>
>Now we take a plane and lay it on top of the spheres so that it is
>tangent to the spheres and intersects with each sphere at only one point
>on the sphere. There are eight possible planes but only two
>of them do not pass in between the spheres.
You'll soon see why it's taken you weeks to find an answer, and why your
professors all got stumped. The missing piece to the puzzle is: Vector
Algebra.
Rename the centers r, s, and t; and the radii R, S, and T. Then the following
describe the objects (<u,v> denotes the inner product).
Spheres: |x - r|^2 = R^2, similarily for (s, S) and (t, T)
Plane: <x,n> = A, <n,n> = 1, where n is the plane's normal.
The plane will intersect a sphere as a tangent at point x if and only if:
<x,n> = A, |x - r|^2 = R^2, and (x - r) & n are parallel.
The last two conditions imply that x = r + R' n, where R' is +R or -R. This,
with the first condition implies that: A = <r,n> + R', or <r,n> = A - R'.
Thus, you get 3 equations relating the plane's parameters, A and n to the
sphere's parameters:
<r,n> = A - R', where R' = +R, or -R
<s,n> = A - S', where S' = +S, or -S
<t,n> = A - T', where T' = +T, or -T
which gives you 8 possible combinations.
If r, s, and t are collinear (t = ar + (1 - a)s), then the problem can only be
solved if T' = aR' + (1 - a)S'. Then you get an infinity of solutions, since
the normal, n, can be varied in a direction perpendicular to r and s, with
suitable adjustments made to A.
Assume r, s, and t are not collinear. If so, you can find the conjugate
vectors u, v, w (<r,u>=1, <r,v>=0, <r,w>=0, etc). In 3-D they are defined by
the cross-product:
u = (s x t)/D, v = (t x r)/D, w = (r x s)/D, D = <r x s, t>.
Then for all vectors x: x = <x,r>u + <x,s>v + <x,t>w. Thus:
n = A(u + v + w) - (R' u + S' v + T' w).
where
R' = +R or -R, S' = +S or -S, T' = +T or -T
u = (s x t)/D, v = (t x r)/D, w = (r x s)/D, D = <r x s, t>.
The constraint <n,n> = 1 will determine A (if a solution exists).
Now try doing THAT without vector algebra (or something equivalent)!
Let L = u + v + w, and M = R' u + S' v + T' w, then the constrint on n implies
that:
|L x M| <= |L|
and that (using some 3-D vector algebra):
A = (<L,M> + e sqrt(|L|^2 - |L x M|^2) ) / |L|^2, where e = +1 or -1
From which you get (using more 3-D vector algebra):
A = (<L,M> + e sqrt(|L|^2 - |L x M|^2) ) / |L|^2
n = ( Lx(LxM) + e L sqrt(|L|^2 - |L x M|^2) ) / |L|^2
where
L = (r x s + s x t + t x r)/D
M = (R' s x t + S' t x r + T' r x s)/D
D = <r x s, t>
R' = +R or -R, S' = +S or -S, T' = +T or -T, e = +1 or -1
NOW... in order to get the answers, you'll need to try out each of the 8
combinations of R', S', and T' to see which ones give you the condition
|L x M| <= |L|. Unless the two norms come out to be exactly equal, you will
have two solutions. One corresponding to e = +1, and the other to e = -1.
I don't want to go through all the algebra, but the vector L x M will simplify
to (R'(s - t) + S'(t - r) + T'(r - s))/D, so that the condition will simplify
to:
|R'(s - t) + S'(t - r) + T'(r - s)| <= |r x s + s x t + t x r|
which will make the comparison process that less taxing.
(The reason for the simplification is that u, v, w and r, s, t have an exact
symmetrical relation with one another, e.g. u x v / <u x v, w> = t, and
<u x v, w> = 1/<r x s, t>)
Algorithm:
Compute D = <r x s, t>
if D is 0: spheres are collinear. No solution exists.
Calculate u = (s x t)/D, v = (t x r)/D, w = (r x s)/D
L = u + v + w
for each R' = +R or -R, S' = +S or -S, T' = +T or -T:
M = R'u + S'v + T'w, L x M = R'(s - t) + S'(t - r) + T'(r - s)
if |L x M| > |L| then this combination is not a solution.
Try the next combination
for each e = +1, -1: calculate solutions:
A = (<L,M> + e sqrt(|L|^2 - |L x M|^2) ) / |L|^2
n = ( Lx(LxM) + e L sqrt(|L|^2 - |L x M|^2) ) / |L|^2
try next combination (there might be other solutions too)
For each solution A, n: <x, n> = A is the equation of a plane
that intersects the three spheres at points of tangent.
Obviously, much of the stuff above can be precomputed before going into the
loop. Laziness keeps me from trying to evaluate a closed form for R', S', T'
from the inequality |L x M| < |L|. That would save on having to go through
the loop to search out the right combination.
Laurence James Edwards
Here's a way to find the points of intersection:
Find the vertices of two cones tangent to the spheres; one tangent to spheres 1
and 2 and the other tangent to spheres 1 and 3 (for instance). A line through
the cone vertices will be in the tangent plane you are seeking. The vertices of
the cones can be found most easily by looking at 2 orthogonal projections of
the spheres, in say the x-y plane and the y-z plane.
Once you have the the line through the vertices, find a unit vector along that
line. Now find the line through the center of one of the spheres, say sphere 1,
and perpendicular to the line through the cone vertices. Call it line 1. Now
construct a unit vector along that line. Take the cross product of these two
unit vectors to find a third unit vector completing a triad. Now find the
distance from the center of sphere 1 to the line through the vertices. The
angle that a radius vector to the point of tangency (at sphere 1) makes with
line 1 is:
theta = arcos(R1/d) where d is the distance from the center of sphere 1 to
the line through the cone vertices.
the point of tangency is then at:
C1 + U1*R1*cos(theta) + U2*R1*sin(theta)
Here, C1 is the position of the center of sphere 1, U1 and U2 are appropriate
unit vectors from the unit vector triad formed before. Specifically U1 lies
along the line through the center of sphere 1 and perpendicular to the line
through the vertices, and U2 lies in a plane perpendicular to the line through
the vertices.
Knowing the radius vector U1*cos(theta)+U2*sin(theta) you can easily find the
other points of tangency for sphere 2 and sphere 3.
The way you form your triad will determine which of the two tangent planes you
get.
Larry Edwards