{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,28]],"date-time":"2026-03-28T08:19:07Z","timestamp":1774685947567,"version":"3.50.1"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2012,1,1]],"date-time":"2012-01-01T00:00:00Z","timestamp":1325376000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003561","name":"Ministry of Culture, Sports and Tourism","doi-asserted-by":"publisher","award":["2008-F-033-02"],"award-info":[{"award-number":["2008-F-033-02"]}],"id":[{"id":"10.13039\/501100003561","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002994","name":"Ministry of Knowledge Economy","doi-asserted-by":"publisher","award":["2008-F-033-02"],"award-info":[{"award-number":["2008-F-033-02"]}],"id":[{"id":"10.13039\/501100002994","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004085","name":"Ministry of Education, Science and Technology","doi-asserted-by":"publisher","award":["2009-0086684"],"award-info":[{"award-number":["2009-0086684"]}],"id":[{"id":"10.13039\/501100004085","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2012,1]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/2077341.2077346","type":"journal-article","created":{"date-parts":[[2012,2,22]],"date-time":"2012-02-22T18:42:36Z","timestamp":1329936156000},"page":"1-14","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":37,"title":["PolyDepth"],"prefix":"10.1145","volume":"31","author":[{"given":"Changsoo","family":"Je","sequence":"first","affiliation":[{"name":"Ewha Womans University and Sogang University, Seoul, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Min","family":"Tang","sequence":"additional","affiliation":[{"name":"Ewha Womans University, Seoul, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Youngeun","family":"Lee","sequence":"additional","affiliation":[{"name":"Ewha Womans University, Seoul, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Minkyoung","family":"Lee","sequence":"additional","affiliation":[{"name":"Ewha Womans University, Seoul, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Young J.","family":"Kim","sequence":"additional","affiliation":[{"name":"Ewha Womans University, Seoul, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,2,2]]},"reference":[{"key":"e_1_2_2_1_1","first-page":"227","article-title":"Penetration depth of two convex polytopes in 3D","volume":"7","author":"Agarwal P. K.","year":"2000","journal-title":"Nord. J. Comput."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1778765.1778819"},{"key":"e_1_2_2_3_1","volume-title":"Euclidean Geometry and Convexity","author":"Benson R. V."},{"key":"e_1_2_2_4_1","volume-title":"Proceedings of the Game Developers Conference.","author":"Bergen G.","year":"2001"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.1997.606761"},{"key":"e_1_2_2_6_1","volume-title":"Proceedings of the IEEE International Conference on Robotics and Automation. 591--596","author":"Cameron S. A."},{"key":"e_1_2_2_7_1","unstructured":"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.  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."},{"key":"e_1_2_2_8_1","doi-asserted-by":"crossref","unstructured":"Cottle R. Pang J. and Stone R. 2009. The Linear Complementarity Problem. SIAM.  Cottle R. Pang J. and Stone R. 2009. The Linear Complementarity Problem. SIAM.","DOI":"10.1137\/1.9780898719000"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01190153"},{"key":"e_1_2_2_10_1","volume-title":"Proceedings of the IEEE\/RSJ International Conference on Intelligent Robots and Systems.","author":"Fisher S."},{"key":"e_1_2_2_11_1","volume-title":"Matrix Computations","author":"Golub G. H.","edition":"3"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/882262.882358"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-008-9219-6"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/311535.311567"},{"key":"e_1_2_2_15_1","unstructured":"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.  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."},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0045-7825(97)00137-0"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45058-0_30"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2004.1260767"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/545261.545266"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1162\/105474603765879530"},{"key":"e_1_2_2_21_1","volume-title":"Proceedings of the IEEE International Conference on Robotics and Automation. 3719--3726","author":"Larsen E."},{"key":"e_1_2_2_22_1","doi-asserted-by":"crossref","volume-title":"Robot Motion Planning","author":"Latombe J.-C.","DOI":"10.1007\/978-1-4615-4022-9"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cagd.2008.06.006"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-00312-7_25"},{"key":"e_1_2_2_25_1","unstructured":"Lin M. and Manocha D. 2003. Collision and proximity queries. Handbook Discr. Comput. Geom. 787--807.  Lin M. and Manocha D. 2003. Collision and proximity queries. Handbook Discr. Comput. Geom. 787--807."},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cagd.2009.01.001"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/70.544772"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10055-004-0138-9"},{"key":"e_1_2_2_32_1","volume-title":"Proceedings of IEEE International Conference on Robotics and Automation. 11--15","author":"Redon S."},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1080\/2151237X.2006.10129216"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1179352.1142006"},{"key":"e_1_2_2_35_1","volume-title":"Proceedings of the IEEE International Conference on Robotics and Automation. 356--361","author":"Tang M."},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1531326.1531380"},{"key":"e_1_2_2_37_1","volume-title":"Proceedings of Robotics: Science and Systems Conference.","author":"Weller R."},{"key":"e_1_2_2_38_1","volume-title":"Proceedings of Robotics: Science and Systems Conference.","author":"Zhang L."},{"key":"e_1_2_2_39_1","first-page":"11","article-title":"Efficient cell labelling and path non-existence computation using c-obstacle query","volume":"27","author":"Zhang L.","year":"2008","journal-title":"Int. J. Robot. Res."},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2007.05.012"},{"key":"e_1_2_2_41_1","volume-title":"Proceedings of the IEEE International Conference on Robotics and Automation (ICRA). 3743--3750","author":"Zhang L."},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00371-006-0060-0"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1276377.1276396"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2077341.2077346","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2077341.2077346","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:54:46Z","timestamp":1750240486000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2077341.2077346"}},"subtitle":["Real-time penetration depth computation using iterative contact-space projection"],"short-title":[],"issued":{"date-parts":[[2012,1]]},"references-count":40,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,1]]}},"alternative-id":["10.1145\/2077341.2077346"],"URL":"https:\/\/doi.org\/10.1145\/2077341.2077346","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,1]]},"assertion":[{"value":"2010-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-02-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}