**0**

# Figuring out ellipsoid-ellipsoid collision detection

###
#1
Members - Reputation: **295**

Posted 30 August 2012 - 10:50 PM

It should be easy to convert the ellipsoids to a sphere and a skewed ellipsoid by applying a series of affine transformations.

I've read that a skewed ellipse is still elliptical, so the skewing is equivalent to a rotation and a scaling, and I assume that the same principle applies to ellipsoids. However, I'm not sure how to determine the rotation and axis lengths of the new ellipse. If I knew that, it would be easy to make the ellipsoid axis-aligned. After that, I'm hoping to be able to perform a sweep test, but I'm not sure how efficiently it can be done, and I haven't figured out the equations to use yet, although I could possibly figure those out with a little work.

I'm also considering working with other collision shapes if ellipsoids don't work out, but it would be really nice to be able to use the same shapes for object-world and object-object collisions.

###
#2
Members - Reputation: **249**

Posted 31 August 2012 - 01:12 AM

But anyway, I would recommend using capsules ('capped cyllinders') for object collisions if your 'objects' are people, for example. Or just plain boxes, if only for coarse collision detection. Ellipsoids are not exactly standard so I don't know why you'd want them so bad.

**Edited by mv348, 31 August 2012 - 01:24 AM.**

###
#4
Members - Reputation: **295**

Posted 31 August 2012 - 02:44 AM

EDIT:

It looks like finding the eigenvectors for basic affine transformations (such as scaling) isn't tough at all, but the eigenvectors for a combined transformation are tougher. I think the set would just be the union of the eigenvector sets of the component transformations if there were no pairs of inverse transformations involved, but I might not always be able to guarantee that. Of course, if I know where the pairs are, I might be able to eliminate them from the calculation.

###
#5
Crossbones+ - Reputation: **12527**

Posted 31 August 2012 - 07:55 AM

- Compute coordinates where one of the ellipsoids becomes axis aligned. Pick the length of the vectors so the ellipsoid becomes a sphere.
- After the transformation, compute coordinates where the other ellipsoid becomes axis aligned. Now you should pick unit-length vectors so you keep the sphere a sphere.
- Compose the two changes of coordinates.

###
#6
Members - Reputation: **295**

Posted 31 August 2012 - 09:29 AM

If the axes of the transformed ellipse coincide with (the transformation) * (the original axes), finding the rotation/scale that correspond to the introduced skew shouldn't be too hard. I'm just not sure if the skewing makes the ellipse bulge, changing its axes beyond what the skew might suggest.

Edit:

I know it changes at least one axis; otherwise this would be way too easy...

I think all I need to do is to figure out how to find the new axes given the eigenvectors. From there, calculating the required transformation should be easy.

###
#7
Crossbones+ - Reputation: **12527**

Posted 31 August 2012 - 09:40 AM

The first step should be easy; I can use an inverse rotation and a scaling instead of finding eigenvectors.

It depends on how the ellipsoid is expressed, but if you do have the axes already, yes.

If the axes of the transformed ellipse coincide with (the transformation) * (the original axes), finding the rotation/scale that correspond to the introduced skew shouldn't be too hard.

Unfortunately, it's not that easy. The first transformation can easily change the axes of the other ellipsoid.

I seem to remember Dave Eberly's book "3D Game Engine Design" had details on how to perform many intersection tests, probably including this one. I'll take a look at it when I get home. Or maybe Dave could lend a hand here, since he does hang out in these forums.

###
#8
Members - Reputation: **295**

Posted 05 September 2012 - 01:18 PM

###
#9
Crossbones+ - Reputation: **12527**

Posted 05 September 2012 - 11:16 PM

I don't think you can get away without an understanding of linear algebra if you want to do this kind of thing.

###
#10
Members - Reputation: **295**

Posted 06 September 2012 - 02:05 AM

I haven't taken a linear algebra course, so I'm learning as I go. I'll see if I can make more sense of the paper I mentioned. If not, I'll probably just switch to capsules for the object-object pass. I've got an idea for a capsule-capsule sweep test that might work.

###
#11
Members - Reputation: **295**

Posted 06 September 2012 - 12:00 PM

###
#14
Members - Reputation: **295**

Posted 06 September 2012 - 08:50 PM

If I can get the eigendecomposition, I should be able to get the second ellipsoid to be axis-aligned. I can then pad the second ellipsoid by the radius of the now-spherical first ellipsoid and make the first ellipsoid a point, making the test a simple case of a ray-ellipsoid intersection.

Is there an algorithm for getting the eigenvectors of an affine 3x3 matrix that is more efficient than the general case, or should I just implement a general eigenvector solver?

I guess that means I can just use dot products to bring the sphere's position into the space defined by the eigenvectors. That should be equivalent to making the ellipsoid axis-aligned, right?..and the solution is to use the eigenvectors as the basis for your coordinates.

###
#15
Crossbones+ - Reputation: **12527**

Posted 06 September 2012 - 09:44 PM

I just realized that capsules are useless for objects that are shorter than they are wide. I might go back to ellipsoids...

If I can get the eigendecomposition, I should be able to get the second ellipsoid to be axis-aligned. I can then pad the second ellipsoid by the radius of the now-spherical first ellipsoid and make the first ellipsoid a point, making the test a simple case of a ray-ellipsoid intersection.

Unfortunately for this plan, a padded ellipsoid is not an ellipsoid.

Is there an algorithm for getting the eigenvectors of an affine 3x3 matrix that is more efficient than the general case, or should I just implement a general eigenvector solver?

I would go with the general method. Worry about getting something that works first, and worry about performance later.

