Can anybody help me out with collision detection based on ellipses? I searched with google but found nothing so far. Well, nothing i could understand and use with c++ anyway. i have to admit, i do not know much about geometry. I would like to know how to check whether two ellipses intersect each other or not and maybe the size of the intersection area. Any hints? Thanks in advance.

Better use capsules (capsule = cylinder capped with spheres; so for 2D it's 2 half-circles joined by lines). Ellipses are rather hard to check for intersection; for example to find intersection points you need to solve quartic equation.

if you know how to do a collision test against a sphere then you know how to do one against an elipse. remember an elipse is just a sphere under a linear transform. suppose I have an elipse and the matrix that would make that eplipse from a unit sphere at the origin for example. for example suppose I got a mojor axis as the x axis and it's length is 2 and the minor axis is unchanged, then the matrix that would take the unit sphere to the elipse is
[2 0 0
0 1 0
0 0 1]

so we have a matrix that takes points from sphere local space to elipse global space(assuming there is no translation). so we know all objects we are testing against are in global space so instead of testing these objects against this elipse we can transform the object by the INVERSE of the matrix above and test against the resulting points against a sphere at the origin! this reduces it to a simple distance test.

tim

"remember an elipse is just a sphere under fake linear transformation". You could be in for the the faked astology of the 21'st centuary if you are not careful.

Quote:Original post by timw
if you know how to do a collision test against a sphere then you know how to do one against an elipse. remember an elipse is just a sphere under a linear transform. suppose I have an elipse and the matrix that would make that eplipse from a unit sphere at the origin for example. for example suppose I got a mojor axis as the x axis and it's length is 2 and the minor axis is unchanged, then the matrix that would take the unit sphere to the elipse is
[2 0 0
0 1 0
0 0 1]

so we have a matrix that takes points from sphere local space to elipse global space(assuming there is no translation). so we know all objects we are testing against are in global space so instead of testing these objects against this elipse we can transform the object by the INVERSE of the matrix above and test against the resulting points against a sphere at the origin! this reduces it to a simple distance test.

tim

As I understand, smek2 are interested in collision between 2 ellipses.
The problem of course is collision of two ellipses that needs different transforms to become circles [or spheres if we talk about ellipsoids]. If one needs ellipse collision detection, one need to be able to detect collisions between two ellipses too.
Colsider two long ellipses (2d) intersecting in cross-like way, so there is four intersection points. There's aint no transformation that can reduce it to two circles (two circles can have at most 2 intersection points) Indeed it does reduce to ellipse versus circle, but you still get quartic equation.

Yes i am interested into checking collision for two ellipses.
Can someone explain (or provide to a good link) for quartic equations and/or capsules (they seem to be a good alternative, but i have no idea about that either)
Anyways, thanks for the replies.

well, quartic equations it's equation of form ax^4+bx^3+cx^2+dx+e=0 . It have up to four roots. You get it if you solve this ellipse-ellipse thing for intersection points. It is rather difficult to derive for general case; there's special-case solution(when both ellipses have same center) http://mathworld.wolfram.com/Circle-EllipseIntersection.html.
(for two ellipses you can transform it so one becomes a circle)

I know that distance between ellipsoids (3D) are commonly computed using iterative methods.

Capsules is quite simple thing. You can use google
Volume of capsule is defined as set of points whose distances to line segment is less or equal to r.
To check for intersection of 2 capsules you just find closest distance between 2 line segments and check if it is greater than r1+r2 .
(I'm currently assuming there's no real reason for you to prefer ellipsoids to capsules.)