We present the first exact, robust, practical and efficient algorithm, and its
implementation, for computing a parametric form of the intersection of two arbitrary
quadrics (Figs 1 & 2) with rational coefficients. Our method is similar in spirit to the
general method introduced by J. Levin in 1976 for computing an explicit representation of
the intersection of two quadrics, but extends it in several directions. Combining results
from the theory of quadratic forms, linear algebra and number theory, we show how to
obtain parametric intersection curves that are both `simple' (the size of the
coefficients is small) and `as rational as possible'.
More precisely, our algorithm/implementation has the following features:

we present the first classification of pairs of quadrics based on the type of their
intersection in real projective space, thus refining over the reals the classification
in complex space by Segre in 1883;

based on this classification, we present the first practical algorithm that correctly identifies and
parameterizes the intersection in all cases;

the parameterization is essentially as simple as possible. We also produced a
C++ implementation of this algorithm, QI,
which is, up to our knowledge, the only existing solution for computing exactly a
parameterization of the intersection of two quadrics.

Fig 1: Chess set modeled by
SGDL inc. with quadrics in CSG form. We computed the
boundary representation of the scene and then rendered with
Candela.

Fig 2: Examples of quadric surfaces.

Publications
 Laurent Dupont, Daniel Lazard, Sylvain Lazard and Sylvain Petitjean. NearOptimal Parameterization of
the Intersection of Quadrics: I. The Generic Algorithm. INRIA Research
Report n^{o} 5667, 2005, 36 pages.
 Laurent Dupont, Daniel Lazard, Sylvain Lazard and Sylvain Petitjean. NearOptimal Parameterization of
the Intersection of Quadrics: II. A Classification of Pencils. INRIA Research Report
n^{o} 5668, 2005, 37 pages.
 Laurent Dupont, Daniel Lazard, Sylvain Lazard and Sylvain Petitjean. NearOptimal Parameterization of
the Intersection of Quadrics: III. Parameterizing Singular Intersections. INRIA Research Report
n^{o} 5669, 2005, 34 pages.
 Sylvain Lazard, Luis Mariano Peñaranda, and Sylvain Petitjean. NearOptimal Parameterization of
the Intersection of Quadrics: IV. An Efficient and Exact Implementation. INRIA Research Report
n^{o} 5670, 2005, 30 pages.
 Laurent Dupont. Paramétrage quasioptimal de l'intersection de deux
quadriques : théorie, algorithmes et implantation (2.5Gb). Thèse d'université,
Université Nancy II, octobre 2004.
 Sylvain Lazard, Luis Mariano Peñaranda, and Sylvain
Petitjean. Intersecting Quadrics: An Efficient and Exact
Implementation, Computational Geometry: Theory and
Applications, vol. 35, number 12,
pp. 7499 (special issue of invited papers from SoCG'04). Also in
Proc. of the 20th annual Symposium on
Computational Geometry (SoCG'04), pp. 419428, NewYork, 2004 (extended abstract.pdf).
 Laurent Dupont, Daniel Lazard, Sylvain Lazard and Sylvain
Petitjean. NearOptimal Parameterization of the Intersection of
Quadrics In Proc. ACM Symposium on Computational Geometry, 2003, pp. 246255. extended abstract.pdf (300k).
 Laurent Dupont, Daniel Lazard, Sylvain Lazard and Sylvain
Petitjean. Towards the Robust Intersection of Implicit
Quadrics. In Uncertainty in Geometric Computations,
J. Winkler and M. Niranjan, editors, pages 5968, Kluwer
Academic Publishers, 2002. extended abstract.ps (77k).
Examples
Fig 3: Examples of intersection curves for regular pencils. The
intersection curve is a smooth quartic
with one or two connected components, or entirely imaginary (d).



(a): Cubic and line 
(b): One (double) line 
(c): One conic 



(d): Three lines, with one double (in green)

(e): One conic and two lines 
(f): Two (double) lines 
Fig 4: Examples of intersection curves for singular pencils when determinantal equation has one quadruple root.



(a): Cuspidal quartic 
(b): Two tangent conics 
(c): One (double) conic 
Fig 5: Examples of intersection curves for singular pencils when determinantal equation has one triple root.




(a): Nodal quartic with an isolated point 
(b): Nodal quartic without isolated point 
(c): Two points 
(d): Two disjoint conics 



(ef): Two conics intesecting in two points 

(g): One conic 
Fig 6: Examples of intersection curves for singular pencils when determinantal equation has one double root and two simple roots.




(a): One point 
(b): One conic and two lines 
(c): One conic and a point 
(d): A cubic and a secant line 




(e): Two points 
(f): Four skew lines 
(g): Two disjoint (simple) lines 
(h): A cubic and a disjoint line 
Fig 7: Examples of intersection curves for singular pencils when determinantal equation has two double roots.




(a): One conic and a (double) line 
(b): Four concurrent lines 
(c): Two intersecting lines 
(d): One (double) line 




(e): Three concurrent lines (one double) 
(f): Two (double) concurrent lines 
(g): Two concurrent lines (one triple) 
(h): A (quadruple) line 
Fig 8: Examples of intersection curves for degenrate pencils when determinantal equation is identically equals to 0.