I've been working on collision detection code for a project, and I'm trying to figure out the method to use to detect collisions between objects. Since I use ellipsoids to test against level geometry, I'd like to use them for collisions between objects as well. The problem is figuring out exactly how. One method I've seen converts the ellipsoids to a sphere and an axis-aligned ellipsoid, which looks like a great solution, but the method involves finding eigenvectors and other advanced stuff that I don't really understand (yet) and would rather not have to implement.

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.

I just typed up a way of computing ellipsoid collisions but there was a flaw in my logic so I'll have to think about it some more.

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.

Computing eigenvectors is precisely how you figure out the axes of the ellipsoid, and I am afraid you are going to have to learn how to use them.

It looks like I might have to learn more about eigenvectors. Capsules are a nice solution for collisions with meshes, but there doesn't seem to be a good sweep test for them that allows arbitrary rotation. Is there a simpler, faster method of finding eigenvectors when the matrices represent affine transformations?

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.

You need to find the eigenvectors of the 3x3 submatrix that maps vectors to vectors (i.e., without the row and column that are zero and a translation). Here's what I would try:

• 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.
  

There is some theorem about simultaneously turning a quadratic form into the identity and diagonalizing another one, which I think is effectively what we are doing here. Unfortunately I couldn't find a good reference with a quick web search.

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

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.

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.
[/quote]

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.

I've tried playing around with the equations for an ellipse, but that's getting me nowhere. I found a method here, but it's beyond my comprehension, especially with defining the ellipse equation in terms of matrices. Is there some other way to represent the relationship between the eigenvectors of the transformation matrix and the axes of the skewed ellipsoid?

It is extremely natural to represent the equation of an ellipsoid using a symmetric matrix. Finding the axes of an ellipsoid is equivalent to finding coordinates in which the ellipsoid is simply a*x^2 + b*y^2 + c*z^2 = 1. In terms of the matrix, you are diagonalizing it (the off-diagonal elements correspond to terms that contain products of different variables). This is a very well understood problem, and the solution is to use the eigenvectors as the basis for your coordinates. So if you figure out a procedure to find the axes, you will have reinvented an algorithm to find the eigenvectors.

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

I think I'm starting to get it...maybe...

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.