3
$\begingroup$

I am trying to implement ellipsoid-ellipsoid collision in my C++ code. Briefly this task can described as next: Let's assume that we have two arbitrarily oriented ellipses in the in space and this ellipses are intersected. This ellipses initially located in the center of coordinate system. We need to find how far we need to move one ellips relative to the other along the line joining their centres until the would not be intersected more. It is quite simple mathematical task. I use next equations:

1)ellipsoid equation in matrix form $$\vec{x}^TA1\vec{x}-1 = 0$$ $$(\vec{x}-d\vec{n})^TA2(\vec{x}-d\vec{n})-1 = 0$$ 2)equality of normals $$A1\vec{x} = \lambda A2(\vec{x}-d\vec{n})$$ Where $$\vec{n}$$ is the unit vector in the direction from one center to another. I am looking for variable $$d$$ from this system.

I have found this system and its solution on the last page of this article http://www.matthiasmueller.info/publications/orientedparticles.pdf It seems like everything is fine, this algorithm works well for most cases, however I have noticed, that for some ellipses there is an error occurs (I mean that this algorithm gives not exact result). I also have noticed, that error occurs primarily when the ratio between the ellipse radii more than 2. In order to solve this problem I have changed all variables in my code from float to double, but it did not give any result. It seems like small error in input data results in very big error in output data. Does anybody know how I can overcome this kind of instability?

$\endgroup$
  • 1
    $\begingroup$ This isn't a solution, but the intersection of two quadric surfaces (which includes ellipses) results in another quadric surface and has a closed form expression. You should be able to find the intersection that results in a point. Neverthess, this solution on a sister site has a bunch of links to papers that may provide you with another path. $\endgroup$ – Damien Oct 9 '13 at 9:25
2
$\begingroup$

In effect you want to "run backwards" until two about-to-intersect ellipses are just touching, to find the time and location of collisions.

I don't think "very simple mathematical task" is how I would describe finding distances between two ellipses in general positions. The concise write-up by David Eberly in Distance Between Ellipses in 2D promises a numerically stable algorithm, and he's well-known for his contributions in this field.

The problem of minimum distance between a circle and an ellipse is easier, involving only a fourth-degree polynomial's roots. So it seems reasonable that the approximate methods you've tried are less reliable when the ellipses have higher ratios between major and minor radii.

For some 3D notation/machinery, see also David Eberly's Distance from a Point to an Ellipse, an Ellipsoid, or a Hyperellipsoid.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.