La détection des collisions au sein d’environnements virtuels denses

L’industrie

   Ce premier domaine d’application est très certainement le plus prédisposé à la mis en place d’outils de simulation interactive. En effet, c’est à plusieurs niveaux que ces outils peuvent être introduits et s’avérer efficaces. Ci-dessous, nous dressons une liste des différentes tâches concernées.
Conception La phase de prototypage consiste à contrôler la validité des ensembles de pièces constituant le produit final en termes de (dé)montabilité. Jusqu’à présent, cette phase nécessite la fabrication de maquettes physiques fidèles aux côtes spécifiées au niveau de la conception (CAO), afin de pouvoir valider manuellement la pertinence de l’ensemble et élaborer les trajectoires de montage. Ce mode opératoire s’avère souvent coûteux et contraignant, que ce soit en termes de temps ou de coûts, la fabrication des maquettes étant souvent sous-traitée à des sociétés annexes. Dans ce cas précis, la simulation interactive va s’avérer être un outil particulièrement adapté, puisqu’elle va permettre à l’opérateur de vérifier la validité de l’ensemble via l’utilisation d’une maquette numérique au sein de laquelle seront directement injectées les informations issues de la CAO. Ainsi, l’opérateur va pouvoir manipuler à sa guise les différents éléments d’un ensemble en prenant en considération les contraintes liées à la géométrie et la cinématique de celui-ci. De plus, dans le cas où des modifications s’avèreraient nécessaires, la maquette numérique pourra dans tous les cas être directement modifiée afin de correspondre au nouvel ensemble ; contrairement à une maquette physique sur laquelle des opérations de rectification vont être à effectuer, voir un ré usinage complet. La figure 1.1 illustre ce type d’application. On y observe un opérateur interagissant avec un environnement virtuel via deux interfaces haptiques. La plateforme présentée permet une immersion visuelle de ce dernier grâce à une restitution stéréoscopique active réalisée sur un système de type bi-plan. L’opérateur, dont la position de la tête est traquée en temps réel, peut à sa guise modifier son point de vue afin d’apprécier au mieux la pertinence des gestes qu’il élabore quant à la réalisation de la tâche étudiée (Dans ce cas précis : l’assemblage du système de motorisation de la vitre à l’intérieur d’une portière de Laguna II RENAULT)
Formation et entraînement La formation est une composante nécessaire à la mise en place d’une chaîne de fabrication, particulièrement dans le cadre de grandes séries. Elle s’avère également nécessaire dans d’autres domaines tels que la maintenance. Le but de la formation est de permettre aux différents intervenants de réaliser au mieux les tâches qui leur sont imparties afin d’améliorer non seulement leur productivité, mais également leur confort. La réalité virtuelle va permettre de simuler virtuellement ces phases de fabrication ou de maintenance. Ainsi, sur un site équipé des calculateurs et des interfaces sensorielles adéquates, les opérateurs vont pouvoir être formés à tous les gestes techniques sans avoir à immobiliser le site réel d’intervention. De plus, le formateur va bénéficier d’outils lui permettant d’agir sur l’environnement virtuel et ainsi faciliter l’apprentissage de ses élèves. Plus généralement, la réalité virtuelle va permettre l’élaboration de simulations interactives visant à enseigner ou parfaire les gestes et techniques nécessaires à un opérateurs dans un contexte donné. Aussi, plusieurs simulateurs sont déjà opérationnels quant à la formation de pilotes d’avions ou encore d’astronautes.
Ergonomie Des critères ergonomiques sont souvent considérés dans le cadre de l’élaboration de produits industriels. Le but de ces derniers est de faciliter l’utilisation du produit en prenant en considération des propriétés propres à l’utilisateur final. Là encore, les simulations interactives peuvent s’avérer très utiles, particulièrement en mode immersif. En effet, le concepteur va pouvoir directement prendre en considération l’ergonomie du produit via une représentation naturelle de celui-ci. Il n’est plus contraint d’utiliser des maquettes physiques.

