Detection de collisions en temps reel entre surfaces NURBS deformables

Video games have reached a new level of realism. Programmable shading, 3D physics simulation and curved surfaces will soon become standard features. Real time collision detection, needed for this kind of application, is a difficult problem where the research is always active. This document presents a survey of the current collision detection algorithms for different object representations. Then, a new algorithm for interactive collision detection between deformable NURBS surfaces is described. This algorithm is intended to be used in real time applications, which need fast, but not exact, collision detection. There are almost no collision detection algorithms dealing with parametric surfaces in real time. Moreover, parametric surfaces are used in an increasing number of games. These reasons motivated the choice of this research avenue.; This new algorithm works by creating oriented bounding boxes (or OBB) hierarchies with the surface control points. It then tests them for overlapping. If the test detects an overlap, the surfaces are subdivided into smaller NURBS surfaces and the algorithm is called recursively on these new surfaces. It stops when a certain precision level is reached, that is user definable as a function of the application. The results are the world space coordinates of the contact point, and the (u, v) parametric coordinates on both surfaces.; The use of OBB allows for fast and effective overlapping tests. The construction of an OBB with the surface's control points is simple and leads to a tight fitting bounding volume, which is the key of this fast collision detection algorithm. As boxes are only computed when needed, the algorithm uses a small amount of memory and can be used with deformable surfaces without any overhead. (Abstract shortened by UMI.)...