Minimum bounding ellipsoid implementation
Author
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!
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
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
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)Quote:Original post by 999999999
Can'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.
Sorry, I cannot help you slack.
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.
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.
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)
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.
I agree with you intest86, but I have information to implement a complete and efficient collision detection system with ellipsoid, not cylinders.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
