Jump to content
  • Advertisement
Sign in to follow this  
bennywilson

Determining an ellipsoid from a set of points

This topic is 2343 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi,

I need to determine the axes of an ellipsoid from a mesh. All of the vertices are on the surface of the ellipse, but none of them necessary correspond to any specific location. For example, the vertices that are furthest from each other do not necessarily lie on the major axis.

I found some papers that deal with fitting ellipsoids to arbitrary points (least squares, etc ). Before I dive down that path, I'm wondering if anyone knows of simpler methods that involve points that are guaranteed to be on the surface.

Thanks,

Share this post


Link to post
Share on other sites
Advertisement
Any robust method is going to be at least as involved as least squares, so I don't think you'll find a simpler one. Even though you might think that your points are on the surface, the data type that stores their coordinates has limited resolution, which means that your points will most likely be a bit outside the surface.

The good news is that least squares is not that hard to implement, and it is a very good tool to know well.

Share this post


Link to post
Share on other sites
Fitting implicit surfaces like ellipsoids requires boundary conditions, usually introduced by Lagrange multipliers. As for ellipsoids it boils down to an eigenvalue problem.

We minimize the deviation from the major axes n. The sample points are zero-mean shifted in Y. We minimize under the condition that the major axes are normalized (otherwise we would always get (0,0,0) as solution).
[Formula]E = \frac{1}{2} n^TY^TYn - \lambda n^Tn \rightarrow min[/Formula]
[Formula]\nabla_n E = Y^TYn - \lambda n = 0[/Formula]
[Formula]Y^TYn = \lambda n[/Formula]
Which is just an eigenvalue problem.

[Formula]n[/Formula] are the principal directions of the ellipsoid (eigenvectors), [Formula]\lambda[/Formula] is the scale per eigenvector (eigenvalue) and [Formula]Y^TY[/Formula] is the covariance matrix of your sample points (zero-mean shifted).
What I just did was a principal component analysis.

Share this post


Link to post
Share on other sites
Another method, which takes into account, that you actually have a triangle mesh, might be the following:

1.) Compute the geometric center of your ellipse.
2.) Compute the curvature at each vertex, and use this curvature as weight for the vertex position.
Since the curvature is higher at the long endings, you get higher weights at these vertex locations.
3.) Compute the weighted sum of all vertex positions and the principal axis, like:

for all vertex positions
{
sum += vertex curvatureWeight * (vertex position - center position )
}

principal axis = normalized( sum );

In order to compute the curvature you can just take the L2-norm of the difference of 2 adjacent vertex normals.
And since you have multiple neighbor normals, I would suggest taking again a weighted average of the L2-norms based on the neighbor vertex distance.

Keep in mind, I didn't try that method out, it just came into my mind, but might be worth a try...

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!