Modélisation et acquisitions
Ce thème fédère les activités de recherche de l'équipe autour de la création, de la représentation, et du traitement de modèles 3D complexes où un objectif est de relever deux défis scientifiques majeurs :
- faciliter la création d'objets 3D, notamment par numérisation ;
- produire des modèles d'objets efficaces au niveau de détail choisi.
La création de mondes virtuels 3D engendre des coûts de production qui croissent proportionnellement à la complexité des scènes et à la nécessité d’avoir recours à des équipes d’artistes producteurs de contenus. Des procédés technologiques de numérisation permettent de faciliter le travail de production de contenus dans certains cas, mais ils imposent souvent des contraintes très fortes et ne passent généralement pas à l’échelle.
Notre approche vise d'une part à développer des procédés permettant de faciliter la création d'objets 3D statiques ou dynamiques, avec ou sans informations d'apparence. Ces travaux portent sur l'usage de technologies de numérisation (photographies, scanners 3D et capteur de mouvement) combinées à des traitements spécifiques.
D'autre part, elle consiste à proposer et étudier de nouvelles structures combinatoires pour la représentation d'objets géométriques. Ces travaux englobent les variétés combinatoires et leurs extensions multi-résolutions ; la modélisation de complexes cellulaires ou simpliciaux ; l'encodage de topologies discrètes ; et la description d'algorithmes exploitant ces structures topologiques pour la reconstruction et la détection de collisions.
L'ensemble de ces travaux est mis à la disposition de la communauté scientifique et industrielle via le développement de deux plateformes : la plateforme de modélisation géométrique CGoGN, qui est une plateforme logicielle open source en LGPL, et une plateforme matérielle dédiée à la numérisation : ExRealis.
Participants permanents
- Deux professeurs: Dominique Bechmann et Jean-Michel Dischler
- Une chargée de recherche: Hyewon Seo
- Quatre maîtres de conférences: Rémi Allègre, David Cazier, Pierre Kraemer et Basile Sauvage
- Deux ingénieurs de recherche: Olivier Génevaux et Sylvain Thery
Autres participants
- 1 Collaborateur extérieur: Frédéric CORDIER (MC UHA Mulhouse, 09/2008-)
- 1 Ingénieur sur contrat: Cyril KERN (ANR VORTISS puis STREP PASSPORT 09/2007-05/2010)
- 4 Post-doctorants: Olivier GUILLOT (ATER, 09/2008-08/2009), Younis HIJAZI (STREP PASSPORT, 02/2009-12/2009), Thomas JUND (ATER, 10/2010-08/2011), Frédéric LARUE (Région Alsace, 12/2008-08/2009)
- 2 Doctorants: Lionel UNTEREINER (Ministère, 10/2010-), Kenneth VANHOEY (Ministère, 10/2010-)
- 6 Anciens doctorants: Dobrina BOLTCHEVA (Région Alsace-IRCAD, 10/2003-10/2007), Marc FOURNIER (Bourse du Canada, 10/2004-11/2008), Thomas JUND (Ministère, 10/2007-09/2010), Pierre KRAEMER (Ministère, 10/2005-11/2008), Frédéric LARUE (RIAM AMI3d, 10/2005-11/2008), Benjamin SCHWARZ (Contrat, 10/2004-08/2009).
Acquisition de modèles géométriques statiques et de leur apparence
Nous avons développé des procédés permettant d'automatiser et de simplifier la création de modèles numériques à partir de la réalité (scans et photographies).
Pour cela nous avons spécifié d'une part un nouveau protocole de numérisation basé sur le principe de la projection de franges (lumière structurée). Ce protocole s’inscrit dans une chaîne complète de traitements que nous avons développée et qui va de l’acquisition à la visualisation. Dans le cadre de cette chaîne de traitements, nous avons proposé des solutions novatrices en matière de recalage, de débruitage, d’intégration et de visualisation des surfaces numérisées 2-FDB07, 4-LAD07, 4-FDB06, 4-LD06. Cette activité a débouché sur la mise en place d’une plateforme technologique de numérisation au sein du laboratoire (équipement + logiciel) et un transfert de technologie vers le CRITT HOLO3.
D'autre part, nous avons conçu et développé des techniques permettant de faciliter la création et l'édition virtuelle de matériaux complexes, basés sur une représentation procédurale 2-GD09, 2-GD10. L’objectif consiste à permettre à des créateurs de contenu 3D de reproduire plus facilement l’existant par des manipulations interactives simples, tout en garantissant une certaine liberté artistique à l’opposé des techniques de numérisation par scanners, qui, à l'inverse, ne permettent que de produire une copie numérique à l’identique. Une partie de ces activités est soutenue par l'ANR ATROCO en collaboration avec l'EPI ARTIS (Grenoble) et le LIRIS (Lyon).
Acquisition et modélisation du mouvement
Les fabricants utilisent des données anthropométriques simples pour la conception des produits industriels. Ces méthodes ne sont ni assez précises ni adaptées que ce soit à la production de masse ou à la production industrielle personnalisée. Pour que les techniques de modélisation du corps humain puissent être utilisées pour l’industrie, il faut qu’elles puissent produire des données tridimensionnelles du corps humain fidèles à la réalité et qu’elles puissent être utilisées de façon interactive et automatique. Le développement de méthodes de modélisation du corps humain qui satisfont toutes ces propriétés est un travail difficile, même avec les logiciels actuels les plus sophistiqués.
Un des sujets les plus difficiles dans ce domaine de recherche est le développement d’une méthode robuste qui permet de calculer en temps réel et automatiquement des modèles du corps humains correspondant aux dimensions et contraintes définies par l’utilisateur/utilisatrice.
Forme et mouvement contrôlables paramétriquement
Avec les applications cibles considérées, le but principal de ce travail de recherche est de développer des méthodes pour créer les modèles de corps humains en temps réel en utilisant un ensemble de paramètres utilisateur. À ce jour, nombre de méthodologies de reconstruction 3D (scanner) sont disponibles pour capturer des formes existantes du monde réel. Une technique de modélisation du corps humain que nous avons développée consiste à utiliser ces formes réelles capturées à l’aide d’un scanner. Ces données provenant du scanner sont organisées de sorte à servir en entrée pour notre méthode d'interpolation de formes. Chaque maillage correspondant à un corps humain scanné est converti en un modèle transformable et qui peut être animé grâce à la conformation d'un modèle générique. En construisant des modèles d'apprentissage statistiques entre les paramètres de contrôle et la géométrie du corps humain, nous obtenons une méthode de modélisation du corps humain qui peut être modifiable à l’aide de paramètres et dont la forme est fidèle à la réalité.
Notre travail porte sur : (1) Le développement d'une méthode pour l'apprentissage précis de la variabilité des données, en particulier pour gérer des modalités multiples telles que l'identité morphologique du corps, les postures du corps ou la variabilité dynamique. Si nous disposons de données suffisamment importantes, notre modèle reproduira à la fois la variabilité de la forme statique (qui dépend de la morphologie de la personne) et la variabilité de la forme dynamique (qui dépend du mouvement du corps) de manière corrélée, permettant un intervalle continu d’interpolation. (2) L'extension du modèle de déformation paramétrique pour pouvoir interpoler les données de mouvements. Le but est de modéliser le mouvement souhaité par une interpolation entre plusieurs mouvements de personnes réelles enregistrée à l’aide d’un logiciel de capture de mouvements.
Recalage avec utilisation de données dynamiques
Le recalage, ou alignement optimal de deux formes arbitraires est un problème fondamental en acquisition de modèle et modélisation. Étant données deux formes, souvent appelées modèle et données, le but est de déterminer une transformation qui aligne de manière optimale le modèle avec les données. Ce processus est nécessaire pour être en mesure de comparer ou intégrer les données obtenues à partir de différentes mesures. Les données de mesure du corps humain, le sujet le plus fréquemment observé par les dispositifs d'imagerie, posent plusieurs difficultés techniques. Tout d’abord, le calcul de correspondance devient un problème complexe à résoudre. Il est assez évident que la différence entre les caractéristiques géométriques et également les formes peuvent être beaucoup trop grandes, du fait de la large variabilité inhérente de la forme du corps humain. Un deuxième problème provient du fait que les corps humains peuvent apparaître avec des postures différentes, ce qui change de manière radicale la question de leur arrangement spatial. Par rapport aux techniques existantes qui sont basées seulement sur les formes statiques, notre objectif est de développer de nouvelles méthodes qui utilisent à la fois les formes statiques et les données de mouvement. En particulier, nous pensons utiliser la redondance importante qui existe entre les données de formes statiques et les données de mouvements. Nous avons capturé les données de mouvement d'une personne et développé des outils qui permettent d'analyser ces mouvements pour en extraire les caractéristiques dynamiques 5-KCWK10, 5-COHK09.
Nous travaillons actuellement sur une nouvelle méthode qui utilise ces caractéristiques dynamiques afin de calculer la correspondance entre deux formes, de façon fiable. Ce travail s’inscrit dans le cadre du projet ANR SHARED (Shape Analysis and Registration of People using Dynamic Data).
Modèles combinatoires multirésolutions
La représentation multi-résolutions d'objets géométriques suscite un intérêt croissant dans de nombreux domaines de l'informatique graphique. Dans ce cadre, une surface n'est plus modélisée par un maillage unique, mais par une série de maillages imbriqués, constituant des niveaux de résolution différents, et par les règles permettant de passer de l'un à l'autre. La représentation est dite adaptative si la résolution maximale n'est pas la même partout. Les modèles multi-résolutions trouvent des applications en analyse multi-résolutions, pour le filtrage ou la compression de maillages, en transmission progressive et pour un affichage dépendant du point de vue.
Les surfaces de subdivision font partie des méthodes permettant de construire des surfaces multi-résolutions. Les modèles utilisés sont souvent des forêts de quadtrees dérivant naturellement des schémas de subdivision employés (quadrisection de faces). Ces structures sont limitées aux maillages triangulaires ou quadrangulaires et les requêtes d'adjacence y sont exécutées en O(log(n)) ce qui reste gênant pour les traitements géométriques usuels.
A contrario, les maillages très denses issus d'acquisition 3D peuvent avoir une connectivité irrégulière. Dans ce cadre, les maillages progressifs forment une hiérarchie naturelle obtenue grâce à des contractions de cellules. Ces modèles n'exploitent pas de structure multi-résolutions et doivent reconstruire les maillages à la volée, pour pouvoir appliquer les algorithmes précédemment cités.
Nous avons conçu et implantée une structure de données tout à fait originale, les cartes multi-résolutions ou MR-maps 2-KCB09. Elle se fonde sur la théorie des cartes combinatoires dont elle hérite la formalisation, la généralité et l'efficacité. Le modèle des MR-maps est également adaptatif c'est-à-dire qu'il permet un raffinement à une profondeur variable suivant les zones de l'objet modélisé. Suite à la définition des MR-maps, nous avons proposé un plongement de celles-ci sur des surfaces de subdivision 3-KCB07, 4-KCB07.
Nous avons montré que le coût mémoire des MR-maps était similaire aux quadtrees dans le cas général et adaptatif alors que l'efficacité des parcours des différents niveaux de résolution est grandement améliorée et reste en temps constant quelque soit le niveau de résolution utilisé.
Ce nouveau type de plongement, jamais proposé pour des cartes combinatoires, possède de nombreux avantages. Les MR-maps supportent un large éventail de schémas de subdivision : les schémas primaux (découpant les faces) ou duaux (éclatement de sommets), et même des schémas plus originaux et non encore utilisés en multi-résolutions comme le schéma <math>\scriptstyle \sqrt{3}</math> ou le schéma quad/triangle 4-KCB07b (mélangeant facettes triangulaires et rectangulaires).
Modèles combinatoires non variétés
La plupart des modèles usuels, comme les cartes, permettent de modéliser des variétés de dimension quelconque de manière très efficace. Cependant pour certaines applications, la possibilité de représenter des objets qui ne sont localement pas des variétés reste essentielle. Ces modèles offrent un domaine de représentation plus large, autorisent des sommets singuliers et conduisent à une représentation de complexes cellulaires permettant de combiner ensemble des objets aux dimensions variées, comme des courbes, des surfaces ou des solides.
Le modèle des arêtes radiales, introduit par Weiler en 1988, et les modèles dérivés sont toujours utilisés, bien que gourmands en mémoire et non optimaux pour les requêtes d'adjacence. Des modèles tétraédriques, plus restreints, sont souvent préférés en pratique car plus efficaces.
Un nouveau modèle a été développé par D. Cazier et P. Kraemer, qui permet de représenter des complexes cellulaires quelconques. Nous l’avons nommé le modèle des X-maps pour cartes étendues. Pour cela nous avons étendu les cartes combinatoires avec une nouvelle relation permettant de lier ses sommets autour de points singuliers. Les composantes connexes d'une X-map privée de cette relation forment une décomposition (non unique) des complexes modélisés en un ensemble de variétés (courbes, surfaces, volumes) accolées. Nous avons proposé, dans 4-CK10, une implémentation duale de ce modèle très compact (jusqu'à 4 fois moins coûteuse que les arêtes radiales). Ce modèle bénéficie de l'efficacité et de la généricité des cartes sur les portions correspondant à des variétés.
Détections des collisions
La recherche de collisions entre les primitives d'une scène dépend de manière quadratique du nombre de primitives présentes. L'accélération des calculs passe souvent par l'utilisation de hiérarchies de boites englobantes (AABB, OBB, k-DOP). Le but est de partitionner l'espace en cellules réduites dans lesquelles un nombre restreint de primitives se trouvent simultanément. Certains travaux utilisent une partition fixe de l'environnement qui se déforme avec la simulation (notamment pour la simulation d'endoscopies ou d'angioscopies). Aucun de ces travaux ne supporte de changements dans la topologie de la scène (découpe, suture, suppression de matière).
Nous avons proposé un nouveau système de détection de collisions, permettant de suivre les déplacements de maillages quelconques (particules, courbes ou surfaces) au sein de scènes complexes et déformables. L'environnement dans lequel les mobiles se déplacent est décomposé en polyèdres convexes et modélisé par une 3-carte. Nous obtenons ainsi une partition volumique de la scène qui s'adapte naturellement à ses propres déformations lors de la simulation et supporte un large éventail de transformations topologiques en temps réel.
Nous avons ensuite mis au point un mécanisme de prédiction permettant de suivre le déplacement de sommets dans l'environnement et exploitant la cohésion temporelle et spatiale de la simulation. Son efficacité est assurée par la structure combinatoire des 3-cartes et leur décomposition implicite en tétraèdres orientés optimisant le nombre de tests géométriques à effectuer 4-JCD09. Ce système supporte naturellement les déformations de l'environnement et des mobiles, et permet une gestion très efficace des changements topologiques grâce à des opérateurs locaux impliquant un nombre contrôlé de mises à jour.
Ces résultats ont été étendus au suivi d'arêtes des maillages en déplacement 4-JCD10, 4-JCD10b. Leurs mouvements sont décomposés en déplacements élémentaires formant des triangles qui balayent l'espace environnant. En utilisant des arguments géométriques sur la convexité de ces déplacements et des cellules parcourues, il est possible d'obtenir une information de collision ou de contact précise, avec peu de calculs supplémentaires. Nous avons ainsi pu expérimenter notre système avec deux types de simulations temps réel très contraignantes : l'insertion d'un cathéter dans un réseau vasculaire déformable et le déplacement de solides déformables dans un environnement lui-même déformable et dont la topologie change.
Voir la galerie vidéo pour des exemples de simulations.
Reconstruction de maillages à partir d'images médicales
Dans le cadre de la reconstruction géométrique des organes du corps humain à partir d'images médicales (scanner, IRM), nous nous sommes intéressés, en collaboration avec l'IRCAD, au passage d'images voxels segmentées vers des 2-variétés ou 3-variétés combinatoires (maillages surfaciques ou volumiques).
Un algorithme innovant 3-BBCK09, basé sur la notion de diagramme de Voronoï discret a été proposé. Il permet de générer un maillage qui reflète parfaitement la topologie des organes en terme d'adjacence (entre organes), d'inclusion (tumeurs) ou d'intersection (vaisseaux-organes). Dans le cadre du projet européen PASSPORT, cet algorithme a été développé dans sa version multi-organes et intégré aux logiciels de visualisation de données médicales de l'IRCAD. Ce travail se poursuit dans le cadre de l’IHU Mix-Surg.
Nous avons également proposé un algorithme levant le verrou majeur de la reconstruction des embranchements multiples dans les arborescences (corps humain ou autre). Dans les réseaux vasculaires, jusqu'à 7 embranchements peuvent se rejoindre.
La génération de maillages adaptés aux vaisseaux sanguins soulève de nombreuses difficultés aussi bien topologiques que géométriques.
Exploitant notre démarche historique de séparation de la topologie et de la forme, cet algorithme 4-HBCK10 utilise des techniques de géométrie algorithmique, en particulier l'enveloppe convexe, pour reconstruire simplement et automatiquement la topologie de tout type d'embranchements.
Perspectives
Acquisition et traitements de modèles volumineux très détaillés
Reconstruction de modèles à partir de sources de données multiples. Nous disposons aujourd'hui d'une chaîne de traitement performante permettant de numériser des objets 3D et de traiter les données obtenues pour produire des modèles restituant à la fois la forme et l'apparence des objets à différents niveaux d'échelle. Mais ces techniques passent difficilement à l'échelle de centaines de millions ou de milliards de points. Une première raison à cette difficulté est la complexité des algorithmes et/ou une demande trop importante en espace mémoire. Les techniques out-of-core ou streaming existantes, opérant sur des structures stockées en mémoire de masse, ne sont adaptées qu'à des traitements localisés ou ne nécessitant pas de disposer de la pleine résolution des données, au prix d'une robustesse réduite aux défauts des données (bruit, absence de données).
Un second frein dans le passage à l'échelle concerne les interventions manuelles dans la chaîne de traitement. Malgré les progrès réalisés récemment dans l'automatisation des traitements, le nombre d'interventions manuelles nécessaires pour ajuster des paramètres ou effectuer des corrections, en repartant parfois de zéro, est encore important, et d'autant plus pénalisant que les données sont volumineuses et les traitements complexes. Une source majeure de difficulté dans la construction automatique des modèles géométriques est le manque d'informations a priori sur les caractéristiques des objets numérisés : structure, forme générale, composants, etc. A cette étape de la chaîne de traitement, les données issues de l'acquisition 3D sont généralement les seules prises en compte par les algorithmes existants.
Pour répondre à ces problématiques, nous souhaitons développer de nouvelles techniques exploitant la complémentarité de sources de données multiples pour la construction de modèles géométriques : scans, photographies, modèles 3D similaires en forme et/ou en apparence, dessins, etc. Nous voulons mettre au point des méthodes qui, à partir de l'analyse de ces données, permettront de saisir les caractéristiques des objets numérisés, pour à la fois localiser et guider la construction des modèles, en réduisant au maximum les interventions manuelles.
Représentation des modèles pour leur visualisation en temps réel. La grande taille et la complexité des modèles obtenus avec la représentation classique par maillages triangulaires posent des problèmes de stockage et rendent difficiles leur visualisation en temps réel. En complémentarité aux représentations multi-échelles, nous cherchons à développer des représentations alternatives aux maillages à la fois compactes et adaptées aux techniques de rendu en temps réel, tout en permettant d'effectuer certaines opérations d'édition (sculpture virtuelle, simulation de phénomènes naturels).
Les représentations par displacement mapping et/ou par grilles de voxels hiérarchiques exploitent de façon très efficace la puissance de calcul des cartes graphiques actuelles. Ces structures de données ont en commun de nécessiter un espace de stockage très important en mémoire graphique pour des modèles complexes, qui n'est pas forcément justifié par la géométrie locale. Afin de pouvoir visualiser des modèles complexes avec des ressources mémoire réduites, et en exploitant au mieux la puissance de calcul des processeurs graphiques, nous souhaitons développer une nouvelle approche de génération procédurale des surfaces s'appuyant sur une décomposition en cartes de relief et sur des techniques de génération procédurale adaptées aux caractéristiques des objets numérisés.
Acquisition et modélisation du mouvement
La plupart des méthodes de recalage existantes utilisent les données statiques des formes pour calculer la correspondance. Notre objectif est de proposer une nouvelle méthode qui utilise aussi les données de mouvements de ces formes (les données dynamiques). Le principal intérêt de cette approche est de pouvoir utiliser ces données de mouvements d’une personne afin d’en extraire les points caractéristiques. Comme ces données sont beaucoup plus riches que les données statiques, le calcul de correspondance sera de meilleure qualité. Grâce au développement récent des technologies d’imagerie médicale, l’obtention de données précises sur les mouvements de la peau ou des organes devient de plus en plus facile. Par exemple, la capture de mouvements de marqueurs placés sur la peau avec des caméras synchronisées est facile à mettre en œuvre. En cardiologie, le tagging IRM qui permet d’observer les mouvements cardiaques est une technique aussi de plus en plus couramment utilisée.
Modèles combinatoires multi-résolutions et multi-échelles
De nombreux travaux utilisent simultanément plusieurs représentations d’un même objet. Elles peuvent correspondre à différentes échelles de visualisation ou à différents niveaux de détails d’un même objet 3D, mais également à des modèles de natures différentes. Ainsi, en simulation, il n’est pas rare d’utiliser un maillage volumique grossier pour les calculs numériques, auquel un maillage surfacique plus fin est associé pour un rendu réaliste. Des représentations multi-échelles sont également utilisées pour la segmentation d’images, la compression ou le filtrage de maillages. Enfin de nombreux algorithmes font appel à des structures hiérarchiques pour accélérer les traitements, comme par exemple le lancer de rayon ou la détection de collisions.
Nous voulons proposer des structures combinatoires pour la représentation de tels objets multi-résolutions et les équiper d'opérateurs topologiques multi-échelles permettant de gérer de manière cohérente et contrôlée les interdépendances entre représentations. Il s'agit par exemple de construire de telles hiérarchies, de les manipuler, d’y appliquer des découpes, des simplifications, des raffinements ou d’y faire des requêtes géométriques efficaces.
Les travaux que nous voulons mener s’articulent autour de trois problématiques avec des perspectives à plus ou moins longs termes détaillées ci-dessous :
Modèles combinatoire multi-résolutions. Nous continuerons nos travaux sur les cartes combinatoires et leurs extensions multi-résolution, notamment pour les maillages volumiques, en visant entre autres les applications suivantes : l'encodage et la visualisation de maillages progressifs volumiques (tétraédriques ou quelconques), la simplification et l'optimisation de tels maillages et leur représentation multi-échelles. A plus long terme nous visons l'analyse multi-résolution de données volumiques, pour leur échantillonnage, leur compression ou leur traitement numérique.
Segmentation d'images ou de maillages. Nous avons exploité la notion de diagrammes de Voronoï discrets, volumiques, contraints par des éléments de surfaces ou des courbes, pour la génération de maillages surfaciques et volumiques à partir d'images segmentées. Nous cherchons à étendre ces notions à des structures combinatoires volumiques pour permettre la segmentation de maillages et aborder sous un angle nouveau les problèmes liés à la simplification ou à l'échantillonnage de maillages volumiques.
Partition de l'espace et structure topologique. Nous avons proposé un mécanisme de suivi de la trajectoire de particules dans des volumes déformables. Celui-ci a été utilisé pour la détection de collision entre un mobile et son environnement, dans le cadre de simulations chirurgicales. Nous voulons exploiter la structuration spatiale définie par nos modèles topologiques, pour aborder de manière plus générale les problèmes de détection de collisions. Nous souhaitons notamment aborder les problèmes difficiles liés aux auto-collisions, à la gestion des découpes et autres changements topologiques. Nos méthodes nous permettrons d'étudier plus généralement la question des requêtes de proximité dans un espace partitionné.