Intersecting quadrics: an efficient and exact implementation

ABSTRACT

We present the first complete, exact and efficient C++ implementation of a method for parameterizing the intersection of two implicit quadrics with integer coefficients of arbitrary size. It is based on the near-optimal algorithm recently introduced by Dupont et al., [2]. Unlike existing implementations, it correctly identifies and parameterizes all the connected components of the intersection in all cases, returning parameterizations with rational functions whenever such parameterizations exist. In addition, the coefficient fields of the parameterizations are either minimal or involve one possibly unneeded square root. We prove upper bounds on the size of the coefficients of the output parameterization and compare these bounds to observed values. We give other experimental results and present some examples.

REFERENCES

• 1: T. Bromwich. Quadratic Forms and Their Classification by Means of Invariant Factors. Cambridge Tracts in Mathematics and Mathematical Physics, 1906.
• 2: Laurent Dupont , Daniel Lazard , Sylvain Lazard , Sylvain Petitjean, Near-optimal parameterization of the intersection of quadrics, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA [doi>10.1145/777792.777830]
• 3: R. T. Farouki , C. Neff , M. A. O'Conner, Automatic parsing of degenerate quadric-surface intersections, ACM Transactions on Graphics (TOG), v.8 n.3, p.174-203, July 1989 [doi>10.1145/77055.77058]
• 4: GMP: The GNU MP Bignum Library. The Free Software Foundation. http://www.swox.com/gmp.
• 5: C.-K. Hung and D. Ierardi. Constructing convex hulls of quadratic surface patches. In Proceedings of 7th CCCG (Canadian Conference on Computational Geometry), Quebec, Canada, pages 255--260, 1995.
• 6: T. Lam. The Algebraic Theory of Quadratic Forms. W.A. Benjamin, Reading, MA, 1973.
• 7: Joshua Levin, A parametric algorithm for drawing pictures of solid objects composed of quadric surfaces, Communications of the ACM, v.19 n.10, p.555-563, Oct. 1976 [doi>10.1145/360349.360355]
• 8: LiDIA: A C++ Library for Computational Number Theory. Darmstadt University of Technology. http://www.informatik.tu-darmstadt.de/TI/LiDIA.
• 9: James R. Miller , Ronald N. Goldman, Geometric algorithms for detecting and calculating all conic sections in the intersection of any two natural quadric surfaces, Graphical Models and Image Processing, v.57 n.1, p.55-66, Jan. 1995 [doi>10.1006/gmip.1995.1006 ]
• 10: B. Mourrain, J.-P. Tecourt, and M. Teillaud. Predicates for the sweeping of an arrangement of quadrics in 3D. Technical Report ECG-TR-242205-01, Effective Computational Geometry for Curves and Surfaces (European project), 2003.
• 11: Fabrice Rouillier , Paul Zimmermann, Efficient isolation of polynomial's real roots, Journal of Computational and Applied Mathematics, v.162 n.1, p.33-50, 1 January 2004 [doi>10.1016/j.cam.2003.08.015]
• 12: R. Sarraga. Algebraic methods for intersections of quadric surfaces in GMSOLID. Computer Vision, Graphics, and Image Processing, 22:222--238, 1983.
• 13: Elmar Schömer , Nicola Wolpert, An exact and efficient approach for computing a cell in an arrangement of quadrics, Computational Geometry: Theory and Applications, v.33 n.1-2, p.65-97, January 2006 [doi>10.1016/j.comgeo.2004.02.007]
• 14: Ching-Kuang Shene , John K. Johnstone, On the lower degree intersections of two natural quadrics, ACM Transactions on Graphics (TOG), v.13 n.4, p.400-424, Oct. 1994 [doi>10.1145/195826.197316]
• 15: Surf : A Tool To Visualize Algebraic Curves and Surfaces. Stephan Endrass, Hans Huelf, Ruediger Oertel, Ralf Schmitt, Kai Schneider and Johannes Beigel. http://surf.sourceforge.net.
• 16: F. Uhlig. Simultaneous block diagonalization of two real symmetric matrices. Linear Algebra and Its Applications, 7:281--289, 1973.
• 17: Wenping Wang , Ronald Goldman , Changhe Tu, Enhancing Levin's method for computing quadric-surface intersections, Computer Aided Geometric Design, v.20 n.7, p.401-422, October 2003 [doi>10.1016/S0167-8396(03)00081-5]
• 18: Wenping Wang , Barry Joe , Ronald Goldman, Computing quadric surface intersections based on an analysis of plane cubic curves, Graphical Models, v.64 n.6, p.335-367, November 2002 [doi>10.1016/S1524-0703(02)00018-7]
• 19: I. Wilf and Y. Manor. Quadric-surface intersection curves: shape and structure. Computer-Aided Design, 25(10):633--643, 1993.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

General Terms:
Algorithms, Experimentation

Keywords:
C++ implementation, experimental analysis, intersection of quadrics