Partenaires


Rechercher

Sur ce site

Sur le Web du CNRS


Accueil du site > Structuration Scientifique > Informatique > Image > Axe Modélisation Géométrique et Synthèse d’Images > Projet thématique ROBUSTESSE DES CALCULS GEOMETRIQUES et CONTRAINTES GEOMETRIQUES (acronyme GéoCon)

Projet thématique ROBUSTESSE DES CALCULS GEOMETRIQUES et CONTRAINTES GEOMETRIQUES (acronyme GéoCon)

L’imprécision numérique de l’arithmétique flottante fait échouer les algorithmes de la géométrie algorithmique ; l’idée est d’épaissir les courbes et surfaces par des tolérances, et d’éviter les cas géométriques ambigus ; après cette perturbation, soit deux objets se coupent, soit ils sont disjoints. Ce paradigme soulève des questions passionnantes, à l’interface de l’arithmétique et de la géométrie, pour la recherche. Répondre à ces questions permettrait par exemple d’expliciter et de formaliser les tolérances utilisées par tous les modeleurs géométriques, de garantir par des preuves formelles (en COQ) la cohérence des modèles géométriques approchés, d’assurer l’inter-opérabilité des modeleurs géométriques.

L’analyse par intervalles est aussi utilisée pour résoudre les contraintes géométriques, pour calculer des couvertures de courbes ou surfaces algébriques implicites, pour suivre des courbes (pour la résolution par homotopie, notamment) de façon fiable. Une thématique émerge : comparaison de diverses arithmétiques, par exemple par intervalles et affine, dans des problèmes divers de modélisation géométrique : opérations booléennes, intersections entre surfaces, résolution de contraintes géométriques.

Tous les modeleurs géométriques de la CFAO (conception et fabrication assistée par ordinateur) fournissent aujourd’hui la possibilité de spécifier la géométrie par un ensemble de contraintes géométriques entre éléments géométriques. Un solveur décompose ensuite le système des contraintes en sous-systèmes irréductibles, puis résout chacun des sous-systèmes, et finalement assemble les solutions.

Les bases tensorielles de Bernstein sont utilisées dans certains solveurs de type Newton par intervalles. Malheureusement, cette base a une cardinalité exponentielle et devient donc inutilisable pour des systèmes de plus de 6 ou 7 inconnues. En recourant à la programmation linéaire, il est possible d’étendre le solveur à un nombre quelconque d’inconnues et d’équations. De plus le solveur prend aussi en compte des équations transcendantes, et des inéquations, algébriques ou transcendantes. Il est programmable sur GPU. Une thèse va commencer sur ce sujet en Septembre 2010 (D Michelucci, L Garnier).

Chercheurs et enseignants-chercheurs permanents :


LE2I - Laboratoire Electronique, Informatique et Image | webmestre : Antoine Trapet | info légales | logo SPIP 2