Near-Optimal Parameterization of the Intersection of Quadrics: I. The Generic Algorithm

Laurent Dupont 1 Daniel Lazard 2 Sylvain Lazard 1 Sylvain Petitjean 1
1 VEGAS - Effective Geometric Algorithms for Surfaces and Visibility
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We present the first efficient algorithm for computing an exact parametric representation of the intersection of two quadrics in three-dimensional real space given by implicit equations with rational coefficients. The output functions parameterizing the intersection are rational functions whenever it is possible, which is the case when the intersection is not a smooth quartic (for example, a singular quartic, a cubic and a line, or two conics). Furthermore, the parameterization is near-optimal in the sense that the number of square roots appearing in the coefficients of these functions is minimal except in a small number of cases where there may be an extra square root. In addition, the algorithm is practical: a complete, robust and efficient C++ implementation is described in Part IV [12] of this paper. In Part I, we present an algorithm for computing a parameterization of the intersection of two arbitrary quadrics which we prove to be near-optimal in the generic, smooth quartic, case. Parts II and III [4, 5] treat the singular cases. We present in Part II the first classification of pencils of quadrics according to the real type of the intersection and we show how this classification can be used to efficiently determine the type of the real part of the intersection of two arbitrary quadrics. This classification is at the core of the design of our algorithms for computing near-optimal parameterizations of the real part of the intersection in all singular cases. We present these algorithms in Part III and give examples covering all the possible situations in terms of both the real type of intersection and the number and depth of square roots appearing in the coefficients.
Type de document :
Rapport
[Research Report] RR-5667, INRIA. 2005
Liste complète des métadonnées

Littérature citée [37 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00071229
Contributeur : Rapport de Recherche Inria <>
Soumis le : mardi 23 mai 2006 - 14:44:16
Dernière modification le : jeudi 11 janvier 2018 - 06:20:14
Document(s) archivé(s) le : dimanche 4 avril 2010 - 22:02:39

Fichiers

Identifiants

  • HAL Id : inria-00071229, version 1

Collections

Citation

Laurent Dupont, Daniel Lazard, Sylvain Lazard, Sylvain Petitjean. Near-Optimal Parameterization of the Intersection of Quadrics: I. The Generic Algorithm. [Research Report] RR-5667, INRIA. 2005. 〈inria-00071229〉

Partager

Métriques

Consultations de la notice

393

Téléchargements de fichiers

227