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 ?)
  • Ne pas se limiter à 2/3 formats semble indispensable pour atteindre l'objectif de diffusion des outils GeoDis comme celui de démarrage des thèses. Sans tomber dans l'extrème des formats exotiques, mieux vaut prévoir large. Liste à compléter spécifique sur ce point ?
  • Si on branche avec un truc comme VTK/ITK, on aura l'avantage de pas avoir à faire ça : ces bibliothèques ont déjà tous les loaders possibles--Dcoeurjo 17 juin 2009 à 14:38 (CEST)

• 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 ??)

• Noyau Géométrique
  • objets : point, droite discrète, plan, cercles, polynomes, coniques, simplexes en dims sup
  • Intersection objects
  • Reconnaissance
  • Reconstruction géométrique

• Algorithmes topo discrète
  • suivi de surface (ouvert/fermé), suivi de bord
  • test de connexité, découpage en composantes connexes, étiquetage en composante connexe
  • points simples binaires, points simples multilabels
  • amincissement, squeletisation
  • complexes cubiques, effondrements

• Algorithmes géo discrète
  • extraction segments maximaux, couverture tangentielle, en temps optimal
  • extraction segments flous maximaux, ..., en temps optimal
  • algorithmes basés préimage : extraction de droites, plans discrets
  • transformées en distance (chanfrein ou autres), extraction d'axe médian
  • algorithmes de polygonalisation, polyédrisation
  • estimateurs géométriques
  • convexité discrète

Ce qu'il pourrait y avoir autour (dans le cadre de plug-in ?):

• visualisation 2D/3D d'objets discrets. Visualiser des données associées à chaque cellule. Interaction ?
• synthèse d'objets discrets
• outil de visu et d'analyse de primitives discretes
• plugins de calcul d'estimateurs discrets pour l'analyse quantitative

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
    • +/- (à discuter) Non-séparation des structures et des algorithmes.
      • Tous les algos liés à la lib sont des méthode
      • L'extension est possible grâce à un système de plug-ins
    • + Images jusqu'à la 4D
    • + Orientée "code concis"
• 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
    • - ne permet pas de visualiser d'autres types d'objets (maillages,...)
    • Englobe une bibliothèque générique (+/- ?) de manipulation de volumes jusqu'à 4D.
• 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)
  • MAEVA Toolkit (david) : bibliothèque d'analyse volumique d'objets discrets 3D (DT, REDT, Axe médian, Power diagram,...)
    • + Assez efficace (multi-thread)
    • - 3d uniquement
• 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
  • ...