Géométrie discrète

Discussion autour de bibliothèques et de codes sur la géométrie discrète

Objectifs généraux

L'objectif est de fournir un noyau stable pour développer des applications utilisant des techniques de géométrie discrète. Autour de ce noyau, un certain nombre de petits applicatifs pourra être proposé. De même, la création de certains plug-in pour des plateformes classiques sera envisagé. Un tel effort collectif de la communauté vise à répondre aux enjeux suivants :

• faciliter le développement de nouveaux algorithmes/outils en géométrie discrète ;
• faciliter la communication de résultats concrets à la communauté, permettre par exemple des comparisons précisions/robustesse/temps de calcul entre différentes approches ;
• mieux diffuser les travaux de géométrie discrète dans d'autres communautés, notamment le traitement et l'analyse d'image, la reconnaissance des formes, la géométrie algorithmique
• accélérer la formation des nouveaux arrivants en géométrie discrète, faciliter le démarrage des thèses, accroître le développement de la communauté

Wishlist scientifique

Ce que doit pouvoir fournir la lib (attention c'est en vrac)

• Définition d'images nD
• I/O sur les images 2D et 3D (--> VKT/ITK ?)

• Modélisation de la surface d'un objet
• Modélisation d'une partition en objets (--> Carte combi ?)

• Itérateurs/Circulateurs
  • Sur le volume (ligne, colonne, coupe isothetique,...)
  • Sur une région (les voxels de la région)
  • Sur les régions (--> carte combi + arbre d'inclusion ?)
  • Sur la surface d'une région (border tracking, support géodésique autour d'un surfel,...)

• Noyau arithmétique (pgcd,...) ( --> passerelle BOOST ?)
• Noyau algèbre linéaire ( --> passerelle BOOST ?)
• Noyau GeoAlgo ( --> passerelle CGAL ??)

Wishlist technique

• Langage, systèmes
  • Langage choisi : C++ ?
  • Systèmes : Linux, MacOS, Windows ?

• Noyau(x) commun(s)

  Contenu du ou des noyaux, dépendance par rapport à d'autres bibliothèques

• Packages

• Plugs-in

• Ponts avec d'autres bibliothèque (non GeoDis) au niveau structure de données.
  • Rendus possibles et faciles à mettre en place ? C'est un minimum. Un utilisateur peut être contraint pour une raison X ou Y de combiner l'utilisation du noyau avec une autre bibliothèque, au niveau structure de données au moins.
  • Offrir d'emblée un certain nombre de ponts ?
  • Oui, notamment ponts pour faciliter le développement de plugs-in (ex Paraview), importer/exporter de CGAL ou de bibliothèques image

Bibliothèques/Outils existants

• Bibliothèques "image"
  • VIGRA (Ullrich Köthe)
  • ITK (opensource, kitware) : bibliothèque de manipulation/transfo d'images (très orientée image médicale)
    • + Compatible VTK
    • + implementation C++ mais des wrappers python/java/tcl existent
    • + Format d'images générique, itérateurs,...
  • CImg (D. Tschumperlé, GREYC) : Bibliothèque C++ avec type de pixel générique.
    • Orientée traitement d'image
    • (Plus de détails à venir... réunion !)
    • + Images jusqu'à la 4D
    • + Orientée "code concis". Nombreux a
• Visualisation
  • VTK (opensource, kitware)
  • Paraview (opensource, kitware) : outils de visualisation de données scientifiques basées sur les pipeline VTK
    • + Interface très bien pensée
    • + Système de plugin basé sur les classes VTK très simple
    • + Tous les filtres VTK sont utilisables dans Paraview
    • + Gestion utlra-simple de cluster de calcul de rendu via MPI
  • QVox (Seb Fourey) : interface de visualistion/manipulation d'objets discrets
    • + Très efficace même sur de gros volumes
    • + mécanisme de plugin 'ligne de commande + interface automatique' très utile
    • + Englobe une bibliothèque générique (+/- ?) de manipulation de volumes jusqu'à 4D.
    • - ne permet pas de visualiser d'autres types d'objets (maillages,...)
• Géométrie/topologie discrète
  • ImaGene (J.-O. Lachaud) : bibliothèque de représentation des sous-ensembles de la grille discrète: objets, surfaces discrètes, ensembles de cellules, contours, etc.
    • + une bonne partie des outils, algorithmes, structures de données sont écrits en dimension quelconque, e.g. suivi de surface nD, estimateurs discrets nD, export en surface triangulée
    • + la géométrie discrète 2D arithmétique est assez complète (couverture tangentielle, tangentes, courbures) et assez générique
    • + pas mal d'outils de type ligne de commande pour traiter les images binaires 2D, contours, analyser/afficher les segments max, avec exportation sous Xfig
    • - la visu 3D est externe (ImaGeneUtils), utilise Coin/OpenInventor et est non-interactive
    • - manque des I/O nD (seul le cas 2D est bien traité)
    • - documentation en ligne essentiellement, peu de doc utilisateur
  • Simplevol : bibliothèque KISS (Keep it Simple & Stupid) de definition/manipulation d'images discrètes (profondeur : uchar)
• Gestion projet/compilation/...
  • cmake langage de description d'un projet pour une compilation multi-plateforme (Makefile sous linux, Visual Project, KDevelop, Xcode...)

Méthodologie

• groupe de travail réduit couvrant les différents champs de la géométrie discrète
• discussion et préparation par interaction sur wiki, mail, téléphone, rencontre
  • mise en valeur des qualités et défauts des codes existants
  • se mettre d'accord sur les objectifs, sur l'architecture générale et le découpage
  • identifier les tâches prioritaires, les intérêts communs, les cibler et attribuer des responsables
  • identifier les codes qui doivent servir de base de travail
  • prévoir le programme des journées prévues
• 3 jours de rencontre/travail en continu fin août/début septembre 2008
  • ...