Geometric skinning with approximate dual quaternion blending

ABSTRACT

Skinning of skeletally deformable models is extensively used for real-time animation of characters, creatures and similar objects. The standard solution, linear blend skinning, has some serious drawbacks that require artist intervention. Therefore, a number of alternatives have been proposed in recent years. All of them successfully combat some of the artifacts, but none challenge the simplicity and efficiency of linear blend skinning. As a result, linear blend skinning is still the number one choice for the majority of developers. In this article, we present a novel skinning algorithm based on linear combination of dual quaternions. Even though our proposed method is approximate, it does not exhibit any of the artifacts inherent in previous methods and still permits an efficient GPU implementation. Upgrading an existing animation system from linear to dual quaternion skinning is very easy and has a relatively minor impact on runtime performance.

REFERENCES

• 1: Marc Alexa, Linear combination of transformations, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 2: Brett Allen , Brian Curless , Zoran Popović, Articulated body deformation from range scan data, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 3: Brett Allen , Brian Curless , Zoran Popović , Aaron Hertzmann, Learning a correlated model of identity and pose-dependent body shape variation for real-time synthesis, Proceedings of the 2006 ACM SIGGRAPH/Eurographics symposium on Computer animation, September 02-04, 2006, Vienna, Austria
• 4: Dragomir Anguelov , Praveen Srinivasan , Daphne Koller , Sebastian Thrun , Jim Rodgers , James Davis, SCAPE: shape completion and animation of people, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 5: Aubel, A. and Thalmann, D. 2000. Realistic deformation of human body shapes. In Proceeding of the Confrance on Computer Animation and Simulation. 125--135.
• 6: Ilya Baran , Jovan Popović, Automatic rigging and animation of 3D characters, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 7: Barr, A. H., Currin, B., Gabriel, S., and Hughes, J. F. 1992. Smooth interpolation of orientations with angular velocity constraints using quaternions. ACM Trans. Graph. 313--320.
• 8: Belta, C. and Kumar, V. 2002. An SVD-based projection method for interpolation on SE(3). IEEE Trans. Robot. Automat. 18, 3, 334--345.
• 9: Bloom, C., Blow, J., and Muratori, C. 2004. Errors and omissions in Marc Alexa's Linear combination of transformations. http://www.cbloom.com/3d/techdocs/lcot_errors.pdf.
• 10: Bottema, O. and Roth, B. 1979. Theoretical kinematics. North-Holland Publishing Company, Amsterdam.
• 11: Samuel R. Buss , Jay P. Fillmore, Spherical averages and applications to spherical splines and interpolation, ACM Transactions on Graphics (TOG), v.20 n.2, p.95-126, April 2001 [doi>10.1145/502122.502124]
• 12: Steve Capell , Seth Green , Brian Curless , Tom Duchamp , Zoran Popović, Interactive skeleton-driven dynamic deformations, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 13: Bruce Char , Keith Geddes , Gaston Gonnet, The maple symbolic computation system, ACM SIGSAM Bulletin, v.17 n.3-4, p.31-42, August-November 1983 [doi>10.1145/1089338.1089344]
• 14: Clifford, W. 1882. Mathematical Papers. Macmillan, London.
• 15: Cordier, F. and Magnenat-Thalmann, N. 2005. A data-driven approach for real-time clothes simulation. Comput. Graph. For. 24, 2, 173--183.
• 16: Dam, E., Koch, M., and Lillholm, M., 1998. Quaternions, interpolation and animation. Tech. rep. DIKU-TR-98/5, University of Copenhagen.
• 17: Daniilidis, K. 1999. Hand-eye calibration using dual quaternions. Int. J. Rob. Research 18, 286--298.
• 18: Daniel Fontijne , Leo Dorst, Modeling 3D Euclidean Geometry, IEEE Computer Graphics and Applications, v.23 n.2, p.68-78, March 2003 [doi>10.1109/MCG.2003.1185582]
• 19: Forstmann, S. and Ohya, J. 2006. Fast skeletal animation by skinned arc-spline based deformation. In Eurographics Short Papers, 1--4.
• 20: Sven Forstmann , Jun Ohya , Artus Krohn-Grimberghe , Ryan McDougall, Deformation styles for spline-based skeletal animation, Proceedings of the 2007 ACM SIGGRAPH/Eurographics symposium on Computer animation, August 02-04, 2007, San Diego, California
• 21: Govindu, V. M. 2004. Lie-algebraic averaging for globally consistent motion estimation. In Proceeding of the IEEE Conference on Computer Vision and Pattern Recognition, Vol. 1, 684--691.
• 22: Guo, Z. and Wong, K. C. 2005. Skinning with deformable chunks. Comput. Graph. For. 24, 3, 373--381.
• 23: Andrew J. Hanson, Visualizing Quaternions (The Morgan Kaufmann Series in Interactive 3D Technology), Morgan Kaufmann Publishers Inc., San Francisco, CA, 2006
• 24: Hejl, J. 2004. Hardware skinning with quaternions. Game Program. Gems 4, Charles River Media, 487--495.
• 25: Michael Hofer , Helmut Pottmann, Energy-minimizing splines in manifolds, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 26: Hyun, D.-E., Yoon, S.-H., Chang, J.-W., Seong, J.-K., Kim, M.-S., and Jüttler, B. 2005. Sweep-based human deformation. Visual Comput. 21, 8--10, 542--550.
• 27: David Jacka , Ashley Reid , Bruce Merry , James Gain, A comparison of linear skinning techniques for character animation, Proceedings of the 5th international conference on Computer graphics, virtual reality, visualisation and interaction in Africa, October 29-31, 2007, Grahamstown, South Africa [doi>10.1145/1294685.1294715]
• 28: Doug L. James , Christopher D. Twigg, Skinning mesh animations, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 29: Johnson, M. P. 2003. Exploiting quaternions to support expressive interactive character motion. PhD thesis, MIT.
• 30: Pushkar Joshi , Mark Meyer , Tony DeRose , Brian Green , Tom Sanocki, Harmonic coordinates for character articulation, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 31: Tao Ju , Scott Schaefer , Joe Warren, Mean value coordinates for closed triangular meshes, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 32: Juttler, B. 1994. Visualization of moving objects using dual quaternion curves. Comput. Graph. 18, 3, 315--326.
• 33: Ladislav Kavan , Jiří Žára, Spherical blend skinning: a real-time deformation of articulated models, Proceedings of the 2005 symposium on Interactive 3D graphics and games, April 03-06, 2005, Washington, District of Columbia [doi>10.1145/1053427.1053429]
• 34: Kavan, L., Collins, S., O'Sullivan, C., and Žára, J., 2006. Dual quaternions for rigid transformation blending. Tech. rep. TCD-CS-2006-46, Trinity College Dublin.
• 35: Ladislav Kavan , Steven Collins , Jiří Žára , Carol O'Sullivan, Skinning with dual quaternions, Proceedings of the 2007 symposium on Interactive 3D graphics and games, April 30-May 02, 2007, Seattle, Washington [doi>10.1145/1230100.1230107]
• 36: Paul G. Kry , Doug L. James , Dinesh K. Pai, EigenSkin: real time large deformation character skinning in hardware, Proceedings of the 2002 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 21-22, 2002, San Antonio, Texas [doi>10.1145/545261.545286]
• 37: Tsuneya Kurihara , Natsuki Miyata, Modeling deformable human hands from medical images, Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation, August 27-29, 2004, Grenoble, France [doi>10.1145/1028523.1028571]
• 38: Kurihara, T. and Nishita, T. 2007. Dual-quaternion skinning with nonrigid transformatio. In Symposium on Computer Animation: Posters. Eurographics Association, Aire-la-Ville, Switzerland, 18--19.
• 39: J. P. Lewis , Matt Cordner , Nickson Fong, Pose space deformation: a unified approach to shape interpolation and skeleton-driven deformation, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.165-172, July 2000 [doi>10.1145/344779.344862]
• 40: Li, J. and Hao, P. 2006. Smooth interpolation on homogeneous matrix groups for computer animation. J. Zhejiang Univ. 7, 7, 1168--1177.
• 41: Cristian Luciano , Pat Banerjee, Avatar kinematics modeling for telecollaborative virtual environments, Proceedings of the 32nd conference on Winter simulation, December 10-13, 2000, Orlando, Florida
• 42: N. Magnenat-Thalmann , R. Laperrière , D. Thalmann, Joint-dependent local deformations for hand animation and object grasping, Proceedings on Graphics interface '88, p.26-33, December 1989, Edmonton, Alberta, Canada
• 43: Arne Marthinsen, Interpolation in Lie Groups, SIAM Journal on Numerical Analysis, v.37 n.1, p.269-285, Nov. 1999 [doi>10.1137/S0036142998338861]
• 44: J. M. McCarthy, Introduction to theoretical kinematics, MIT Press, Cambridge, MA, 1990
• 45: Bruce Merry , Patrick Marais , James Gain, Animation space: A truly linear framework for character animation, ACM Transactions on Graphics (TOG), v.25 n.4, p.1400-1423, October 2006 [doi>10.1145/1183287.1183294]
• 46: Merry, B. 2007. Personal communication.
• 47: Maher Moakher, Means and Averaging in the Group of Rotations, SIAM Journal on Matrix Analysis and Applications, v.24 n.1, p.1-16, 2002 [doi>10.1137/S0895479801383877]
• 48: Alex Mohr , Michael Gleicher, Building efficient, accurate character skins from examples, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003
• 49: Richard M. Murray , S. Shankar Sastry , Li Zexiang, A Mathematical Introduction to Robotic Manipulation, CRC Press, Inc., Boca Raton, FL, 1994
• 50: Sang Il Park , Jessica K. Hodgins, Capturing and animating skin deformation in human motion, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 51: Sang Il Park , Hyun Joon Shin , Sung Yong Shin, On-line locomotion generation based on motion blending, Proceedings of the 2002 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 21-22, 2002, San Antonio, Texas [doi>10.1145/545261.545279]
• 52: Perez, A. and McCarthy, J. M. 2004. Dual quaternion synthesis of constrained robotic systems. J. Mech. Desi. 126, 425--435.
• 53: Michael Pratscher , Patrick Coleman , Joe Laszlo , Karan Singh, Outside-in anatomy based character rigging, Proceedings of the 2005 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 29-31, 2005, Los Angeles, California [doi>10.1145/1073368.1073415]
• 54: Rhee, T., Lewis, J., and Neumann, U. 2006. Real-time weighted pose-space deformation on the GPU. Comput. Graph. For. 25, 3, 439--448.
• 55: Ferdi Scheepers , Richard E. Parent , Wayne E. Carlson , Stephen F. May, Anatomy-based modeling of the human musculature, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.163-172, August 1997 [doi>10.1145/258734.258827]
• 56: Ken Shoemake , Tom Duff, Matrix animation and polar decomposition, Proceedings of the conference on Graphics interface '92, p.258-264, September 1992, Vancouver, British Columbia, Canada
• 57: Ken Shoemake, Animating rotation with quaternion curves, Proceedings of the 12th annual conference on Computer graphics and interactive techniques, p.245-254, July 1985
• 58: Dave Shreiner , Mason Woo , Jackie Neider , Tom Davis, OpenGL(R) Programming Guide: The Official Guide to Learning OpenGL(R), Version 2 (5th Edition) (OpenGL), Addison-Wesley Professional, 2005
• 59: Peter-Pike J. Sloan , Charles F. Rose, III , Michael F. Cohen, Shape by example, Proceedings of the 2001 symposium on Interactive 3D graphics, p.135-143, March 2001 [doi>10.1145/364338.364382]
• 60: Joseph Teran , Eftychios Sifakis , Silvia S. Blemker , Victor Ng-Thow-Hing , Cynthia Lau , Ronald Fedkiw, Creating and Simulating Skeletal Muscle from the Visible Human Data Set, IEEE Transactions on Visualization and Computer Graphics, v.11 n.3, p.317-328, May 2005 [doi>10.1109/TVCG.2005.42]
• 61: Xiaohuan Corina Wang , Cary Phillips, Multi-weight enveloping: least-squares approximation techniques for skin animation, Proceedings of the 2002 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 21-22, 2002, San Antonio, Texas [doi>10.1145/545261.545283]
• 62: Robert Y. Wang , Kari Pulli , Jovan Popović, Real-time enveloping with rotational regression, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 63: Wenping Wang , Bert Jüttler , Dayue Zheng , Yang Liu, Computation of rotation minimizing frames, ACM Transactions on Graphics (TOG), v.27 n.1, p.1-18, March 2008 [doi>10.1145/1330511.1330513]
• 64: Wareham, R., Cameron, J., and Lasenby, J. 2005. Applications of conformal geometric algebra in computer vision and graphics. Lecture Notes in Computer Science Vol. 3519, 329--349.
• 65: Weber, O., Sorkine, O., Lipman, Y., and Gotsman, C. 2007. Context-aware skeletal shape deformation. Comput. Graph. For. 26, 3.
• 66: Xiaosong Yang , Arun Somasekharan , Jian J. Zhang, Curve skeleton skinning for human and creature characters: Research Articles, Computer Animation and Virtual Worlds, v.17 n.3-4, p.281-292, July 2006 [doi>10.1002/cav.v17:3/4]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Hierarchy and geometric transformations

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Animation

General Terms:
Algorithms

Keywords:
Skinning, dual quaternions, linear combinations, rigid transformations, transformation blending