Sign in to follow this  
Nairb

Swept ellipsoid-ellipsoid collision

Recommended Posts

Nairb    766
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 this post


Link to post
Share on other sites
oliii    2196
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 this post


Link to post
Share on other sites
polypterus    100
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 this post


Link to post
Share on other sites
quasar3d    814
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 this post


Link to post
Share on other sites
Dave Eberly    1173
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 this post


Link to post
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 this post


Link to post
Share on other sites
polypterus    100
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.

Share this post


Link to post
Share on other sites
Dave Eberly    1173
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 this post


Link to post
Share on other sites
polypterus    100
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.

Share this post


Link to post
Share on other sites
Dave Eberly    1173
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.


This is the PDF for ellipses and for ellipsoids: Intersection of Swept Ellipses and Swept Ellipsoids. I replaced the bisection discussion by one that uses Newton's method and avoids the circle-sweptregion and sphere-sweptregion tests (these are implicitly tested in the algorithm). Wild Magic source code is included in the PDF, both for ellipses and ellipsoids.


[Edited by - Dave Eberly on May 10, 2009 1:20:16 PM]

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this