“Continuous penalty forces” by Tang, Manocha, Otaduy and Tong

  • ©Min Tang, Dinesh Manocha, Miguel A. Otaduy, and Ruofeng Tong




    Continuous penalty forces



    We present a simple algorithm to compute continuous penalty forces to determine collision response between rigid and deformable models bounded by triangle meshes. Our algorithm computes a well-behaved solution in contrast to the traditional stability and robustness problems of penalty methods, induced by force discontinuities. We trace contact features along their deforming trajectories and accumulate penalty forces along the penetration time intervals between the overlapping feature pairs. Moreover, we present a closed-form expression to compute the continuous and smooth collision response. Our method has very small additional overhead compared to previous penalty methods, and can significantly improve the stability and robustness. We highlight its benefits on several benchmarks.


    1. Allard, J., Faure, F., Courtecuisse, H., Falipou, F., Duriez, C., and Kry, P. G. 2010. Volume contact constraints at arbitrary resolution. ACM Transactions on Graphics 29, 3. Google ScholarDigital Library
    2. Baraff, D., and Witkin, A. 1998. Large steps in cloth simulation. In Proc. of ACM SIGGRAPH, 43–54. Google ScholarDigital Library
    3. Barbič, J., and James, D. L. 2008. Six-DoF haptic rendering of contact between geometrically complex reduced deformable models. IEEE Transactions on Haptics 1, 1, 39–52. Google ScholarDigital Library
    4. Bridson, R., Fedkiw, R., and Anderson, J. 2002. Robust treament for collisions, contact and friction for cloth animation. In Proc. of ACM SIGGRAPH, 594–603. Google ScholarDigital Library
    5. Choi, K.-J., and Ko, H.-S. 2002. Stable but responsive cloth. In Proc. of ACM SIGGRAPH, 604–611. Google ScholarDigital Library
    6. Drumwright, E. 2008. A fast and stable penalty method for rigid body simulation. IEEE Transactions on Visualization and Computer Graphics 14 (January), 231–240. Google ScholarDigital Library
    7. Duriez, C., Andriot, C., and Kheddar, A. 2004. Signorini’s contact model for deformable objects in haptic simulations. In Proc. of IEEE Int’l Conf. Intelligent Robots and Systems, 3232–3237.Google Scholar
    8. Duriez, C., Dubois, F., Kheddar, A., and Andriot, C. 2006. Realistic haptic rendering of interacting deformable objects in virtual environments. IEEE Transactions on Visualization and Computer Graphics 12, 1, 36–47. Google ScholarDigital Library
    9. Ellis, R. E., Sarkar, N., and Jenkins, M. A. 1997. Numerical methods for the force reflection of contact. ASME Transactions on Dynamic Systems Measurement and Control 119, 4, 768–774.Google ScholarCross Ref
    10. Faure, F., Barbier, S., Allard, J., and Falipou, F. 2008. Image-based collision detection and response between arbitrary volumetric objects. In Proc. of ACM Siggraph/Eurographics Symp. on Computer Animation, 155–162. Google ScholarDigital Library
    11. Fisher, S., and Lin, M. C. 2001. Deformed distance fields for simulation of non-penetrating flexible bodies. In Proc. of Eurographic workshop on Computer animation & simulation, 99–111. Google ScholarDigital Library
    12. Harmon, D., Vouga, E., Smith, B., Tamstorf, R., and Grinspun, E. 2009. Asynchronous contact mechanics. In Proc. of ACM SIGGRAPH, 87:1–87:12. Google ScholarDigital Library
    13. Harmon, D., Zhou, Q., and Zorin, D. 2011. Asynchronous integration with phantom meshes. In Proceedings of the 2011 ACM SIGGRAPH/Eurographics Symposium on Computer Animation, SCA ’11, 247–256. Google ScholarDigital Library
    14. Hasegawa, S., and Sato, M. 2004. Real-time rigid body simulation for haptic interactions based on contact volume of polygonal objects. Computer Graphics Forum 23, 3, 529–538.Google ScholarCross Ref
    15. Heidelberger, B., Teschner, M., Keiser, R., Müller, M., and Gross, M. 2004. Consistent penetration depth estimation for deformable collision response. In Proc. of Vision, Modeling, Visualization, 339–346.Google Scholar
    16. Irving, G., Teran, J., and Fedkiw, R. 2004. Invertible finite elements for robust simulation of large deformation. In Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation, Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, SCA ’04, 131–140. Google ScholarDigital Library
    17. Mahvash, M., and Hayward, V. 2005. High-fidelty passive force-reflecting virtual environments. IEEE Transactions on Robotics 21, 1, 38–46. Google ScholarDigital Library
    18. Mirtich, B. 1996. Impulse-based Dynamic Simulation of Rigid Body Systems. Ph. D. thesis, Dept. Elec. Engin. Comput. Sci., Univ. California, Berkeley, CA. Google ScholarDigital Library
    19. Moore, M., and Wilhelms, J. 1988. Collision detection and response for computer animation. In Proc. of ACM SIGGRAPH, 289–298. Google ScholarDigital Library
    20. Ortega, M., Redon, S., and Coquillart, S. 2007. A six degree-of-freedom god-object method for haptic display of rigid bodies with surface properties. IEEE Transactions on Visualization and Computer Graphics 13, 458–469. Google ScholarDigital Library
    21. Otaduy, M. A., Tamstorf, R., Steinemann, D., and Gross, M. 2009. Implicit contact handling for deformable objects. In Proc. of Eurographics, 559–568.Google Scholar
    22. Pauly, M., Pai, D. K., and Guibas, L. J. 2004. Quasirigid objects in contact. In Proc. of the 2004 ACM SIGGRAPH/Eurographics Symp. Computer animation, 109–119. Google ScholarDigital Library
    23. Provot, X. 1997. Collision and self-collision handling in cloth model dedicated to design garment. Graphics Interface, 177–189.Google Scholar
    24. Redon, S., Kim, Y. J., Lin, M. C., and Manocha, D. 2004. Fast continuous collision detection for articulated models. In Proceedings of the ninth ACM symposium on Solid modeling and applications, 145–156. Google ScholarDigital Library
    25. Rengifo, C., Aoustin, Y., Chevallereau, C., and Plestan, F. 2009. A penalty-based approach for contact forces computation in bipedal robots. In Proc. of IEEE-RAS Int’l Conf. on Humanoid Robots, 121–127.Google Scholar
    26. Tang, M., Curtis, S., Yoon, S.-E., and Manocha, D. 2009. ICCD: Interactive continuous collision detection between deformable models using connectivity-based culling. IEEE Transactions on Visualization and Computer Graphics 15, 4, 544–557. Google ScholarDigital Library
    27. Teran, J., Sifakis, E., Irving, G., and Fedkiw, R. 2005. Robust quasistatic finite elements and flesh simulation. In Proc. of the ACM SIGGRAPH/Eurographics Symp. on Computer animation, 181–190. Google ScholarDigital Library
    28. Terzopoulos, D., Platt, J., Barr, A., and Fleischer, K. 1987. Elastically deformable models. In Proc. of ACM SIGGRAPH, 205–214. Google ScholarDigital Library
    29. Teschner, M., Kimmerle, S., Heidelberger, B., Zachmann, G., Raghupathi, L., Fuhrmann, A., p. Cani, M., Faure, F., Magnenat-thalmann, N., Strasser, W., and Volino, P. 2005. Collision detection for deformable objects. Computer Graphics Forum 24, 61–81.Google ScholarCross Ref
    30. Witkin, A., and Baraff, D. 1997. Physically based modeling: Principles and practice. SIGGRAPH 1997 Course.Google Scholar
    31. Wriggers, P., Vu Van, T., and Stein, E. 1990. Finite element formulation of large deformation impact-contact problems with friction. Computers & Structures 37, 3, 319–331.Google Scholar
    32. Wriggers, P. 2006. Computational Contact Mechanics, 2nd Edition. Springer.Google Scholar
    33. Yamane, K., and Nakamura, Y. 2006. Stable penalty-based model of frictional contacts. In Proc. of IEEE Int’l Conf. on Robotics and Automation, 1904–1909.Google Scholar
    34. Zhang, L., Kim, Y. J., Varadhan, G., and Manocha, D. 2007. Generalized penetration depth computation. Comput. Aided Des. 39, 625–638. Google ScholarDigital Library

ACM Digital Library Publication: