Computing inverse kinematics with linear programming

Inverse Kinematics (IK) is a popular technique for synthesizing motions of virtual characters. In this paper, we propose a Linear Programming based IK solver (LPIK) for interactive control of arbitrary multibody structures. There are several advantages of using LPIK. First, inequality constraints can be handled, and therefore the ranges of the DOFs and collisions of the body with other obstacles can be handled easily. Second, the performance of LPIK is comparable or sometimes better than the IK method based on Lagrange multipliers, which is known as the best IK solver today. The computation time by LPIK increases only linearly proportional to the number of constraints or DOFs. Hence, LPIK is a suitable approach for controlling articulated systems with large DOFs and constraints for real-time applications.