Linear combination of transformations

ABSTRACT

Geometric transformations are most commonly represented as square matrices in computer graphics. Following simple geometric arguments we derive a natural and geometrically meaningful definition of scalar multiples and a commutative addition of transformations based on the matrix representation, given that the matrices have no negative real eigenvalues. Together, these operations allow the linear combination of transformations. This provides the ability to create weighted combination of transformations, interpolate between transformations, and to construct or use arbitrary transformations in a structure similar to a basis of a vector space. These basic techniques are useful for synthesis and analysis of motions or animations. Animations through a set of key transformations are generated using standard techniques such as subdivision curves. For analysis and progressive compression a PCA can be applied to sequences of transformations. We describe an implementation of the techniques that enables an easy-to-use and transparent way of dealing with geometric transformations in graphics software. We compare and relate our approach to other techniques such as matrix decomposition and quaternion interpolation.

REFERENCES

• 1: ALEXA, M., AND MÜLLER, W. 2000. Representing animations by principal components. Computer Graphics Forum 19, 3 (August), 411-418. ISSN 1067-7055.
• 2: Alan H. Barr , Bena Currin , Steven Gabriel , John F. Hughes, Smooth interpolation of orientations with angular velocity constraints using quaternions, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, p.313-320, July 1992
• 3: Richard H. Bartels , John C. Beatty , Brian A. Barsky, An introduction to the use of splines in computer graphics, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1986
• 4: DENMAN, E. D., AND BEAVERS JR., A. N. 1976. The matrix sign function and computations in systems. Appl. Math. Comput. 2, 63-94.
• 5: DO CARMO, M. P. 1992. Riemannian Geometry. Birkhäuser Verlag, Boston.
• 6: Stephen Mann , Leo Dorst, Geometric Algebra: A Computational Framework for Geometrical Applications (Part 2), IEEE Computer Graphics and Applications, v.22 n.4, p.58-67, July 2002 [doi>10.1109/MCG.2002.1016699]
• 7: DYN, N., LEVIN, D., AND GREGORY, J. 1987. A 4-point interpolatory subdivision scheme for curve design. Computer Aided Geometric Design 4, 4, 257-268.
• 8: GABRIEL, S. A., AND KAJIYA, J. T. 1985. Spline interpolation in curved space. In SIGGRAPH '85 State of the Art in Image Synthesis seminar notes.
• 9: GOLUB, G. H., AND VAN LOAN, C. F. 1989. Matrix Computations, second ed., vol. 3 of Johns Hopkins Series in the Mathematical Sciences. The Johns Hopkins University Press, Baltimore, MD, USA. Second edition.
• 10: F. Sebastin Grassia, Practical parameterization of rotations using the exponential map, Journal of Graphics Tools, v.3 n.3, p.29-48, 1 March 1998
• 11: HESTENES, D. 1991. The design of linear algebra and geometry. Acta Applicandae Mathematicae 23, 65-93.
• 12: HIGHAM, N. J. 1997. Stable iterations for the matrix square root. Numerical Algorithms 15, 2, 227-242.
• 13: Roger A Horn, Topics in matrix analysis, Cambridge University Press, New York, NY, 1986
• 14: Josef Hoschek , Dieter Lasser , Larry L. Schumaker, Fundamentals of computer aided geometric design, A. K. Peters, Ltd., Natick, MA, 1993
• 15: JOLLIFFE, I. T. 1986. Principal Component Analysis. Series in Statistics. Springer-Verlag.
• 16: KENNEY, C., AND LAUB, A. J. 1989. Condition estimates for matrix functions. SIAM Journal on Matrix Analysis and Applications 10, 2, 191-209.
• 17: Myoung-Jun Kim , Myung-Soo Kim , Sung Yong Shin, A general construction scheme for unit quaternion curves with simple high order derivatives, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.369-376, September 1995 [doi>10.1145/218380.218486]
• 18: Jerome Edward Lengyel, Compression of time-dependent geometry, Proceedings of the 1999 symposium on Interactive 3D graphics, p.89-95, April 26-29, 1999, Atlanta, Georgia, United States [doi>10.1145/300523.300533]
• 19: Arne Marthinsen, Interpolation in Lie Groups, SIAM Journal on Numerical Analysis, v.37 n.1, p.269-285, Nov. 1999 [doi>10.1137/S0036142998338861]
• 20: MOLER, C. B., AND LOAN, C. F. V. 1978. Nineteen dubious ways to compute the matrix exponential. SIAM Review 20, 801-836.
• 21: Richard M. Murray , S. Shankar Sastry , Li Zexiang, A Mathematical Introduction to Robotic Manipulation, CRC Press, Inc., Boca Raton, FL, 1994
• 22: NAEVE, A., AND ROCKWOOD, A. 2001. Geometric algebra. SIGGRAPH 2001 course #53.
• 23: F. C. Park , Bahram Ravani, Smooth invariant interpolation of rotations, ACM Transactions on Graphics (TOG), v.16 n.3, p.277-295, July 1997 [doi>10.1145/256157.256160]
• 24: Ravi Ramamoorthi , Alan H. Barr, Fast construction of accurate quaternion splines, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.287-292, August 1997 [doi>10.1145/258734.258870]
• 25: 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
• 26: Ken Shoemake, Animating rotation with quaternion curves, ACM SIGGRAPH Computer Graphics, v.19 n.3, p.245-254, Jul. 1985
• 27: SHOEMAKE, K. 1991. Quaternions and 4x4 matrices. Graphics Gems II, 351-354. ISBN 0-12-064481-9. Held in Boston.
• 28: WEB3D CONSORTIUM. 1999. H-Anim. http://ece.uwaterloo.ca:80/~h-anim.
• 29: ZEFRAN, M., AND KUMAR, V. 1998. Rigid body motion interpolation. Computer Aided Design 30, 3, 179-189.
• 30: ZEFRAN, M., KUMAR, V., AND CROKE, C. 1996. Choice of riemannian metrics for rigid body kinematics. In ASME 24th Biennial Mechanisms Conference.
• 31: Milos Zefran , Vijay Kumar, Continuous methods for motion planning, 1996
• 32: ZORIN, D., AND SCHRÖDER, P. 1999. Subdivision for modeling and animation. SIGGRAPH 1999 course # 47.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.1 Interpolation
          Subjects: Spline and piecewise polynomial interpolation

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

General Terms:
Algorithms

Keywords:
exponential map, linear space, logarithm, matrix exponential, transformations