“Interactive Generalized Penetration Depth Computation for Rigid and Articulated Models Using Object Norm” by Tang and Kim

  • ©Min Tang and Young J. Kim

Conference:


Type:


Title:

    Interactive Generalized Penetration Depth Computation for Rigid and Articulated Models Using Object Norm

Session/Category Title: Animating Characters

Presenter(s)/Author(s):


Moderator(s):


Abstract:


    We present a novel, real-time algorithm to accurately approximate the generalized penetration depth (PDg) between two overlapping rigid or articulated models. Given the high complexity of computing PDg, our algorithm approximates PDg based on iterative, constrained optimization on the contact space, defined by the overlapping objects. The main ingredient of our algorithm is a novel and general formulation of distance metric, the object norm, in a configuration space for articulated models, and a compact closed-form solution for it. Then, we perform constrained optimization, by linearizing the contact constraint, and minimizing the object norm under such a constraint. In practice, our algorithm can compute locally optimal PDg for rigid or articulated models consisting of tens of thousands of triangles in tens of milliseconds. We also suggest three applications using PDg computation: retraction-based motion planning, physically-based animation, and data-driven grasping.

References:


    1. P. K. Agarwal, L. J. Guibas, S. Har-Peled, A. Rabinovitch, and M. Sharir. 2000. Penetration depth of two convex polytopes in 3d. Nordic J. Comput. 7, 227–240.
    2. J. Allard, F. Faure, H. Courtecuisse, F. Falipou, C. Duriez, and P. G. Kry. 2010. Volume contact constraints at arbitrary resolution. ACM Trans. Graph. 29, 4.
    3. J. Baumgarte. 1972. Stabilization of constraints and integrals of motion in dynamical systems. Comput. Methods Appl. Mech. Engin. 1, 1, 1–16.
    4. G. Bergen. 2001. Proximity queries and penetration depth computation on 3d game objects. In Proceedings of the Game Developers Conference.
    5. S. Cameron. 1997. Enhancing gjk: Computing minimum and penetration distance between convex polyhedra. In Proceedings of the International Conference on Robotics and Automation. 3112–3117.
    6. S. A. Cameron and R. K. Culley. 1986. Determining the minimum translational distance between two convex polyhedra. In Proceedings of the IEEE International Conference on Robotics and Automation. 591–596.
    7. E. Catto. 2005. Iterative dynamics with temporal coherence. In Proceedings of the Game Developers Conference.
    8. D. Dobkin, J. Hershberger, D. Kirkpatrick, and S. Suri. 1993. Computing the intersection-depth of polyhedra. Algorithmica 9, 518–533.
    9. S. Fisher and M. C. Lin. 2001. Fast penetration depth estimation for elastic bodies using deformed distance fields. In Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems.
    10. C. Goldfeder, M. Ciocarlie, H. Dang, and P. K. Allen. 2009. The columbia grasp database. In International Conference on Robotics and Automation.
    11. P. Hachenberger. 2009. Exact minkowksi sums of polyhedra and exact and efficient decomposition of polyhedra into convex pieces. Algorithmica 55, 2, 329–345.
    12. G. D. Hart, B. M. Riviere, and G. D. Hart. 2002. A constraint-stabilized time-stepping approach for rigid multibody dynamics with joints, contact and friction. In Proceedings of the International Journal for Numerical Methods in Engineering. 2335–2371.
    13. M. Hofer and H. Pottmann. 2004. Energy-minimizing splines in manifolds. In Proceedings of the ACM SIGGRAPH Conference.
    14. K. Hoff, A. Zaferakis, M. Lin, and D. Manocha. 2002. Fast 3d geometric proximity queries between rigid and deformable models using graphics hardware acceleration. Tech. rep. TR02-004. Department of Computer Science, University of North Carolina.
    15. C. Je, M. Tang, Y. Lee, M. Lee, and Y. Kim. 2012. PolyDepth: Real-time penetration depth computation using iterative contact-space projection. ACM Trans. Graph. 31, 1.
    16. F. Jourdan, P. Alart, and M. Jean. 1998. A gauss-seidel like algorithm to solve frictional contact problems. Comput. Methods Appl. Mech. Engin. 155, 1–2, 31–47.
    17. K. Kazerounian and J. Rastegar. 1992. Object norms: A class of coordinate and metric independent norms for displacement. In Proceedings of the ASME Design Engineering Technical Conference.
    18. Y. J. Kim, M. C. Lin, and D. Manocha. 2004. Incremental penetration depth estimation between convex polytopes using dual-space expansion. IEEE Trans. Vis. Comput. Graph. 10, 1, 152–164.
    19. Y. J. Kim, M. A. Otaduy, M. C. Lin, and D. Manocha. 2002. Fast penetration depth computation for physically-based animation. In Proceedings of the ACM Symposium on Computer Animation.
    20. Y. J. Kim, M. A. Otaduy, M. C. Lin, and D. Manocha. 2003. Six-degree-of-freedom haptic rendering using incremental and localized computations. Presence 12, 3, 77–295.
    21. J. J. Kuffner and S. M. LaValle. 2000. RRT-Connect: An efficient approach to single-query path planning. In Proceedings of the IEEE International Conference on Robotics and Automation.
    22. E. Larsen, S. Gottschalk, M. C. Lin, and D. Manocha. 2000. Fast proximity queries with swept sphere volumes. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA’00). 3719–3726.
    23. J. Lien. 2008. Covering minkowski sum boundary using points with applications. Comput. Aided Geom. Des. 25, 8, 652–666.
    24. J. Lien. 2009. A simple method for computing minkowski sum boundary in 3d using collision detection. In Algorithmic Foundation of Robotics VIII, G. Chirikjian, H. Choset, M. Morales, and T. Murphey, Eds., Springer Tracts in Advanced Robotics, vol. 57, Springer, 401–415.
    25. B. Mirtich. 1996. Impulse-based dynamic simulation of rigid body systems. Ph.D. dissertation, University of California, Berkeley.
    26. M. Moore and J. Wilhelms. 1988. Collision detection and response for computer animation. In Proceedings of the 15th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH’88). J. Dill, Ed., 289–298.
    27. G. Nawratil, H. Pottmann, and B. Ravani. 2009. Generalized penetration depth computation based on kinematical geometry. Comput. Aided Geom. Des. 26, 4, 425–443.
    28. C. J. Ong. 1993. Penetration distances and their applications to path planning. Ph.D. dissertation, Michigan University, Ann Arbor.
    29. C. J. Ong and E.G. Gilbert. 1996. Growth distances: New measures for object separation and penetration. IEEE Trans. Robotics Automation 12, 6, 888–903.
    30. M. Ortega, S. Redon, and S. Coquillart. 2007. A six degree-of-freedom god-object method for haptic display of rigid bodies with surface properties. IEEE Trans. Vis. Comput. Graph. 13, 3, 458–469.
    31. M. A. Otaduy, R. Tamstorf, D. Steinemann, and M. Gross. 2009. Implicit contact handling for deformable objects. Comput. Graph. Forum 28, 2.
    32. J. Pan, L. Zhang, and D. Manocha. 2010. Retraction-based rrt planner for articulated models. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA’10).
    33. S. Redon, A. Kheddar, and S. Coquillart. 2002. Gauss’ least constraints principle and rigid body simulations. In Proceedings of the IEEE International Conference on Robotics and Automation. 11–15.
    34. S. Redon and M. Lin. 2005. Practical local planning in the contact space. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA’05).
    35. S. Redon and M. C. Lin. 2006. A fast method for local penetration depth computation. J. Graph. Tools 11, 2, 7–50.
    36. D. C. Ruspini and O. Khatib. 1997. Collision/contact models for the dynamic simulation of complex environments. In Proceedings of the 9th International Symposium of Robotics Research.
    37. H. Schmidl, N. Walker, and M. C. Lin. 2004. CAB: Fast update of obb trees for collision detection between articulated bodies. J. Graph. Tools 9, 1–9.
    38. A. Sud, N. Govindaraju, R. Gayle, I. Kabul, and D. Manocha. 2006. Fast proximity computation among deformable models using discrete voronoi diagrams. In Proceedings of the ACM SIGGRAPH Papers. 1144–1153.
    39. M. Tang, Y. J. Kim, and D. Manocha. 2009a. C2A: Controlled conservative advancement for continuous collision detection of polygonal models. In Proceedings of the IEEE International Conference on Robotics and Automation. 356–361.
    40. M. Tang, M. Lee, and Y. J. Kim. 2009b. Interactive hausdorff distance computation for general polygonal models. ACM Trans. Graph. 28, 3.
    41. B. Wang, F. Faure, and D. K. Pai. 2012. Adaptive Image-based intersection volume. ACM Trans. Graph. 31, 4.
    42. R. Weller and G. Zachmann. 2009. Inner sphere trees for proximity and penetration queries. In Proceedings of the Robotics: Science and Systems Conference.
    43. L. Zhang, Y. J. Kim, and D. Manocha. 2007a. A fast and practical algorithm for generalized penetration depth computation. In Proceedings of Robotics: Science and Systems Conference.
    44. L. Zhang, Y. J. Kim, and D. Manocha. 2007b. C-DIST: Efficient distance computation for rigid and articulated models in configuration space. In Proceedings of the ACM Solid and Physical Modeling Conference (SPM’07).
    45. L. Zhang, Y. J. Kim, and D. Manocha. 2008. Efficient cell labelling and path non-existence computation using c-obstacle query. Int. J. Robotics Res. 27, 11–12, 1246–1257.
    46. L. Zhang, Y. J. Kim, G. Varadhan, and D. Manocha. 2007c. Generalized penetration depth computation. Comput.-Aid. Des. 39, 8, 625–638.
    47. L. Zhang and D. Manocha. 2008. An efficient retraction-based rrt planner. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA’08). 3743–3750.
    48. X. Zhang, S. Redon, M. Lee, and Y. J. Kim. 2007d. Continuous collision detection for articulated models using taylor models and temporal culling. ACM Trans. Graph. 26, 3.

ACM Digital Library Publication:


Overview Page: