Détection continue de collisions entre triangles et fonctions distance signée en temps réel

Pelletier-Guénette, Joël (2025). Détection continue de collisions entre triangles et fonctions distance signée en temps réel. Mémoire de maîtrise électronique, Montréal, École de technologie supérieure.

Prévisualisation

PDF Télécharger (1MB) | Prévisualisation

Résumé

De l’entrainement virtuel de pilotes et de chirurgiens à l’optimisation de trajectoire, en passant par l’esquive d’obstacles en temps réel pour l’aérospatial ou la robotique, plusieurs systèmes modernes dépendent de simulations physiques en temps réel. La détection précise et robuste des collisions est au cœur des simulations physiques utiles à ces domaines. Elle est toutefois extrêmement difficile à effectuer dans les applications en temps réel. La bonne représentation des objets simulés a un impact direct sur le réalisme et sur l’efficacité avec laquelle nous pouvons simuler divers phénomènes physiques. Ce mémoire introduit des solutions efficaces pour la détection de collision de haute qualité entre des maillages de triangles et des fonctions distance signée (SDF). Le problème de détection continue des collisions (CCD) est abordé comme un problème d’optimisation spatio-temporel cherchant le moment exact d’impact (TOI) entre un triangle et l’isosurface d’une SDF. Cette méthode est plus robuste que les précédentes, qui se basent sur l’échantillonnage par points, et plus performante que les méthodes de pointes pour la détection discrète des collisions (DCD) triangle-SDF. Une méthode de raffinement adaptatif est aussi proposée pour fournir efficacement de l’information supplémentaire lors de collisions avec de grands triangles. Cela permet l’utilisation de géométrie efficace pour réduire le coût de la détection de collision. Une comparaison avec des algorithmes de pointe expose les capacités et les avantages de l’approche proposée par la simulation de milliers de scénarios difficiles avec collisions. Les résultats expérimentaux démontrent que ce travail de recherche améliore la qualité des simulations physiques tout en maintenant la performance nécessaire au temps réel. Dans l’ensemble, ce travail fournit la première méthode fonctionnelle pour la CCD triangle-SDF robuste en temps réel, et ouvre la porte à un grand nombre de nouvelles applications potentielles pour la simulation physique, particulièrement quand de petits objets aux mouvements rapides interagissent.

Titre traduit

Real-time continuous collision detection between triangles and signed distance functions

Résumé traduit

From virtual training for surgeons and pilots to live obstacle avoidance and trajectory optimization in aerospace and robotics, many modern systems rely on real-time physics simulations. Accurate and robust collision detection is key for useful simulations. Yet, it is excessively difficult to achieve in real-time applications. The proper modelling of objects directly affects the realism of physics-based simulations and how efficiently we can simulate physical phenomena. This thesis introduces efficient solutions for high-quality collision detection between triangle meshes and signed distance functions (SDFs). The continuous collision detection (CCD) problem is tackled with a novel spatio-temporal optimization to seek the exact time of impact (TOI) between a triangle and an SDF isosurface. This method offers improved robustness over existing point sampling methods, and outperforms recent triangle-SDF discrete collision detection (DCD) algorithms. Also proposed, is a novel adaptive refinement method to efficiently provide supplemental contact information over large triangles. Efficient coarse geometry can thus be used to reduce the cost of collision detection involving triangle meshes. A comparison against state-of-the-art algorithms is provided, and exposes the capabilities and advantages of the proposed approach through simulating thousands of difficult collision scenarios. Experimental results demonstrate that this work improves the quality of physics simulations while maintaining real-time performance. Overall, this work provides the first working method for robust triangle SDF CCD, and opens the door to a wide array of new potential applications for physics-based simulations where small and fast moving objects interact.

Type de document:	Mémoire ou thèse (Mémoire de maîtrise électronique)
Renseignements supplémentaires:	"Mémoire par articles présenté à l’École de technologie supérieure comme exigence partielle à l'obtention de la maîtrise avec mémoire en génie des technologies de l'information". Comprend des références bibliographiques (pages 45-48).
Mots-clés libres:	infographie, simulation physique, détection de collisions, fonction distance signée, analyse numérique
Directeur de mémoire/thèse:	Directeur de mémoire/thèse Andrews, Sheldon
Programme:	Maîtrise en ingénierie > Génie des technologies de l'information
Date de dépôt:	24 févr. 2026 18:12
Dernière modification:	24 févr. 2026 18:12
URI:	https://espace.etsmtl.ca/id/eprint/3785

Gestion Actions (Identification requise)

Dernière vérification avant le dépôt