Fast approximation to the spherical linear interpolation function

• US 7,219,114 B2
• Filed: 04/10/2002
• Issued: 05/15/2007
• Est. Priority Date: 04/10/2002
• Status: Active Grant

• Current Assignee: Patent Purchase Manager LLC (Intellectual Ventures LLC)
• Original Assignee: Patent Purchase Manager LLC (Intellectual Ventures LLC)
• Inventors: Budge, William
• Primary Examiner(s): Chaki; Kakali
• Assistant Examiner(s): Do; Chat C.
• Application Number:
  US10/120,904
• Publication Number:
  US 20030195907A1
• Time in Patent Office: 1,861 Days
• Field of Search: 708/300, 708/313, 708/290, 345/473, 709/290
• US Class Current: 708/290
• CPC Class Codes: G06F 17/17 Function evaluation by approximation methods, e.g. inter- or extrapolation, smoothing, least mean square method G06F17/18 takes precedence ; interpolation for numerical control G05B19/18

Abstract

A method for an accurate approximation to Slerp function that is much faster to compute on current processors. Specifically, the present invention provides a method for obtaining an interpolated quaternion comprising forming a first product of a first quaternion and a first scaling function; forming a second product of a second quaternion and a second scaling function; and forming a sum of the first product and the second product, wherein the first scaling function is approximated by obtaining a first polynomial and wherein the second scaling function is approximated by obtaining a second polynomial, thus obtaining an interpolated quaternion that is in between the first quaternion and the second quaternion.

Claims

1. A computer-implemented method for performing animation with interpolation, comprising:

forming a first product of a first quaternion and a first scaling function;

forming a second product of a second quaternion and a second scaling function; and

forming a sum of said first product and said second product,

wherein said first scaling function is approximated by obtaining a first polynomial having at least two variables that is an approximation of said first scaling function,

wherein said second scaling function is approximated by obtaining a second polynomial having at least two variables that is an approximation of said second scaling function, thus obtaining an interpolated quaternion that is in between said first quaternion and said second quaternion; and

carrying out computer-generated animation based on the obtained interpolated quaternion.

2. The computer-implemented method of claim 1 wherein said obtaining said first and said second polynomials includes obtaining bivariate polynomials that approximate the respective first and second scaling functions.

3. The computer-implemented method of claim 1 wherein said obtaining said first and said second polynomials include obtaining approximations of a first and a second minimax bivariate polynomials, wherein a minimax polynomial is a polynomial of a given degree whose maximum error is the smallest.

4. A computer-implemented method for performing animation with interpolation, comprising:

forming a first product of a first quaternion and a first scaling function;

forming a second product of a second quaternion and a second scaling function; and

forming a sum of said first product and said second product,

wherein said first scaling function is approximated by obtaining a first polynomial that is an approximation of said first scaling function,

wherein said second scaling function is approximated by obtaining a second polynomial that is an approximation of said second scaling function, thus obtaining an interpolated quaternion that is in between said first quaternion and said second quaternion; and

carrying out computer-generated animation based on the obtained interpolated quaternion;

wherein said obtaining said first and said second polynomials include obtaining approximations of a first and a second minimax bivariate polynomials, wherein a minimax polynomial is a polynomial of a given degree whose maximum error is the smallest; and

wherein said obtaining said approximations of said first and said second minimax bivariate polynomials comprises obtaining a first and a second Chebyshev polynomial.

5. The computer-implemented method of claim 4 wherein said Chebyshev polynomials are of order N, M, wherein N is less than M.

6. The computer-implemented method of claim 4 wherein said Chebyshev polynomials are of order N, M, wherein M equals N+1.

7. A computer readable device having computer readable code embodied therein, said code embodying instructions for causing a computer to obtain an interpolated quaternion, comprising:

instructions for forming a first product of a first quaternion and a first scaling function;

instructions for forming a second product of a second quaternion and a second scaling function;

instructions for forming a sum of said first product and said second product,

wherein said first scaling function is approximated by obtaining a first polynomial having at least two variables that is an approximation of said first scaling function,

wherein said second scaling function is approximated by obtaining a second polynomial having at least two variables that is an approximation of said second scaling function, thus causing a computer to obtain an interpolated quaternion that is in between said first quaternion and said second quaternion; and

instruction for carrying out computer-generated animation based on the obtained interpolated quaternion.

8. The computer readable device of claim 7 wherein said instructions for obtaining said first and said second polynomials further comprise instructions for obtaining bivariate polynomials that approximate the respective first and second scaling functions.

9. The computer readable device of claim 7 wherein said instructions for obtaining said first and said second polynomials further comprise instructions for obtaining approximations of a first and a second minimax bivariate polynomials, wherein a minimax polynomial is a polynomial of a given degree whose maximum error is the smallest.

10. A computer readable device having computer readable code embodied therein, said code embodying instructions for causing a computer to obtain an interpolated quaternion, comprising:

instructions for forming a first product of a first quaternion and a first scaling function;

instructions for forming a second product of a second quaternion and a second scaling function;

instructions for forming a sum of said first product and said second product,

wherein said first scaling function is approximated by obtaining a first polynomial that is an approximation of said first scaling function,

wherein said second scaling function is approximated by obtaining a second polynomial that is an approximation of said second scaling function, thus causing a computer to obtain an interpolated quaternion that is in between said first quaternion and said second quaternion,

wherein said instructions for obtaining said first and said second polynomials further comprise instructions for obtaining approximations of a first and a second minimax bivariate polynomials, wherein a minimax polynomial is a polynomial of a given degree whose maximum error is the smallest, and

wherein said instructions for obtaining said approximations of said first and said second minimax bivariate polynomials further comprise instructions for obtaining a first and a second Chebyshev polynomial; and

instruction for carrying out computer-generated animation based on the obtained interpolated quaternion.

11. The computer readable device of claim 10 wherein said Chebyshev polynomials are of order N, M, wherein N is less than M.

12. The computer readable device of claim 10 wherein said Chebyshev polynomials are of order N, M, wherein M equals N+1.

13. A system for performing animation with interpolation, comprising:

memory for storing code; and

at least one processor, wherein said processor operates in response to said code to;

form a first product of a first quaternion and a first scaling function, wherein said first scaling function is approximated by obtaining a first polynomial having at least two variables that is an approximation of said first scaling function,

form a second product of a second quaternion and a second scaling function, wherein said second scaling function is approximated by obtaining a second polynomial having at least two variables that is an approximation of said second scaling function,

form a sum of said first product and said second product, thus obtaining an interpolated quaternion that is in between said first quaternion and said second quaternion, and

carry out computer-generated animation based on the obtained interpolated quaternion.

14. The system of claim 13, further comprising a display that displays animation based on the obtained interpolated quaternion.