Kenny Erleben
Sheldon Andrews
ABSTRACT
Inverse kinematics (IK) is a central component of systems for motion capture, character animation, motion planning, and robotics control. The field of computer graphics has developed fast stationary point solvers methods, such as the Jacobian transpose method and cyclic coordinate descent. Much work with Newton methods focus on avoiding directly computing the Hessian, and instead approximations are sought, such as in the BFGS class of solvers. This paper presents a numerical method for computing the exact Hessian of an IK system with spherical joints. It is applicable to human skeletons in computer animation applications and some, but not all, robots. Our results show that using exact Hessians can give performance advantages and higher accuracy compared to standard numerical methods used for solving IK problems. Furthermore, we provide code and supplementary details that allows researchers to plug-in exact Hessians in their own work with little effort.
Supplemental Material
Available for Download
Supplemental material.
- Charles George Broyden. 1970. The convergence of a class of double-rank minimization algorithms 1. general considerations. IMA Journal of Applied Mathematics 6,1 (1970), 76--90. Google Scholar
Cross Ref
- S.R. Buss. 2004. Introduction to Inverse Kinematics with Jacobian Transpose, Pseudoin-verse and Damped Least Squares methods. Technical Report.Google Scholar
- B. Le Callennec. 2006. Interactive Techniques for Motion Deformation of Articulated Figures Using Prioritized Constraints. Ph.D. Dissertation. École Polytechnique Fédérale de Lausanne (EPFL).Google Scholar
- Thomas F Coleman and Yuying Li. 1996. An interior trust region approach for nonlinear minimization subject to bounds. SIAM Journal on optimization 6, 2 (1996), 418--445. Google ScholarDigital Library
- John J. Craig. 1989. Introduction to Robotics: Mechanics and Control. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA.Google ScholarDigital Library
- Morten Engell-Nørregård and Kenny Erleben. 2009. A Projected Non-linear ConjugateGoogle Scholar
- Gradient Method for Interactive Inverse Kinematics.. In MATHMOD 2009 - 6th Vienna International Conference on Mathematical Modelling.Google Scholar
- Morten Engell-Nørregård and Kenny Erleben. 2011. Technical Section: A Projected Back-tracking Line-search for Constrained Interactive Inverse Kinematics. Comput. Graph. 35, 2 (April 2011), 288--298. Google ScholarDigital Library
- Martin Fedor. 2003. Application of inverse kinematics for skeleton manipulation in real-time. In SCCG '03: Proceedings of the 19th spring conference on Computer graphics. ACM Press, New York, NY, USA, 203--212. Google ScholarDigital Library
- Roger Fletcher. 1970. A new approach to variable metric algorithms. The computer journal 13, 3 (1970), 317--322. Google ScholarCross Ref
- Michael Girard and A.A. Maciejewski. 1985. Computational Modeling for the Computer Animation of Legged Figures. SIGGRAPH Comput. Graph. 19, 3 (July 1985), 263--270. Google ScholarDigital Library
- Pawan Harish, Mentar Mahmudi, Benoît Le Callennec, and Ronan Boulic. 2016. Parallel Inverse Kinematics for Multithreaded Architectures. ACM Trans. Graph. 35, 2, Article 19 (Feb. 2016), 13 pages. Google ScholarDigital Library
- Nicholas J Higham. 1988. Computing a nearest symmetric positive semidefinite matrix. Linear algebra and its applications 103 (1988), 103--118. Google ScholarCross Ref
- Edmond S. L. Ho, Taku Komura, and Rynson W. H. Lau. 2005. Computing inverse kinematics with linear programming. In VRST '05: Proceedings of the ACM symposium on Virtual reality software and technology. ACM, New York, NY, USA, 163--166. Google ScholarDigital Library
- T. C. Hsia and Z. Y. Guo. 1991. New inverse kinematic algorithms for redundant robots. Journal of Robotic Systems 8, 1 (1991), 117--132. Google ScholarCross Ref
- Sung-Hee Lee, Junggon Kim, F. C. Park, Munsang Kim, and J. E. Bobrow. 2005. Newton-Type Algorithms for Dynamics-Based Robot Movement Optimization. IEEE Transactions on Robotics 21,4 (Aug 2005), 657--667. Google ScholarDigital Library
- M. Müller, T. Röder, M. Clausen, B. Eberhardt, B. Krüger, and A. Weber. 2007. Documentation Mocap Database HDM05. Technical Report. Universität Bonn.Google Scholar
- Jorge Nocedal and Stephen J. Wright. 1999. Numerical optimization. Springer-Verlag, New York. xxii+636 pages.Google Scholar
- Chris Wellman. 1993. Inverse Kinematics and Geometric Constraints for Articulated Figure Manipulation. Master's thesis. Simon Fraser University.Google Scholar
- Jianmin Zhao and Norman I. Badler. 1994. Inverse kinematics positioning using nonlinear programming for highly articulated figures. ACM Trans. Graph. 13, 4 (1994), 313--336. Google ScholarDigital Library
- Victor B Zordan. 2002. Solving computer animation problems with numeric optimization. Technical Report. Georgia Institute of Technology.Google Scholar
Index Terms
- Inverse kinematics problems with exact Hessian matrices
Recommendations
Efficient Calculation of Bounds on Spectra of Hessian Matrices
We introduce a new method for the calculation of bounds on eigenvalues of Hessian matrices $\nabla^2 \varphi(x)$ of twice continuously differentiable functions $\varphi:U\subseteq\mathbb{R}^n\rightarrow \mathbb{R}$. The computational complexity of the ...
Inverse eigenvalue problems of tridiagonal symmetric matrices and tridiagonal bisymmetric matrices
The problem of generating a matrix A with specified eigenpairs, where A is a tridiagonal symmetric matrix, is presented. A general expression of such a matrix is provided, and the set of such matrices is denoted by S"E. Moreover, the corresponding least-...
Inverse problems for symmetric matrices with a submatrix constraint
This paper is concerned with the following problems: Problem I(a). Given a full column rank matrix X@?R^n^x^p and symmetric matrices B@?R^p^x^p and A"0@?R^r^x^r, find an nxn symmetric matrix A such thatX^TAX=B,A([1,r])=A"0, where A([1,r]) is the rxr ...
Comments