Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I need to know how to get the closest point on the surface of an ellipsoid to another point.

I had an idea, but apparently i was wrong, and oversimplfying.

What i did was squash the ellipsoid and point into local space, so the ellispoid is a unit circle

vector3 pointLocalCoord = ( pointOriginal - ellipsoid.origin ) / ellipsoid.radii

Then from there, the closest point should be 1, in the direction of the transformed point from the origin

vector3 closestPointOnEllipsoidLocal = norm ( pointLocalCoord )

Then get back into standard space

vector3 closestPointOnEllipsoidWorld = closestPointOnEllipsoidLocal * ellipsoid.radius + ellipsoid.origin

But of course, all of this seems not to work, 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 go a bit out of my scope of knowledge.

Also, if that seems right to you, please do tell. I'm pretty sure its wrong though.

Edit: Sorry for the unresponsiveness with this and my other question. They're different, i was axperimenting with something else

share|improve this question
    
That reads correctly to me, if ellipsoid.radii is a Vector3 and norm is Vector3.Normalize (and vector3 is Vector3 for that matter). What is with the non-XNA type and function names? –  Andrew Russell May 29 '11 at 14:55
    
Yeah; and the reason for the non xna stuff, idk... i guess i wasnt gonna originally list it as a xna thing –  Larry May 29 '11 at 15:43
    
-1 This is pretty much the same as your other question. Except that you cant figure out how to implement the answer. IF that is the case update your question and ask for additional information. –  AttackingHobo May 29 '11 at 20:42
    
+1 This is not the same question. I suggest your reconsider your downvote regardless of your consideration for the poster, because it gives people the wrong idea that the answer is trivial. –  Sam Hocevar May 30 '11 at 16:39
    
If you want to find a general solution, in any dimension, you can check out: mathproblems123.wordpress.com/2013/10/17/… In Matlab you can code it in about 10-20 lines. Using another program shouldn't make things harder. –  Beni Bogosel Oct 23 '13 at 20:03
add comment

1 Answer

up vote 11 down vote accepted

As your feared, you are oversimplifying. If you transform your scene so that the ellipse becomes a circle, you are using a non-isometric transformation and relative distance is not preserved. This can be best seen in the following diagram, where the point closest to the black point clearly changes:

closest point on an ellipse

Finding the closest point on an ellipse is a non-trivial problem. It requires the root of a 4th-degree polynomial that usually does not have a computable answer. However, you can refine an approximate answer with Newton's method and converge reasonably well.

I suggest you read David Eberly's Distance from a Point to an Ellipse in 2D for both a written proof of the formula, and 50 to 100 lines of code that you can reuse to solve your problem.

share|improve this answer
    
+1 also for the paper –  Maik Semder May 30 '11 at 18:34
    
Okay, i see now. Thanks for the diagram. Ill have a look see at the paper. –  Larry Jun 2 '11 at 3:53
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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