Collision detection in volumetric subdivisions

La détection de collision dans des scènes complexes est un processus crucial dans les simulations physiques et les applications temps-réel. Si des performances suffisantes sont obtenues pour des scènes statiques, les approches classiques atteignent leurs limites lorsque la complexité des scènes augmente et lorsque les objets représentés deviennent déformables. Nous présentons dans cette thèse une approche générique, efficace et précise pour la détection de la collision dans le cadre de la simulation d'opérations chirurgicales. Les mobiles sont représentés par des maillages en déplacement dans un environnement déformable. Leurs sommets sont suivis dans une subdivision volumique convexe de cet espace environnant. Des particules sont continuellement lancées le long des arêtes des maillages pour détecter les collisions et suivre les contacts entre les mobiles et leur environnement. Cette méthode est couplée à un mécanisme de prédiction exploitant la cohérence temporelle et les relations d'adjacences topologiques pour réduire le nombre de tests géométriques nécessaires. Notre méthode gère la subdivision dynamique des mobiles et des zones de contact. Elle permet également de gérer efficacement les modifications géométriques et topologiques de l'environnement, telles que des coupures ou des déchirures, ou plus généralement l'ajout ou la suppression de matière. Nous expérimentons des simulations physiques basées sur la méthode des masse-ressort et du shape-matching et analysons les performances de notre méthode. Nous comparons également notre approche aux méthodes classiques basées sur des structures hiérarchiques.Collision detection in complex scenes is a critical process required for physical simulations and real-time applications. If good performance are achieved for static scenes, classical approaches reach their limits when the scene complexity increase and when the objects are deformable. We present a generic, efficient and accurate approach for collision detection which is adapted for surgery simulation. The moving objects are represented as meshes moving inside a deformable environment. The vertices are followed in a convex volumetric subdivision of the surrounding space. Particles are spanned along the edges of the meshes to detect collision and follow the contacts occuring between the moving object and its environment. This method is coupled with a forecast mechanism using temporal consistency and topological adjacency relation to reduce the required geometrical tests. Our method handles the dynamic subdivision of both the moving object and the contact area. It also allows to handle efficiently geometrical and topological changes of the environment, such as cuts, tears, or more generally any add or removal of material. We experiment physical simulation based on mass-spring and shape-matching physical models and analyse the performance of our method. We also compare our approach with classical methods based on a hierarchical structure