Texte remanié de: Thèse de doctorat--Mathématiques--Université de Paris-Sud, 2005. Titre de soutenance : Principe de Hasse pour les surfaces de Del Pezzo de degré 4. / Mention parallèle de titre ou de responsabilité : Intersections of two quadrics and pencils of curves of genus 1. Introduction en anglais et en français. Bibliogr. p. 209-213.

Cette thèse présente un ensemble de travaux en géométrie algorithmique non linéaire portant d'une<br />part sur le développement d'algorithmes géométriques certifiés et efficaces traitant d'objets courbes et, en particulier, de quadriques et, d'autre part, sur les propriétés des droites de l'espace dans un contexte de visibilité tridimensionnelle.<br /><br />Ma réalisation principale concernant les quadriques est le développement du premier algorithme exacte, complet, quasi optimal et efficace pour calculer une paramétrisation de l'intersection de deux quadriques en trois dimensions. Cette contribution est une avancée très importante sur un problème ancien et c'est la première solution complète et certifiée à l'un des problèmes les plus élémentaires de modélisation par surfaces courbes implicites. Je présente également un très joli résultat sur les diagrammes de Voronoï de trois droites qui sont des partitions de l'espace en cellules bornées par des morceaux de quadriques. Nous montrons que la topologie de tels diagrammes est invariante pour des droites en positions générales et nous obtenons une propriété de monotonie sur les arcs des diagrammes. Nous en déduisons un algorithme simple pour ordonner des points le long de ces arcs, ce qui est vraisemblablement une avancée substantielle pour le développement futur d'algorithmes efficaces pour calculer l'axe médian de polyèdres. La technique de preuve, qui utilise fortement les outils modernes de calcul formel, est également intéressante en elle même.<br /><br />Concernant les propriétés des droites de l'espace dans un contexte de visibilité tridimensionnelle, je présente un ensemble de résultats cohérents sur différentes problématiques. En premier lieu, je présente des résultats sur les propriétés structurelles des droites tangentes ou transversales à quatre primitives. Précisément, je présente une caractérisation des configurations dégénérées de quatre sphères qui admettent un nombre infini de tangentes communes, une caractérisation de l'ensemble des droites transversales à quatre segments, et une étude du nombre maximum de tangentes à quatre triangles. Je présente ensuite plusieurs résultats sur les propriétés combinatoires de structures géométriques de visibilité tridimensionnelle. En particulier, je présente plusieurs résultats importants sur la complexité des silhouettes de polyèdres depuis un point de vu aléatoire et sur la complexité en moyenne et dans le cas le pire du complexe de visibilité, une structure de données encodant des informations de visibilité. Je présente également de nouvelles bornes étonnantes sur la complexité dans le cas le pire de l'ombre portée sur un plan par une source lumineuse polygonale en présence d'obstacles polyédriques convexes. En dernier lieu, je présente le premier algorithme non trivial et implantable pour calculer l'ensemble des segments tangents à quatre parmi $k$ polyèdres convexes non nécessairement disjoints, c'est-à-dire, essentiellement les sommets du complexe de visibilité.

