Sign in to follow this  
glSmurf

collision detection with ellipsoids (again?)

Recommended Posts

ok ...this was abit harder then I first thought. I can't even compute if the two ellipsoids intersect, and when it comes to finding the intersection point and normal it gets even more difficult. It is abit easier if both ellipsoids are axis aligned but that is rarely the case. I know I'm not the first one to struggle with this problem and if anyone know anything that might help, please post that info.

Share this post


Link to post
Share on other sites
Quote:
Original post by glSmurf
ok ...this was abit harder then I first thought. I can't even compute if the two ellipsoids intersect
It is more than a bit harder than you think it is. The lengthy answer is given in this paper:

Wang, Wenping. Jiaye Wang. Myung-Soo Kim. "An Algebraic Condition for the Separation of Two Ellipsoids." Computer Aided Geometric Design, vol. 18, no. 6, pp. 531-539, July 2001.

You can find the paper online here:

http://3map.snu.ac.kr/mskim/ftp/ellipsoid.pdf

The short answer, though, is: give up on ellipsoids!

Share this post


Link to post
Share on other sites
I realize this is not the answer you're looking for, but if you want to try something easier I recommend using bounding cylinders. I've found them to be more precise than bounding spheres or bounding boxes (for the objects I'm using), and you can always use multiple clyinders to achieve higher accuracy. I assume you can figure out how to detect collision for them (its a circle with a height).

Share this post


Link to post
Share on other sites
I was looking for the same thing as you were back a few days ago, how to determine if two ellipsoids defined as a center point and a radius vector were colliding. Well I gave up. But I did find a pretty good demo, too bad they didnt release the source code.

http://www.morrowland.com/apron/tut_gl.php
scroll down to find the program. It is named "ELLIPSOID COLLISION DEMO".

Or if you want the direct link.
http://www.morrowland.com/apron/tutorials/gl/gl_ellipsoid_collision.zip

P.S. I know that didn't help at all. Sorry.

Share this post


Link to post
Share on other sites
I've given up, and all ellipsoid relative code has been deleted =/

Quote:
Original post by wyrzy
I realize this is not the answer you're looking for, but if you want to try something easier I recommend using bounding cylinders. I've found them to be more precise than bounding spheres or bounding boxes (for the objects I'm using), and you can always use multiple clyinders to achieve higher accuracy. I assume you can figure out how to detect collision for them (its a circle with a height).

I wasn't going to use the ellipsoids as bounding volumes =) thanks anyways

Quote:
Original post by AcePilot
I was looking for the same thing as you were back a few days ago, how to determine if two ellipsoids defined as a center point and a radius vector were colliding. Well I gave up. But I did find a pretty good demo, too bad they didnt release the source code.

http://www.morrowland.com/apron/tut_gl.php
scroll down to find the program. It is named "ELLIPSOID COLLISION DEMO".

Or if you want the direct link.
http://www.morrowland.com/apron/tutorials/gl/gl_ellipsoid_collision.zip

P.S. I know that didn't help at all. Sorry.

I think you'll have to buy the cd in order to get the source code for that demo =(. and I it also uses the ellipsoids as a bounding volume (unrotated)

guess I'll just have to move on to the next shape on my list =(

Share this post


Link to post
Share on other sites
I always thought it could be done rather easily but never tested the method I'm thinking about. So your expertise might save me some time :). The way I see it:

- Take the shortest distance between the two ellipsoid up vectors.
- The two points on both up vectors can be (should already be) expressed as a parametric value along their respective axis kn € [0;1].
- The radius of the cross section along each up vectors can be computed using cos(kn) * uradius.
- And from there overlap is easy to tell by comparing distances...

Am I overlooking something?

Another thing I was thinking about is that it should be possible to use SAT with perfect sphere and alikes. A sphere is a convex with an infinity of planes and edges so provided that you pick the correct ones SAT should work perfectly. This could extend to ellipsoid as well.
My 20 yen.

Share this post


Link to post
Share on other sites
oooo...I haven't looked yet but I think geometrictools.com might have something...as it certainly had something strange about basis vectors...

Also, I remember from an geometrictools.com ellipsoid-to-triangle collision paper I read, peroxide.dk I think, they simplified the problem by making a matrix to transform the ellipsoid into a sphere then applying the matrix to all of the triangles.

Perhaps you could do that to make a sphere-to-ellipsoid collision?

EDIT: put in clickies and wanted to report that I believe geometric tools 'only' has intersection for 2D ellipsoids, but maybe you could project your 3D ellipsoids into the three planes? I not sure that would work though :S

Share this post


Link to post
Share on other sites
I am going to try this later on today, because I think it's doable, and not that hard due to symmetry. If my method works, it will undoubtedly reduce to the same math in the paper that Christer referred to.

So, you have two arbitrarily oriented ellipsoids A and B, with radii A.xyz and B.xyz, and you want to find their contact point & normal.

You want to put B in a space such that A becomes a unit sphere. If B and A are axis aligned, this is easily done by :

B.x /= A.x; B.y /= A.y; B.z /= A.z, and similarly for the center of B.

If A and B are not axis aligned, then you can't represent the ellipse's radius by 3 scalars, but by 3 vectors.

If you rotate these vectors into A's axis aligned space, then scale down the resulting vectors by A.xyz, rotate the ellipsoid center into A's space and scale down, you will now have arbitrary ellipsoid B vs unit sphere A.

Now we can rotate around the unit sphere A with no problem, so we can rotate the ellipsoid B so that its radius vectors become
axis aligned, and of the form :

b.x = < * 0 0 >
b.y = < 0 * 0 >
b.z = < 0 0 * >


Now we have an axis-aligned ellipsoid vs a sphere. We could add the sphere's radius of 1 to the ellipsoid radii and simply test the origin WRT the ellipse.

So it boils down to taking advantage of symmetry to reduce the problem to something conceptually simpler.

Once you've calculated your point in A's sphere space, you'd need to go through the inverse of whatever transforms you've made up to this point, and then plug the point into your Ellipsoid->GetNormal( point ) function to get the normal at that point.

Share this post


Link to post
Share on other sites
Quote:
Original post by SimmerD
I am going to try this later on today, because I think it's doable, and not that hard due to symmetry. If my method works, it will undoubtedly reduce to the same math in the paper that Christer referred to.

So, you have two arbitrarily oriented ellipsoids A and B, with radii A.xyz and B.xyz, and you want to find their contact point & normal.

You want to put B in a space such that A becomes a unit sphere. If B and A are axis aligned, this is easily done by :

B.x /= A.x; B.y /= A.y; B.z /= A.z, and similarly for the center of B.

If A and B are not axis aligned, then you can't represent the ellipse's radius by 3 scalars, but by 3 vectors.

If you rotate these vectors into A's axis aligned space, then scale down the resulting vectors by A.xyz, rotate the ellipsoid center into A's space and scale down, you will now have arbitrary ellipsoid B vs unit sphere A.
[...]


I didn't go through your complete method to check wether that would be easily solvable but B base is not going to stay orthogonal if B is not axis aligned. So the sphere would need to be skewed to account for that... I guess...

Share this post


Link to post
Share on other sites
Quote:
Original post by SimmerD
I don't see why it wouldn't be orthognal. X, Y & Z are still independent dimensions, there's no projection involved...


Okay, maybe I misunderstood you but you transform B into A space. So the scaling will take place in (say) world space but B axis vectors will most likely have some orientation so scaling them will make them non-orthogonal.

Share this post


Link to post
Share on other sites
Yes, you are right, B's axes would be stored as 3 vectors, and then be anisotropically scaled into the space of A.

I suppose the question then becomes - does B still represent an ellipsoid? I think so, but I'm not sure.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this