Principes de fonctionnement d’une simulation interactive

   La réalité virtuelle immersive (RV) consiste en la simulation interactive du monde réel au sein d’un environnement numérique. Elle est fonctionnellement décomposable en deux parties (Figure 1.4). La première, que nous nommerons moteur physique, est assimilable à un logiciel. Elle a pour fonction de régir en temps réel l’évolution des entités de l’environnement virtuel selon les lois de la physique, ainsi que leurs interactions. Deux types d’interactions peuvent être identifiés : celles liées aux contraintes cinématiques inter-objets, assimilables à des liaisons mécaniques (pivot, prismatique,. . .), et celles inhérentes aux collisions entre ces derniers. La seconde composante d’une plate-forme RV consiste en l’interfaçage de l’environnement virtuel avec le ou les opérateurs participant à la simulation. Il existe plusieurs types d’interfaces, chacune destinée à la stimulation d’un des sens du ou des opérateurs, on parle d’interfaces visuelles, auditives et haptiques.

Décomposition spatiale régulière

   Cette première approche consiste à réaliser la décomposition spatiale suivant une grille régulière allignée sur les axes principaux (figure 2.2) [Tur89]. Les zones obtenues, assimilables à des cubes, sont communément appelées voxels. Bien que dans le cadre de cette première approche la décomposition spatiale soit triviale, plusieurs difficultés sont observables quant à la mise en œuvre de l’algorithme. La première, d’ordre purement algorithmique, est de mettre à jour les listes d’appartenance des objets aux différentes zones de l’espace de façon suffisamment performante pour remplir les contraintes de temps inhérentes à une simulation temps réel. Une deuxième difficulté réside dans le dimensionnement des voxels. En effet, une décomposition voxélique trop fine risquerait d’engendrer un nombre de tests d’appartenance trop important et, a contrario, une décomposition trop grossière ne s’avérera pas suffisamment sélective pour réduire sensiblement le nombre de paires d’objets à considérer. Aussi, le choix des paramètres de discrétisation sera généralement conditionné par différents critères tels que le nombre d’objets contenus dans la scène, leur taille, leur répartition et leur cinématique.

Types de volumes englobants

   Plusieurs types de géométries peuvent être utilisés dans le cadre de cette décomposition de l’objet. Les plus communément utilisés sont les sphères [RKS01], les boîtes isothétiques (AABB : Axis Aligned Bounding Boxes) [LAM01] et les boîtes englobantes orientées (OBB : Oriented Bounding Boxes) [GLM96]. D’autres types de volumes englobant plus sophistiqués ont été proposés tels que les polytopes à orientation discrète (k-dops) [KHM+98], les tribox [CR99] ou encore les enveloppes convexes. Chacun de ces types de volumes englobants se voit plus ou moins adapté en fonction de la géométrie considérée et du niveau de performance escompté. Ainsi, les sphères englobantes ont pour principal avantage la simplicité des tests de chevauchement . En effet, un test de chevauchement entre deux sphères se limite à une comparaison entre la distance séparant leur centre et la somme de leurs rayons respectifs. Cependant, les sphères donnent généralement une approximation moins optimale de la géométrie considérée, en comparaison avec les OBBs par exemple qui, malgré des tests de chevauchement beaucoup plus lourds (théorème des 15 axes séparateurs [GLM96]), limitent l’exécution de tests non-pertinents de par un volume englobé minimal. Avec la figure 2.6, nous proposons une illustration de ce phénomène

Hiérarchies de volumes englobants

  Comme expliqué précédemment, les approches utilisant des hiérarchies de volumes englobants consistent en une décomposition hiérarchique des objets de la scène. En se basant sur les décompositions ainsi obtenues, plusieurs tests d’intersections donnant lieu à des descentes récursives des hiérarchies permettent d’isoler les paires de zones au sein desquelles des collisions sont susceptibles d’avoir lieu. Ces techniques permettent ainsi de réduire de manière importante la combinatoire considérée lors de la phase d’identification des contacts, améliorant sensiblement les performances du processus. Dans le cas rigide, le positionnement relatif des primitives qui composent les objets au sein de leur repère de construction n’évoluent pas durant la simulation. Dans ce contexte, il n’est pas nécessaire de mettre à jour les hiérarchies de volumes englobants. Ceci n’est pas vrai dans le cas déformable. En effet, une déformation est assimilable au déplacement de tout ou partie des composantes d’un objet dans son repère de construction. Aussi, dans le cadre de simulation d’objets déformables, l’utilisation d’approches basées sur des hiérarchies de volumes englobants nécessite une mise à jour régulière de ces dernières, en fonction de l’évolution de la forme des objets simulés. Il est à noter que le temps nécessaire à ces mises à jour vient s’additionner à la durée du processus global de détection des collisions et qu’il doit, par conséquent, se voir minimisé.

Table des matières

