{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T03:12:10Z","timestamp":1767237130784,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":57,"publisher":"ACM","license":[{"start":{"date-parts":[[2014,7,27]],"date-time":"2014-07-27T00:00:00Z","timestamp":1406419200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2014,7,27]]},"DOI":"10.1145\/2614028.2615399","type":"proceedings-article","created":{"date-parts":[[2014,7,28]],"date-time":"2014-07-28T13:21:45Z","timestamp":1406553705000},"page":"1-81","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":24,"title":["Navigation meshes and real-time dynamic planning for virtual worlds"],"prefix":"10.1145","author":[{"given":"Marcelo","family":"Kallmann","sequence":"first","affiliation":[{"name":"University of California Merced"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mubbasir","family":"Kapadia","sequence":"additional","affiliation":[{"name":"Disney Research Zurich"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,7,27]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/336154.336206"},{"key":"e_1_3_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/566654.566606"},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/MRA.2008.921540"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1982.58"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574703"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/323233.323261"},{"volume-title":"Computational geometry: algorithms and applications","author":"De Berg M.","key":"e_1_3_2_2_7_1","unstructured":"De Berg , M. , Cheong , O. , and van Kreveld , M. 2008. Computational geometry: algorithms and applications . Springer . De Berg, M., Cheong, O., and van Kreveld, M. 2008. Computational geometry: algorithms and applications. Springer."},{"volume-title":"AAAI'06: Proceedings of the 21st national conference on Artificial intelligence, AAAI Press, 942--947","author":"Demyen D.","key":"e_1_3_2_2_8_1","unstructured":"Demyen , D. , and Buro , M . 2006. Efficient triangulation-based pathfinding . In AAAI'06: Proceedings of the 21st national conference on Artificial intelligence, AAAI Press, 942--947 . Demyen, D., and Buro, M. 2006. Efficient triangulation-based pathfinding. In AAAI'06: Proceedings of the 21st national conference on Artificial intelligence, AAAI Press, 942--947."},{"volume-title":"Proceedings of the 5th Workshop Algorithm Engineering and Experiments, 37--44","author":"Devillers O.","key":"e_1_3_2_2_9_1","unstructured":"Devillers , O. , and Pion , S . 2003. Efficient exact geometric predicates for delaunay triangulations . In Proceedings of the 5th Workshop Algorithm Engineering and Experiments, 37--44 . Devillers, O., and Pion, S. 2003. Efficient exact geometric predicates for delaunay triangulations. In Proceedings of the 5th Workshop Algorithm Engineering and Experiments, 37--44."},{"volume-title":"Proceedings of the IEEE International Conference on Robtics and Automation, IEEE, ICRA.","author":"Garcia F.","key":"e_1_3_2_2_10_1","unstructured":"Garcia , F. , Kapadia , M. , and Badler , N. I . 2014. Gpu-based dynamic search on adaptive resolution grids . In Proceedings of the IEEE International Conference on Robtics and Automation, IEEE, ICRA. Garcia, F., Kapadia, M., and Badler, N. I. 2014. Gpu-based dynamic search on adaptive resolution grids. In Proceedings of the IEEE International Conference on Robtics and Automation, IEEE, ICRA."},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2010.5509263"},{"key":"e_1_3_2_2_12_1","doi-asserted-by":"crossref","unstructured":"Gochev K. Cohen B. J. Butzke J. Safonova A. and Likhachev M. 2011. Path planning with adaptive dimensionality. In SOCS.  Gochev K. Cohen B. J. Butzke J. Safonova A. and Likhachev M. 2011. Path planning with adaptive dimensionality. In SOCS .","DOI":"10.1109\/ICRA.2012.6225228"},{"key":"e_1_3_2_2_13_1","first-page":"100","article-title":"A formal basis for the heuristic determination of minimum cost paths. Systems Science and Cybernetics","volume":"4","author":"Hart P.","year":"1968","unstructured":"Hart , P. , Nilsson , N. , and Raphael , B. 1968 . A formal basis for the heuristic determination of minimum cost paths. Systems Science and Cybernetics , IEEE Transactions on 4 , 2, 100 -- 107 . Hart, P., Nilsson, N., and Raphael, B. 1968. A formal basis for the heuristic determination of minimum cost paths. Systems Science and Cybernetics, IEEE Transactions on 4, 2, 100--107.","journal-title":"IEEE Transactions on"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(94)90010-8"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795289604"},{"key":"e_1_3_2_2_16_1","unstructured":"Hjelle O. and D\u00e6hlen M. 2006. Triangulations and Applications (Mathematics and Visualization). Springer-Verlag New York Inc. Secaucus NJ USA.   Hjelle O. and D\u00e6hlen M. 2006. Triangulations and Applications (Mathematics and Visualization) . Springer-Verlag New York Inc. Secaucus NJ USA."},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/336154.336226"},{"volume-title":"Proceedings of the IEEE International Conference on Robtics and Automation, IEEE, ICRA '14","author":"Huang T.","key":"e_1_3_2_2_18_1","unstructured":"Huang , T. , Kapadia , M. , Badler , N. I. , and Kallmann , M . 2014. Path planning for coherent and persistent groups . In Proceedings of the IEEE International Conference on Robtics and Automation, IEEE, ICRA '14 . Huang, T., Kapadia, M., Badler, N. I., and Kallmann, M. 2014. Path planning for coherent and persistent groups. In Proceedings of the IEEE International Conference on Robtics and Automation, IEEE, ICRA '14."},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25090-3_30"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/1948395.1948426"},{"key":"e_1_3_2_2_21_1","volume-title":"Proceedings of the Eurographics \/ SIGGRAPH Symposium on Computer Animation (SCA).","author":"Kallmann M.","year":"2010","unstructured":"Kallmann , M. 2010 . Shortest paths with arbitrary clearance from navigation meshes . In Proceedings of the Eurographics \/ SIGGRAPH Symposium on Computer Animation (SCA). Kallmann, M. 2010. Shortest paths with arbitrary clearance from navigation meshes. In Proceedings of the Eurographics \/ SIGGRAPH Symposium on Computer Animation (SCA)."},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2580947"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"crossref","unstructured":"Kapadia M. and Badler N. I. 2013. Navigation and steering for autonomous virtual humans. Wiley Interdisciplinary Reviews: Cognitive Science.  Kapadia M. and Badler N. I. 2013. Navigation and steering for autonomous virtual humans. Wiley Interdisciplinary Reviews: Cognitive Science .","DOI":"10.1002\/wcs.1223"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1507149.1507185"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCG.2011.68"},{"key":"e_1_3_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00371-011-0669-5"},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2485895.2485909"},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2522628.2522654"},{"key":"e_1_3_2_2_29_1","first-page":"1","article-title":"ADAPT: The agent development and prototyping testbed","volume":"99","author":"Kapadia M.","year":"2014","unstructured":"Kapadia , M. , Marshak , N. , and Badler , N. I. 2014 . ADAPT: The agent development and prototyping testbed . IEEE Transactions on Visualization and Computer Graphics 99 , 1 . Kapadia, M., Marshak, N., and Badler, N. I. 2014. ADAPT: The agent development and prototyping testbed. IEEE Transactions on Visualization and Computer Graphics 99, 1.","journal-title":"IEEE Transactions on Visualization and Computer Graphics"},{"volume-title":"National Conf. on AI, AAAI, 476--483","author":"Koenig S.","key":"e_1_3_2_2_30_1","unstructured":"Koenig , S. , and Likhachev , M . 2002. D* Lite . In National Conf. on AI, AAAI, 476--483 . Koenig, S., and Likhachev, M. 2002. D* Lite. In National Conf. on AI, AAAI, 476--483."},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/566570.566605"},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2004.00782.x"},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2009.01405.x"},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230140304"},{"key":"e_1_3_2_2_35_1","unstructured":"Likhachev M. Gordon G. J. and Thrun S. 2003. ARA*: Anytime A* with Provable Bounds on Sub-Optimality. In NIPS.  Likhachev M. Gordon G. J. and Thrun S. 2003. ARA * : Anytime A * with Provable Bounds on Sub-Optimality. In NIPS ."},{"key":"e_1_3_2_2_36_1","unstructured":"Likhachev M. Ferguson D. I. Gordon G. J. Stentz A. and Thrun S. 2005. Anytime Dynamic A*: An Anytime Replanning Algorithm. In ICAPS 262--271.  Likhachev M. Ferguson D. I. Gordon G. J. Stentz A. and Thrun S. 2005. Anytime Dynamic A*: An Anytime Replanning Algorithm. In ICAPS 262--271."},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/70.466615"},{"key":"e_1_3_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/359156.359164"},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/2421731.2421751"},{"key":"e_1_3_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2012.149"},{"key":"e_1_3_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01530888"},{"key":"e_1_3_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/160985.161156"},{"volume-title":"Proceedings of the IEEE\/RSJ International Conference on Intelligent Robots and Systems, IEEE, IROS '13","author":"Mubbasir Kapadia","key":"e_1_3_2_2_43_1","unstructured":"Mubbasir Kapadia , Francisco Garcia, C. D. B., and Badler , N. I . 2013. Dynamic search on the gpu . In Proceedings of the IEEE\/RSJ International Conference on Intelligent Robots and Systems, IEEE, IROS '13 . Mubbasir Kapadia, Francisco Garcia, C. D. B., and Badler, N. I. 2013. Dynamic search on the gpu. In Proceedings of the IEEE\/RSJ International Conference on Intelligent Robots and Systems, IEEE, IROS '13."},{"key":"e_1_3_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.5555\/1624562.1624607"},{"key":"e_1_3_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2522628.2522900"},{"key":"e_1_3_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cag.2013.03.004"},{"key":"e_1_3_2_2_47_1","unstructured":"Recast 2014. Recast navigation mesh. https:\/\/github.com\/memononen\/recastnavigation.  Recast 2014. Recast navigation mesh. https:\/\/github.com\/memononen\/recastnavigation."},{"key":"e_1_3_2_2_48_1","series-title":"Lecture Notes in Computer Science","volume-title":"Triangle: Engineering a 2d quality mesh generator and delaunay triangulator. In Applied Computational Geometry: Towards Geometric Engineering","author":"Shewchuk J. R.","year":"1996","unstructured":"Shewchuk , J. R. 1996 . Triangle: Engineering a 2d quality mesh generator and delaunay triangulator. In Applied Computational Geometry: Towards Geometric Engineering , M. C. Lin and D. Manocha, Eds., vol. 1148 of Lecture Notes in Computer Science . Springer-Verlag , May, 203--222. From the First ACM Workshop on Applied Computational Geometry. Shewchuk, J. R. 1996. Triangle: Engineering a 2d quality mesh generator and delaunay triangulator. In Applied Computational Geometry: Towards Geometric Engineering, M. C. Lin and D. Manocha, Eds., vol. 1148 of Lecture Notes in Computer Science. Springer-Verlag, May, 203--222. From the First ACM Workshop on Applied Computational Geometry."},{"key":"e_1_3_2_2_49_1","first-page":"3","article-title":"Adaptive precision floating-point arithmetic and fast robust geometric predicates","volume":"18","author":"Shewchuk J. R.","year":"1997","unstructured":"Shewchuk , J. R. 1997 . Adaptive precision floating-point arithmetic and fast robust geometric predicates . Discrete & Computational Geometry 18 , 3 (Oct.), 305--363. Shewchuk, J. R. 1997. Adaptive precision floating-point arithmetic and fast robust geometric predicates. Discrete & Computational Geometry 18, 3 (Oct.), 305--363.","journal-title":"Discrete & Computational Geometry"},{"key":"e_1_3_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2522628.2522629"},{"key":"e_1_3_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2448196.2448198"},{"key":"e_1_3_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1002\/cav.403"},{"key":"e_1_3_2_2_53_1","unstructured":"The CGAL Project. 2014. CGAL User and Reference Manual 4.4 ed. CGAL Editorial Board. http:\/\/doc.cgal.org\/4.4\/Manual\/packages.html.  The CGAL Project. 2014. CGAL User and Reference Manual 4.4 ed. CGAL Editorial Board. http:\/\/doc.cgal.org\/4.4\/Manual\/packages.html."},{"key":"e_1_3_2_2_54_1","unstructured":"Tripath Toolkit 2010. Triangulation and path planning toolkit. http:\/\/graphics.ucmerced.edu\/software\/tripath\/.  Tripath Toolkit 2010. Triangulation and path planning toolkit. http:\/\/graphics.ucmerced.edu\/software\/tripath\/."},{"volume-title":"In Proceedings of the IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS), 3526--3532","author":"van Toll W. G., IV, A. F. C.","key":"e_1_3_2_2_55_1","unstructured":"van Toll , W. G., IV, A. F. C. , and Geraerts , R . 2011. Navigation meshes for realistic multi-layered environments . In In Proceedings of the IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS), 3526--3532 . van Toll, W. G., IV, A. F. C., and Geraerts, R. 2011. Navigation meshes for realistic multi-layered environments. In In Proceedings of the IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS), 3526--3532."},{"key":"e_1_3_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1002\/cav.1468"},{"key":"e_1_3_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2005.11.007"}],"event":{"name":"SIGGRAPH '14: Special Interest Group on Computer Graphics and Ineractive Techniques Conference","sponsor":["SIGGRAPH ACM Special Interest Group on Computer Graphics and Interactive Techniques"],"location":"Vancouver Canada","acronym":"SIGGRAPH '14"},"container-title":["ACM SIGGRAPH 2014 Courses"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2614028.2615399","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2614028.2615399","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:22:03Z","timestamp":1750278123000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2614028.2615399"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,7,27]]},"references-count":57,"alternative-id":["10.1145\/2614028.2615399","10.1145\/2614028"],"URL":"https:\/\/doi.org\/10.1145\/2614028.2615399","relation":{},"subject":[],"published":{"date-parts":[[2014,7,27]]},"assertion":[{"value":"2014-07-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}