L'algèbre géométrique est un outil permettant de représenter et manipuler les objets géométriques de manière générique, efficace et intuitive. A titre d'exemple, l'Algèbre Géométrique Conforme (CGA), permet de représenter des cercles, des sphères, des plans et des droites comme des objets algébriques. Les intersections entre ces objets sont incluses dans la même algèbre. Il est possible d'exprimer et de traiter des objets géométriques plus complexes comme des coniques, des surfaces quadriques en utilisant une extension de CGA. Cependant due à leur représentation requérant un espace vectoriel de haute dimension, les implantations de l'algèbre géométrique, actuellement disponible, n'autorisent pas une utilisation efficace de ces objets. Dans ce manuscrit, nous présentons tout d'abord une implantation de l'algèbre géométrique dédiée aux espaces vectoriels aussi bien basses que hautes dimensions. L'approche suivie est basée sur une solution hybride de code pré-calculé en vue d'une exécution rapide pour des espaces vectoriels de basses dimensions, ce qui est similaire aux approches de l'état de l'art. Pour des espaces vectoriels de haute dimension, nous proposons des méthodes de calculs ne nécessitant que peu de mémoire. Pour ces espaces, nous introduisons un formalisme récursif et prouvons que les algorithmes associés sont efficaces en termes de complexité de calcul et complexité de mémoire. Par ailleurs, des règles sont définies pour sélectionner la méthode la plus appropriée. Ces règles sont basées sur la dimension de l'espace vectoriel considéré. Nous montrons que l'implantation obtenue est bien adaptée pour les espaces vectoriels de hautes dimensions (espace vectoriel de dimension 15) et ceux de basses dimensions. La dernière partie est dédiée à une représentation efficace des surfaces quadriques en utilisant l'algèbre géométrique. Nous étudions un nouveau modèle en algèbre géométrique de l'espace vectoriel $mathbb{R}^{9,6}$ pour manipuler les surfaces quadriques. Dans ce modèle, une surface quadrique est construite par l'intermédiaire de neuf points. Nous montrerons que ce modèle permet non seulement de représenter de manière intuitive des surfaces quadriques mais aussi de construire des objets en utilisant les définitions de CGA. Nous présentons le calcul de l'intersection de surfaces quadriques, du vecteur normal, du plan tangent à une surface en un point de cette surface. Enfin, un modèle complet de traitement des surfaces quadriques est détaillé / Geometric Algebra is considered as a very intuitive tool to deal with geometric problems and it appears to be increasingly efficient and useful to deal with computer graphics problems. The Conformal Geometric Algebra includes circles, spheres, planes and lines as algebraic objects, and intersections between these objects are also algebraic objects. More complex objects such as conics, quadric surfaces can also be expressed and be manipulated using an extension of the conformal Geometric Algebra. However due to the high dimension of their representations in Geometric Algebra, implementations of Geometric Algebra that are currently available do not allow efficient realizations of these objects. In this thesis, we first present a Geometric Algebra implementation dedicated for both low and high dimensions. The proposed method is a hybrid solution that includes precomputed code with fast execution for low dimensional vector space, which is somehow equivalent to the state of the art method. For high dimensional vector spaces, we propose runtime computations with low memory requirement. For these high dimensional vector spaces, we introduce new recursive scheme and we prove that associated algorithms are efficient both in terms of computationnal and memory complexity. Furthermore, some rules are defined to select the most appropriate choice, according to the dimension of the algebra and the type of multivectors involved in the product. We will show that the resulting implementation is well suited for high dimensional spaces (e.g. algebra of dimension 15) as well as for lower dimensional spaces. The next part presents an efficient representation of quadric surfaces using Geometric Algebra. We define a novel Geometric Algebra framework, the Geometric Algebra of $mathbb{R}^{9,6}$ to deal with quadric surfaces where an arbitrary quadric surface is constructed by merely the outer product of nine points. We show that the proposed framework enables us not only to intuitively represent quadric surfaces but also to construct objects using Conformal Geometric Algebra. In the proposed framework, the computation of the intersection of quadric surfaces, the normal vector, and the tangent plane of a quadric surface are provided. Finally, a computational framework of the quadric surfaces will be presented with the main operations required in computer graphics

Le monde physique dans lequel nous vivons est essentiellement géométrique. Le calcul géométrique est une brique centrale de nombreux domaines, comme la conception assistée par ordinateur, le graphisme, la robotique, la vision artificielle et bien d'autres. Depuis plus de trois décennies, la géométrie algorithmique est la discipline dédiée à l'établissement de bases solides pour l'étude des algorithmes géométriques qui relèvent de ces applications. Elle s'est historiquement et traditionnellement concentrée sur le traitement d'objets linéaires. Pour de nombreuses applications, il est nécessaire de manipuler des objets généraux comme des courbes et des surfaces complexes. L'extension du répertoire de la géométrie algorithmique aux objets courbes pose de nombreuses difficultés: refonte des structures de données et algorithmes fondamentaux; irruption massive de questions algébriques; explosion du nombre de cas dégénérés...<br /><br />Cette thèse d'habilitation contribue à l'établissement d'un calcul géométrique effectif pour les objets courbes de faible degré. Elle reprend mes principales contributions sur le sujet ces dernières années. Mentionnons notamment: un algorithme exact, optimal et efficace pour le calcul du paramétrage de l'intersection de deux quadriques à coefficients entiers; la caractérisation des positions relatives de deux coniques projectives à l'aide de prédicats géométriques de faible degré, mis au jour grâce à la théorie des invariants algébriques; la caractérisation des dégénérescences du problème de tangentes réelles communes à quatre sphères; la convexité du cône des directions de droites perçant trois boules disjointes, et les conséquences importantes de ce résultat en théorie de transversales géométriques. Le manuscrit se conclue par un panel de directions de recherche poursuivant et étendant les résultats obtenus à ce jour.

