# Swept ellipsoid-ellipsoid collision

This topic is 3540 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Last collision question for a while, I promise. :-) Does anyone have a good resource for swept ellipsoid to ellipsoid collision? I'm already using swept ellipsoid-triangle collision for my general level collision, and I'd ideally like to use those ellipsoids for my entity-entity collision as well. Preliminary google searches haven't yielded much. If it comes down to it, I can probably use swept AABB collisions for my entity-entity collision, though finding the sliding plane for that seems to be a pain. It's not as nice, but I doubt users would notice. Cheers, --Brian

##### Share on other sites
swept ellipsoid vs ellipsoid is actually quite hard, especially with oriented ellipsoids.

You could approximate your entities with two or three of spheres for entity collisions, but you can get aabb-aabb collision with the slide plane, using the swept SAT.

The swept SAT will also give you Triangle-AABB, Triangle-OBB, Triangle-Triangle, AABB-OBB and OBB-OBB collisions all for free.

I have a pretty solid 2D version, the 3D version is a simple extension to the algorithm.

##### Share on other sites
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.

##### Share on other sites
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.

##### Share on other sites
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.

##### Share on other sites
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..

##### Share on other sites
I think they are assuming ellipsoids are not necessarily aligned to the same, or even any, axis.

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

##### Share on other sites
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.

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

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

(You must login to your GameDev.net account.)

• 15
• 14
• 46
• 22
• 27
• ### Forum Statistics

• Total Topics
634045
• Total Posts
3015218
×

## Important Information

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!