Spelling suggestions: "subject:"détection dde collision"" "subject:"détection dde kollision""
1 |
Simulation Dynamique en Temps-Réel et Interaction 3D de Tissu Biologique: Application aux Simulateurs MédicauxSundaraj, Kenneth 23 January 2004 (has links) (PDF)
L'avènement de l'imagerie médicale et de nouvelles techniques opératoires a bouleversé les méthodes de travail des médecins. Mais ce changement nécessitera une formation renforcée des praticiens et chirurgiens. C'est pourquoi le dévelopment d'outils appropriés comme les simulateurs médico-chirurgicaux se fait de plus en plus ressentir. Dans ce cadre, nous nous sommes intéressés au problème de la modélisation des phénomènes de déformation de tissu biologique et à la détection des collisions dans un environment virtuel. Dans un premier temps, nous présentons les différents modèles physiques existants et les différentes méthodes de résolution numérique associées aux objets déformable. Nous proposons ensuite un modèle développé pour la simulation de tissu biologique, en présentant successivement les aspects liés à la formulation du modèle, à la résolution du modèle, et au traitement des interactions physiques. Ce modèle, basé sur l'utilisation du principe de Pascal, permet de modéliser de manière relativement satisfaisante des corps biologiques, tout en permettant une simulation interactive. Dans un deuxième temps, nous présentons les différents algorithmes existants pour la détection de collision, ainsi que la difficulté d'adapter ces algorithmes aux simulateurs médicaux où les objets déformables complexes forment la base du modèle. Nous proposons ensuite les algorithmes développés pour traiter ce problème dans le cadre des simulateurs médicaux. Ces algorithmes présentent des caractéristiques de robustesse numérique et d'efficacité supérieures á l'existant, et permettent de traiter des corps déformables. Nous appliquons ces résultats dans le cadre d'un simulateur échographique de la cuisse humaine et d'une simulateur de chirurgie arthroscopique du LCA (ligament croisé antérieur du genou).
|
2 |
Détection de collision par lancer de rayon : La quête de la performance / Ray-traced collision detection : Quest for performanceLehericey, François 20 September 2016 (has links)
La détection de collision est une tâche essentielle pour la simulation physique d’environnements virtuels. De nos jours, la détection de collision est l’un des goulets d’étranglement calculatoire dans les applications de réalité virtuelle dû à la complexité des environnements que l’on souhaite simuler et par la contrainte d’interaction en temps-réel. Nous avons concentré nos travaux sur la seconde étape de la détection de collision (narrow-phase) dans laquelle les tests de collisions sont effectués sur des paires d’objets. Contrairement à la première étape, les tests de collisions sont effectués sur des versions détaillées des modèles géométriques et sont donc très sensible au niveau calculatoire à la complexité géométrique de ceux-ci.Cette thèse vise à améliorer les performances de la détection de collision lors de l’utilisation d’objets géométriques complexes (formes représentées par un maillage, éventuellement non-convexe et/ou déformable). Nos méthodes permettent d’accélérer le calcul de la narrow-phase. Les algorithmes proposés peuvent être implémentés sur GPU pour profiter de leur puissance de calcul et ainsi améliorer les performances.Pour réaliser la narrow-phase, nous proposons un pipeline adapté à une implémentation GPU. Celui-ci permet de réaliser la narrow-phase à l’aide d’algorithmes basés lancer de rayon. Notre méthode repose sur un principe commun où tous les tests de collision sont effectués par lancer de rayon à partir des sommets des objets. Cette généricité nous permet de réaliser les tests sur des maillages ayant n’importe quelles propriétés (rigide ou déformable, convexe ou non-convexe). Les algorithmes de lancer de rayon utilisés étant choisis en fonction des propriétés des objets pour optimiser les performances.Nous avons généralisé la méthode de détection de collision utilisée pour supporter, en plus des objets volumiques, des objets surfaciques (tels que des tissus). Cette méthode est compatible avec le pipeline proposé et permet de réaliser des tests de collisions entre n’importe quelle combinaison d’objets.De plus, nous proposons d’exploiter la cohérence temporelle pour améliorer les performances. Le résultat de la détection de collision est généralement très semblable entre deux pas de temps successifs. Suite à cette observation, nous proposons un algorithme de lancer de rayon itératif qui intègre le résultat du pas précédent pour exploiter cette cohérence temporelle. Cet algorithme peut être utilisé conjointement avec des algorithmes de lancer de rayon standard. Il permet de remplacer certains tests unitaires pour mettre à jour de manière incrémentale le résultat de la détection de collision. L’algorithme de lancer de rayon itératif est ajouté au pipeline en tant qu’alternative aux autres algorithmes de lancer de rayon et est utilisé prioritairement dû à son faible coût calculatoire. / Collision detection is an essential task for physical simulation of virtual environments. Nowadays, collision detection is one of the main bottleneck of virtual reality applications. This is due to the complexity of the environments we want to simulate and the real-time interaction constraint. We have concentrated our work on the second phase of collision detection, the narrow-phase, in which collision queries are performed on pairs of objects. Contrary to the first phase of collision detection, collision queries are performed on the full representation of the objects (with all details) and are thus sensible to the geometric complexity of the objects in term of computation time.This thesis is aimed to improve the performances of collision detection when using geometrically complex objects (represented with triangle meshes, potentially non-convex and deformable). Our methods are able to reduce computation times. Our proposed algorithms can be implemented on GPU to take advantage of their computational power and thus further improve the performances of our methods.To implements our narrow-phase, we propose a pipeline which is adapted for GPU execution. This pipeline perform collision detection with ray-tracing algorithms. Our methods rely on a shared principle where all collision queries are performed by casting rays from the vertices of the objects. This genericity allow us to perform collision detection on triangle meshes with any properties (rigid or deformable, convex or non-convex). The ray-tracing algorithms used are dynamically selected depending on the properties of the objects to improve the performances.We have generalized the collision detection method we use in our pipeline to handle, in addition to volumetric objects (represented by their surface), surface objects (such as cloth). This method is compatible with our pipeline and allow us to perform collision detection with any combination of volumetric and surface objects.Furthermore, we propose to exploit temporal coherency to improve performances. The result of collision queries (contact points) are generally similar between successive time-step. Starting from this observation, we propose a ray-racing algorithm which use the result of the previous time-step to exploit this temporal coherency. This ray-tracing algorithm can be used in conjunction to standard ray-tracing algorithms. It is used to replace standard ray-tracing algorithms in specific condition to update the result of the previous time-step instead of computing it from scratch. The iterative ray-tracing algorithm is added in our pipeline as an alternative to other ray-tracing algorithms and is used in priority due to his lower computational cost compared to other algorithms.
|
3 |
Contribution à la modélisation et la commande robuste de robots manipulateurs à articulations flexibles. Applications à la robotique interactive.Makarov, Maria 21 May 2013 (has links) (PDF)
La problématique traitée dans cette thèse concerne la commande de robots manipulateurs à articulations flexibles. Les méthodes développées visent à satisfaire les spécifications de performance et de robustesse en suivi de trajectoire, ainsi qu'à assurer un niveau de sécurité compatible avec un scénario de fonctionnement interactif dans lequel l'homme et le robot partagent un même espace de travail. Seules les mesures moteur sont utilisées dans un contexte d'instrumentation réduite. Le premier objectif de performance de la commande de mouvement est atteint grâce à l'identification expérimentale d'un modèle flexible représentatif du système, et l'usage de ce modèle pour la synthèse de lois de commande avancées intégrées au sein d'une structure cascade. Deux approches complémentaires fondées d'une part sur la commande prédictive de type GPC (Generalized Predictive Control), et d'autre part sur la commande Hinfini, sont considérées pour la synthèse de lois de commande à deux degrés de liberté, prédictives et robustes. Les performances de ces deux approches sont analysées et évaluées expérimentalement. Le deuxième objectif de sécurité est abordé à travers un algorithme de détection de collisions du robot avec son environnement, sans capteur d'effort et en présence d'incertitudes de modélisation. Afin de séparer efficacement les effets dynamiques des collisions de ceux des erreurs de modélisation, une stratégie adaptative de filtrage et de décision tenant compte de l'état du système est proposée. La validation expérimentale montre une très bonne sensibilité de détection, compatible avec les normes et les recommandations de sécurité relatives à la robotique collaborative.
|
4 |
Paramétrage et Capture Multicaméras du Mouvement HumainKnossow, David 23 April 2007 (has links) (PDF)
Au cours de cette thèse, nous avons abordé la problématique du suivi du mouvement humain. Nous proposons d'utiliser plusieurs caméras vidéos, permettant de s'affranchir de contraintes sur l'environnement de capture ainsi que de la pose de marqueurs sur l'acteur, au contraire des systèmes courament utilisés. Cela complexifie la recherche d'une information pertinente dans les images mais aussi la corrélation de cette information entre les différentes images ainsi que l'interprétation de cette information en terme de mouvements articulaires du corps humain. Nous nous intéressons à une approche utilisant les contours occultants du corps et étudions le lien entre le mouvement articulaire du corps et le mouvement apparent des contours dans les images. La minimisation de l'erreur entre les contours extraits des images et la projection du modèle nous permet d'estimer le mouvement de l'acteur. Nous montrons que l'utilisation d'images video permet entre autres de produire des informations complémentaires telles que les contacts entre les parties du corps de l'acteur. Ces informations sont importantes pour la ré-utilisation des mouvements en animation 3D.
|
5 |
Geometric operators for motion planningHimmelstein, Jesse 19 September 2008 (has links) (PDF)
La planification du mouvement connait une utilisation croissante dans le contexte industriel. Qu'elle soit destinée à la programmation des robots dans l'usine ou au calcul de l'assemblage d'une pièce mécanique, la planification au travers des algorithmes probabilistes est particulièrement efficace pour résoudre des problèmes complexes et difficiles pour l'opérateur humain. Cette thèse CIFRE, effectuée en collaboration entre le laboratoire de recherche LAAS-CNRS et la jeune entreprise Kineo CAM, s'attache à résoudre la problématique de planification de mouvement dans l'usine numérique. Nous avons identifié trois domaines auxquels s'intéressent les partenaires industriels et nous apportons des contributions dans chacun d'eux: la détection de collision, le volume balayé et le mouvement en collision. La détection de collision est un opérateur critique pour analyser des maquettes numériques. Les algorithmes de planification de mouvement font si souvent appel à cet opérateur qu'il représente un point critique pour les performances. C'est pourquoi, il existe une grande variété d'algorithmes spécialisés pour chaque type de géométries possibles. Cette diversité de solutions induit une difficulté pour l'intégration de plusieurs types de géométries dans la même architecture. Nous proposons une structure algorithmique rassemblant des types géométriques hétérogènes pour effectuer les tests de proximité entre eux. Cette architecture distingue un noyau algorithmique commun entre des approches de division de l'espace, et des tests spécialisés pour un couple de primitives géométriques donné. Nous offrons ainsi la possibilité de facilement ajouter des types de données nouveaux sans pénaliser la performance. Notre approche est validée sur un cas de robot humanoïde qui navigue dans un environnement inconnu grâce à la vision. Concernant le volume balayé, il est utilisé pour visualiser l'étendue d'un mouvement, qu'il soit la vibration d'un moteur ou le geste d'un mannequin virtuel. L'app roche la plus innovante de la littérature repose sur la puissance du matériel graphique pour approximer le volume balayé très rapidement. Elle est toutefois limitée en entrée à un seul objet, qui lui-même doit décrire un volume fermé. Afin d'adapter cet algorithme au contexte de la conception numérique, nous modifions son comportement pour traiter des " soupes de polygones " ainsi que des trajectoires discontinues. Nous montrons son efficacité sur les mouvements de désassemblage pour des pièces avec un grand nombre de polygones. Une soupe de polygones est plus difficile à manipuler qu'un volume bien formé. Le calcul du volume balayé introduit des opérateurs d'agrandissement et de rétrécissement des objets discrétisés. Le rétrécissement peut être utilisé pour d'autres applications dans la planification du mouvement à condition que la topologie de l'objet soit conservée pendant la transformation. Afin de préserver celle-ci, nous définissons le calcul du squelette qui préserve l'équivalence topologique. En gardant le squelette, nous employons l'opérateur de rétrécissement pour chercher les passages étroits des problèmes difficiles de planification de mouvement. Enfin, nous abordons le problème de la planification de mouvement en collision. Cette antilogie exprime la capacité d'autoriser une collision bornée pendant la recherche de trajectoire. Ceci permet de résoudre certains problèmes d'assemblage très difficiles. Par exemple, lors du calcul des séquences de désassemblage, il peut être utile de permettre à des "pièces obstacles" telles que les vis de se déplacer pendant la planification. De plus, en autorisant la collision, nous sommes capables de résoudre des problèmes de passage en force. Cette problématique se pose souvent dans la maquette numérique où certaines pièces sont " souples " ou si le problème consiste à identifier la trajectoire "la moins pire" quand aucun chemin sans collision n'existe. Nous apportons dans ce travail plusieurs contributions qui s'appliq uent à la conception numérique pour la robotique industrielle. Nous essayons de marier une approche scientifique avec des critères de fonctionnalités strictes pour mieux s'adapter aux utilisateurs de la conception numérique. Nous cherchons à exposer les avantages et les inconvénients de nos approches tout au long du manuscrit.
|
6 |
Efficient contact determination between solids with boundary representations (B-Rep) / Détermination efficace des contacts entre solides représentés par modélisation surfacique (B-Rep)Crozet, Sébastien 08 December 2017 (has links)
Avec le développement de systèmes robotiques avancés et de tâches de téléopération complexes, le besoin pour la réalisation de simulations en amont des opérations sur les systèmes réels se fait de plus en plus ressentir. Cela concerne en particulier les tests de faisabilité, d’entrainement d’opérateurs humains, de planification de mouvement, etc. Ces simulations doivent généralement être réalisées avec une précision importante des phénomènes physiques, notamment si l’opérateur humain est supposé faire face aux mêmes comportements mécaniques dans le monde réel que sur la scène virtuelle. La détection de collision, c’est à dire le calcul de points de contact et des normales de contact entre des objets rigides en mouvement et susceptibles d’interagir, occupe une portion significative des temps de calcul pour ce type de simulations. La précision ainsi que le niveau de continuité de ces informations de contact sont d’importance premières afin de produire des comportements réalistes des objets simulés. Cependant, la qualité des informations de contact ainsi calculées dépend fortement de la représentation géométrique des parties de la scène virtuelle directement impliquées dans la simulation mécanique. D'une part, les représentations géométriques basées sur des volumes discrets ou des tessellations permettent une génération de contacts extrêmement rapide, mais en contrepartie introduisent des artefacts numériques dus à l’approximation des formes en contact. D'autre part, l’utilisation de représentations surfaciques lisses (composées de courbes et surfaces lisses) produites par les modeleurs CAO permet d’éliminer ce problème d’approximations. Cependant, ces approches sont actuellement considérées trop lentes en pratique pour des applications en temps réel.Cette thèse est dédiée au développement d’une premier framework de détection de collision entre solides modélisés par représentation surfacique lisses suffisamment efficace pour offrir des performances temps-réel pour certaines applications industrielles nécessitant un niveau de précision élevé. Ces applications prennent typiquement la forme de la simulation d’opérations d’insertion avec faible jeu. L’approche proposée est basée sur une hiérarchie de volumes englobants et tire profit de caractéristiques clef des composants mécaniques industriels dont les surfaces sujettes à des contacts fonctionnels sont généralement modélisées par des surfaces canoniques (cylindres, sphères, cônes, plans, tores). Les contacts sur des surfaces d’interpolation telles que les NURBS sont généralement accidentels et rencontrés lors d’opérations de maintenance et de fabrication. Cette hiérarchie de volumes englobants est améliorée par l’identification d'entités supermaximales afin d’éviter la localisation redondante de points de contacts entre surfaces canoniques parfois découpées en plusieurs entités distinctes. De plus, le concept de cônes polyédrique de normales est défini afin d’établir des bornes de normales plus précises que les cônes de normales de révolution existants. Additionnellement, le framework ainsi développé est étendu afin de supporter des configurations incluant des câbles modélisés par des courbes de Bézier dilatées. Enfin, l’exploitation de la cohérence temporelle, ainsi que la parallélisation de l’ensemble du framework permet l’exécution en temps réel de certains scénarios industriels. / With the development of advanced robotic systems and complex teleoperation tasks, the need to perform simulations before operating on physical systems becomes of increasing interest for feasibility tests, training of the human operators, motion planning, etc. Such simulations usually need to be performed with great accuracy of physical phenomena if, e.g., the operator is expected to face the same ones in the real world and in the virtual scene. Collision detection, i.e., the computation of contact points and contact normals between interacting rigid bodies, occupies a time-consuming part of such a physical simulation. The accuracy and smoothness of such contact information is of primary importance to produce a realistic behavior of the simulated objects. However, the quality of the computed contact information strongly depends on the geometric representation of the parts of the virtual scene directly involved in the mechanical simulation. On the one hand, discrete volumes-based and tessellation-based geometric representations allow very fast contacts generation at the cost of the potential introduction of numerical artifacts due to the approximation of the interacting geometrical shapes. On the other hand, the use of boundary representations (issued by CAD modelers) composed of smooth curve and surfaces removes this approximation problem but is currently considered being too slow in practice for real-time applications.This Ph.D focuses on developing a first complete collision detection framework on solids with smooth boundary representations that achieves real-time performances. Our goal is to allow the real-time simulation of industrial scenarios that require a high level of accuracy. Typical applications are insertion tasks with small mechanical clearances. The proposed approach is based on a bounding-volume hierarchy and takes advantage of key features of industrial mechanical components which are often modeled with surfaces describing functional contacts with canonical surfaces (cylinder, sphere, cone, plane, torus) while contacts over free-form surfaces like B-Splines are mostly accidental and encountered during operations of maintenance and manufacturing. We augment this hierarchy with the identification of supermaximal features in order to avoid redundant exact localization of contact points on canonical surfaces that may be represented as distinct features of the CAD model. In addition, we define polyhedral normal cones that offer tighter bounds of normals than existing normal cones of revolution. Moreover, we extend our method to handle configurations that involve beams modeled as deformable dilated Bézier curves. Finally, parallelization of the full approach allows industrial scenarios to be executed in real-time.
|
7 |
Contribution à la modélisation et la commande robuste de robots manipulateurs à articulations flexibles. Applications à la robotique interactive. / Contribution to modeling and robust control of flexible-joint robot manipulators – Applications to interactive roboticsMakarov, Maria 21 May 2013 (has links)
La problématique traitée dans cette thèse concerne la commande de robots manipulateurs à articulations flexibles. Les méthodes développées visent à satisfaire les spécifications de performance et de robustesse en suivi de trajectoire, ainsi qu’à assurer un niveau de sécurité compatible avec un scénario de fonctionnement interactif dans lequel l’homme et le robot partagent un même espace de travail. Seules les mesures moteur sont utilisées dans un contexte d’instrumentation réduite. Le premier objectif de performance de la commande de mouvement est atteint grâce à l’identification expérimentale d’un modèle flexible représentatif du système, et l’usage de ce modèle pour la synthèse de lois de commande avancées intégrées au sein d’une structure cascade. Deux approches complémentaires fondées d’une part sur la commande prédictive de type GPC (Generalized Predictive Control), et d’autre part sur la commande Hinfini, sont considérées pour la synthèse de lois de commande à deux degrés de liberté, prédictives et robustes. Les performances de ces deux approches sont analysées et évaluées expérimentalement. Le deuxième objectif de sécurité est abordé à travers un algorithme de détection de collisions du robot avec son environnement, sans capteur d’effort et en présence d’incertitudes de modélisation. Afin de séparer efficacement les effets dynamiques des collisions de ceux des erreurs de modélisation, une stratégie adaptative de filtrage et de décision tenant compte de l’état du système est proposée. La validation expérimentale montre une très bonne sensibilité de détection, compatible avec les normes et les recommandations de sécurité relatives à la robotique collaborative. / The present thesis addresses the problem of motion control of flexible-joint robot manipulators using motor sensors only. The global objective is to guarantee tracking performance and robustness with respect to modeling uncertainties, together with safe human-robot interaction in a collaborative scenario where the robot and the human operator share the same workspace. The first objective of performance is achieved through the experimental identification of a flexible model of the system and the use of this model for the design of advanced control laws implemented in a cascade structure. Two complementary approaches, based either on predictive (Generalized Predictive Control, GPC) or Hinfinity control frameworks, are considered to design predictive and robust two degrees-of-freedom controllers. Experimental evaluation and analysis of the proposed strategies is provided. The second objective of safety is addressed by a novel algorithm for human-robot collision detection, without force sensors and in the presence of modeling uncertainties. In order to efficiently separate the dynamic effects of the collisions from the effects due to modeling errors, the proposed approach includes adaptive filtering and uses dynamic thresholds depending on the robot state. Experimental evaluation demonstrates a good detection sensitivity which is consistent with safety standards and recommendations for collaborative robotics.
|
8 |
Development of virtual reality tools for arthroscopic surgery training / Développement d'outils de réalité virtuelle pour l'enseignement de la chirurgie arthroscopiqueYaacoub, Fadi 12 November 2008 (has links)
The minimally invasive approach of arthroscopy means less pain and faster recovery time for patients compared to open surgery. However, it implies a high difficulty of performance. Therefore, surgeon should remain at a high level of technical and professional expertise to perform such operations. Surgeon’s skills are being developed over years of surgical training on animals, cadavers and patients. Nowadays, cadavers and animal specimens present an ethical problem also the practice on real humans is usually risky. For surgeons to reach a high level, new and alternative ways of performing surgical training are required. Virtual reality technology has opened new realms in the practice of medicine. Today, virtual reality simulators have become one of the most important training methods in the medical field. These simulators allow medical students to examine and study organs or any structure of the human body in ways that were not possible few years earlier. Similarly, the surgeon as well as the medical student can gain a valuable experience by performing a particular surgery with an anatomical accuracy and realism as it is actually performed in the real world. Thus, they can practice on virtual operation before they proceed and operate on real patients. In this thesis, a virtual reality training simulator for wrist arthroscopy is introduced. Two main issues are addressed: the 3-D reconstruction process and the 3-D interaction. Based on a sequence of CT images a realistic representation of the wrist joint is obtained suitable for the computer simulation. Two main components of the computer-based system interface are illustrated: the 3-D interaction to guide the surgical instruments and the user interface for haptic feedback. In this context, algorithms that model objects using the convex hull approaches and simulate real time exact collision detection between virtual objects are presented. A force feedback device, coupled with a haptic algorithm, is used as a haptic interface with the computer simulation system. This leads in the development of a low cost system with the same benefits as professional devices. In this regard, the wrist arthroscopy can be simulated and medical students can learn the basic skills required with safety, flexibility and less cost / La chirurgie arthroscopique présente actuellement un essor très important pour le bénéfice du plus grand nombre des patients. Cependant, cette technique possède un certain nombre d’inconvénients et il est donc nécessaire pour le médecin de s’entrainer et répéter ses gestes afin de pouvoir exécuter ce type d’opération d’une façon efficace et certaine. En effet, les méthodes traditionnelles d’enseignement de la chirurgie sont basées sur l’autopsie des cadavres et l’entrainement sur des animaux. Avec l’évolution de notre société, ces deux pratiques deviennent de plus en plus critiquées et font l’objet de réglementations très restrictives. Afin d’atteindre un niveau plus élevé, de nouveaux moyens d’apprentissage sont nécessaires pour les chirurgiens. Récemment, la réalité virtuelle commence d’être de plus en plus utilisée dans la médecine et surtout la chirurgie. Les simulateurs chirurgicaux sont devenus une des matières les plus récentes dans la recherche de la réalité virtuelle. Ils sont également devenus une méthode de formation et un outil d’entrainement valable pour les chirurgiens aussi bien que les étudiants en médecine. Dans ce travail, un simulateur de réalité virtuelle pour l’enseignement de la chirurgie arthroscopique, surtout la chirurgie du poignet, a été préesenté. Deux questions principales sont abordées : la reconstruction et l’interaction 3-D. Une séquence d’images CT a été traitée afin de générer un modèle 3-D du poignet. Les deux principales composantes de l’interface du système sont illustrées : l’interaction 3-D pour guider les instruments chirurgicaux et l’interface de l’utilisateur pour le retour d’effort. Dans ce contexte, les algorithmes qui modélisent les objets en utilisant les approches de “Convex Hull” et qui simulent la détection de collision entre les objets virtuels en temps réel, sont présentés. En outre, un dispositif de retour d’effort est utilisé comme une interface haptique avec le système. Cela conduit au développement d’un système à faible coût, avec les mêmes avantages que les appareils professionnels. A cet égard, l’arthroscopie du poignet peut être simulée et les étudiants en médecine peuvent facilement utiliser le système et peuvent apprendre les compétences de base requises en sécurité, flexibilité et moindre coût
|
9 |
Détection de Collision pour Environnements Large Échelle : Modèle Unifié et Adaptatif pour Architectures Multi-coeur et Multi-GPUAvril, Quentin 16 September 2011 (has links) (PDF)
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.
|
Page generated in 0.1126 seconds