I don't have a good resource myself. Sounds like a hard problem unless you are going to convert one ellipsoid into faces. Maybe there is some easy way I don't know about.

However if both ellipsoids are oriented in the same way and have the same "relative" dimensions then it's easy. I imagine if you are using this for characters in a game this could be the case. Scaling one ellipsoid to a sphere will then scale all the others to spheres and then you can simply do sphere to sphere collision. My guess is this is how a lot of games do it. It's probably the easiest way if you can get away with it.

At my previous company we had this same issue, but nobody was able to come up with a solution. Then one of my collegues asked some math professor he knew about it, and his reaction was that it was probably going to be so ridiculously complex that we should just forget about it:). I believe the hacky solution we eventually used was to just use a triangle mesh for one of the two ellipsoids.

For a swept ellipse test, the contact point turns out to be a common root to two quadratic polynomials in (x,y), say, q0(x,y) = 0 and q1(x,y) = 0. These reduce a degree 4 polynomial in x, say p0(x). However, you also know that the two ellipses are tangent at the point of contact, which gives you another quadratic polynomial equation q2(x,y) = 0. Reduce q0 = 0 and q1 = 0 to another degree 4 polynomial in x, say p1(x). Now x must be a root to two polynomials in one variable. You can work through the elimination process for p0 = 0 and p1 = 0 to obtain a set of equations that relate the coefficients of q0, q1, and q2. To get to this point, only arithmetic operations are used (i.e. it is fast). These coefficients are polynomial functions of time t, so solving the equations tells you the (potential) contact times. This will be the computational bottleneck.

The swept ellipsoid test is similar in structure. The contact point is a common root to two quadratic polynomials in (x,y,z), say, q0(x,y,z) = 0, q1(x,y,z) = 0. Knowing that the ellipsoids are tangent gives you two more quadratic equations, q2(x,y,z) = 0 and q3(x,y,z) = 0. You can reduce q0 = 0, q1 = 0, and q2 = 0 to obtain a polynomial p0(x) = 0. And you can reduce q0 = 0, q1 = 0, and q3 = 0 to obatin a polynomial p1(x) = 0. Follow the same elimination process as was done for ellipses to obtain polynomial equations in contact time t.

This is most likely computationally intensive, so you might consider different bounding volumes. I have not worked through the details, but ellipsoids that are prolate or oblate might reduce some of the complexity from the general ellipsoid case.

Hmm, I think you could do it like this: Set up the equations for the ellipses, perform a change of coordinates (using a linear transformation) to turn one of the ellipses into a circle(or sphere for 3D). Solving the collision equation should be easier this way. If both the ellipses are of the same shape (this is likely to happen in a game, if for instance you are using a bounding ellipse for all the players in the game) then it's just a swept sphere against a sphere.. which I'd imagine would be a simple equation..

I think they are assuming ellipsoids are not necessarily aligned to the same, or even any, axis.

Quote:Original post by Scuppy
I think they are assuming ellipsoids are not necessarily aligned to the same, or even any, axis.

I'm not 100% sure about this. For a lot of gaming applications they very well might be aligned. Depends what he's doing.

You can transform one ellipsoid to a sphere and the other ellipsoid to be axis-aligned. It turns out that the problem has a solution that can be computed reasonably fast in a collision system. Tomorrow, I will be posting a PDF to my Geometric Tools website that describes how to compute the contact time and contact point for two moving ellipses (2D) and for two moving ellipsoids (3D) when those objects are initially separated.

Quote:Original post by Dave Eberly
You can transform one ellipsoid to a sphere and the other ellipsoid to be axis-aligned. It turns out that the problem has a solution that can be computed reasonably fast in a collision system. Tomorrow, I will be posting a PDF to my Geometric Tools website that describes how to compute the contact time and contact point for two moving ellipses (2D) and for two moving ellipsoids (3D) when those objects are initially separated.

Yeah that's true. Good call! I'll have to check that out. Hopefully us non-math wizards will be able to understand it.