{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:11:19Z","timestamp":1750306279031,"version":"3.41.0"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2016,2,19]],"date-time":"2016-02-19T00:00:00Z","timestamp":1455840000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"CTI Switzerland","award":["15870.1 PFES-ES"],"award-info":[{"award-number":["15870.1 PFES-ES"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2016,5,25]]},"abstract":"<jats:p>In this article, we present a parallel prioritized Jacobian-based inverse kinematics algorithm for multithreaded architectures. We solve damped least squares inverse kinematics using a parallel line search by identifying and sampling critical input parameters. Parallel competing execution paths are spawned for each parameter in order to select the optimum that minimizes the error criteria. Our algorithm is highly scalable and can handle complex articulated bodies at interactive frame rates. We show results on complex skeletons consisting of more than 600 degrees of freedom while being controlled using multiple end effectors. We implement the algorithm both on multicore and GPU architectures and demonstrate how the GPU can further exploit fine-grain parallelism not directly available on a multicore processor. Our implementations are 10 to 150 times faster compared to a state-of-the-art serial implementation while providing higher accuracy. We also demonstrate the scalability of the algorithm over multiple scenarios and explore the GPU implementation in detail.<\/jats:p>","DOI":"10.1145\/2887740","type":"journal-article","created":{"date-parts":[[2016,2,22]],"date-time":"2016-02-22T13:07:16Z","timestamp":1456146436000},"page":"1-13","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":17,"title":["Parallel Inverse Kinematics for Multithreaded Architectures"],"prefix":"10.1145","volume":"35","author":[{"given":"Pawan","family":"Harish","sequence":"first","affiliation":[{"name":"Immersive Interaction Group (IIG), \u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne (EPFL)"}]},{"given":"Mentar","family":"Mahmudi","sequence":"additional","affiliation":[{"name":"Immersive Interaction Group (IIG), \u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne (EPFL)"}]},{"given":"Beno\u00eet Le","family":"Callennec","sequence":"additional","affiliation":[{"name":"Moka Studio, Martigny, Switzerland"}]},{"given":"Ronan","family":"Boulic","sequence":"additional","affiliation":[{"name":"Immersive Interaction Group (IIG), \u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne (EPFL)"}]}],"member":"320","published-online":{"date-parts":[[2016,2,19]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25324-9_42"},{"key":"e_1_2_2_2_1","unstructured":"AMD. 2013. OpenCL Programming and Optimization. Retrieved from http:\/\/free.eol.cn\/edu_net\/edudown\/AMDppt\/OpenCLProgrammingandO ptimization-Part II.pdf.  AMD. 2013. OpenCL Programming and Optimization. Retrieved from http:\/\/free.eol.cn\/edu_net\/edudown\/AMDppt\/OpenCLProgrammingandO ptimization-Part II.pdf."},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.gmod.2011.05.003"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.1985.1087234"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1080\/2151237X.2005.10129202"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2664666.2664667"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1778765.1781157"},{"volume-title":"Proceedings of the 1992 IEEE International Conference on Robotics and Automation. 434--441","author":"Deo A. S.","key":"e_1_2_2_10_1","unstructured":"A. S. Deo and I. D. Walker . 1992. Robot subtask performance with singularity robustness using optimal damped least-squares . In Proceedings of the 1992 IEEE International Conference on Robotics and Automation. 434--441 . A. S. Deo and I. D. Walker. 1992. Robot subtask performance with singularity robustness using optimal damped least-squares. In Proceedings of the 1992 IEEE International Conference on Robotics and Automation. 434--441."},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1177\/027836499301200101"},{"volume-title":"Proceedings of the 2013 IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS\u201913)","author":"Farzan S.","key":"e_1_2_2_12_1","unstructured":"S. Farzan and G. N. DeSouza . 2013. From D-H to inverse kinematics: A fast numerical solution for general robotic manipulators using parallel processing . In Proceedings of the 2013 IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS\u201913) . 2507--2513. S. Farzan and G. N. DeSouza. 2013. From D-H to inverse kinematics: A fast numerical solution for general robotic manipulators using parallel processing. In Proceedings of the 2013 IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS\u201913). 2507--2513."},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/325334.325244"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/0702016"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1186562.1015755"},{"key":"e_1_2_2_16_1","unstructured":"M. Harris S. Sengupta and J. D. Owens. 2007. Parallel prefix sum (scan) with CUDA. In GPU Gems 3 Hubert Nguyen (Ed.). Addison Wesley.  M. Harris S. Sengupta and J. D. Owens. 2007. Parallel prefix sum (scan) with CUDA. In GPU Gems 3 Hubert Nguyen (Ed.). Addison Wesley."},{"volume-title":"Proceedings of the International Conference on Computer Graphics Theory and Applications. 300--307","author":"Hildenbrand D.","key":"e_1_2_2_17_1","unstructured":"D. Hildenbrand , H. Lange , F. Stock , and A. Koch . 2008. Efficient inverse kinematics algorithm based on conformal geometric algebra using reconfigurable hardware . In Proceedings of the International Conference on Computer Graphics Theory and Applications. 300--307 . D. Hildenbrand, H. Lange, F. Stock, and A. Koch. 2008. Efficient inverse kinematics algorithm based on conformal geometric algebra using reconfigurable hardware. In Proceedings of the International Conference on Computer Graphics Theory and Applications. 300--307."},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/IPDPS.2009.5161058"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.168600"},{"volume-title":"2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops (CVPRW\u201910)","author":"Lehment N. H.","key":"e_1_2_2_21_1","unstructured":"N. H. Lehment , D. Arsic , M. Kaiser , and G. Rigoll . 2010. Automated pose estimation in 3d point clouds applying annealing particle filters and inverse kinematics on a GPU . In 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops (CVPRW\u201910) . 87--92. N. H. Lehment, D. Arsic, M. Kaiser, and G. Rigoll. 2010. Automated pose estimation in 3d point clouds applying annealing particle filters and inverse kinematics on a GPU. In 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshops (CVPRW\u201910). 87--92."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSMC.1977.4309644"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2009.79"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/38.55154"},{"volume-title":"Proceedings of the 2012 IEEE EMBS Conference on Biomedical Engineering and Sciences (IECBES\u201912)","author":"Masinghe W.","key":"e_1_2_2_25_1","unstructured":"W. Masinghe , G. Collier , A. Ordys , and T. Nanayakkara . 2012. A novel approach to determine the inverse kinematics of a human upper limb model with 9 degrees of freedom . In Proceedings of the 2012 IEEE EMBS Conference on Biomedical Engineering and Sciences (IECBES\u201912) . 525--530. W. Masinghe, G. Collier, A. Ordys, and T. Nanayakkara. 2012. A novel approach to determine the inverse kinematics of a human upper limb model with 9 degrees of freedom. In Proceedings of the 2012 IEEE EMBS Conference on Biomedical Engineering and Sciences (IECBES\u201912). 525--530."},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1177\/027836498700600201"},{"key":"e_1_2_2_27_1","unstructured":"C. R. Rao J. L. Solka and E. J. Wegman. 2005. Handbook of Statistics: Data Mining and Data Visualization. Elsevier.   C. R. Rao J. L. Solka and E. J. Wegman. 2005. Handbook of Statistics: Data Mining and Data Visualization. Elsevier."},{"volume-title":"Proceedings of the 2014 IEEE International Conference on Robotics and Automation (ICRA\u201914)","author":"Schroder M.","key":"e_1_2_2_28_1","unstructured":"M. Schroder , J. Maycock , H. Ritter , and M. Botsch . 2014. Real-time hand tracking using synergistic inverse kinematics . In Proceedings of the 2014 IEEE International Conference on Robotics and Automation (ICRA\u201914) . 5447--5454. M. Schroder, J. Maycock, H. Ritter, and M. Botsch. 2014. Real-time hand tracking using synergistic inverse kinematics. In Proceedings of the 2014 IEEE International Conference on Robotics and Automation (ICRA\u201914). 5447--5454."},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1186822.1073218"},{"key":"e_1_2_2_30_1","first-page":"501","article-title":"Solution of incorrectly formulated problems and the regularization method","volume":"151","author":"Tikhonov A. N.","year":"1963","unstructured":"A. N. Tikhonov . 1963 . Solution of incorrectly formulated problems and the regularization method . Doklady Akademii Nauk SSSR 151 (1963), 501 -- 504 . A. N. Tikhonov. 1963. Solution of incorrectly formulated problems and the regularization method. Doklady Akademii Nauk SSSR 151 (1963), 501--504.","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"e_1_2_2_31_1","unstructured":"M. K. Transtrum and J. P. Sethna. 2012. Improvements to the Levenberg-Marquardt algorithm for nonlinear least-squares minimization. http:\/\/arxiv.org\/abs\/1201.5885 (01\/ 2012).  M. K. Transtrum and J. P. Sethna. 2012. Improvements to the Levenberg-Marquardt algorithm for nonlinear least-squares minimization. http:\/\/arxiv.org\/abs\/1201.5885 (01\/ 2012)."},{"key":"e_1_2_2_32_1","unstructured":"V. Volkov and J. Demmel. 2008. LU QR and Cholesky Factorizations Using Vector Capabilities of GPUs. Technical Report. EECS Department University of California Berkeley.  V. Volkov and J. Demmel. 2008. LU QR and Cholesky Factorizations Using Vector Capabilities of GPUs. Technical Report. EECS Department University of California Berkeley."},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-004-0560-5"},{"key":"e_1_2_2_34_1","unstructured":"A. Watt and M. Watt. 1991. Advanced Animation and Rendering Techniques. ACM New York NY.   A. Watt and M. Watt. 1991. Advanced Animation and Rendering Techniques. ACM New York NY."},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/70.97878"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2887740","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2887740","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:38:51Z","timestamp":1750221531000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2887740"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,2,19]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,5,25]]}},"alternative-id":["10.1145\/2887740"],"URL":"https:\/\/doi.org\/10.1145\/2887740","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"type":"print","value":"0730-0301"},{"type":"electronic","value":"1557-7368"}],"subject":[],"published":{"date-parts":[[2016,2,19]]},"assertion":[{"value":"2015-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-02-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}