Fast approximation to the spherical linear interpolation function

• US 20030195907A1
• Filed: 04/10/2002
• Published: 10/16/2003
• Est. Priority Date: 04/10/2002
• Status: Active Grant

• Current Assignee: Patent Purchase Manager LLC (Intellectual Ventures LLC)
• Original Assignee: The 3DO Company
• Inventors: Budge, William
• Granted Patent: US 7,219,114 B2
• Time in Patent Office: Days
• 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 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 said first product and said second product,

wherein said first scaling function is approximated by obtaining a first polynomial,

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

2. The method of claim 1 wherein said obtaining said first and said second polynomials includes obtaining bivariate polynomials.

3. The 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. The method of claim 3 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 method of claim 3 wherein said obtaining said approximations of said first and said second minimax bivariate polynomials comprises obtaining a first and a second Chebyshev polynomial, wherein said Chebyshev polynomials are of order N, M, wherein N is less than M.

6. The method of claim 3 wherein said obtaining said approximations of said first and said second minimax bivariate polynomials comprises obtaining a first and a second Chebyshev polynomial, 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; and

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,

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

8. The computer readable device of claim 7 wherein said code for obtaining said first and said second polynomials further comprises instructions for obtaining bivariate polynomials.

9. The computer readable device of claim 7 wherein said code for obtaining said first and said second polynomials further comprises 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. The computer readable device of claim 9 wherein said code for obtaining said approximations of said first and said second minimax bivariate polynomials further comprises instructions for obtaining a first and a second Chebyshev polynomial.

11. The computer readable device of claim 9 wherein said code for obtaining said approximations of said first and said second minimax bivariate polynomials further comprises instructions for obtaining a first and a second Chebyshev polynomial, wherein said Chebyshev polynomials are of order N, M, wherein N is less than M.

12. The computer readable device of claim 9 wherein said code for obtaining said approximations of said first and said second minimax bivariate polynomials further comprises instructions for obtaining a first and a second Chebyshev polynomial, wherein said Chebyshev polynomials are of order N, M, wherein M equals N+1.