• Mme  Brigitte  Plateau (ID-IMAG, professeur de l'INPG),
• M.  Jean-Marc  Vincent  (ID-IMAG,  maître de  conférences de  l'UJF),
• M.  François  Faure (iMAGIS-GRAVIR-IMAG,  maître de  conférences de  l'UJF).
  

Jury  :

• Mme  Marie-Paule Cani (présidente du jury / professeur de l'INPG / GRAVIR-EVASION / Grenoble),
• M.  Serge  Miguet (rapporteur externe /  professeur de l'Université Lyon  2 / LIRIS / Lyon),
• M.  Jean-Michel  Dischler   (rapporteur  externe / professeur  de l'ULP / LSIIT-IGG, Strasbourg),
• Mme  Brigitte Plateau  (examinateur (directeur  de thèse)  / professeur de l'INPG / ID-IMAG / Grenoble),
• M.  Jean-Marc Vincent (examinateur (co-encadrant) / maître de conférences de  l'UJF / ID-IMAG / Grenoble),
• M.  François  Faure (examinateur (co-encadrant) /  maître de conférences de l'UJF / GRAVIR-EVASION / Grenoble).

Résumé de la thèse :

Problématique
En informatique graphique,  l'animation de textiles constitue un axe de recherche  particulièrement important de par ses nombreuses applications  dans le  monde industriel  auprès des  industries  de la confection et du  tissage et grâce à son  application directe dans les jeux  vidéos  ou encore  dans  les  films  d'animation, en  permettant notamment l'habillage de personnages virtuels.

Dans le  contexte industriel  pour le développement  d'activités liées aux textiles, la simulation  doit impérativement être réaliste.  C'est pourquoi  elle  est basée  sur  une  modélisation physique  de l'objet déformable afin de reproduire au mieux son comportement.  En effet, afin d'obtenir un  résultat réaliste, les lois fondamentales de la physique comme la vitesse, les forces (gravitation, vent, ...), les frottements,  doivent être  utilisées pour  modéliser le  mouvement de plusieurs objets  interagissants.  Les modèles  employés pouvant alors être  numériquement   très  complexes,   le  calcul  d'une   image  de personnages  varie de  la seconde  à plusieurs  minutes  suivant leurs complexités.

L'une  des  difficultés  principales  réside  donc  dans  l'obtention d'animations interactives en temps réel, c'est-à-dire dans la possibilité de  calculer 25  images de la  simulation de  textiles par seconde en autorisant des interactions de la part de l'utilisateur. De telles simulations  intéressent aussi  bien les industries  du textile que celles du loisir.  Au niveau industriel, cette simulation intégrée aux logiciels de Conception  Assistée par Ordinateur (CAO) permettrait de réduire  considérablement les  coûts de mise  au point en  ayant un aperçu direct de l'apparence d'un  vêtement sans avoir à le retoucher. A un niveau  plus ludique, il est facile  d'imaginer les répercussions que  cela aurait.   Imaginez-vous dans  un monde  virtuel et  voyez le réalisme que cela  apporterait de se voir avec  des vêtements ayant un comportement  semblable à la  réalité avec  l'intégration de  tous les mouvements des tissus en réponse à vos propres mouvements. Ainsi, les retombées  concernent à  la fois  l'industrie de  la confection  et du tissage,  mais également  les applications  de type  réalité virtuelle avec des défilés de mode virtuels.

Afin de  réaliser ces animations  interactives, tout en  conservant la même complexité de simulation pour des modèles de tailles importantes, nous   avons   choisi   de   diminuer   les   temps   de   calcul   en parallélisant  les algorithmes employés  et en  les exécutant ensuite sur une grappe de machines.

Pour  atteindre  l'objectif  de  ce travail  de  recherche,  plusieurs problèmes  majeurs  étaient  à  résoudre.  Tout  d'abord,  de  manière générale dans  le domaine  du parallélisme, ce  projet de  recherche a posé le problème des  contraintes de temps  réel et  de leur implication sur l'architecture des  systèmes.  En effet, dans le cadre d'une animation de textiles, les  temps d'exécution sont de l'ordre de la  minute, impliquant  des tâches  de  calcul de  petites tailles  et nécessitant par conséquent un parallélisme à grain très fin. Ensuite,  dans  le  cadre   plus  précis  de  la  simulation  d'objets déformables, un  point majeur  à résoudre résidait  dans l'élaboration des calculs dynamiques,  c'est-à-dire dans la réalisation des calculs  du mouvement du  tissu au  cours du  temps.  Enfin,  un autre point important  à résoudre concernait  l'obtention des images issues de  la parallélisation  de la simulation.   En effet,  dans le domaine de l'informatique graphique,  une simulation en temps réel n'a d'intérêt que si sa visualisation est possible.

Collaborations
Afin de répondre à l'ensemble de ces problèmes, ce travail de recherche, alliant calcul  haute performance,  réalité virtuelle  et informatique graphique, a  fait l'objet  d'une collaboration entre  le laboratoire d'Informatique et Distribution  (ID-IMAG) et le laboratoire GRAphisme, VIsion et Robotique (GRAVIR-IMAG), tous deux localisés à Grenoble.

Par ailleurs, ce travail a été partiellement financé par le contrat de la  thématique  prioritaire  n°4   "Sciences  et  technologies  de l'information, outils et applications" de la région Rhône-Alpes au travers du projet  SAPPE. Ce projet a été réalisé  dans le cadre d'une collaboration avec la société  Yxendis (Saint-Chamond), qui conçoit et commercialise  des produits logiciels  pour l'infographie  textile, en vue d'un transfert de technologie.

Architecture et environnement parallèle
Dès  le  commencement  de  ce  travail  de  recherche,  l'architecture parallèle visée  était de type grappe de machines.  Le choix concernant  l'utilisation   d'une  grappe  de  machines  plutôt  qu'une machine  multi-processeurs  dédiée  telle  qu'un  Cray  est  facilement compréhensible.  En  effet, à l'heure  actuelle, il est  beaucoup moins coûteux  de réunir plusieurs  ordinateurs ordinaires  que de  se doter d'une  machine  unique  multi-processeurs.   Par ailleurs,  une  grappe d'ordinateurs a  l'avantage d'offrir une  grande souplesse d'évolution grâce  à la  possibilité de  rajouter à  tout moment  des processeurs. Cette  dynamicité de l'architecture  n'est, hélas,  pas fournie  par les machines multi-processeurs. De plus, de nos jours, la grande majorité des entreprises  sont dotées  à la  fois d'un  réseau local  et  d'un parc informatique  conséquent.   Il  est  alors  facile  de  maximiser  les ressources  matérielles  existantes   en  employant  par  exemple  ces machines la nuit  en tant que grappe de  calcul, alors que d'ordinaire elles sont inexploitées.

Afin d'exploiter au maximum les  ressources offertes par une grappe de machines,  j'ai  utilisé  l'environnement  de  programmation parallèle Athapascan  développé   au  sein  du  laboratoire Informatique  et  Distribution  (ID-IMAG)  dans  le  cadre  du  projet INRIA-APACHE.   Le  parallélisme  au  sein de  cet  environnement  est exprimé sous la forme de  tâches de calculs s'exécutant en concurrence sur  la  machine  parallèle  cible.  L'emploi  de  cet  environnement, facilité  par  une  interface   applicative  de  haut  niveau,  permet d'assurer  la portabilité  des  programmes créés  en autorisant,  sans aucune   modification  des  programmes,   une  exécution   aussi  bien séquentielle, SMP  (machines multi-processeurs) que  distribuée.  Nous conservons     ainsi,    au     travers    de     la    programmation, l'extensibilité  offerte   initialement  par  la   grappe  de machines.

Ce projet de recherche a ainsi permis de valider l'approche de l'environnement  de programmation  parallèle  Athapascan, en mettant notamment  au point une application  avec des contraintes "temps  réel",  ainsi  que  le  contrôle dynamique  de  son ordonnanceur. En effet, il faut  savoir qu'au commencement de ma thèse cet  environnement   était  encore  en   cours  de  recherche   et  de développement par MM. Jean-Louis  Roch, Thierry Gautier et Rémi Revire (ID-IMAG,  projet APACHE)  et qu'il  n'avait  été testé  que sur  une application à gros grains de dynamique moléculaire, nommée "Takakaw".   Ainsi, tout  au long  de ma  thèse, j'ai  travaillé  en étroite collaboration  avec eux,  en  leur faisant  part  des améliorations  à apporter  à l'environnement  pour obtenir  de  meilleures performances dans le  cadre d'une  application à grains  fins :  communications pas assez  réactives,  graphe  de   flots  de  données  dupliqués  sur l'ensemble   des  noeuds,   surcoût  important   de  l'ordonnancement, contention du multi-threading, etc.

Au final, la validation  de l'environnement Athapascan a fait l'objet  d'une publication avec  MM.  Thierry  Gautier et  Rémi Revire (cf. publications).

Modélisation physique et parallélisation
Pour modéliser les  textiles, j'ai employé un modèle  physique de type masses-ressorts   basé   sur   une   discrétisation  de   l'objet   en particules. Ce modèle permet de  décrire la mécanique du textile en le discrétisant en  un ensemble de masses interagissants  entre elles par l'intermédiaire de ressorts plus ou moins complexes. La formulation de l'équation  du mouvement  associée  à  cet objet,  dictée  par la  loi fondamentale  de la  dynamique,  conduit alors  à  la résolution  d'un système d'Equations Différentielles Ordinaires (EDO).

Au  final,  les algorithmes  conduisant  à  la  génération des  images souhaitées peuvent se décomposer selon la structure suivante :

• recherche des collisions possibles entre les objets de la scène,
• calcul  d'une  matrice  représentant  l'environnement  global (positions des objets, forces, ...),
• résolution de  systèmes  linéaires pour  la position  des points, leur vitesse et leur accélération.

L'implantation   parallèle  de  ces   calculs  dynamiques   a nécessité l'élaboration   de   structures    de   données   précises   pour   la parallélisation   des  algorithmes.   Notons  tout   d'abord   que  la parallélisation est basée sur un partitionnement de l'objet en sous-ensembles  de  particules,   la  taille  de  ces  sous-ensembles permettant de  définir la granularité de  l'algorithme parallèle. J'ai notamment  effectué une  étude  sur les  différents  paramètres de  la parallélisation,   résultant  essentiellement   de   la  décomposition physique de l'objet, afin d'obtenir les meilleures performances.

Par ailleurs, en employant ce partitionnement, j'ai implanté en parallèle deux méthodes  d'intégration  des  équations  du  mouvement  :  la méthode explicite  "leap-frog" et la  méthode d'Euler implicite. Dans le cadre  de l'intégration par la méthode  d'Euler implicite, les opérations  les   plus  coûteuses  en   calcul  correspondent  aux résolutions de  systèmes linéaires par la  méthode du gradient conjugué  impliquant   notamment  des  opérations  d'algèbre linéaire de type multiplications  de matrices creuses et de vecteurs. C'est pourquoi,  afin d'effectuer ces opérations  de manière efficace, j'ai  notamment  proposé  une  nouvelle structure  de  données parallèle.

Couplage simulation numérique parallèle / visualisation multi-écrans
Pour  effectuer  la   visualisation  de  l'application,  j'ai  utilisé l'environnement  de réalité  virtuelle Net  Juggler développé initialement  au  sein   du  Laboratoire  d'Informatique  Fondamentale d'Orléans  (LIFO), dont le  développement s'est  poursuivi au  sein du laboratoire   ID-IMAG.   Cet   environnement   permet  notamment   une visualisation de  l'application sur plusieurs écrans  en tirant parti des cartes graphiques disposées sur une grappe de machines.

L'emploi de  cet environnement a  imposé la réalisation  d'un couplage entre la simulation parallèle et la visualisation. J'ai ainsi implanté deux modules  distincts, une simulation  parallèle de textiles  et une visualisation multi-écrans,  que j'ai  ensuite couplés en  les faisant communiquer efficacement à l'aide de sockets et de primitives de diffusion  MPI (Message  Passing Interface). L'intérêt  d'une telle combinaison peut  permettre, à  terme, une meilleure  compréhension de simulations de  phénomènes très complexes nécessitant  de gros volumes de données dont la visualisation n'était pour le moment pas réalisable sans l'utilisation de machines fort coûteuses telles que des Silicon Graphics.

Du point de vue scientifique, l'étude d'algorithmes parallèles pour la synthèse d'animations a impliqué un  nouveau regard sur le domaine. En effet, la distribution des calculs sur une grappe de multi-processeurs et les  délais inévitablement variables de  récupération des résultats ont  remis  en  cause  l'approche synchrone  utilisée  jusqu'alors  en synthèse   d'animations.   J'ai   donc   implanté  un   modèle totalement  asynchrone  dans  lequel les  sous-ensembles  (simulation parallèle,    affichage,   interaction)   peuvent    être   exécutés indépendamment en  l'absence d'actions synchronisées.   Cette approche parallèle,  encourageant le  développement  d'algorithmes asynchrones, peut ainsi  permettre le  déploiement d'applications de  type serveurs d'animations   capables  de  gérer   efficacement  un   monde  virtuel multi-utilisateurs.

Ce  modèle  asynchrone  a  fait l'objet  de  différentes  publications réalisées notamment  avec les concepteurs  de Net Juggler,  MM. Bruno Raffin et Jérémie Allard, qui avaient également  testé  ce couplage  en  implantant  en  MPI une  simulation parallèle de fluides.  Au  final, nous avons réalisé une démonstration visualisée sur plusieurs écrans, nommée "démo valley", intégrant à l'intérieur d'un décor 3-D d'une vallée, leur simulation interactive de fluides écrite  en MPI, ma simulation interactive  de textiles écrite en Athapascan,  avec une simulation de prairie  implantée par MM. François Faure et  Franck Perbet (EVASION-GRAVIR).  L'utilisateur peut alors naviguer  dans ce monde  virtuel via un lapin  dont les effets  de  fourure  ont  été   réalisés  par  M.  Jérémie  Allard  en surperposant  plusieurs  couches  transparentes  de  textures.   Cette démonstration  est  visible  sur  la plate-forme  GrImage  de  l'INRIA Rhône-Alpes.

Il  est à  noter  que le  couplage  entre la  simulation parallèle  et l'environnement  multi-écrans ouvre  un nouveau  domaine  de recherche concernant  la gestion efficace  du  flux entre  applications parallèles  de  type   simulation  numérique  et  réalité  virtuelle, permettant  la   construction  d'applications  interactives  complexes traitant de gros volumes de données. Ce travail de recherche m'a ainsi permis  d'appréhender les  divers  problèmes liés  aux contraintes  de temps  réel et  au couplage  d'une visualisation  interactive  sur une simulation numérique.

Réalisations logicielles
Mon  travail  de  thèse  a  abouti  à  une  plate-forme permettant  d'effectuer une  simulation de  textiles en  parallèle pouvant être  visualisée sur  plusieurs écrans.  Actuellement, le  prototype que j'ai réalisé, d'environ  20 000 lignes de code C++ en Athapascan, permet  d'effectuer une simulation en parallèle d'environ un  million  de  particules  sur  une  grappe  de  200  PCs  avec  une visualisation sur 3 autres PCs.

Perspectives