Parallel algorithms of physical simulation in computer graphics: application to cloth simulation

The topic of this Ph. D. thesis combines high performance computing and virtual reality. We propose parallel computing methods for 3D object animation in computer graphics. We target a cloth simulation with physically-based models. The fundamental law of dynamics are used to model with realism the movement of several objects. Due to the numerical complexity of the models used, a frame needs from one second to several minutes of computation on a single CPU. The goal is to decrease this time by parallelizing the algorithms and by executing them on a SMPs cluster to obtain real time animations. Several integrating methods have been parallelized. When implicit methods are used, linear systems are solved with a Conjugate Gradient method involving a high number of computations with linear algebra operations like multiplication of sparse matrices and vectors. This Ph. D. thesis proposes new efficient parallel algorithmic structures and asynchronous algorithms. This work also validates the approach of the Athapascan parallel programing environment (INRIA-APACHE project) and its dynamic control scheduler for the implementation of soft real time applications. Code coupling has also been experimented between the parallel cloth simulation and the multi display rendering environment Net Juggler. It enables real time multi display cloth rendering through managed communications.
Cette thèse combine le calcul haute performance à la réalité virtuelle par son apport de méthodes de calcul parallèle pour l'animation d'objets 3D en synthèse d'image. Son application vise plus particulièrement le domaine de la simulation de textiles par modèles physiques. Les lois fondamentales de la dynamique ont en effet été employées pour modéliser le mouvement de plusieurs objets dans un souci de réalisme. Les modèles employés étant numériquement complexes, le calcul d'une image en séquentiel varie de la seconde à plusieurs minutes suivant la complexité du modèle. L'objectif a été de diminuer ce temps par la parallélisation des algorithmes et l'exécution sur grappes de machines multiprocesseurs afin d'obtenir des animations en temps réel. Différentes méthodes d'intégration des équations du mouvement ont été implantées en parallèle. Dans le cas de l'emploi de méthodes implicites, les opérations coûteuses en calcul proviennent de la résolution de systèmes linéaires par la méthode du Gradient Conjugué impliquant des opérations d'algèbre linéaire de type multiplications de matrices creuses et de vecteurs. Ce projet de thèse a contribué à l'obtention de nouvelles structures algorithmiques parallèles efficaces avec l'obtention d'algorithmes asynchrones. Il a également permis de valider l'approche de l'environnement de programmation parallèle Athapascan (projet INRIA-APACHE) avec la mise au point d'applications avec des contraintes temps réel mou ainsi que le contrôle dynamique de son ordonnanceur. Durant ce projet de thèse, un couplage entre la simulation parallèle de textiles et son affichage utilisant l'environnement de visualisation multi-écrans Net Juggler a également été réalisé en faisant communiquer efficacement ces deux programmes parallèles.