Closest point to an ellipsoid
Closest point to an ellipsoid
Hi!
Can anyone provide a solution for finding the closest point to an ellipsoid? I have a workaround solution, but it's rather non-mathematical and I don't think it's 100% punctual.
Just to clear up, I'm not talking about the intersection point (I), but the point on the ellipsoid (CP) where from the distance to the given point (P) is the smallest possible:
I simply could not find any good solution on the net: most of them claims to calculate the closest point, but it only gives the intersection point.
A solution that gives correct result no matter if the point is inside or outside of the ellipsoid would be even better.
...But any help is appreciated!
Thank you in advance!
PI
Can anyone provide a solution for finding the closest point to an ellipsoid? I have a workaround solution, but it's rather non-mathematical and I don't think it's 100% punctual.
Just to clear up, I'm not talking about the intersection point (I), but the point on the ellipsoid (CP) where from the distance to the given point (P) is the smallest possible:
I simply could not find any good solution on the net: most of them claims to calculate the closest point, but it only gives the intersection point.
A solution that gives correct result no matter if the point is inside or outside of the ellipsoid would be even better.
...But any help is appreciated!
Thank you in advance!
PI
Yes I have an idea and Im trying it at the moment. My solution must work mathematically but I dont know how much work it will be to code this, so Im trying it now on a paper. My approach is to set the equation of the point CP which is generated out of the ellipse constants 'a' and 'b'. Then you create the vector CP-P create the length of it throw one of the two variables out and make a simple extremum task by deriving the function and setting it to zero.
Unfortunately I cant see the easier geometrically way.
Unfortunately I cant see the easier geometrically way.
Looks like you only transformed the "closest point". You didn't inverse-transform the point you are testing before hand first.PI wrote:As a very first approach, my idea was the same, and for some situations, it might be good. But just look at the image below:
The one you've suggested, is marked with blue, while the -more or less- correct one is marked with red.
Thanks anyway, but do you or somebody have another idea?
Cheers,
PI
If you still don't get it, read from page 37 of this (VERY nice paper).
Last edited by BlindSide on Mon Aug 31, 2009 11:48 am, edited 1 time in total.
ShadowMapping for Irrlicht!: Get it here
Need help? Come on the IRC!: #irrlicht on irc://irc.freenode.net
Need help? Come on the IRC!: #irrlicht on irc://irc.freenode.net
An ellipse contain 2 foci. Your closest point would be, if I had to guess, the intersection on the ellipse to the closest point on the segment of line made by these 2 foci. To get that point, you find the closest point on the line made by those 2 points, and if it's outside of their range, take the extreme end. I'd wager this will work, but I just woke up, so...
http://www.mathwarehouse.com/ellipse/fo ... llipse.php
http://www.mathwarehouse.com/ellipse/fo ... llipse.php
@BlindSide:
I've read it again, and realized that I've misunderstood you.
I think what you're suggesting is intersecting the ellipsoid with the original ray; let me explain:
- P is the given point;
- TP is the transformed P (from ellipsoid-space to sphere-space);
- I is the intersection with the sphere;
- TI is the transformed I (from sphere-space to to ellipsoid-space);
Image:
This is exactly what I use to find the intersection point.
Or did I misunderstand you again?
@xray:
Can you please explain it in some other way? I know I'm dumb but I can't really get it.
JeroenP:
That sounds like computing the normal from P towards to Q, but how to get the distance I need to go that direction? The tangent approach does ring a bell, though.
@Dorth:
Are you suggesting this?
F1 and F2 the 2 foci.
LI is the closest point to the line F1-F2.
And finally, the blue CP is what you've suggested (if I've understood you correctly), and the red one where it should be:
Sorry for my lack of brain, guys
And thanks for your patience!
PI
I've read it again, and realized that I've misunderstood you.
I think what you're suggesting is intersecting the ellipsoid with the original ray; let me explain:
- P is the given point;
- TP is the transformed P (from ellipsoid-space to sphere-space);
- I is the intersection with the sphere;
- TI is the transformed I (from sphere-space to to ellipsoid-space);
Image:
This is exactly what I use to find the intersection point.
Or did I misunderstand you again?
@xray:
Can you please explain it in some other way? I know I'm dumb but I can't really get it.
JeroenP:
That sounds like computing the normal from P towards to Q, but how to get the distance I need to go that direction? The tangent approach does ring a bell, though.
@Dorth:
Are you suggesting this?
F1 and F2 the 2 foci.
LI is the closest point to the line F1-F2.
And finally, the blue CP is what you've suggested (if I've understood you correctly), and the red one where it should be:
Sorry for my lack of brain, guys
And thanks for your patience!
PI
Sorry, I really was tired.
Keep what I said for when the intersection is outside the line segment. When it's inside, however, draw a line perpendicular to the segment to reach the point (p1). Now, from that point (p2) on the segment to the center of the ellipse, you have a new segment, seg2. Divide seg2 in 2. The center of that subdivision will be called p3. Take p1, p2 and p3 form a triangle. On the intersection of the hypothenuse with the ellipse, your closest point should be.
http://img7.imageshack.us/img7/7748/answerg.png
Keep what I said for when the intersection is outside the line segment. When it's inside, however, draw a line perpendicular to the segment to reach the point (p1). Now, from that point (p2) on the segment to the center of the ellipse, you have a new segment, seg2. Divide seg2 in 2. The center of that subdivision will be called p3. Take p1, p2 and p3 form a triangle. On the intersection of the hypothenuse with the ellipse, your closest point should be.
http://img7.imageshack.us/img7/7748/answerg.png
It is, ain't it? Guess my instincts at math suck at the moment (as do my verification steps) as far as /2, like all things in math, there's bound to be a common point to all such formulas, so a middle point, a /3 point, a pi link or something, when we'll find that solution of yours, it'll be obvious which ^^
(hmmm, watching this, it looks more like you made a line to a point 1/3rd of the way from p2 and p3. Could this be it?)
(hmmm, watching this, it looks more like you made a line to a point 1/3rd of the way from p2 and p3. Could this be it?)
Ok first of all I tried my solution, and it works but the problem is that the equation what you get to calculate the x and y coordinates of this point on your ellipse is really long, so I dont think its a good choice to go this way. But I can explain it again: Like you said you are searching the minimum length of the vector CP to P. And when you (dont know if you had this in your math lessons) here something about a minimum in math then a big bell should ring in your head Cause there is a big section in maths which concern with extremum = minimum or maximum. For example you have an equation for example a parabel y = x^2 then you can calculate the minimum of this parabel by doing some mathematical steps. The first step is to differentiate this equation towards x. Then you set this new equation what you get to zero and solve it again towards x so that you get the x coordinate of the minimum, after this you only have to get the y coordinate by putting the calculated x into your root parabel function, thats it. And this is the way I did it with your problem, its exactly the same way but unfortunately you get a really big function which I wouldnt calculate every frame when you know what I mean.
But there is another solution which JeroenP said. I think you misunderstood him, Ill try his way and maybe the equation will be much simpler.
But there is another solution which JeroenP said. I think you misunderstood him, Ill try his way and maybe the equation will be much simpler.
I tried the method which JeroenP had in mind and I get the exact same equation like the solution I tried with the extremum. So in my opinion there is no other way to get the answer to this question... seems not to be an easy question. Dont know how urgent you need a solution, but I would recommend making some simplifications, so maybe theres a work around for it. Or someone gets a new idea for solving this problem.
Sorry guys I didn't have as much spare time as yesterday.
I really appreciate the effort you guys put into this! Thanks!
@Dorth:
Yes, see my approach below. (I've added your idea about the foci, thanks!)
xray:
Yeah, it does ring a bell, however, I'm not really familiar with derivates and integrates... I did everything I had to in school, but I haven't spent enough time understanding them in a depth. Plus, I'm much more like an artist, and as an artist, my approach was visual.
I guess the method you suggest won't be really fast, however, I'm still interested. Did I mention to that I'd like to have a solution in 3D? I guess that complicates things a bit.
Again, thanks guys!
----------------------------------------------------------
Maybe this is what I should have started with: my approach. The two reasons why I did not:
1# to have a brainstorming about the problem,
2# I've simply forgotten
I've made a sphere-problem of the ellipsoid-problem:
Image:
What I do here is:
- transform P into TP
- calculate Q
- transform Q into TQ
- get the intersection point with the sphere (I)
- transform I to TI
- TI is the closest point
Code:
Here are the issues about it:
- fails on the inner side of the ellipsoid (the more deeper "Point" is)
- issues towards the highest peaks (small)
- I bet it's not punctual! (90-95% would be great)
I can make a small test program if you want!
Can you help me to repair it? Or: can it be repaired?
Thank you
Cheers,
PI
I really appreciate the effort you guys put into this! Thanks!
@Dorth:
Yes, see my approach below. (I've added your idea about the foci, thanks!)
xray:
Yeah, it does ring a bell, however, I'm not really familiar with derivates and integrates... I did everything I had to in school, but I haven't spent enough time understanding them in a depth. Plus, I'm much more like an artist, and as an artist, my approach was visual.
I guess the method you suggest won't be really fast, however, I'm still interested. Did I mention to that I'd like to have a solution in 3D? I guess that complicates things a bit.
Again, thanks guys!
----------------------------------------------------------
Maybe this is what I should have started with: my approach. The two reasons why I did not:
1# to have a brainstorming about the problem,
2# I've simply forgotten
I've made a sphere-problem of the ellipsoid-problem:
Image:
What I do here is:
- transform P into TP
- calculate Q
- transform Q into TQ
- get the intersection point with the sphere (I)
- transform I to TI
- TI is the closest point
Code:
Code: Select all
// getClosestPointToEllipsoid
// gives the closest point to an axis-aligned ellipsoid
// assumes that the ellipsoid is at the origin
// treats the ellispoid-problem as a sphere-problem
// \param Point: the point you want to project onto the ellipsoid
// \param Radius: the ellipsoid radius
// \return the closest point ont the ellipsoid
// issues:
// - fails on the inner side of the ellipsoid (the more deeper "Point" is)
// - issues towards the highest peaks
// - not punctual
core::vector3df CGame::getClosestPointToEllipsoid(const core::vector3df& Point, const core::vector3df& Radius)
{
// prepare "mn" (= "a"), "mx" (= "b"), and later "c"
float mx = core::max_(Radius.X, Radius.Y, Radius.Z);
float mn = core::min_(Radius.X, Radius.Y, Radius.Z);
core::vector3df mpr = core::vector3df(mn) / Radius;
core::vector3df rpm = Radius / core::vector3df(mn);
// now check if the "Point" is inside, outside, or on the ellipsoid
// the original direction to "Point"
core::vector3df dir = core::vector3df(Point).normalize();
// the intersection point on the ellipsoid
core::vector3df isect = core::vector3df((dir * mpr).normalize() * Radius);
// if it's on the ellipsoid, return
float plen = Point.getLengthSQ(), ilen = isect.getLengthSQ();
if (core::equals(plen, ilen)) return isect;
// transform "Point" to sphere-space
core::vector3df tp = Point * mpr;
// calculate "q" (for the inside, it's really bad)
core::vector3df q = (plen > ilen) ? (Point - tp) : (Point - (tp * mpr));
// clamp "q" to the nearest focus point of the ellipse
float c = sqrt((mx * mx) - (mn * mn));
if (q.getLength() > c) q.setLength(c);
// transform "q" to sphere-space
core::vector3df tq = q * mpr;
// calculate intersection of the sphere with ray "tp-tq"
core::line3df ray(tp, tq);
double dist = 1;
ray.getIntersectionWithSphere(core::vector3df(), mn, dist);
core::vector3df n = (tq - tp).normalize();
// the intersection point
core::vector3df i = tp + (n * dist);
// transform the intersection point back to ellipsoid-space
core::vector3df ti = i * rpm;
return ti;
}
- fails on the inner side of the ellipsoid (the more deeper "Point" is)
- issues towards the highest peaks (small)
- I bet it's not punctual! (90-95% would be great)
I can make a small test program if you want!
Can you help me to repair it? Or: can it be repaired?
Thank you
Cheers,
PI
Here's my $0.02:
If you could find the ellipsoid of the same proportions as the inner one on which the point P lies then intersection of a ray using the tangent vector of that point will yield the closest point from P to the original ellipsoid.
Hmmm. Sounds about right but I don't how useful it is to you.
If you could find the ellipsoid of the same proportions as the inner one on which the point P lies then intersection of a ray using the tangent vector of that point will yield the closest point from P to the original ellipsoid.
Hmmm. Sounds about right but I don't how useful it is to you.
Irrlicht Demos: http://irrlicht.sourceforge.net/forum/viewtopic.php?f=6&t=45781