Implementing and interpolating rotations from a computing input device

Patent metadata

Field	Value
Publication number	US-9595080-B2
Application number	US-201414473711-A
Country	US
Kind code	B2
Filing date	Aug 29, 2014
Priority date	Jun 19, 2008
Publication date	Mar 14, 2017
Grant date	Mar 14, 2017

Abstract

Novel and simple methods, systems, and computer program products for implementing a 3D rotation using input from a mouse, trackball, or other input device are described. Methods of implementing rotations are presented which lead to new realizations of the 3D rotation group and its double-cover, the unit quaternions. New methods, systems, and computer program products are also presented for interpolating rotations of a 3D scene that is more efficient than previously-known quaternion-based methods. The new methods are also used to derive the quaternion composition formula from the geometry of 3D rotations.

First claim

What is claimed is:

1. A computer program product for implementing a method for calculating rotations of a graphical object for display upon a computer system display using input from a computing input device, the computer program product comprising one or more computer hardware storage devices having computer executable instructions encoded thereon which, when executed upon one or more computer processors, perform the method comprising:
accessing a stored graphical data structure comprising data defining a graphical object which is to be displayed on a computer system display device;
receiving input from a computing input device, the input comprising data associated with an intended rotation of the graphical object;
receiving one or more data structures comprising two rotations, A 1 and A 2 , the two rotations associated with the intended rotation of the graphical object;
expressing each rotation as a composition of two reflections, each reflection having a common initial reflection for each of the rotations, such that A 1 =R 1 R and A 2 =R 2 R 1 and each reflection R j being of the form R j =2u j u j T −I;
interpolating two unit vectors, u 0 and u 1 , by u s , 0<s<1, using a standard spherical interpolation on a two-dimensional unit sphere in three-dimensions;
computing interpolated rotations using the formula A s =R s R;
applying the computed interpolated rotations to the stored graphical data structure to realize the intended rotation; and
storing an updated graphical data structure defining the graphical object with the rotations applied which is to be rendered upon the computer system display device.

2. A computer program product for implementing a method for rotating a computer animated object by constructing a rotation matrix for rotating a unit vector u 0 to another unit vector u 1 and preserving a plane and axis defined by the unit vectors, the computer program product comprising one or more computer hardware storage devices having computer executable instructions encoded thereon which, when executed upon one or more computer processors, perform the method comprising:
accessing a stored graphical data structure representing a computer animated object which is to be displayed on a computer system display device;
computing a sum, s, of the unit vectors, s=u 0 +u 1 ;
determining whether the sum, s, is equal to zero;
generating a rotation matrix based upon the unit vectors and the sum, s; and
computing a rotation matrix, A, as a result of the formula:
A=I− 2 ss t /( s t s )+2 u 1 u o t ;

applying the computed rotation matrix to the stored graphical data structure to effect a rotation of the computer animated object; and
storing an updated graphical data structure defining the computer animated object with the rotation applied which is to be rendered upon the computer system display device.

3. A computer program product for implementing a method for rotating vectors defining a viewpoint of a viewer of a computer graphics output device to implement rotation of a computer generated image by taking a unit vector u 0 to another unit vector u 1 and preserving the plane and axis defined by the unit vectors, the computer program product comprising one or more computer hardware storage devices having computer executable instructions encoded thereon which, when executed upon one or more computer processors, perform the method comprising:
accessing a stored graphical data structure representing a computer generated image which is to be displayed on a computer system display device;
receiving data indicative of unit vectors u 0 and u 1 from a computer input device;
computing a rotation as seen from the viewpoint by performing an inverse rotation A −1 on an orthogonal frame describing an orientation of a viewpoint, wherein performing the inverse rotation A −1 on an orthogonal frame comprises:
constructing a sum s of the unit vectors, s=u 0 +u 1 ;
computing a normalization factor k=2/s T s;
performing an inverse rotation for two of three vectors of a viewpoint frame, e 0 and e 1 , by reflecting in s, then reflecting in computing u 0 , by applying the following equations:
w=kss T e j −e j , and
A −1 e j =2 u 0 u 0 T w j −w j ; and

