Article

Near-optimal parameterization of the intersection of quadrics

Authors:

Laurent Dupont,

Daniel Lazard,

Sylvain Lazard,

Sylvain PetitjeanAuthors Info & Claims

SCG '03: Proceedings of the nineteenth annual symposium on Computational geometry

Pages 246 - 255

https://doi.org/10.1145/777792.777830

Published: 08 June 2003 Publication History

Get Access

Abstract

In this paper, we present the first exact, robust and practical method for computing an explicit representation of the intersection of two arbitrary quadrics whose coefficients are rational. Combining results from the theory of quadratic forms, linear algebra and number theory, we show how to obtain parametric intersection curves that are near-optimal in the number and depth of radicals involved.

References

[1]

L. Alonso, F. Cuny, S. Petitjean, J.-C. Paul, S. Lazard, and E. Wies. The virtual mesh: A geometric abstraction for efficiently computing radiosity. ACM Transactions on Graphics, 20(3):169--201, 2001.

Digital Library

Google Scholar

[2]

M. Benouamer, D. Michelucci, and B. Peroche. Error-free boundary evaluation based on a lazy rational arithmetic: a detailed implementation. Computer-Aided Design, 26(6):403--416, 1994.

Crossref

Google Scholar

[3]

A. Bowyer, J. Berchtold, D. Eisenthal, I. Voiculescu, and K. Wise. Interval methods in geometric modeling. In Proc. of International Conference on Geometric Modeling and Processing, Hong Kong, 2000. Invited presentation.

Digital Library

Google Scholar

[4]

J. Cremona. Reduction of binary cubic and quartic forms. LMS Journal of Computation and Mathematics, 2:62--92, 1999.

Crossref

Google Scholar

[5]

J. Cremona and D. Rusin. Efficient solution of rational conics. Mathematics of Computation, posted on December 18, 2002 (to appear in print).

Digital Library

Google Scholar

[6]

L. Dupont, D. Lazard, S. Lazard, and S. Petitjean. Towards the robust intersection of implicit quadrics. In Proc. of Workshop on Uncertainty in Geometric Computations, 2001. Sheffield, UK.

Google Scholar

[7]

R. Farouki, C. Neff, and M. O'Connor. Automatic parsing of degenerate quadric-surface intersections. ACM Transactions on Graphics, 8(3):174--203, 1989.

Digital Library

Google Scholar

[8]

P. Finsler. Aber das Vorkommen definiter und semidefiniter Formen in Scharen quadratischer Formen. Comment. Math. Helv., 9:188--192, 1936/1937.

Crossref

Google Scholar

[9]

S. Fortune. Polyhedral modelling with exact arithmetic. In Proc. of ACM Symposium on Solid Modeling and Applications, pages 225--234, 1995.

Digital Library

Google Scholar

[10]

N. Geismann, M. Hemmer, and E. Schoemer. Computing the intersection of quadrics: exactly and actually. In Proc. of ACM Symposium on Computational Geometry, pages 264--273, 2001.

Digital Library

Google Scholar

[11]

R. Goldman and J. Miller. Combining algebraic rigor with geometric robustness for the detection and calculation of conic sections in the intersection of two natural quadric surfaces. In Proc. of ACM Symposium on Solid Modeling Foundations and CAD/CAM Applications, pages 221--231, 1991.

Digital Library

Google Scholar

[12]

J. Harris. Algebraic Geometry: A First Course. Graduate Texts in Mathematics. Springer Verlag, 1992.

Google Scholar

[13]

C. Hoffmann. Robustness in geometric computations. Journal of Computing and Information Science in Engineering, 1(2):143--156, 2001.

Crossref

Google Scholar

[14]

J. Keyser, T. Culver, M. Foskey, and S. Krishnan. ESOLID - A system for exact boundary evaluation. In Proc. of 7th ACM Symposium on Solid Modeling and Applications, pp. 23--34, 2002.

Digital Library

Google Scholar

[15]

J. Keyser, T. Culver, D. Manocha, and S. Krishnan. Efficient and exact manipulation of algebraic points and curves. Computer-Aided Design, 32(11):649--662, 2000. Special issue on robustness.

Crossref

Google Scholar

[16]

J. Keyser, S. Krishnan, and D. Manocha. Efficient and accurate B-Rep generation of low degree sculptured solids using exact arithmetic: I -- Representations, II -- Computation. Computer Aided Geometric Design, 16(9):841--859, 861--882, 1999.