Les plantes sont des éléments essentiels du monde qui nous entoure. Ainsi, si l’on veut créer des environnements virtuels qui soient à la fois agréables et réalistes, un effort doit être fait pour modéliser les plantes. Malgré les immenses progrès en vision par ordinateur pour reconstruire des objets de plus en plus compliqués, les plantes restent difficiles à reconstruire à cause de la complexité de leur topologie. Cette thèse se divise en deux grandes parties. La première partie s’intéresse à la modélisation de plantes, biologiquement réalistes, à partir d’une seule image. Nous générons un modèle de plante respectant les contraintes biologiques de son espèce et tel que sa projection soit la plus fidèle possible à l’image. La première étape consiste à extraire de l’image le squelette de la plante. Dans la plupart de nos images, aucune branche n’est visible et les images peuvent être de qualité moyenne. Notre première contribution consiste en une méthode de squelettisation basée sur les champs de vecteurs. Le squelette est extrait suite à un partitionnement non déterministe du feuillage de l’image assurant son réalisme. Dans un deuxième temps, la plante est modélisée en 3D. Notre deuxième contribution est la création de modèles pour différents types de plantes, basée sur les L-systèmes. Puis, un processus d’analyse-par-synthèse permet de choisir le modèle 3D final : plusieurs propositions de squelette sont générées et un processus bayésien permet d’extraire le modèle maximisant le critère a posteriori. Le terme d’attache aux données (vraisemblance) mesure la similarité entre l’image et la reprojection du modèle, la probabilité a priori mesure le réalisme du modèle. Après avoir généré des modèles de plantes, des modèles de fruits doivent être créés. Ayant travaillé principalement sur les pieds de vigne, nous avons développé une méthode pour reconstruire une grappe de raisin à partir d’au moins deux vues. Chaque baie est assimilée à un ellipsoïde de révolution. La méthode obtenue peut être plus généralement adaptée à tout type de fruits assimilables à une quadrique de révolution. La seconde partie de cette thèse s’intéresse à la reconstruction de quadriques de révolution à partir d’une ou plusieurs vues. La reconstruction de quadriques et, en général, la reconstruction de surfaces 3D est un problème très ancien en vision par ordinateur qui a donné lieu à de nombreux travaux. Nous rappelons les notions nécessaires de géométrie projective des quadriques, et de vision par ordinateur puis, nous présentons un état de l’art sur les méthodes existantes sur la reconstruction de surfaces quadratiques. Nous détaillons un premier algorithme permettant de retrouver les images des foyers principaux d’une quadrique de révolution à partir d’une vue « calibrée », c’est-à-dire pour laquelle les paramètres intrinsèques de la caméra sont connus. Puis, nous détaillons comment utiliser ce résultat pour reconstruire, à partir d’un schéma de triangulation linéaire, tout type de quadriques de révolution à partir d’au moins deux vues. Enfin, nous montrons comment il est possible de retrouver la pose 3D d’une quadrique de révolution dont on connaît les paramètres à partir d’un seul contour occultant. Nous évaluons les performances de nos méthodes et montrons quelques applications possibles. / Plants are essential elements of our world. Thus, 3D plant models are necessary to create realistic virtual environments. Mature computer vision techniques allow the reconstruction of 3D objects from images. However, due to the complexity of the topology of plants, dedicated methods for generating 3D plant models must be devised. This thesis is divided into two parts. The first part focuses on the modeling of biologically realistic plants from a single image. We propose to generate a 3D model of a plant, using an analysis-by-synthesis method considering both a priori information of the plant species and a single image. First, a dedicated 2D skeletonisation algorithm generates possible branching structures from the foliage segmentation. Then, we built a 3D generative model based on a parametric model of branching systems taking into account botanical knowledge. The resulting skeleton follows the hierarchical organisation of natural branching structures. Varying parameter values of the generative model (main branching structure of the plant and foliage), we produce a series of candidate models. A Bayesian model optimizes a posterior criterion which is composed of a likelihood function which measures the similarity between the image and the reprojected 3D model and a prior probability measuring the realism of the model. After modeling plant models branching systems and foliage, we propose to model the fruits. As we mainly worked on vines, we propose a method for reconstructing a vine grape from at least two views. Each bay is considered to be an ellipsoid of revolution. The resulting method can be adapted to any type of fruits with a shape similar to a quadric of revolution. The second part of this thesis focuses on the reconstruction of quadrics of revolution from one or several views. Reconstruction of quadrics, and in general, 3D surface reconstruction is a very classical problem in computer vision. First, we recall the necessary background in projective geometry quadrics and computer vision and present existing methods for the reconstruction of quadrics or more generally quadratic surfaces. A first algorithm identifies the images of the principal foci of a quadric of revolution from a "calibrated" view (that is, the intrinsic parameters of the camera are given). Then we show how to use this result to reconstruct, from a linear triangulation scheme, any type of quadrics of revolution from at least two views. Finally, we show that we can derive the 3D pose of a given quadric of revolution from a single occluding contour. We evaluate the performance of our methods and show some possible applications.

