gdalgorithms-list

RE: [Algorithms] Nearest point on plane for 2D IK

[Robert D. <RD...@ac...>]

> Hi,
> 
> I am looking for an algorithm to compute the intersecting 
> point P between a ray and
> a sphere. I know the center C and the radius R of the sphere, 
> the origin O of the ray
> and its direction V. Basically I need to find the closest 
> intersection from O.
> 
> But that's not all: In addition to this, IF the ray does not 
> intersect or is tangent to the
> sphere, I need to know the tangential point with the sphere.
> 
> Does anybody know a fast and accurate solution to this 
> problem? maybe a good web
> site or some code would greatly help!...

Hmmm ... surely what you want is to find the point on the line closest to
the center of the sphere (easy to do) and then if that is less than R away
from the center you have definite intersection, and proceed to compute the
points at which the line intersects the sphere, and otherwise, you
conveniently have a point which is in line with the nearest tangential point
of the sphere, so you can easily find that tangential point.

Rob

RE: [Algorithms] Nearest point on plane for 2D IK

[Steve W. <Ste...@im...>]

How about if you use the center of the sphere and the point at the beginning
of your ray to use as the normal for a plane passing through the center of
the sphere.  Calculate the intersection of the ray and that plane.
Calculate the point that is the sphere's radius from it's center along the
line from the center of the sphere to the intersection of the ray and the
plane.  That's not the tangent yet because we need to move that point in an
arc around the sphere toward the beginning of the ray by the same angle as
described by the center of the sphere to the intersection of the ray and the
plane to the beginning of the ray.

Just using my virtual protractor and compass.

Rockn-Roll

> -----Original Message-----
> From: David Kornmann [mailto:da...@ik...]
> Sent: Tuesday, August 29, 2000 2:43 PM
> To: gda...@li...
> Subject: Re: [Algorithms] Nearest point on plane for 2D IK
> 
> 
> 
> 
> 
> > Hmmm ... surely what you want is to find the point on the 
> line closest to
> > the center of the sphere (easy to do) and then if that is 
> less than R away
> > from the center you have definite intersection, and proceed 
> to compute the
> > points at which the line intersects the sphere, and otherwise, you
> > conveniently have a point which is in line with the nearest 
> tangential point
> > of the sphere, so you can easily find that tangential point.
> 
> Well, computing the point when the ray intersect with the 
> sphere is not a big
> deal.
> The problem comes when the ray does not intersect:
> 
>  I am not looking for the closest surface point on the sphere 
> then, but a point
> that
> can be described as follow:
> 
> - Take the plane defined with the ray and the center of the sphere.
> - Rotate the ray around its origin and along the plane until 
> it is tangent to
> the sphere.
> - Compute the tangetial point (easy).
> 
> That's what seems to me complicated and which needs to be 
> very accurate.
> 
> Any idea?
> 
> Thanks.
> 
> David Kornmann.
> --
> 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 

RE: [Algorithms] Nearest point on plane for 2D IK

[Steve W. <Ste...@im...>]

> -----Original Message-----
> From: Steve Wood 
> That's not the tangent yet because we need to move 
> that point in an arc around the sphere toward the 
> beginning of the ray by the same angle as

Oops!  Not that angle but 90 degrees minus that angle...darn KMart virtual
protractor!
Rockn-Roll

> described by the center of the sphere to the intersection of 
> the ray and the
> plane to the beginning of the ray.

> -----Original Message-----
> From: Steve Wood 
> Sent: Tuesday, August 29, 2000 4:15 PM
> To: 'gda...@li...'
> Subject: RE: [Algorithms] Nearest point on plane for 2D IK
> 
> 
> How about if you use the center of the sphere and the point 
> at the beginning
> of your ray to use as the normal for a plane passing through 
> the center of
> the sphere.  Calculate the intersection of the ray and that plane.
> Calculate the point that is the sphere's radius from it's 
> center along the
> line from the center of the sphere to the intersection of the 
> ray and the
> plane.  That's not the tangent yet because we need to move 
> that point in an
> arc around the sphere toward the beginning of the ray by the 
> same angle as
> described by the center of the sphere to the intersection of 
> the ray and the
> plane to the beginning of the ray.
> 
> Just using my virtual protractor and compass.
> 
> Rockn-Roll
> 
> > -----Original Message-----
> > From: David Kornmann [mailto:da...@ik...]
> > Sent: Tuesday, August 29, 2000 2:43 PM
> > To: gda...@li...
> > Subject: Re: [Algorithms] Nearest point on plane for 2D IK
> > 
> > 
> > 
> > 
> > 
> > > Hmmm ... surely what you want is to find the point on the 
> > line closest to
> > > the center of the sphere (easy to do) and then if that is 
> > less than R away
> > > from the center you have definite intersection, and proceed 
> > to compute the
> > > points at which the line intersects the sphere, and otherwise, you
> > > conveniently have a point which is in line with the nearest 
> > tangential point
> > > of the sphere, so you can easily find that tangential point.
> > 
> > Well, computing the point when the ray intersect with the 
> > sphere is not a big
> > deal.
> > The problem comes when the ray does not intersect:
> > 
> >  I am not looking for the closest surface point on the sphere 
> > then, but a point
> > that
> > can be described as follow:
> > 
> > - Take the plane defined with the ray and the center of the sphere.
> > - Rotate the ray around its origin and along the plane until 
> > it is tangent to
> > the sphere.
> > - Compute the tangetial point (easy).
> > 
> > That's what seems to me complicated and which needs to be 
> > very accurate.
> > 
> > Any idea?
> > 
> > Thanks.
> > 
> > David Kornmann.
> > --
> > 
> > _______________________________________________
> > GDAlgorithms-list mailing list
> > GDA...@li...
> > http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> > 
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> http://lists.sourceforge.net/mailman/listinfo/gdalgorithms-list
> 