Introduction générale
Position du problème et contexte
Contributions principales
Organisation du mémoire
1 La réalité virtuelle : Enjeux et Limites 
1.1 Introduction
1.2 Domaines d’application et enjeux 
1.2.1 L’industrie
1.2.2 La médecine
1.3 Concepts de base 
1.3.1 Principes de fonctionnement d’une simulation interactive
1.3.2 Fonctionnement d’un moteur physique
1.4 Conclusion et discussion 
2 Détection des collisions : Etat de l’art 
2.1 Introduction
2.2 Gestion de la complexité géométrique 
2.2.1 Subdivision spatiale
2.2.2 Critères topologiques et cinématiques
2.2.3 L’approche projective
2.2.4 Hiérarchies de volumes englobants
2.2.5 Multirésolution
2.2.6 Accélération matérielle
2.3 Détection des collisions entre corps déformables
2.3.1 Hiérarchies de volumes englobants
2.3.2 Subdivision spatiale
2.3.3 Approches stochastiques
2.4 Adaptation du processus de détection des collisions en fonction des propriétés géométriques des objets simulés
2.4.1 Détection des collisions en mode discret
2.4.2 Problématique des objets concaves
2.4.3 Détection de collisions au sein d’environnements hétérogènes
2.5 Notion de cohérence spatio-temporelle 
2.6 Conclusions
3 Les algorithmes évolutionnaires : Concepts fondamentaux 
3.1 Introduction
3.2 Principes généraux et notations
3.2.1 Notations
3.2.2 Schéma de fonctionnement
3.3 Représentation des individus
3.3.1 Génotype d’un individu
3.3.2 Phénotype et qualité d’un individu
3.4 Opérateurs de variation 
3.4.1 Notions d’exploration et d’exploitation
3.4.2 Opérateurs de mutation
3.4.3 Opérateurs de croisement
3.5 Processus de sélection 
3.5.1 Sélection déterministe
3.5.2 Sélection stochastique
3.6 Notions avancées 
3.6.1 Composition de la solution : L’approche parisienne
3.6.2 Maintien de la diversité génétique
3.6.3 Parallélisation : Méthodes de sous-populations
3.7 Conclusions 
4 Application des algorithmes évolutionnaires à la détection de collisions
4.1 Introduction : De Darwin à la détection de collisions 
4.2 Représentation des individus 
4.2.1 Définition générique
4.2.2 Représentation génotypique
4.2.3 Représentation phénotypique
4.2.4 Evaluation de la qualité
4.3 Opérateurs de variation 
4.3.1 Opérateurs d’exploration
4.3.2 Opérateurs d’exploitation
4.3.3 Opérateurs de croisement
4.4 Maintien de la diversité génétique 
4.4.1 Le partage appliqué à ESPIONS
4.4.2 Carte de densité
4.4.3 Nouvelle expression de la fonction fitness
4.5 Schémas de fonctionnement
4.5.1 Schéma de fonctionnement classique
4.5.2 Fonctionnement d’ESPIONS : une évolution perpétuelle
4.5.3 Schémas d’intégration d’ESPIONS
4.5.4 Parallélisation du processus ESPIONS
4.6 Discussion concernant la cohérence spatio-temporelle 
4.7 Conclusion 
5 Analyse expérimentale d’ESPIONS et implémentations dans un contexte applicatif 
5.1 Introduction : ESPIONS, de la théorie à la pratique 
5.2 Etude expérimentale de l’algorithme ESPIONS
5.2.1 Caractéristiques de l’algorithme
5.2.2 Déroulement des expériences
5.2.3 Effets des opérateurs de variation
5.2.4 Effets du partage
5.2.5 Effets du nombre d’individus
5.2.6 Discussion et conclusions
5.3 Couplage d’ESPIONS avec un module déterministe de détection des collisions 
5.3.1 Le module client : LMD++
5.3.2 Fonctionnement du couplage LMD++ / ESPIONS
5.3.3 Résultats obtenus
5.3.4 Discussion
5.4 Couplage d’ESPIONS avec un module de simulation d’objets déformables 
5.4.1 Le module client
5.4.2 Fonctionnement du couplage
5.4.3 Résultats obtenus
5.4.4 Discussion
5.5 Parallélisation d’ESPIONS 
5.5.1 Procédure expérimentale
5.5.2 Résultats expérimentaux
5.5.3 Discussions
Conclusions et perspectives
Conclusion générale
Récapitulatif
Perspectives
A Architecture de l’algorithme ESPIONS

Télécharger le rapport complet