determining a third viewpoint orientation vector e 2 by computing a cross product of the two vectors that have been rotated such that e 2 =e 0 ×e 1 ; and

applying the computed rotation to the stored graphical data structure to effect a rotation of the computer generated image; and
storing an updated graphical data structure defining the computer generated image with the rotation applied which is to be rendered upon the computer system display device.

4. A computer program product for implementing a method for rotating a graphical object by calculating a spherical interpolation of two unit quaternions, the computer program product comprising one or more computer hardware storage devices having computer executable instructions encoded thereon which, when executed upon one or more computer processors, perform the method comprising:
accessing a stored graphical data structure representing a graphical object which is to be displayed on a computer system display device;
accessing a data structure comprising two unit quarternions, Q 0 and Q 1 ;
determining that L((s+t)/2)=0.5 (Q(s)+Q(t)) does not result in a unit quaternion;
normalizing Q((s+t)/2)=L((s+t)/2)/∥L((s+t)/2)∥ to obtain unit quaternions with to equally spaced Q t values, wherein
the normalization of Q((s+t)/2)=L((s+t)/2)/∥L((s+t)/2)∥ with s=0 and t=1 produces Q(½);
the normalization of Q((s+t)/2)=L((s+t)/2)/∥L((s+t)/2)∥ with s=0 and t=½ produces Q(¼); and
the normalization of Q((s+t)/2)=L((s+t)/2)/∥L((s+t)/2)∥ with s=½ and t=1 produces Q(¾);

applying the unit quaternions obtained by normalizing to the stored graphical data structure to realize a rotation of the graphical object; and
storing an updated graphical data structure defining the graphical object with the rotation applied which is to be rendered upon the computer system display device.

5. The computer program product of claim 4 , the method further comprising:
normalizing Q((s+t)/2)=L((s+t)/2)/∥L((s+t)/2)∥ with s=0 and t=¼ to produce Q(⅛).

6. The computer program product of claim 4 , the method further comprising:
normalizing Q((s+t)/2)=L((s+t)/2)/∥L((s+t)/2)∥ with s=¼ and t=½ to produce Q(⅜).

7. The computer program product of claim 4 , the method further comprising:
normalizing Q((s+t)/2)=L((s+t)/2)/∥L((s+t)/2)∥ with s=½ and t=¾ to produce Q(⅝).

8. The computer program product of claim 4 , the method further comprising:
normalizing Q((s+t)/2)=L((s+t)/2)/∥L((s+t)/2)∥ with s=¾ and t=1 to produce Q(⅞).

9. A computer program product for implementing a method for mapping a point in an e 1 -e 2 plane orthogonal to a vector e 3 to a point in the plane orthogonal to an arbitrary given unit vector u, the computer program product comprising one or more computer hardware storage devices having computer executable instructions encoded thereon which, when executed upon one or more computer processors, perform the method comprising:
accessing a graphical data structure comprising a point p1 in a plane P, the graphical data structure further representing a graphical object which is to be displayed on a computer system display device;
mapping the point p1 to a point p2 in the plane, such that p2 is orthogonal to a given unit vector u by, including:
accessing a data structure comprising a vector v=c 1 e 1 +c 2 e 2 ;
rotating the vector v by applying a rotation taking e 3 to u, wherein applying the rotation taking e 3 to u to the vector v comprises:
applying a reflection in e 3 to

Assignees

• The Univ Of Utah Res Found
• Univ Utah Res Found

Inventors

• Palais Robert Andrew
• Palais Richard Sheldon

Classifications

• G06T13/20 Primary

  Three-dimensional [3D] animation · CPC title

• G06T19/20

  Editing of three-dimensional [3D] images, e.g. changing shapes or colours, aligning objects or positioning parts · CPC title

• G06T2219/2016

  Rotation, translation, scaling · CPC title

• G06T2210/32

  Image data format · CPC title

• G06T3/60 Primary

  Rotation of whole images or parts thereof · CPC title