Digital Library

Google Scholar

[17]

T. Lam. The Algebraic Theory of Quadratic Forms. W.A. Benjamin, Reading, MA, 1973.

Google Scholar

[18]

J. Levin. A parametric algorithm for drawing pictures of solid objects composed of quadric surfaces. Communications of the ACM, 19(10):555--563, 1976.

Digital Library

Google Scholar

[19]

J. Levin. Mathematical models for determining the intersections of quadric surfaces. Computer Graphics and Image Processing, 11(1):73--87, 1979.

Crossref

Google Scholar

[20]

J. Miller and R. Goldman. Geometric algorithms for detecting and calculating all conic sections in the intersection of any two natural quadric surfaces. Graphical Models and Image Processing, 57(1):55--66, 1995.

Digital Library

Google Scholar

[21]

MuPAD, the open computer algebra system, www.sciface.com.

Google Scholar

[22]

F. Rouillier and P. Zimmermann. Efficient isolation of a polynomial real roots. Journal of Computational and Applied Mathematics, 2002. To appear. Technical Report RR-4113, Inria, 2001.

Digital Library

Google Scholar

[23]

C.-K. Shene and J. Johnstone. On the lower degree intersections of two natural quadrics. ACM Transactions on Graphics, 13(4):400--424, 1994.

Digital Library

Google Scholar

[24]

K. Sugihara. How to make geometric algorithms robust. IEICE Transactions on Information and Systems, E83-D(3):447--454, 2000.

Google Scholar

[25]

F. Uhlig. Simultaneous block diagonalization of two real symmetric matrices. Linear Algebra and Its Applications, 7:281--289, 1973.

Crossref

Google Scholar

[26]

F. Uhlig. A canonical form for a pair of real symmetric matrices that generate a nonsingular pencil. Linear Algebra and Its Applications, 14:189--209, 1976.

Crossref

Google Scholar

[27]

I. Wilf and Y. Manor. Quadric-surface intersection curves: shape and structure. Computer-Aided Design, 25(10):633--643, 1993.

Crossref

Google Scholar

Cited By

View all

Fu GRiedel CHolmes TLiu J(2019)Geometric Modeling of the Z-Surface and Z-Curve of GNSS Signals and Their Solution TechniquesIEEE Transactions on Geoscience and Remote Sensing10.1109/TGRS.2018.285304657:1(212-223)Online publication date: Jan-2019
https://doi.org/10.1109/TGRS.2018.2853046
Kukelova ZHeller JFitzgibbon A(2016)Efficient Intersection of Three Quadrics and Applications in Computer Vision2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)10.1109/CVPR.2016.199(1799-1808)Online publication date: Jun-2016
https://doi.org/10.1109/CVPR.2016.199
Lind MYstgaard P(2014)Mesh-based tool path calculations for tubular jointsAdvances in Mechanical Engineering10.1177/168781402093338312:6Online publication date: 1-Jun-2014
https://doi.org/10.1177/1687814020933383
Show More Cited By

Index Terms

Near-optimal parameterization of the intersection of quadrics
1. Computing methodologies
  1. Computer graphics
    1. Shape modeling
      1. Point-based models
  2. Symbolic and algebraic manipulation
    1. Symbolic and algebraic algorithms
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Near-optimal parameterization of the intersection of quadrics: I. The generic algorithm

We present an exact and efficient algorithm for computing a proper parametric representation of the intersection of two quadrics in three-dimensional real space given by implicit equations with rational coefficients. The output functions parameterizing ...
Near-optimal parameterization of the intersection of quadrics: III. Parameterizing singular intersections

We conclude, in this third part, the presentation of an algorithm for computing an exact and proper parameterization of the intersection of two quadrics. The coordinate functions of the parameterizations in projective space are polynomial, whenever it ...
Planar intersection and blending of natural quadrics

Reviews

Reviewer: Joel Cohen

