 |
QI: Quadric Intersection |
(Model courtesy of SGDL Systems)
What is QI?
QI stands for "Quadrics Intersection". QI is the first exact,
robust, efficient and usable implementation of an algorithm for parameterizing
the intersection of two arbitrary quadrics, given in implicit form, with
integer coefficients. This implementation is based on the parameterization
method described in
- Near-Optimal Parameterization of the Intersection of
Quadrics. Proc. 19th ACM Symp. on Comput. Geom.,
pp. 246--255, 2003.
- Near-Optimal
Parameterization of the Intersection of Quadrics: I. The Generic Algorithm,
Journal of Symbolic Computation, 43(3):168--191 2008. (Research
report.)
-
Near-Optimal Parameterization of
the Intersection of Quadrics: II. A Classification of Pencils, Journal of Symbolic
Computation 43(3):192--215, 2008. (Research
report.)
- Near-Optimal
Parameterization of
the Intersection of Quadrics: III. Parameterizing Singular Intersections, Journal of Symbolic
Computation 43(3):216--232, 2008. (Research
report.)
- Intersecting
Quadrics: An Efficient and Exact Implementation,
Computational
Geometry: Theory and Applications, 35(1-2):74--99, 2006 (special issue of SoCG'04). (Research
report.)
QI has the following features:
- it computes an exact parameterization of the intersection of two
quadrics with integer coefficients of arbitrary size;
- it correctly identifies, separates and parameterizes all the
connected components of the intersection and gives all the relevant
topological information;
- the parameterization is rational when one exists; otherwise the
intersection is a smooth quartic and the parameterization involves the
square root of a polynomial;
- the parameterization is either optimal in the degree of the extension
of the integers on which its coefficients are defined or, in a small
number of well-identified cases, involves one extra possibly unnecessary
square root;
- it is fast and efficient and can routinely compute parameterizations of
the intersection of quadrics with input coefficients having ten digits in
less than 50 milliseconds on a mainstream PC.
Who uses QI?
We have had feedback from people using QI in the following contexts:
- Interactions between potential energy surfaces in photochemistry
(Department of Chemistry, Imperial College, London).
- Intersections in a thermal tool for spacecraft thermal radiation
analysis.
- Image of conics seen by a catadioptric camera with a paraboloidal mirror
(Institut de Recherche en Informatique de Toulouse).
What is the status of QI?
QI is free for non-commercial use. Please read the accompanying license for details. Use of this software in
published work should be acknowledged. Also, we would be pleased to hear
whatever use you have of the code.
Additionally, the implementation used by QI of Uspensky's algorithm for
isolating the real roots of a univariate polynomial (written by members of the
Spaces and Vegas teams) is released under the terms of the GNU Lesser General
Public License. You can get it here (with the
accompanying template Makefile).
How do I get QI?
Go to the download page and read on.
Can I quickly give it a try?
Yes. We have set up an online intersection server where
you can see for yourself what QI does without going through the compilation
process. You can then decide whether you want to get the source and have a
local installation.
What is the version history?
The first official version was released on June 2nd, 2004.
The latest version is 0.9.0, released on January 9th, 2007.
Comments? Suggestions? Bugs?
For any question, please mail to:
