Kinetic bounding volume hierarchies for deformable objects

ABSTRACT

We present novel algorithms for updating bounding volume hierarchies of objects undergoing arbitrary deformations. Therefore, we introduce two new data structures, the kinetic AABB tree and the kinetic BoxTree.The event-based approach of the kinetic data structures framework enables us to show that our algorithms are optimal in the number of updates. Moreover, we show a lower bound for the total number of BV updates, which is independent of the number of frames.We used our kinetic bounding volume hierarchies for collision detection and performed a comparison with the classical bottom-up update method. The results show that our algorithms perform up to ten times faster in practically relevant scenarios.

REFERENCES

• 1: K P Agarwal , Micha Sharir, Davenport--Schinzel Sequences and Their Geometric Applications, Duke University, Durham, NC, 1995
• 2: Agarwal, P. K., Basch, J., Guibas, L. J., Hershberger, J., and Zhang, L. 2002. Deformable Free-Space Tilings for Kinetic Collision Detection. I. J. Robotic Res. 21, 3, 179--198.
• 3: Julien Basch , Leonidas J. Guibas , John Hershberger, Data structures for mobile data, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.747-756, January 05-07, 1997, New Orleans, Louisiana, United States
• 4: Bergen, G. V. D., 1998. Efficient Collision Detection of Complex Deformable Models using AABB Trees, Dec. 07.
• 5: Jeff Erickson , Leonidas J. Guibas , Jorge Stolfi , Li Zhang, Separation-sensitive collision detection for convex objects, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.327-336, January 17-19, 1999, Baltimore, Maryland, United States
• 6: Susan Fisher , Ming C. Lin, Deformed distance fields for simulation of non-penetrating flexible bodies, Proceedings of the Eurographic workshop on Computer animation and simulation, p.99-111, September 02-03, 2001, Manchester, UK
• 7: 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]
• 8: Naga K. Govindaraju , David Knott , Nitin Jain , Ilknur Kabul , Rasmus Tamstorf , Russell Gayle , Ming C. Lin , Dinesh Manocha, Interactive collision detection between deformable models using chromatic decomposition, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 9: Heidelberger, B., Teschner, M., and Gross, M. H. 2004. Detection of collisions and self-collisions using image-space techniques. In WSCG, 145--152.
• 10: Doug L. James , Dinesh K. Pai, BD-tree: output-sensitive collision detection for reduced deformable models, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 11: Klein, J., and Zachmann, G. 2003. Adb-trees: Controlling the error of time-critical collision detection. In Vision, Modeling and Visualisation 2003, Akademische Verlagsgesellschaft Aka GmbH, Berlin, T. Ertl, B. Girod, G. Greiner, H. Niemann, H.-P. Seidel, E. Steinbach, and R. Westermann, Eds., 37--46.
• 12: 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 ]
• 13: Knott, D., and Pai, D., 2003. Cinder: Collision and interference detection in real--time using graphics hardware.
• 14: Larsson, T., and Akenine-Moeller, T. 2003. Efficient collision detection for models deformed by morphing. The Visual Computer 19, 2-3 (June), 164--174.
• 15: Rynson W.H. Lau , Oliver Chan , Mo Luk , Frederick W.B. Li, LARGE a collision detection framework for deformable objects, Proceedings of the ACM symposium on Virtual reality software and technology, November 11-13, 2002, Hong Kong, China [doi>10.1145/585740.585760]
• 16: Ming Chieh Lin , John F. Canny, Efficient collision detection for animation and robotics, 1993
• 17: Mezger, J., Kimmerle, S., and Etzmuss, O. 2003. Hierarchical Techniques in Collision Detection for Cloth Animation. Journal of WSCG 11, 2, 322--329.
• 18: Palmer, I. J., and Grimsdale, R. L. 1995. Collision detection for animation using sphere-trees. j-CGF 14, 2 (June), 105--116.
• 19: Provot, X. 1997. Collision and self-collision handling in cloth model dedicated to design garments. 177--189.
• 20: Speckmann, B. 2001. Kinetic Data Structures for Collision Detection. PhD thesis.
• 21: Teschner, M., Kimmerle, S., Heidelberger, B., Zachmann, G., Raghupathi, L., Fuhrmann, A., Cani, M.-P., Faure, F., Magnenat-Thalmann, N., Strasser, W., and Volino, P. 2005. Collision detection for deformable objects. Computer Graphics forum 24, 1 (Mar.), 61--81.
• 22: 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
• 23: Wingo Sai-Keung Wong , George Baciu, Dynamic Interaction between Deformable Surfaces and Nonsmooth Objects, IEEE Transactions on Visualization and Computer Graphics, v.11 n.3, p.329-340, May 2005 [doi>10.1109/TVCG.2005.44]
• 24: Wingo Sai-Keung Wong , George Baciu, GPU-based intrinsic collision detection for deformable surfaces: Collision Detection and Deformable Objects, Computer Animation and Virtual Worlds, v.16 n.3-4, p.153-161, July 2005 [doi>10.1002/cav.v16:3/4]
• 25: Zachmann, G., and Weller, R. 2006. Kinetic bounding volume hierarchies for collision detection of deformable objects. Tech. Rep. IfI-06-02, TU-Clausthal.
• 26: Zachmann, G. 1995. The boxtree: Exact and fast collision detection of arbitrary polyhedra. In SIVE Workshop, 104--112.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Virtual reality; Animation