VEGAS VEGAS VEGAS
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:
  1. 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;
  2. based on this classification, we present the first practical algorithm that correctly identifies and parameterizes the intersection in all cases;
  3. 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.
Chess game

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.


ellipsoid cone Hyperboloid2
Elliptic Cylinder Hyperbolic paraboloid Hyperboloid1


Fig 2: Examples of quadric surfaces.

Publications

Examples



ellipsoid Hyperboloid2 Hyperboloid2 cone
(a)
(b)
(c)
(d)


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).
ellipsoid
cone
Hyperboloid2
(a): Cubic and line
(b): One (double) line
(c): One conic
ellipsoid
cone
Hyperboloid2
(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.
ellipsoid
cone
Hyperboloid2
(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.
ellipsoid
cone
Hyperboloid2
ellipsoid
(a): Nodal quartic with an isolated point
(b): Nodal quartic without isolated point
(c): Two points
(d): Two disjoint conics
cone
Hyperboloid2
Hyperboloid2
(e-f): 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.
ellipsoid
cone
Hyperboloid2
Hyperboloid2
(a): One point
(b): One conic and two lines
(c): One conic and a point
(d): A cubic and a secant line
ellipsoid
cone
Hyperboloid2
Hyperboloid2
(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.
ellipsoid
cone
Hyperboloid2
Hyperboloid2
(a): One conic and a (double) line
(b): Four concurrent lines
(c): Two intersecting lines
(d): One (double) line
ellipsoid
cone
Hyperboloid2
Hyperboloid2
(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.