“PolyDepth: Real-Time Penetration-Depth Computation Using Iterative Contact-Space Projection” by Je, Tang, Lee, Lee and Kim

  • ©Changsoo Je, Min Tang, Youngeun Lee, Minkyoung Lee, and Young J. Kim

Conference:


Type:


Title:

    PolyDepth: Real-Time Penetration-Depth Computation Using Iterative Contact-Space Projection

Presenter(s)/Author(s):



Abstract:


    We present a real-time algorithm that finds the Penetration Depth (PD) between general polygonal models based on iterative and local optimization techniques. Given an in-collision configuration of an object in configuration space, we find an initial collision-free configuration using several methods such as centroid difference, maximally clear configuration, motion coherence, random configuration, and sampling-based search. We project this configuration on to a local contact space using a variant of continuous collision detection algorithm and construct a linear convex cone around the projected configuration. We then formulate a new projection of the in-collision configuration onto the convex cone as a Linear Complementarity Problem (LCP), which we solve using a type of Gauss-Seidel iterative algorithm. We repeat this procedure until a locally optimal PD is obtained. Our algorithm can process complicated models consisting of tens of thousands triangles at interactive rates.

References:


    Agarwal, P. K., Guibas, L. J., Har-peled, S., Rabinovitch, A., and Sharir, M. 2000. Penetration depth of two convex polytopes in 3D. Nord. J. Comput. 7, 227–240. Google ScholarDigital Library
    Allard, J., Faure, F., Courtecuisse, H., Falipou, F., Duriez, C., and Kry, P. G. 2010. Volume contact constraints at arbitrary resolution. ACM Trans. Graph. 29, 82:1–82:10. Google ScholarDigital Library
    Benson, R. V. 1966. Euclidean Geometry and Convexity. McGraw-Hill, New York.Google Scholar
    Bergen, G. 2001. Proximity queries and penetration depth computation on 3d game objects. In Proceedings of the Game Developers Conference.Google Scholar
    Cameron, S. 1997. Enhancing GJK: Computing minimum and penetration distance between convex polyhedra. In Proceedings of the International Conference on Robotics and Automation. 3112–3117.Google ScholarCross Ref
    Cameron, S. A. and Culley, R. K. 1986. Determining the minimum translational distance between two convex polyhedra. In Proceedings of the IEEE International Conference on Robotics and Automation. 591–596.Google Scholar
    Choi, Y.-K., Li, X., Rong, F., Wang, W., and Cameron, S. 2006. Computing the minimum directional distance between two convex polyhedra. HKU CS Tech. rep. TR-2006-01.Google Scholar
    Cottle, R., Pang, J., and Stone, R. 2009. The Linear Complementarity Problem. SIAM.Google Scholar
    Dobkin, D., Hershberger, J., Kirkpatrick, D., and Suri, S. 1993. Computing the intersection-depth of polyhedra. Algorithmica 9, 518–533.Google ScholarCross Ref
    Fisher, S. and Lin, M. C. 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.Google Scholar
    Golub, G. H. and Van Loan, C. F. 1996. Matrix Computations 3rd Ed. Johns Hopkins University Press, Baltimore, MD. Google ScholarDigital Library
    Guendelman, E., Bridson, R., and Fedkiw, R. 2003. Nonconvex rigid bodies with stacking. ACM Trans. Graph. 22, 3, 871–878. Google ScholarDigital Library
    Hachenberger, P. 2009. Exact Minkowski sums of polyhedra and exact and efficient decomposition of polyhedra into convex pieces. Algorithmica 55, 2, 329–345. Google ScholarDigital Library
    Hoff, K., Culver, T., Keyser, J., Lin, M., and Manocha, D. 1999. Fast computation of generalized Voronoi diagrams using graphics hardware. In Proceedings of ACM SIGGRAPH Conference. 277–286. Google ScholarDigital Library
    Hoff, K., Zaferakis, A., Lin, M., and Manocha, D. 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.Google Scholar
    Jourdan, F., Alart, P., and Jean, M. 1998. A Gauss-Seidel like algorithm to solve frictional contact problems. Comput. Methods Appl. Mechan. Engin. 155, 1-2, 31–47.Google ScholarCross Ref
    Kim, Y., Lin, M., and Manocha, D. 2004a. Fast penetration depth estimation using rasterization hardware and hierarchical refinement. In Algorithmic Foundations of Robotics V, Springer Tracts in Advanced Robotics, vol. 7, Springer, 505–522.Google ScholarCross Ref
    Kim, Y. J., Lin, M., and Manocha, D. 2004b. Incremental penetration depth estimation between convex polytopes using dual-space expansion. IEEE Trans. Vis. Comput. Graph. 10, 1, 152–164. Google ScholarDigital Library
    Kim, Y. J., Otaduy, M. A., Lin, M. C., and Manocha, D. 2002. Fast penetration depth computation for physically-based animation. In Proceedings of the ACM Symposium on Computer Animation. Google ScholarDigital Library
    Kim, Y. J., Otaduy, M. A., Lin, M. C., and Manocha, D. 2003. Six-degree-of-freedom haptic rendering using incremental and localized computations. Presence 12, 3, 277–295. Google ScholarDigital Library
    Larsen, E., Gottschalk, S., Lin, M., and Manocha, D. 2000. Fast distance queries with rectangular swept sphere volumes. In Proceedings of the IEEE International Conference on Robotics and Automation. 3719–3726.Google Scholar
    Latombe, J.-C. 1991. Robot Motion Planning. Kluwer Academic Publishers. Google ScholarDigital Library
    Lien, J.-M. 2008. Covering Minkowski sum boundary using points with applications. Comput. Aid. Geom. Des. 25, 8, 652–666. Google ScholarDigital Library
    Lien, J.-M. 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.Google ScholarCross Ref
    Lin, M. and Manocha, D. 2003. Collision and proximity queries. Handbook Discr. Comput. Geom. 787–807.Google Scholar
    Lin, M. C. 1993. Efficient collision detection for animation and robotics. Ph.D. thesis, University of California, Berkeley, CA. Google ScholarDigital Library
    Mirtich, B. V. 1996. Impulse-Based dynamic simulation of rigid body systems. Ph.D. thesis. Google ScholarDigital Library
    Nawratil, G., Pottmann, H., and Ravani, B. 2009. Generalized penetration depth computation based on kinematical geometry. Comput. Aided Geom. Des. 26, 425–443. Google ScholarDigital Library
    Ong, C. 1993. Penetration distances and their applications to path planning. Ph.D. thesis, Michigan University, Ann Arbor.Google Scholar
    Ong, C. J. and Gilbert, E. 1996. Growth distances: New measures for object separation and penetration. IEEE Trans. Robot. Autom. 12, 6, 888–903.Google ScholarCross Ref
    Redon, S. 2004. Fast continuous collision detection and handling for desktop virtual prototyping. Virtual Reality 8, 63–70. Google ScholarDigital Library
    Redon, S., Kheddar, A., and Coquillart, S. 2002. Gauss’ least constraints principle and rigid body simulations. In Proceedings of IEEE International Conference on Robotics and Automation. 11–15.Google Scholar
    Redon, S. and Lin, M. C. 2006. A fast method for local penetration depth computation. J. Graph. Tools 11, 2, 37–50.Google ScholarCross Ref
    Sud, A., Govindaraju, N., Gayle, R., Kabul, I., and Manocha, D. 2006. Fast proximity computation among deformable models using discrete Voronoi diagrams. In Proceedings of the ACM, SIGGRAPH. ACM, New York. 1144–1153. Google ScholarDigital Library
    Tang, M., Kim, Y. J., and Manocha, D. 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. Google ScholarDigital Library
    Tang, M., Lee, M., and Kim, Y. J. 2009b. Interactive Hausdorff distance computation for general polygonal models. ACM Trans. Graph. 28, 74:1–74:9. Google ScholarDigital Library
    Weller, R. and Zachmann, G. 2009. Inner sphere trees for proximity and penetration queries. In Proceedings of Robotics: Science and Systems Conference.Google Scholar
    Zhang, L., Kim, Y., and Manocha, D. 2007a. A fast and practical algorithm for generalized penetration depth computation. In Proceedings of Robotics: Science and Systems Conference.Google Scholar
    Zhang, L., Kim, Y., and Manocha, D. 2008. Efficient cell labelling and path non-existence computation using c-obstacle query. Int. J. Robot. Res. 27, 11-12, 1246–1257.Google Scholar
    Zhang, L., Kim, Y., Varadhan, G., and Manocha, D. 2007b. Generalized penetration depth computation. Comput.-Aid. Des. 39, 8, 625–638. Google ScholarDigital Library
    Zhang, L. and Manocha, D. 2008. An efficient retraction-based RRT planner. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA). 3743–3750.Google Scholar
    Zhang, X., Lee, M., and Kim, Y. J. 2006. Interactive continuous collision detection for non-convex polyhedra. Vis. Comput. 22, 749–760. Google ScholarDigital Library
    Zhang, X., Redon, S., Lee, M., and Kim, Y. J. 2007c. Continuous collision detection for articulated models using Taylor models and temporal culling. ACM Trans. Graph. 26, 3, 15. Google ScholarDigital Library


ACM Digital Library Publication:



Overview Page: