Point to ellipsoid distance

Please don't post Bullet support questions here, use the above forums instead.
Post Reply
Posts: 1
Joined: Fri Jan 18, 2013 4:34 pm

Point to ellipsoid distance

Post by zetzar »

I wanted to implement a point to ellipsoid distance/closest point and went for two ways:

1. Scale to a sphere, get the closest point and normal and scale them back. This one works pretty well, is very fast and seems other people have used it although they know it's inaccurate.
2. The method published on David Eberly's site which is accurate (depending on how many iterations you give to the non-linear equation solver).

Clearly 2 is heavy on computation so I was looking for in-between solution. One thing I tried in 2D and worked pretty well is first run 2 with very few iterations (between 1 and 6) and then run 1 with the resulting closest point from 1. This seems to reduce errors quite a bit.

But then I thought I could run 1 and use the resulting closest point as some kind of seed to start from and iteratively get closer to the correct point. Eberly does mention Newton-Raphson in his approach but he's right that it starts failing for y0 close to 0. So I tried using the Langrange multipliers method and Newton to solve the equations directly on the point X (if I substitute lambda in the ellipse equation I get the same thing as Eberly).

Find attached the formula I got for 2D, where M is the ellipse diagonal matrix, Y the query point and X0 and lambda0 are the initial guesses for the closest point and the Lagrange multiplier (I used lambda0 = 0). Now I might've got the matehmatics wrong or screwed the implementation, cause in 2D the solution goes towards the center of the ellipse.

What I'd like to know is if my idea is correct and if there's any chance to fix it (maybe it doesn't converge or something). In theory this should work for any curve.

EDIT: Actually there's no 1/2 at the beginning.
NR.gif (2.74 KiB) Viewed 4413 times
Post Reply