This interesting paper describes a new algorithm that finds an exact parametric representation for the intersection curve of two implicit quadric surfaces in 3, or the projective space, 3, when the surface polynomials have rational number coefficients. Since the approach involves exact arithmetic, the parametric representation of the intersection curve involves radicals in an extension field of , and an important practical consideration is a representation that is not unnecessarily complicated with nested radicals. The authors present a practical algorithm, which depending on the type of input quadrics, provides a representation of the intersection curve that is either optimal in the number and depth of the radicals, or in some cases, may contain one unnecessary radical. Their approach, which builds on the general pencil method of J. Levin, is based on the reduction of quadratic forms, and on new results on the intersection of quadrics. This paper presents the theoretical basis of the approach, and a detailed description of the algorithm. Although the algorithm is quite involved, it appears to be a significant improvement over previous approaches. An online implementation of the algorithm is available online at http://www.loria.fr/equipes/isa/quadrics.html. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SCG '03: Proceedings of the nineteenth annual symposium on Computational geometry

June 2003

398 pages

ISBN:1581136633

DOI:10.1145/777792

Conference Chair:
Steve Fortune
Bell Laboratories

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 08 June 2003

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SoCG03

Sponsor:

SoCG03: Annual ACM Symposium on Computational Geometry

June 8 - 10, 2003

California, San Diego, USA

Acceptance Rates

SCG '03 Paper Acceptance Rate 42 of 118 submissions, 36%;

Overall Acceptance Rate 625 of 1,685 submissions, 37%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
473
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 09 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Fu GRiedel CHolmes TLiu J(2019)Geometric Modeling of the Z-Surface and Z-Curve of GNSS Signals and Their Solution TechniquesIEEE Transactions on Geoscience and Remote Sensing10.1109/TGRS.2018.285304657:1(212-223)Online publication date: Jan-2019
https://doi.org/10.1109/TGRS.2018.2853046
Kukelova ZHeller JFitzgibbon A(2016)Efficient Intersection of Three Quadrics and Applications in Computer Vision2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)10.1109/CVPR.2016.199(1799-1808)Online publication date: Jun-2016
https://doi.org/10.1109/CVPR.2016.199
Lind MYstgaard P(2014)Mesh-based tool path calculations for tubular jointsAdvances in Mechanical Engineering10.1177/168781402093338312:6Online publication date: 1-Jun-2014
https://doi.org/10.1177/1687814020933383
Tu CWang WMourrain BWang J(2009)Using signature sequences to classify intersection curves of two quadricsComputer Aided Geometric Design10.1016/j.cagd.2008.08.00426:3(317-335)Online publication date: 1-Mar-2009
https://dl.acm.org/doi/10.1016/j.cagd.2008.08.004
Emiris ITsigaridas E(2008)Real algebraic numbers and polynomial systems of small degreeTheoretical Computer Science10.1016/j.tcs.2008.09.009409:2(186-199)Online publication date: 10-Dec-2008
https://dl.acm.org/doi/10.1016/j.tcs.2008.09.009
Dupont LLazard DLazard SPetitjean S(2008)Near-optimal parameterization of the intersection of quadricsJournal of Symbolic Computation10.1016/j.jsc.2007.10.00643:3(168-191)Online publication date: 1-Mar-2008
https://dl.acm.org/doi/10.1016/j.jsc.2007.10.006
Lazard SPeòaranda LPetitjean S(2006)Intersecting quadricsComputational Geometry: Theory and Applications10.5555/1646483.164658035:1-2(74-99)Online publication date: 1-Aug-2006
https://dl.acm.org/doi/10.5555/1646483.1646580
Lazard SPeñaranda LPetitjean S(2006)Intersecting quadrics: an efficient and exact implementationComputational Geometry10.1016/j.comgeo.2005.10.00435:1-2(74-99)Online publication date: Aug-2006
https://doi.org/10.1016/j.comgeo.2005.10.004
Chen XYong JZheng GPaul JSun J(2006)Computing minimum distance between two implicit algebraic surfacesComputer-Aided Design10.1016/j.cad.2006.04.01238:10(1053-1061)Online publication date: 1-Oct-2006
https://dl.acm.org/doi/10.1016/j.cad.2006.04.012
Goldman R(2006)Algebraic geometry and geometric modeling: insight and computationAlgebraic Geometry and Geometric Modeling10.1007/978-3-540-33275-6_1(1-22)Online publication date: 2006
https://doi.org/10.1007/978-3-540-33275-6_1
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Near-optimal parameterization of the intersection of quadrics: I. The generic algorithm

Near-optimal parameterization of the intersection of quadrics: III. Parameterizing singular intersections

Planar intersection and blending of natural quadrics

Reviews

Access critical reviews of Computing literature here