Collision detection in simulation can easily become a bottleneck due to its computationally intensive nature. Recent developments in graphics hardware, however, offer a viable solution for rapid and efficient collision detection. The authors propose a new two-phase technique using the latest graphics hardware. In the broad phase, a scene graph is created to partition objects in a 3D environment for initial collision checking. In the narrow phase, a multiple-viewing volumes method is used to detect interferences between a convex model and a model of arbitrary geometry. First, the convex model is used to define six viewing volumes. The convex and arbitrary models are then rendered respectively within the defined viewing volumes. Finally, results of collision detection can be easily achieved by querying the occlusions between these rendered models in the image space. Compared with other collision detection algorithms, this method produces promising results and is successfully applied in our 3D virtual reality games.
Arvo, J., & Kirk, D. (1989). A survey of ray tracing acceleration techniques. In A. Glassner (Ed.), An introduction to ray tracing (pp. 201-262). San Diego, CA: Academic Press.
2.
Baciu, G., & Wong, S-K. W. (1997). Rendering in object interference detection on conventional graphics workstations. Proceedings of the Fifth Pacific Conference on Computer Graphics and Applications.
3.
Baciu, G., Wong, S-K. W., et al. (1999). RECODE: An image-based collision detection algorithm. Journal of Visualization and Computer Animation, 10(4), 181-192.
4.
Bergen, G. (1999). A fast and robust GJK implementation for collision detection of convex objects. Journal of Graphics Tools, 4(2), 7-25.
5.
Cai, Y., Chui, C-K., et al. (2003). VR simulated training for less invasive vascular intervention. Computers & Graphics, 27(2), 215-221.
6.
Chazell, B., Dobkin, D. P., et al. (1997). Strategies for polyhedral surface decomposition: An experimental study. Computational Geometry: Theory and Applications, 7, 327-342.
7.
Cohen, J., Lin, M., et al. (1995). I-COLLIDE: An interactive and exact collision detection system for large-scale environments. Proceedings of the ACM Interactive 3D Graphics Conference.
8.
Ehmann, S., & Lin, M. (2001). Accurate and fast proximity queries between polyhedra using convex surface decomposition. Proceedings of Eurographics ’01.
9.
Gao, X-S., & Wang, D-K. (1992). On the automatic derivation of a set of geometric formulae. Mathematics Mechanization Research Preprints, 8, 26-37.
10.
Gottschalk, S., Lin, M., et al. (1996). OBB-tree: A hierarchical structure for rapid interference detection. Proceedings of ACM SIGGRAPH.
11.
Govindaraju, N. K., Redon, S., et al. (2003). CULLIDE: Interactive collision detection between complex models in large environments using graphics hardware. Proceedings of the Eurographics/SIGGRAPH Graphics Hardware Workshop.
12.
Hoff, K. E., III, Zaferakis, A., et al. (2001). Fast and simple 2D geometric proximity queries using graphics hardware. Proceedings of the ACM Symposium on Interactive 3D Graphics.
13.
Jiménez, P., Thomas, F., et al. (2001). Collision detection: A survey. Computers & Graphics, 25(2), 269-285.
14.
Kapur, D., Saxena, T., et al. (1994). Algebraic and geometric reasoning using Dixon resultants. Proceedings of the International Symposium on Symbolic and Algebraic Computation, Oxford, UK.
15.
Kilgrad, M. J. (2002). Graphics hardware functionality for geometric computations with OpenGL. Santa Clara, CA: NVIDIA Corporation.
16.
Kim, Y. J., Lin, M., et al. (2002). Fast penetration depth estimation using rasterization hardware and hierarchical refinement. Workshop on Algorithmic Foundations of Robotics (WAFR).
17.
Klosowski, J. T., Held, J. T., et al. (1998). Efficient collision detection using bounding volume hierarchies of k-DOPs. IEEE Trans. Visualization and Computer Graphics, 4(1), 21-37.
18.
Li, Z., Chui, C-K., et al. (2001). Computer environment for interventional neuroradiology procedures. Simulation & Gaming, 32(3), 404-419.
19.
Lin, M. C., & Gottschalk, S. (1998). Collision detection between geometric models: A survey. IMA Conference on Mathematics of Surfaces.
20.
Lombardo, J. C., Cani, M. P., et al. (1999). Real-time collision detection for virtual surgery. Computer Animation '99.
21.
Myszkowski, K., Okunev, O. G., et al. (1995). Fast collision detection between complex solids using rasterizing graphics hardware. The Visual Computer, 11(9), 497-512.
22.
Rossignac, J., Megahed, A., et al. (1992). Interactive inspection of solids: Cross-section and interferences. Computer & Graphics, 26(2), 353-360.
23.
Samet, H. (1989). Spatial data structures: Quadtree, Octrees and other hierarchical methods. Reading, MA: Addison-Wesley.
24.
Shinya, M., & Forgue, M. (1991). Interference detection through rasterization. Journal of Visualization and Computer Animation, 2, 131-134.
25.
Shpitalni, M., & Lipson, H. (1997). Automatic reasoning for design under geometric constraints. Annals of the CIRP, 46(1), 85-89.
26.
Vassilev, T., Spanlang, B., et al. (2001). Fast cloth animation on walking avatars. Computer Graphics Forum, 20(3), 260-267.
27.
Wynn, C. (2001). Using p-buffers for off-screen rendering in OpenGL. Santa Clara, CA: NVIDIA Corporation.
