GENEPI Equipe associée Géométrica - Université Polytechnique de Brooklyn (proposition au format pdf)

PROGRAMME DE TRAVAIL

Le travail envisagé consiste en l'étude et le développement d'algorithmes génériques et robustes pour la manipulation d'objets géométriques, en particulier les objets courbes, ainsi que le développement des interfaces des structures de données (graphes) supportant les objets géométriques. Nous développons ces points.

 Programmation générique et noyau géométrique.

La programmation générique est une méthodologie dans laquelle des concepts sont utilisés par des algorithmes via un mécanisme générique (templates en C++). Elle permet de séparer la spécification de la fonctionalité, de l'implémentation concrète (modèle). Les algorithmes sont paramétrés par un concept dont un modèle est fourni lors de l'instantiation. Cela permet de comparer plusieurs modèles d'un même concept (expérimentation) ou bien de substituer ces modèles pour des situations différentes (par ex. modèle protégé plus lent avec validation, ou bien modèle ``de course'' quand on sait que le calcul ne posera pas de problèmes de robustesse). Cette approche a rencontré ailleurs du succès, par exemple avec la C++ Standard Template Library.

En mettant l'accent sur les concepts, nous proposons d'étudier les primitives sous-jacentes au calcul géométrique, les différents niveaux d'opération requis (s'agit-il d'un calcul affine, ou bien métrique? quelle fonctionalité minimale est requise par cet algorithme?). CGAL offre une implémentation de référence mais ne distingue pas les différents concepts de noyaux utilisés. Nous proposons d'établir une sorte de dictionnaire (avec une sémantique et une syntaxe, éventuellement dans plusieurs langages de programmation) pour les différents noyaux géométriques, de façon à ce que les algorithmes puissent être développés comme des "Graphics Gems'' susceptibles d'être distribués indépendemment ou facilement intégrés à CGAL. À long terme, cela devrait mener au développement d'une interface standard (dont CGAL serait la preuve de faisabilité centrale) pour la programmation géométrique. Des efforts similaires ont été réalisés avec beaucoup de succès dans le domaine de l'algèbre linéaire (BLAS niveaux 1, 2 et 3) et ont conduit à plusieurs implémentations qui offrent chacune des avantages spécifiques. Idem avec les concepts de graphes (Boost Graph Library) dont les algorithmes peuvent opérer sur des graphes venant de bibliothèques distinctes (BGL, LEDA, Stanford GraphBase). Notre but est un développement similaire dans le domaine des algorithmes géométriques.

Dans un premier temps, les concepts de types de nombres (coordonnées) et de noyaux géométriques seront développés. Les noyaux existants (CGAL et autres) seront intégrés. Puis les algorithmes (existant et autres, par exemple ceux récemment proposés par les partenaires) pourront être (re)paramétrés. Les concepts ainsi établis, s'ils sont adoptés par la communauté, simplifieront aussi l'enseignement du calcul géométrique car ils pourront être utilisés comme véhicule de connaissances tout en fournissant un outil concret aux étudiants pour réaliser des projets pratiques. De plus, la littérature scientifique (articles, livres) utilisant ces concepts sera directement applicable et exprimée sans ambiguïté.

  Robustesse.

Nous proposons de continuer notre investigation de la robustesse des algorithmes, et en particulier du paradigme du calcul géométrique exact, dans lequel ce sont les décisions prises par l'algorithme au cours de son exécution qui sont certifiées exactes (même si elles sont basées sur un calcul inexact). C'est un cadre déjà bien inscrit dans la bibliothèque CGAL, qui comprend beaucoup d'objets géométriques linéaires et d'algorithmes sur ceux-ci, et plus récemment des objets courbes (cercles et arcs, coniques dans un certain degré).

En particulier, un objet qui retiendra notre attention lors de la première année est l'intégration des courbes de Bezier de degré borné (en pratique, les patches cubiques sont le plus utilisés) dans le paradigme du calcul exact. Ce cas est très important en pratique du fait de son utilisation dans le moteur Postscript/Acrobat et dans les bibliothèques d'affichage graphique (PDF, QT, Quartz, Specifications "Scalable Vector Graphics'' du W3C). Par ailleurs il étend le travail effectué par les partenaires sur les objets linéaires (déterminants) et courbes (arcs de cercles, coniques). Nous prévoyons de collaborer également avec Y.-J. Chiang sur les applications au graphique.

La technologie courante utilise le rendu en résolution fixe (pour impression sur imprimante ou rendu écran), mais le zoom et les situations critiques (proches de singularité) peuvent produire des artifacts incorrects lors du rendu. Il serait désirable d'avoir un moteur de calcul exact et efficace. Pour cela, deux directions de recherche:
1. le calcul exact: déterminer les prédicats et les constructions géométriques utilisés et en fournir une version générique, paramétrée par un type de nombre (qui peut être exact mais inefficace),
2. le calcul filtré: une fois ces prédicats determinés, il faut pour les mettre en oeuvre de façon efficace qu'ils ne soient appelés que lorsque le calcul flottant ne suffit pas à résoudre les incertitudes. Le développement de filtres arithmétiques utilisant des outils tels que le calcul par intervalle, la multi-précission adaptative, etc. fera du calcul exact une alternative fiable et acceptable (pas de perte de performance notable).

  Structures de données.

Nous proposons également d'étendre le travail de généralisation de l'interface des structures de données de type Halfedge Data Structure effectué par H. Brönnimann, au cas des triangulations qui sont omni-présentes dans les travaux de GEOMETRICA (et bien sûr dans CGAL), ainsi qu'à d'autres graphes permettant de représenter des diagrammes de Voronoï et des arrangements d'objets courbes (2D et 3D).

Ce travail permettra de découpler davantage (i.e. rendre plus facilement ré-utilisable) les algorithmes géométriques des structures combinatoires (graphes) sur lesquels ils opèrents. Ce dernier point est en connection directe avec les travaux effectués dans la Boost Graph Library mentionnée plus haut. Nous pourrons collaborer également avec J. Iacono sur les aspects d'efficacité de ces structures de données.