Marc Alexa
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.
- ALEXA, M., AND MÜLLER, W. 2000. Representing animations by principal components. Computer Graphics Forum 19, 3 (August), 411-418. ISSN 1067-7055.Google Scholar
- BARR, A. H., CURRIN, B., GABRIEL, S., AND HUGHES, J. F. 1992. Smooth interpolation of orientations with angular velocity constraints using quaternions. Computer Graphics (Proceedings of SIGGRAPH 92) 26, 2 (July), 313-320. ISBN 0-201-51585-7. Held in Chicago, Illinois. Google Scholar
- BARTELS, R. H., BEATTY, J. C., AND BARSKY, B. A. 1985. An introduction to the use of splines in computer graphics. Google Scholar
- DENMAN, E. D., AND BEAVERS JR., A. N. 1976. The matrix sign function and computations in systems. Appl. Math. Comput. 2, 63-94.Google Scholar
- DO CARMO, M. P. 1992. Riemannian Geometry. Birkhäuser Verlag, Boston.Google Scholar
- DORST, L., AND MANN, S. 2001. Geometric algebra: a computation framework for geometrical applications. submitted to IEEE Computer Graphics & Applications. available as http://www.cgl.uwaterloo.ca/~smann/Papers/CGA01.pdf. Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- 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.Google Scholar
- GRASSIA, F. S. 1998. Practical parameterization of rotations using the exponential map. Journal of Graphics Tools 3, 3, 29-48. ISSN 1086-7651. Google Scholar
- HESTENES, D. 1991. The design of linear algebra and geometry. Acta Applicandae Mathematicae 23, 65-93.Google Scholar
- HIGHAM, N. J. 1997. Stable iterations for the matrix square root. Numerical Algorithms 15, 2, 227-242.Google Scholar
- HORN, R. A., AND JOHNSON, C. A. 1991. Topics in Matrix Analysis. Cambridge University press, Cambridge. Google Scholar
- HOSCHEK, J., AND LASSER, D. 1993. Fundamentals of computer aided geometric design. ISBN 1-56881-007-5. Google Scholar
- JOLLIFFE, I. T. 1986. Principal Component Analysis. Series in Statistics. Springer-Verlag.Google Scholar
- KENNEY, C., AND LAUB, A. J. 1989. Condition estimates for matrix functions. SIAM Journal on Matrix Analysis and Applications 10, 2, 191-209.Google Scholar
- KIM, M.-J., SHIN, S. Y., AND KIM, M.-S. 1995. A general construction scheme for unit quaternion curves with simple high order derivatives. Proceedings of SIGGRAPH 95 (August), 369-376. ISBN 0-201-84776-0. Held in Los Angeles, California. Google Scholar
- LENGYEL, J. E. 1999. Compression of time-dependent geometry. 1999 ACM Symposium on Interactive 3D Graphics (April), 89-96. ISBN 1-58113-082-1. Google Scholar
- MARTHINSEN, A. 2000. Interpolation in Lie groups. SIAM Journal on Numerical Analysis 37, 1, 269-285. Google Scholar
- MOLER, C. B., AND LOAN, C. F. V. 1978. Nineteen dubious ways to compute the matrix exponential. SIAM Review 20, 801-836.Google Scholar
- MURRAY, R. M., LI, Z., AND SASTRY, S. S. 1994. A Mathematical Introduction to Robotic Manipulation. CRC Press. Google Scholar
- NAEVE, A., AND ROCKWOOD, A. 2001. Geometric algebra. SIGGRAPH 2001 course #53.Google Scholar
- PARK, F. C., AND RAVANI, B. 1997. Smooth invariant interpolation of rotations. ACM Transactions on Graphics 16, 3 (July), 277-295. ISSN 0730-0301. Google Scholar
- RAMAMOORTHI, R., AND BARR, A. H. 1997. Fast construction of accurate quaternion splines. Proceedings of SIGGRAPH 97 (August), 287-292. ISBN 0-89791-896-7. Held in Los Angeles, California. Google Scholar
- SHOEMAKE, K., AND DUFF, T. 1992. Matrix animation and polar decomposition. Graphics Interface '92 (May), 258-264. Google Scholar
- SHOEMAKE, K. 1985. Animating rotation with quaternion curves. Computer Graphics (Proceedings of SIGGRAPH 85) 19, 3 (July), 245-254. Held in San Francisco, California. Google Scholar
- SHOEMAKE, K. 1991. Quaternions and 4x4 matrices. Graphics Gems II, 351-354. ISBN 0-12-064481-9. Held in Boston.Google Scholar
- WEB3D CONSORTIUM. 1999. H-Anim. http://ece.uwaterloo.ca:80/~h-anim.Google Scholar
- ZEFRAN, M., AND KUMAR, V. 1998. Rigid body motion interpolation. Computer Aided Design 30, 3, 179-189.Google Scholar
- ZEFRAN, M., KUMAR, V., AND CROKE, C. 1996. Choice of riemannian metrics for rigid body kinematics. In ASME 24th Biennial Mechanisms Conference.Google Scholar
- ZEFRAN, M. 1996. Continuous methods for motion planning. PhD-thesis, U. of Pennsylvania, Philadelphia, PA. Google Scholar
- ZORIN, D., AND SCHRÖDER, P. 1999. Subdivision for modeling and animation. SIGGRAPH 1999 course # 47.Google Scholar
Index Terms
- Linear combination of transformations
Recommendations
Linear combination of transformations
SIGGRAPH '02: Proceedings of the 29th annual conference on Computer graphics and interactive techniquesGeometric 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 ...
Shift-Invert Arnoldi Approximation to the Toeplitz Matrix Exponential
The shift-invert Arnoldi method is employed to generate an orthonormal basis from the Krylov subspace corresponding to a real Toeplitz matrix and an initial vector. The vectors and recurrence coefficients produced by this method are exploited to ...
Robust Linear Stability Analysis and a New Method for Computing the Action of the Matrix Exponential
Linear stability analysis of a large-scale dynamical system requires computing the rightmost eigenvalue of a large sparse matrix $A$. To enhance the convergence to this eigenvalue, an iterative eigensolver is usually applied to a transformation of $A$ ...
Comments