# 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 on other sites
Quote:
 Original post by glSmurfok ...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 on other sites
=/ not the answer I wanted ...but I can't say I didn't expect it

##### 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 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 on other sites
I've given up, and all ellipsoid relative code has been deleted =/

Quote:
 Original post by wyrzyI 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 AcePilotI 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.zipP.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 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 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 on other sites
thanks for all replies, but as I said before I have given up. atleast for now =)

##### 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 on other sites
Quote:
 Original post by SimmerDI 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 on other sites
I don't see why it wouldn't be orthognal. X, Y & Z are still independent dimensions, there's no projection involved...

##### Share on other sites
Quote:
 Original post by SimmerDI 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 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.

## Create an account

Register a new account

• ### Forum Statistics

• Total Topics
628293
• Total Posts
2981869

• 11
• 10
• 10
• 11
• 17