Solving the interference problem for ellipses and ellipsoids: New formulae.

Abstract

The problem of detecting when two moving ellipses or ellipsoids overlap is of interest to robotics, CAD/CAM, computer animation, etc., where ellipses and ellipsoids are often used for modelling (and/or enclosing) the shape of the objects under consideration. By analysing symbolically the sign of the real roots of the characteristic polynomial of the pencil defined by two ellipses/ellipsoids A and B given by XTAX = 0 and XTBX = 0, we derive new formulae characterising when A and B overlap, are separate, or touch each other externally. This characterisation is defined by a minimal set of polynomial inequalities depending only on the entries of A and B so that we need only compute the characteristic polynomial of the pencil defined by A and B, det(TA + B), and not the intersection points between them. Compared with the best available approach dealing with this problem, the new formulae involve a smaller set of polynomials and less sign conditions. As an application, this characterisation provides also a new approach for exact collision detection of two moving ellipses or ellipsoids since the analysis of the univariate polynomials (depending on the time) in the previously mentioned formulae provides the collision events between them.