Jump to content
  • Advertisement
Sign in to follow this  
slack

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.

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

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 this post


Link to post
Share on other sites
Advertisement
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 this post


Link to post
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 set
vec3 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 this post


Link to post
Share on other sites
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.

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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.

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!