I guess that means I can just use dot products to bring the sphere's position into the space defined by the eigenvectors. That should be equivalent to making the ellipsoid axis-aligned, right?..and the solution is to use the eigenvectors as the basis for your coordinates.

At the very least you should learn enough linear algebra to know how to change coordinates from one basis to another (i.e., multiply by a matrix). But yes, it can be expressed as a bunch of dot products.

###
#16
Members - Reputation: **295**

Posted 06 September 2012 - 11:04 PM

Are you sure? I took an ellipse and expanded each axis by a fixed amount, and the resulting ellipse seemed to be a perfectly padded ellipse so that a point colliding with it is equivalent to a circle colliding with the original. I didn't verify it mathematically, but it looked just fine with a ruler, which is probably good enough for an approximate collision detection.Unfortunately for this plan, a padded ellipsoid is not an ellipsoid.

Sounds like a good plan. Looks like it's Google time.I would go with the general method. Worry about getting something that works first, and worry about performance later.

Edit:

I've found some code that might work. Does 6,000 cycles per decomposition sound reasonably efficient?

Oh... now I see it. For some reason, linear algebra takes longer to "click" in my mind than most other topics do. I might need a little more practice...At the very least you should learn enough linear algebra to know how to change coordinates from one basis to another (i.e., multiply by a matrix). But yes, it can be expressed as a bunch of dot products.

I think I've just about got this figured out, though.

**Edited by BLM768, 06 September 2012 - 11:24 PM.**

###
#17
Members - Reputation: **1161**

Posted 06 September 2012 - 11:50 PM

That said, there is an implementation of the ellipsoid-ellipsoid intersection at my web site.

Regarding capsules, better choice than ellipsoids because the intersection/separation tests are simpler to implement. For capsule-capsule sweep, a simple implementation uses bisection over the desired time interval. At each time you apply a (static) capsule-capsule overlap test, which reduces to a computation of distance between line segments and a comparson involving this distance and capsule radii. You can avoid the iteration--I have pseudocode for this in my Game Physics 2nd edition (section 6.3.2).

Regarding bounded cylinders, the game physics book and a document at my web site show the complexity of intersection testing via separating axes. Turns out that it is simpler to do cylinder-cylinder intersection with infinite cylinders, then clip the intersection set based on the finite cylinder heights. Not an exact test (result is not a closed form solution), but effective. I have a document about this at my web site and a sample application (for the infinite cylinder-cylinder test).

###
#18
Members - Reputation: **295**

Posted 07 September 2012 - 01:06 AM

If I can manage to simplify it to a ray-ellipsoid intersection by padding one ellipse, the code shouldn't be hard (except for the eigendecomposition, for which I can just use existing code). The simplification would also make it possible to solve all but the eigendecomposition analytically. I think that would take care of a lot of the numerical robustness issues, although I don't know for sure.My advice is to skip ellipsoids. Use a bounding box or a k-DOP (or some convex polyhedron with a small number of faces), then use separating axis tests. The coding is just a lot easier, and the numerical robustness issues in determining ellipsoid-ellipsoid intersection can be avoided.

I've actually been working off that implementation, although the final implementation will probably be quite different.That said, there is an implementation of the ellipsoid-ellipsoid intersection at my web site.

They are easier, and I was going to use them, but I realized that they don't handle disk-shaped objects well at all; they can't get any flatter than a sphere. I'm not sure how often that would be an issue, but it would be nice to not have to worry about it.Regarding capsules, better choice than ellipsoids because the intersection/separation tests are simpler to implement.

If I knew of a better algorithm to find the eigendecomposition, I think I could get ellipsoids to work extremely well. The fact that I need one of those complex, time-consuming algorithms makes me a little uneasy about my solution, but not enough to abandon it before I see how well it works.

I just realized, though, that getting the inverse matrix to get the modified velocity back into world space might be hairy...

Hmm... I guess I might have to drop ellipsoids (except for collision with meshes; the code for that is just too nice to replace) and go with capsules. I suppose that I'll just have to go without disk-shaped objects or special-case the collision code somehow.

Darn it; I was getting a really nice solution before the technical details had to spoil it for me. There's just too much math in this math stuff .

As far as capsule-capsule collision goes, I'm pretty sure I can simplify it to sweeping a line segment against a larger capsule, which could give me a really nice analytical solution as long as sweeping it against the spherical ends isn't a problem. I think I can figure it out...

###
#19
Crossbones+ - Reputation: **12527**

Posted 07 September 2012 - 07:04 AM

Are you sure? I took an ellipse and expanded each axis by a fixed amount, and the resulting ellipse seemed to be a perfectly padded ellipse so that a point colliding with it is equivalent to a circle colliding with the original. I didn't verify it mathematically, but it looked just fine with a ruler, which is probably good enough for an approximate collision detection.Unfortunately for this plan, a padded ellipsoid is not an ellipsoid.

Think of an ellipsoid that is very very skinny: Say 2 units long, 0.0001 wide and 0.0001 deep. Now add one unit of padding. The resulting figure is much closer to a capsule than it is to an ellipsoid.

###
#20
Members - Reputation: **295**

Posted 07 September 2012 - 09:10 AM

Think of an ellipsoid that is very very skinny: Say 2 units long, 0.0001 wide and 0.0001 deep. Now add one unit of padding. The resulting figure is much closer to a capsule than it is to an ellipsoid.

OK; I see. Degenerate or near-degenerate cases seem to be great for disproving incorrect ideas; I might have to make use of that fact.

A padded capsule should still be a capsule, though, right? Even the degenerate case seems to work there.