Ellipse Collisions

viteria

Hey guys, new here, basically i want to know how i can make two ellipses bouce when they hit each other, and when i mean ellipse, i dont mean circles, i mean all types of ellipses Thanks for the help Matteo

quark

If you want accuracy then you need to see if the two ellipse boundaries intersect, this is extremely difficult and computationally very expensive, especially if the ellipses are rotated so they are not aligned to the x and y axis. I know because I tried to create a program to calculate the intersection points of 2 rotated ellipses, it requires the solution of a quartic equation and involves complex numbers. I gave up after many days of programming.

When trying to calculate collisions between difficult shapes then it is common to estimate the shape with circles or rectangles and then use these in the calculations.

quark

My previous post assumed you were using vector graphics. If you are using bitmap images then it is a bit easier. See the source code for this sketch

prince_polka

@quark would you mind sharing the quartic equation?

TfGuy44

You could try to derive it yourself. It's math, yo.

First what's the equation for an ellipse?

a * x * x + b * x * y + c * y * y + d * x + e * y + f = 0

Where a, b, c, d, e, and f are constants that describe the ellipse. Good.

Of course you have two of them:

a1 * x1 * x1 + b1 * x1 * y1 + c1 * y1 * y1 + d1 * x1 + e1 * y1 + f1 = 0
a2 * x2 * x2 + b2 * x2 * y2 + c2 * y2 * y2 + d2 * x2 + e2 * y2 + f2 = 0

Okay. And you want the points of intersection of them, of course, which are points where x1 == x2 and y1 == y2. So really, you want to see if:

a1 * x * x + b1 * x * y + c1 * y * y + d1 * x + e1 * y + f1 = a2 * x * x + b2 * x * y + c2 * y * y + d2 * x + e2 * y + f2

has any solutions. That's your quartic equation right there. Enjoy!

quark

That's your quartic equation right there.

Unfortunately that is not a quartic. A quartic is a polynomial of the form
F(z) = p * z^4 + q * z^3 + r * z^2 + s * z + t
where p != 0

would you mind sharing the quartic equation?

It was over a year ago when I tried solving this so I have dragged my mind back to it and looked up my research.

I am afraid it is not that simple because the determination of the coefficients for the quartic function (p, q, r, s & t) depends on the two sets of ellipse coefficients (a, b, c, d, e & f) which depend on the position and rotation of the ellipse.

Anyway if you are interested this paper and Wikipedia article formed the basis for my work.

The maximum number of intersection points between two ellipses is four, which come from the four 4 solutions to a quartic. If a solution has two real numbers then it represents a displayable intersection point. Any solution that has 1 or 2 complex numbers is rejected because our ellipses are in the real number plane..

Solving the quartic has several intermediate stages which may generate complex numbers but might still end up with a real solution. So you need to be prepared to program using complex number maths.

prince_polka

Thanks

jeremydouglass

I would guess that at a certain point producing the required solution system will be more computationally intensive than a raster-based collision solution -- and the code of a raster-based solution will also be easier to write and more legible.

Just draw two low-rez ellipses into buffer. If your second ellipse touches a pixel that was already touched, return a hit.

This approach has the disadvantage of not being elegant, but a major advantage is that it is flexible. If you change your two ellipses into two rounded rectangles or obrounds (or make one side flat, or give them legs, etc.) -- then raster collision still just works. Of course, it is extremely inefficient of you are working with shapes that have simple solutions.