Oriented convex polyhedra for collision detection in 3D computer animation

ABSTRACT

This paper presents a method for fast-approximate collision detection between 3D models S undergoing rigid body motion. To enclose a 3D model in as tight as possible, we propose an approach known as oriented convex polyhedra R(S). By surrounding the 3D models tightly, the veracity of detected collision can be improved. It is known that the large number of empty corners which belongs to any 3D bounding volumes B(S) can affect the truthfulness of collision detection. Therefore, we describe a way to compute R(S) using intersection of a set of halfspaces. The directions of these halfspaces are generated from calculating covariance matrix. To acquire the tightest R(S) as possible, we have improved the quality of abutting corners by implementing similar approach as Tribox Bounds method. In our case, improvements of abutting corners are important since the generated intersection points will be used for intersection testing. To detect collision between R(S), we utilize local space of R(S) and perform a straightforward approach by simply checking its interval pairs. Our proposed approach was implemented and we perform a number of comparisons in terms of time and recorded collision with other B(S). From the conducted tests, R(S) performs well and might be a possible choice for detecting collisions of the 3D models undergoing rigid body motion.

REFERENCES

• 1: Ulf Assarsson , Tomas Möller, Optimized view frustum culling algorithms for bounding boxes, Journal of Graphics Tools, v.5 n.1, p.9-22, Sept. 2000
• 2: Bade, A. and Away, Yuwaldi. 2004.Bounding Volumes Approaches in Collision Detection: Requirements and advantages. 2nd National Conference on Computer Graphics and Multimedia 2004 (CoGRAMM04), Kuala Lumpur, Malaysia.
• 3: Gino Van Den Bergen , Gino Johannes Bergen, Collision Detection, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2003
• 4: Gino van den Bergen, Efficient collision detection of complex deformable models using AABB trees, Journal of Graphics Tools, v.2 n.4, p.1-13, April 1997
• 5: Chin-Shyurng, F. and Jui-Lung, W. 1999. Efficient Time-Interrupted and Time-Continuous Collision Detection Among Polyhedral Objects in Arbitrary Motion. Journal Of Information Science and Engineering 15, 769--799 (1999).
• 6: Crosnier, A., Rossignac, J. 1999. Tribox bounds for three-dimensional objects. Computers & Graphics 23 (3): 429--437.
• 7: Christer Ericson, Real-Time Collision Detection (The Morgan Kaufmann Series in Interactive 3-D Technology) (The Morgan Kaufmann Series in Interactive 3D Technology), Morgan Kaufmann Publishers Inc., San Francisco, CA, 2004
• 8: Eberly. D. 2002. Dynamic Collision Detection Using Oriented Bounding Boxes. Geometric Tools Inc. Chapel Hill, North Carolina. http://www.geometrictools.com.
• 9: Funfzig, C. and. Fellner, D. 2003. Easy realignment of k-Dop Bounding Volumes. Proceeding of Graphics Interface 2003, pages 257--264.
• 10: S. Gottschalk , M. C. Lin , D. Manocha, OBBTree: a hierarchical structure for rapid interference detection, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.171-180, August 1996 [doi>10.1145/237170.237244]
• 11: Stefan Aric Gottschalk , Dinesh Manocha , Ming C. Lin, Collision queries using oriented bounding boxes, 2000
• 12: Philip M. Hubbard, Collision Detection for Interactive Graphics Applications, IEEE Transactions on Visualization and Computer Graphics, v.1 n.3, p.218-230, September 1995 [doi>10.1109/2945.466717]
• 13: Dan Halperin , Micha Sharir, New bounds for lower envelopes in three dimensions, with applications to visibility in terrains, Proceedings of the ninth annual symposium on Computational geometry, p.11-18, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.160989]
• 14: Timothy L. Kay , James T. Kajiya, Ray tracing complex scenes, Proceedings of the 13th annual conference on Computer graphics and interactive techniques, p.269-278, August 1986
• 15: James Thomas Klosowski , Joseph S. Mitchell, Efficient collision detection for interactive three-dimensional graphics and virtual environments, 1998
• 16: James T. Klosowski , Martin Held , Joseph S. B. Mitchell , Henry Sowizral , Karel Zikan, Efficient Collision Detection Using Bounding Volume Hierarchies of k-DOPs, IEEE Transactions on Visualization and Computer Graphics, v.4 n.1, p.21-36, January 1998 [doi>10.1109/2945.675649]
• 17: Konecny, Petr. 1998. Bounding Volumes in Computer Graphics. MSc Thesis, Faculty of Informatics, Masaryk Universitiy, Brno, Czech Republic.
• 18: Lahanas. M, K. Thorsten, Milickovic. N, Karouzakis. K, Baltas. D. and Zamboglou. N. 2000. Optimized Bounding Boxes for Three-Dimensional Treatment Planning in Brachytherapy. Medical Physics, vol. 27, no. 10, pp. 2333--2342.
• 19: Larsson, T., Akenine-Möller, T. 2003. Strategies for Bounding Volume Hierarchy Updates for Ray Tracing of Deformable Models. MRTC Report, ISSN 1404--3041 ISRN MDH-MRTC-92/2003-1-SE.
• 20: Tomas Möller , Eric Haines, Real-time rendering, A. K. Peters, Ltd., Natick, MA, 1999
• 21: Matthew Moore , Jane Wilhelms, Collision detection and response for computer animationr3, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.289-298, Aug. 1988
• 22: Müller, G., Schäfer. S. and Fellner, D. 1999. A Rapid Clustering Algorithm for Efficient Rendering. Eurographics Association, ISSN 1017--4656.
• 23: G. Zachmann, Rapid Collision Detection by Dynamically Aligned DOP-Trees, Proceedings of the Virtual Reality Annual International Symposium, p.90, March 14-18, 1998

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Animation

Keywords:
bounding volumes, collision detection, virtual environments