Soient $X$ et $Y$ des variétés au dessus d’un corps $F$. Dans de nombreuses situations, il s’avère important de savoir si un cycle algébrique modulo équivalence rationnelle y sur Y, défini au dessus du corps des fonctions $F(X)$ de $X$, est en fait déjà défini au niveau du corps de base $F$. Dans cet essai, on traite de cette question, en faisant varier la variété $X$ parmi des variétés telles que des quadriques, des variétés projectives homogènes ou des espaces principaux homogènes. Dans chaque situation, on utilise des outils appropriés tels que les opérations de Steenrod, des résultats de décomposition motivique, ou certains invariants cohomologiques de groupes algébriques. / Let $X$ and $Y$ be some varieties over a field $F$. In many situations, it is important to know if an algebraic cycle modulo rational equivalence $y$ on $Y$ defined over the function field $F(X)$ of $X$ is actually defined over the base field $F$. In this dissertation, we study that matter, making the variety $X$ vary among varieties such as quadrics, projective homogeneous varieties or principal homogeneous spaces. In each situation, we use appropriate tools, such as Steenrod operations, motivic decomposition results or cohomological invariants of algebraic groups.

Cette thèse comporte deux parties. Dans la première partie on étudie le motif de Chow d’un fibré en quadriques de dimension relative impaire sur une surface. On montre que ce motif admet une décomposition qui fait intervenir le motif de Prym du revêtement double de la courbe discriminante. Dans la deuxième partie on s’intéresse à des fibrations lagrangiennes, obtenues comme jacobiennes intermédiaires relatives des familles de variétés de Fano de dimension trois contenant une surface K3 fixée, et à l’existence d’une compactification symplectique. Dans un cas particulier, on étudie une compactification partielle en utilisant des calculs avec le logiciel Macaulay2. / This thesis consists of two parts. In the first part we study the Chow motive of a quadric bundle of odd relative dimension over a surface. We show that this motive admits a decomposition which involves the Prym motive of the double covering of the discriminant curve.In the second part, we consider Lagrangian fibrations, obtained as relative intermediate Jacobians of families of Fano threefolds containing a fixed K3 surface, and the existence of a symplectic compactification. In a particular case, we study a partial compactification using calculations with the software system Macaulay2.