Advertisement Jump to content
Sign in to follow this  

Determining an ellipsoid from a set of points

This topic is 2494 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


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.


Share this post

Link to post
Share on other sites
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, you agree to our community Guidelines, Terms of Use, and Privacy Policy. is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!