David Cazier Collision
Retour à la page de David Cazier
Détections des collisions
La recherche de collisions entre les primitives d'une scène dépend de manière quadratique du nombre de primitives présentes. L'accélération des calculs passe souvent par l'utilisation de hiérarchies de boites englobantes (AABB, OBB, k-DOP). Le but est de partitionner l'espace en cellules réduites dans lesquelles un nombre restreint de primitives se trouvent simultanément. Certains travaux utilisent une partition fixe de l'environnement qui se déforme avec la simulation (notamment pour la simulation d'endoscopies ou d'angioscopies). Aucun de ces travaux ne supporte de changements dans la topologie de la scène (découpe, suture, suppression de matière).
Nous avons proposé un nouveau système de détection de collisions, permettant de suivre les déplacements de maillages quelconques (particules, courbes ou surfaces) au sein de scènes complexes et déformables. L'environnement dans lequel les mobiles se déplacent est décomposé en polyèdres convexes et modélisé par une 3-carte. Nous obtenons ainsi une partition volumique de la scène qui s'adapte naturellement à ses propres déformations lors de la simulation et supporte un large éventail de transformations topologiques en temps réel.
Nous avons proposé un mécanisme de prédiction permettant de suivre le déplacement de sommets dans l'environnement et exploitant la cohésion temporelle et spatiale de la simulation. Son efficacité est assurée par la structure combinatoire des 3-cartes et leur décomposition implicite en tétraèdres orientés optimisant le nombre de tests géométriques à effectués 3-JCD09, 4-JCD09. Ce système supporte naturellement les déformations de l'environnement et des mobiles, et permet une gestion très efficace des changements topologiques grâce à des opérateurs locaux impliquant un nombre contrôlé de mises à jour.
Ces résultats ont été étendus au suivi d'arêtes des maillages en déplacement 4-JCD10, 4-JCD10a. Leurs mouvements sont décomposés en déplacements élémentaires formant des triangles qui balayent l'espace environnant. En utilisant des arguments géométriques sur la convexité de ces déplacements et des cellules parcourues, il est possible d'obtenir une information de collision ou de contact précise, avec peu de calculs supplémentaires. Nous avons ainsi pu expérimenter notre système avec deux types de simulations temps réel très contraignantes : l'insertion d'un cathéter dans un réseaux vasculaire déformable et le déplacement de solides déformables dans un environnement lui-même déformable et dont la topologie change.
Voir la galerie vidéo pour des exemples de simulations.