GMaker0507 263 Report post Posted May 29, 2011 [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] 0 Share this post Link to post Share on other sites
alvaro 21272 Report post Posted May 29, 2011 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. 0 Share this post Link to post Share on other sites
haegarr 7374 Report post Posted May 29, 2011 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]. 0 Share this post Link to post Share on other sites
Emergent 982 Report post Posted May 29, 2011 · Hidden Hidden (disregard.) 0 Share this post Link to post
GMaker0507 263 Report post Posted May 30, 2011 Thanks for the reply's. It might take me some time to understand them both, i might just jump off it for now. 0 Share this post Link to post Share on other sites
Dave Eberly 1173 Report post Posted June 18, 2011 [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 . 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). 0 Share this post Link to post Share on other sites