Game Development Reference
Figure 17.14 Incorrect response calculation by penalty
In this chapter, we prepared a summary of collision detection and explained the four
phases of the process: identification of close objects, approximate search of the col-
lision, exact detection of the collision and then its processing. We mainly focused on
detection between polyhedral bodies. There are other approaches for more complex
geometries. We did not consider the problems of self-collisions, i.e. collision of a part
of a body with another part of the same body, which arise, for example, during a
deformation. The process of collision detection still remains expensive and unfortu-
nately not adequately robust. The current researches are trying to solve the problem of
managing the calculation time, either by compromising between calculation time and
accuracy, or by using dedicated hardware. Collision detection for deformable bodies
is also a highly active subject of research as this type of detection remains a bit slower
than the detection between rigid convex bodies. Finally, a lot of work still remains to
be completed before we find an algorithm that can be used on dedicated hardware.
Baciu, G., Sai-Keung, W. & Sun, H. (1999) Recode: An image-based collision detection
algorithm. Journal of Visualization and Computer Animation , 10, 181-192.
Bandi, S. & Thalmann, D. (1995) An adaptative spacial subdivision of the object space for
fast collision detection of animated rigid bodies. Computer Graphics Forum (Proceedings of
EUROGRAPHICS'95) , 14 (3), 259-270.
Baraff, D. (1990) Curved surfaces and coherence for non-penetrating rigid body simulation.
Computer Graphics (Proceedings of ACM SIGGRAPH 90) , 24 (4), 19-28.
Barequet, G., Chazelle, B., Guilbas, L., Mitchell, J. & Tal, A. (1996) Boxtree: A hier-
archical representation for surfaces in 3d. Computer Graphics Forum (Proceedings of
EUROGRAPHICS'96) , 15 (3), 387-396.
Bergen, G. (1998) Efficient collision detection of complex deformable models using aabb trees.
Journal of Graphics Tools , 2 (4), 1-14.
Bergen, G. (1999) A fast and robust GJK implementation for collision detection of convex
objects. Journal of Graphics Tools , 4 (2), 7-25.
Bergen, G. (2001) Proximity queries and penetration depth computation on 3d game objects.
In: Game Developers Conference .
Boyse, J.W. (1979) Interference detection among solids and surfaces. Communications ACM ,
22 (1), 3-9.