Sign in to follow this  
GMaker0507

Closest Point on a Ellipsoid

Recommended Posts

GMaker0507    263
[color="#333333"][size="4"]I need to know how to get the closest point on the surface of an ellipsoid to another point.[/size]

[size="4"]I had an idea, but apparently i was wrong, and oversimplfying.[/size]

[size="4"]What i did was squash the ellipsoid and point into local space, so the ellispoid is a unit circle centered at the origin[/size]

vector3 pointLocalCoord = ( pointOriginal - ellipsoid.origin ) / ellipsoid.radii[size="4"]Then from there, the closest point should be 1 , in the direction of the transformed point from the origin[/size]

vector3 closestPointOnEllipsoidLocal = norm ( pointLocalCoord )[size="4"]Then get back into standard space[/size]

vector3 closestPointOnEllipsoidWorld = closestPointOnEllipsoidLocal * ellipsoid.radius + ellipsoid.origin[size="4"]But of course, all of this seems not to work.[/size]

[size="4"]I'm trying to find the closest point to the center of a box. In this case, the box is stretched out alot along the x-axis. It works if the ellipsoid is directly over the center of the box, but not if the ellipsoid is moved . I measured the distance from the point i got using the method above to the center of the box, and it was actually larger than the distance i measured from the bottom point on the box.[/size]

[size="4"]I was curious if any body could point me in the direction of some pre-existing code or such; as some of the articles i've tried reading kinda seem a bit troublesome[/size]

[/color]

Share this post


Link to post
Share on other sites
alvaro    21247
Your change of coordinates turned the ellipsoid into a sphere, but it messed your distance function: Instead of having spheres as surfaces of equidistance you now have ellipsoids, so you didn't make the problem any easier.

You can probably try to minimize the square of the distance, subject to the solution being on the ellipsoid. This can be done using a [url="http://en.wikipedia.org/wiki/Lagrange_multiplier"]Lagrange multiplier[/url], and everything should be quadratic in the equations involved, so it should be easy to solve.

Share this post


Link to post
Share on other sites
haegarr    7372
The shortest distance is ever along a normal on the ellipsoid surface. See e.g. [url="http://www.geometrictools.com/Documentation/DistancePointToEllipsoid.pdf"]David's short paper[/url].

Share this post


Link to post
Share on other sites
Dave Eberly    1173
[quote name='haegarr' timestamp='1306693233' post='4817191']
The shortest distance is ever along a normal on the ellipsoid surface. See e.g. [url="http://www.geometrictools.com/Documentation/DistancePointToEllipsoid.pdf"]David's short paper[/url].
[/quote]

Yes, that PDF is quite short. Your post inspired me to make it longer :o . The similar point-ellipse PDF already had a lot of the ideas for computing the distance robustly. I originally mentioned the inspiration for the PDFs and my source code was a Graphics Gems IV article. That article converts the problem to computing the largest root of a polynomial (degree 4 for the ellipse, degree 6 for the ellipsoid). The suggestion is to us Newton's Method with an initial guess greater than the largest root, and the authors provided an initial guess. Unfortunately, the convergence of the method is not guaranteed. In particular, the problems occur when the query point is near a coordinate axis (for the ellipse) or near a coordinate plane (for the ellipsoid). This showed up in my point-ellipse code, which I had then rewrote to include special handling for such points. I never got around to doing the same thing for the point-ellipsoid code.

A new PDF combines the point-ellipse and point-ellipsoid PDFs, but has a greatly expanded discussion on robustness and on why you do [b]not[/b] want to use the polynomial idea. The numerical problems occur as a result of a topological change in the graph of a function F(t) (I defined this in the PDFs). In terms of the polynomial P(t), the problem is that points near the coordinate axes/planes cause P(t) to have a largest root that is multiplicity 2 when you are on the axes/planes. Newton's Method needs to be modified to handle roots of multiplicity larger than 1, but even so, finding the largest root of F(t) is much easier to make robust.

The new PDF is [url="http://www.geometrictools.com/Documentation/DistancePointEllipseEllipsoid.pdf"]Distance from a Point to an Ellipse, an Ellipsoid, or a Hyperellipsoid[/url] . I updated my WM5 source code to use this and I added a new sample application to illustrate. The application has the code for point-hyperellipsoid (any dimension you want).

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this