Fast penetration depth computation for physically-based animation

ABSTRACT

We present a novel and fast algorithm to compute penetration depth (PD) between two polyhedral models for physically-based animation. Given two overlapping polyhedra, it computes the minimal translation distance to separate them using a combination of object-space and image-space techniques. The algorithm computes pairwise Minkowski sums of decomposed convex pieces and performs a closest point query using rasterization hardware. It uses bounding volume hierarchies, object-space and image-space culling algorithms to further accelerate the computation and refines the estimated PD in a hierarchical manner. We demonstrate its application to contact response computation and a time-stepping method for dynamic simulation.

REFERENCES

• 1: Pankaj K. Agarwal , Leonidas J. Guibas , Sariel Har-Peled , Alexander Rabinovitch , Micha Sharir, Penetration depth of two convex polytopes in 3D, Nordic Journal of Computing, v.7 n.3, p.227-240, Fall 2000
• 2: David Baraff, Dynamic simulation of nonpenetrating rigid bodies, Cornell University, Ithaca, NY, 1992
• 3: David Baraff, Fast contact force computation for nonpenetrating rigid bodies, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.23-34, July 1994 [doi>10.1145/192161.192168]
• 4: BARBER, B., DOBKIN, D., AND HUHDANPAA, H. 1993. The quickhull algorithm for convex hull. Tech. Rep. GCG53, The Geometry Center, MN.
• 5: BERGEN, G. 2001. Proximity queries and penetration depth computation on 3D game objects. Game Developers Conference.
• 6: CAMERON, S., AND CULLEY, R. K. 1986. Determining the minimum translational distance between two convex polyhedra. Proceedings of International Conference on Robotics and Automation, 591-596.
• 7: CAMERON, S. 1997. Enhancing GJK: Computing minimum and penetration distance between convex polyhedra. Proceedings of International Conference on Robotics and Automation, 3112-3117.
• 8: Bernard Chazelle , David P. Dobkin , Nadia Shouraboura , Ayellet Tal, Strategies for polyhedral surface decomposition: an experimental study, Computational Geometry: Theory and Applications, v.7 n.5-6, p.327-342, April 1997 [doi>10.1016/S0925-7721(96)00024-7]
• 9: DOBKIN, D., HERSHBERGER, J., KIRKPATRICK, D., AND SURI, S. 1993. Computing the intersection-depth of polyhedra. Algorithmica 9, 518-533.
• 10: EHMANN, S., AND LIN, M. C. 2001. Accurate and fast proximity queries between polyhedra using convex surface decomposition. Computer Graphics Forum (Proc. of Eurographics'2001) 20, 3.
• 11: EPSTEIN, D., JANSEN, F., AND ROSSIGNAC, J. 1989. Z-buffering rendering from CSG: The trickle algorithm. Tech. rep., IBM Research Report RC15182.
• 12: 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
• 13: GILBERT, E. G., JOHNSON, D. W., AND KEERTHI, S. S. 1988. A fast procedure for computing the distance between objects in three-dimensional space. IEEE J. Robotics and Automation vol RA-4, 193-203.
• 14: Jack Goldfeather , Jeff P M Hultquist , Henry Fuchs, Fast constructive-solid geometry display in the pixel-powers graphics system, Proceedings of the 13th annual conference on Computer graphics and interactive techniques, p.107-116, August 1986
• 15: 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]
• 16: Arthur Gregory , Ajith Mascarenhas , Stephen Ehmann , Ming Lin , Dinesh Manocha, Six degree-of-freedom haptic display of polygonal models, Proceedings of the conference on Visualization '00, p.139-146, October 2000, Salt Lake City, Utah, United States
• 17: GUIBAS, L., AND SEIDEL, R. 1987. Computing convolutions by reciprocal search. Discrete Comput. Geom 2, 175-193.
• 18: Kenneth E. Hoff, III , John Keyser , Ming Lin , Dinesh Manocha , Tim Culver, Fast computation of generalized Voronoi diagrams using graphics hardware, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.277-286, July 1999 [doi>10.1145/311535.311567]
• 19: Kenneth E. Hoff, III , Andrew Zaferakis , Ming Lin , Dinesh Manocha, Fast and simple 2D geometric proximity queries using graphics hardware, Proceedings of the 2001 symposium on Interactive 3D graphics, p.145-148, March 2001 [doi>10.1145/364338.364383]
• 20: 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]
• 21: KAUL, A., AND ROSSIGNAC, J. 1992. Solid-interpolating deformations: construction and animation of pips. Computer and Graphics 16, 107-116.
• 22: KIM, Y. J., LIN, M. C., AND MANOCHA, D. 2002. DEEP: Dual-space Expansion for Estimating Penetration depth between convex polytopes. In IEEE Conference on Robotics and Automation.
• 23: KIM, Y. J., OTADUY, M. A., LIN, M. C., AND MANOCHA, D. 2002. Fast penetration depth computation using rasterization hardware and hierarchical refinement. Tech. rep. TR02-014, UNC-Chapel Hill.
• 24: 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]
• 25: LIN, M., AND CANNY, J. F. 1991. Efficient algorithms for incremental distance computation. In IEEE Conference on Robotics and Automation, 1008-1014.
• 26: Michael McKenna , David Zeltzer, Dynamic simulation of autonomous legged locomotion, ACM SIGGRAPH Computer Graphics, v.24 n.4, p.29-38, Aug. 1990
• 27: William A. McNeely , Kevin D. Puterbaugh , James J. Troy, Six degree-of-freedom haptic rendering using voxel sampling, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.401-408, July 1999 [doi>10.1145/311535.311600]
• 28: Brian Mirtich , John Canny, Impulse-based simulation of rigid bodies, Proceedings of the 1995 symposium on Interactive 3D graphics, p.181-ff., April 09-12, 1995, Monterey, California, United States [doi>10.1145/199404.199436]
• 29: Brian Mirtich, V-Clip: fast and robust polyhedral collision detection, ACM Transactions on Graphics (TOG), v.17 n.3, p.177-208, July 1998 [doi>10.1145/285857.285860]
• 30: Brian Mirtich, Timewarp rigid body simulation, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.193-200, July 2000 [doi>10.1145/344779.344866]
• 31: Matthew Moore , Jane Wilhelms, Collision detection and response for computer animationr3, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.289-298, Aug. 1988
• 32: ONG, C. J., AND GILBERT, E. 1996. Growth distances: New measures for object separation and penetration. IEEE Transactions on Robotics and Automation 12, 6.
• 33: Jarek Rossignac , Abe Megahed , Bengt-Olaf Schneider, Interactive inspection of solids: cross-sections and interferences, ACM SIGGRAPH Computer Graphics, v.26 n.2, p.353-360, July 1992
• 34: STEWART, D. E., AND TRINKLE, J. C. 1996. An implicit time-stepping scheme for rigid body dynamics with inelastic collisions and Coulomb friction. International Journal of Numerical Methods in Engineering 39, 2673-2691.
• 35: THEOHARIS, T., PAPAIANNOU, G., AND KARABASSI, E. 2001. The magic of the Z-buffer: A survey. Proc. of 9th International Conference on Computer Graphics, Visualization and Computer Vision, WSCG.
• 36: WIEGAND, T. F. 1996. Interactive rendering of CSG models. Computer Graphics Forum 15, 4, 249-261.
• 37: WITKIN, A., AND BARAFF, D. 1997. Physically Based Modeling: Principles and Practice. ACM Press. Course Notes of ACM SIGGRAPH.

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: Visible line/surface algorithms

Keywords:
collision detection, dynamics simulation, geometric modeling, graphics hardware, image-space computations, robotics