# 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.

## 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 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 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 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...

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 10
• 11
• 13
• 9
• 11
• ### Forum Statistics

• Total Topics
634092
• Total Posts
3015448
×