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

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.

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