Re: [Algorithms] Nearest point on plane for 2D IK

[David K. <da...@ik...>]

> Hmmm ... surely what you want is to find the point on the line closest to
> the center of the sphere (easy to do) and then if that is less than R away
> from the center you have definite intersection, and proceed to compute the
> points at which the line intersects the sphere, and otherwise, you
> conveniently have a point which is in line with the nearest tangential point
> of the sphere, so you can easily find that tangential point.

Well, computing the point when the ray intersect with the sphere is not a big
deal.
The problem comes when the ray does not intersect:

 I am not looking for the closest surface point on the sphere then, but a point
that
can be described as follow:

- Take the plane defined with the ray and the center of the sphere.
- Rotate the ray around its origin and along the plane until it is tangent to
the sphere.
- Compute the tangetial point (easy).

That's what seems to me complicated and which needs to be very accurate.

Any idea?

Thanks.

David Kornmann.
--

Re: [Algorithms] Nearest point on plane for 2D IK

[Thatcher U. <tu...@tu...>]

From: David Kornmann <da...@ik...>
>
> > Hmmm ... surely what you want is to find the point on the line closest
to
> > the center of the sphere (easy to do) and then if that is less than R
away
> > from the center you have definite intersection, and proceed to compute
the
> > points at which the line intersects the sphere, and otherwise, you
> > conveniently have a point which is in line with the nearest tangential
point
> > of the sphere, so you can easily find that tangential point.
>
> Well, computing the point when the ray intersect with the sphere is not a
big
> deal.
> The problem comes when the ray does not intersect:
>
>  I am not looking for the closest surface point on the sphere then, but a
point
> that
> can be described as follow:
>
> - Take the plane defined with the ray and the center of the sphere.
> - Rotate the ray around its origin and along the plane until it is tangent
to
> the sphere.
> - Compute the tangetial point (easy).
>
> That's what seems to me complicated and which needs to be very accurate.

The description is a little confusing, but if I understand correctly, this
is not hard to solve.  Lets label the points:

R = ray origin
C = center of circle
T = tangent point you're interested in

If I catch your meaning, you want C, T, and the ray to all be coplanar.

If you make a triangle out of R, C and T, you have a right triangle, with
the right angle at T.  You can compute the length of the hypotenuse, it's
just |RC|, and you know the length of CT because it's equal to the circle's
radius.  So you can compute the angle CRT, it's just arcsin(|CT| / |RC|).
The angle RCT is 90 - CRT.  There's some plane which contains all these
points; compute its normal: n = normalize((C-R) x ray_direction).  To find
T, take the vector CR, rotate about n by angle RCT, and make its length
equal to the sphere radius.

What's the purpose of this?

--
Thatcher Ulrich
http://tulrich.com

Re: [Algorithms] Nearest point on plane for 2D IK

[Dave E. <eb...@ma...>]

From: "David Kornmann" <da...@ik...>
> - Take the plane defined with the ray and the center of the sphere.
> - Rotate the ray around its origin and along the plane until it is tangent
to
> the sphere.
> - Compute the tangetial point (easy).

Let C be the center of the sphere and let R be its radius.
Let the ray have origin P and direction vector D.  Assume
the ray does not pass through C.  The plane containing
C and the ray has normal N = Cross(D,C-P).  The plane
itself is Dot(N,X-P) = 0.  Let L = Length(C-P).  The point
you are looking for can be viewed as a point of
intersection of the sphere |X-C|^2 = R^2, the sphere
|X-P|^2 = L^2, and the plane Dot(N,X-P) = 0.  This gives
you three equations (two quadratic, one linear) in three
unknowns.  Alternatively you can think of intersecting each
of the spheres with the plane.  Within the plane you need
to find the intersection of two circles.

You can reduce the two quadratics to one.  Subtract the
sphere equations to get
2*Dot(P-C,X) + |C|^2 - |P|^2 = R^2 - L^2.

Do the algebra to set up the three equations as
p0 = (x-c0)^2 + (y-c1)^2 + (z-c2)^2 - R^2 = 0
p1 = a0*x+a1*y+a2*z+a3
p2 = b0*x+b1*y+b2*z+b3

res0 = Resultant[p0,p1,z] =
  d20*x^2+d11*x*y+d02*y^2+d10*x+d01*y+d00

where
  d00 = a3^2+2*a2*a3*c2+a2^2*(c0^2+c1^2+c2^2-R^2)
  d10 = 2*(a0*a3-a2^2*c0+a0*a2*c2)
  d01 = 2*(a1*a3-a2^2*c1+a1*a2*c2)
  d11 = 2*a0*a2
  d20 = a0^2+a2^2
  d02 = a1^2+a2^2

res1 = Resultant[p1,p2,z] = e0*x+e1*y+e2

where
  e0 = a2*b0-a0*b2
  e1 = a2*b1-a1*b2
  e2 = a2*b3-a3*b2

res2 = Resultant[res0,res1,y] =  f2*x^2 + f1*x + f0

where
  f0 = d00*e1^2 - d01*e1*e2 + d02*e2^2
  f1 = d10*e1^2+2*d02*e0*e2-d01*e0*e1-d11*e1*e2
  f2 = d02*e0^2-d11*e0*e1+d20*e1^2

Solve res2 = 0 for up to 2 values of x.  For each,
solve res1 = 0 for y.  For each pair (x,y) from this
construction, solve p1 = 0 for z.  You get up to
two points (x,y,z).  The one that is in the wedge
formed by the ray P+t*D and P+t*(C-P) is the
solution you want.

--
Dave Eberly
eb...@ma...
http://www.magic-software.com