# Minimum bounding ellipsoid implementation

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

## Recommended Posts

Anyone know of existing code for finding the smallest ellipsoid that contains a set of points? I looked at the CGAL code and related papers, but it's a bit convoluted. There is an alternative least squares method for fitting an ellipsoid to data, but I wasn't able to find anything other than a few papers that discussed it. I'd prefer to avoid implementing and debugging this myself if possible. Thanks!

##### Share on other sites
slack,

I would look into computing the smallest bounding volume for a OBB. There are plenty of articles on how to do that. An OBB and an elipsoid will typically share the same data structure that is:

struct Ellipsoid/OBB
{
float3 center;
float halfWidth[3];
QUAT orientation;
};

Even if you don't ues a representation like that you can still translate it over from an OBB to an ellipsoid.

Good luck

##### Share on other sites
Can't you just calculate the maximum distance from the center of three separate axes?

// assuming you already know the AABB of the points setvec3 center = (aabb.vMax - aabb.vMin) / 2;float rx = 0.0f, ry = 0.0f, rz = 0.0f;for (int i = 0; i < pointCount; i++){   vec3 dvec = points - center;   if (dvec.x > rx)      rx = dvec.x;   if (dvec.y > ry)      ry = dvec.y;   if (dvec.z > rz)      rz = dvec.z;}// the ellipsoid has the radius = (rx,ry,rz)

##### Share on other sites
Quote:
 Original post by 999999999Can't you just calculate the maximum distance from the center of three separate axes?

Unfortunately, no. Think about the case where you are trying to surround a box with an ellipsoid. If you used your method, you would generate a sphere inside the box. You want a sphere OUTSIDE the box.

##### Share on other sites
Here's a crazy idea: compute an optimal OBB for the points. Scale the points along the OBB axes by an amount equal to the the OBB axis lengths, so that they fit in a unit length OBB. Now compute a bounding sphere for the points (there should be ways to do this near-optimally). Stretch the bounding sphere back by the inverse of the scale transformation to form an ellipse.

I don't know how optimal it will be, but it may be not too bad. In many cases it will probably be very near optimal.

##### Share on other sites
how can I calculate an OBB out of a point set?

##### Share on other sites
It may not be exactly what you're looking for, but you might look here.

##### Share on other sites
thank you jyk, but it seems that your link makes heavy use of features already implemented in that engine. I think it would be difficult to integrate that in my project. I planned to use an ellipsoid to approximate the player character. now I think I'll create the ellipsoid with the wrong method I showed above and I will scale it by an arbitrary value to fit approximately the object. The right method is not worth trying to implement (at least in my case)

##### Share on other sites
Have you considered just using a cylinder? Assuming your player chatacter is standing ti should be easy enough to compute. Find the bounding circly in the horizontal 2D plane, then the min and max heights, and then just throw them together to get a cylinder.

##### Share on other sites
I agree with you intest86, but I have information to implement a complete and efficient collision detection system with ellipsoid, not cylinders.

1. 1
2. 2
JoeJ
20
3. 3
frob
20
4. 4
5. 5

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

• Total Topics
632212
• Total Posts
3004819

×