Détection de Collision pour Environnements Large Échelle : Modèle Unifié et Adaptatif pour Architectures Multi-coeur et Multi-GPU

Virtual reality environments are becoming increasingly large and complex and real-time interaction level is becoming difficult to stably insure. Indeed, because of their complexity, detailed geometry and specific physical properties, these large scale environments create a critical computational bottleneck on physical algorithms. Our work focused on the first step of the physical process: the collision detection. These algorithms can sometimes have a quadratic complexity. Solving and simplifying the collision detection problem is integral to alleviating this bottleneck. Hardware architectures have undergone extensive changes in the last few years that have opened new ways to relieve this computational bottleneck. Multiple processor cores offer the ability to execute algorithms in parallel on one single processor. At the same time, graphics cards have gone from being a simple graphical display device to a supercomputer. These supercomputers now enjoy attention from a specialized community dealing solely with physical simulation. To perform large scale simulations and remain generic on the runtime architecture, we proposed unified and adaptive mapping models between collision detection algorithms and the runtime architecture using multi-core and multi-GPU architectures. We have developed innovative and effective solutions to significantly reduce the computation time in large scale environments while ensuring the stability and reproducibility of results. Our models cover the global collision detection pipeline, focusing both high and low level algorithms. Our models based on multi-core, GPU and multi-GPU combine different techniques of spatial subdivision algorithms based on topology and load balancing techniques based on data stealing. Our hybrid solution enables us to increase space and computing time within large scale virtual environments. The coupling of these new algorithms led us to develop two models of dynamic algorithmic adaptation based (or not) on off-line precomputed scenarios. Finally, it became necessary to add a new dimension to the collision detection pipeline taking into account of the architecture for optimal execution. With this formalism, we proposed a new pipeline of collision detection with a granularity of parallelism on multicore processors or multi-GPU platforms. It enables simultaneous execution of different stages of the pipeline and a parallel internal to each of these steps.Les environnements de réalité virtuelle devenant de plus en plus complexes et de très grandes dimensions, un niveau d'interaction temps-réel devient impossible à garantir. En effet, de par leur complexité, due à une géométrie détaillée et aux propriétés physiques spécifiques, ces environnements large échelle engendrent un goulet d'étranglement calculatoire critique sur les algorithmes de simulation physique. Nous avons focalisé nos travaux sur la première étape de ces algorithmes qui concerne la détection de collision, car les problématiques font partie intégrante de ce goulet d'étranglement et leur complexité peut parfois se révéler quadratique dans certaines situations. Le profond bouleversement que subissent les architectures machines depuis quelques années ouvre une nouvelle voie pour réduire le goulet d'étranglement. La multiplication du nombre de cœurs offre ainsi la possibilité d'exécuter ces algorithmes en parallèle sur un même processeur. Dans le même temps, les cartes graphiques sont passées d'un statut de simple périphérique d'affichage graphique à celui de supercalculateur. Elles jouissent désormais d'une attention toute particulière de la part de la communauté traitant de la simulation physique. Afin de passer au large échelle et d'être générique sur la machine d'exécution, nous avons proposé des modèles unifiés et adaptatifs de correspondance entre les algorithmes de détection de collision et les architectures machines de type multi-coeur et multi-GPU. Nous avons ainsi défini des solutions innovantes et performantes permettant de réduire significativement le temps de calcul au sein d'environnements large échelle tout en assurant la pérennité des résultats. Nos modèles couvrent l'intégralité du pipeline de détection de collision en se focalisant aussi bien sur des algorithmes de bas ou de haut niveau. Nos modèles multi-coeur, GPU et multi-GPU allient différentes techniques de subdivision spatiale à des algorithmes basés topologie ainsi que des techniques d'équilibrage de charge basées sur le vol de données. Notre solution hybride permet d'accroitre l'espace et le temps de calcul ainsi que le passage au large échelle. L'association de ces nouveaux algorithmes nous a permis de concevoir deux modèles d'adaptation algorithmique dynamique basés, ou non, sur des scénarios de pré-calcul hors-ligne. Enfin, il nous est apparu indispensable d'ajouter au pipeline de détection de collision une nouvelle dimension révélant la prise en compte des architectures pour une exécution optimale. Grâce à ce formalisme, nous avons proposé un nouveau pipeline de détection de collision offrant une granularité de parallélisme sur processeurs multi-coeur. Il permet une exécution simultanée des différentes étapes du pipeline ainsi qu'un parallélisme interne à chacune de ces étapes