Efficient interpolation using not linear interpolation
View Patent ↗Interpolation logic described herein provides a good approximation to a bicubic interpolation, which is generally smoother than bilinear interpolation, without performing all the calculations normally needed for a bicubic interpolation. This allows an approximation of smooth bicubic interpolation to be performed on devices (e.g. mobile devices) which have limited processing resources. At each of a set of predetermined interpolation positions within an array of data points, a set of predetermined weights represent a bicubic interpolation which can be applied to the data points. For a plurality of the predetermined interpolation positions which surround the sampling position, the corresponding sets of predetermined weights and the data points are used to determine a plurality of surrounding interpolated values which represent results of performing the bicubic interpolation at the surrounding predetermined interpolation positions. A linear interpolation is then performed on the surrounding interpolated values to determine an interpolated value at the sampling position.
1. A not linear interpolation unit configured in fixed-function hardware circuitry to, for a plurality of predetermined interpolation positions which surround a sampling position within an array of data points, use corresponding sets of predetermined weights and a plurality of the data points to determine a plurality of surrounding interpolated values which represent results of performing a not linear interpolation at the surrounding predetermined interpolation positions,wherein the predetermined weights are set in the fixed-function hardware circuitry.
2. The not linear interpolation unit of claim 1 wherein the not linear interpolation unit is further configured to pass the surrounding interpolated values to a linear interpolation unit.
3. The not linear interpolation unit of claim 1 wherein the array is an n-dimensional array, and the surrounding predetermined interpolation positions are the 2 n positions of the predetermined interpolation positions which are closest to the sampling position, wherein n≥1.
4. The not linear interpolation unit of claim 3 wherein n=1, and wherein said not linear interpolation is a cubic interpolation.
5. The not linear interpolation unit of claim 3 wherein n=2, and wherein said not linear interpolation is a bicubic interpolation.
6. The not linear interpolation unit of claim 1 comprising fixed-function multiplier logic configured in hardware to determine the plurality of surrounding interpolated values.
7. The not linear interpolation unit of claim 6 wherein the fixed-function multiplier logic comprises multiply and add (MAD) logic implemented in hardware and arranged to perform weighted sums of the data points using the corresponding sets of predetermined weights to determine the plurality of surrounding interpolated values.
8. The not linear interpolation unit of claim 1 wherein the not linear interpolation unit is configured to perform weighted sums of the data points using the corresponding sets of predetermined weights to determine the plurality of surrounding interpolated values.
9. The not linear interpolation unit of claim 8 wherein said plurality of data points comprises a 4×4 set of data points, wherein the sampling position is described by two parameters, and wherein the not linear interpolation unit comprises:
an A calculation unit configured to determine first and second intermediate interpolated values either side of a first component of the sampling position in a first dimension for each of the lines of the 4 33 4 set of data points in the first dimension, wherein the first component of the sampling position in the first dimension is indicated by a first of the two parameters;
a first B calculation unit configured to use the first intermediate interpolated values from the four lines in the first dimension to determine first and second surrounding interpolated values either side of a second component of the sampling position in a second dimension indicated by a second of the two parameters; and
a second B calculation unit configured to use the second intermediate interpolated values from the four lines in the first dimension to determine third and fourth surrounding interpolated values either side of the second component of the sampling position in the second dimension indicated by the second of the two parameters.
10. The not linear interpolation unit of claim 9 wherein the A calculation unit is configured to determine the first and second intermediate interpolated values for each of the lines in the first dimension by performing a weighted sum according to:
w A (u)A +w B (u)B +w c (u) C +w D (u) D
where A, B, C and D are the four data points of the line in the first dimension and w A , w B , w c and w D are their corresponding weights which are functions of the first parameter, u, wherein the values of the weights are predetermined for values of the first parameter corresponding to the predetermined interpolation positions, and wherein the A calculation unit is configured to determine the first and second intermediate interpolated values respectively at the two of the predetermined interpolation positions which are closest to the first component of the sampling position in the first dimension.
11. The not linear interpolation unit of claim 10 wherein the A calculation unit comprises hardware adapted to perform the weighted sum, and wherein the predetermined weights are set to provide an imperfect representation of the not linear interpolation to thereby simplify the hardware adapted to perform the weighted sum compared to providing a perfect representation of the not linear interpolation.
12. The not linear interpolation unit of claim 11 wherein the not linear interpolation is a Catmull-Rom interpolation.
13. The not linear interpolation unit of claim 10 wherein for each of the predetermined interpolation positions the sum of the predetermined weights w A , w B , w C and w D is one, and wherein the predetermined weights are symmetric such that w A (u) ≡w D ( 1 −u) and w B (u) ≡w c ( 1 −u).
14. The not linear interpolation unit of claim 9 wherein the A calculation unit is configured to add an offset when determining said first and second intermediate interpolated values in order to ensure that the first and second intermediate interpolated values are not negative.
15. The not linear interpolation unit of claim 9 wherein the A calculation unit is configured to process one of the four lines in the first dimension on each of a plurality of clock cycles, and wherein the first B calculation unit is configured to multiply the first intermediate interpolated values by appropriate ones of the predetermined weights on each of the plurality of clock cycles and to accumulate the results over the plurality of clock cycles to determine the first and second surrounding interpolated values; and
wherein the second B calculation unit is configured to multiply the second intermediate interpolated values by appropriate ones of the predetermined weights on each of the plurality of clock cycles and to accumulate the results over the plurality of clock cycles to determine the third and fourth surrounding interpolated values.
16. The not linear interpolation unit of claim 13 , wherein the predetermined interpolation positions divide a region between adjacent data points of the array into 8 sections, and the not linear interpolation is a Catmull-Rom spline, and wherein the weights w A , w B , w C and w D are given by:
U
w A
w B
w C
w D
0
0
1
0
0
1/8
−12/256
247/256
23/256
−2/256
2/8
−2/32
28/32
7/32
−1/32
3/8
−18/256
186/256
100/256
−12/256
4/8
−2/32
18/32
18/32
−2/32
5/8
−12/256
100/256
186/256
−18/256
6/8
−1/32
7/32
28/32
−2/32
7/8
−2/256
23/256
247/256
−12/256
8/8
0
0
1
0.
17. The not linear interpolation unit of claim 1 wherein the data points in the array are texels of a texture.
18. Interpolation logic comprising:
the not linear interpolation unit of claim 1 ; and
a linear interpolation unit configured to perform a linear interpolation on the plurality of surrounding interpolated values to determine an interpolated value at the sampling position.
19. A logic-implemented interpolation method comprising:
for a plurality of predetermined interpolation positions which surround a sampling position within an array of data points, using, by at least one logic module implemeneted in fixed-function hardware circuitry, corresponding sets of predetermined weights and a plurality of the data points to determine a plurality of surrounding interpolated values which represent results of performing a not linear interpolation at the surrounding predetermined interpolation positions, wherein the predetermined weights are set in the fixed-function hardware circuitry.
20. A non-transitory computer readable storage medium having stored thereon a computer readable description of a not linear interpolation unit that, when processed, configures a system for generating the not linear interpolation unit,
wherein the not linear interpolation unit is configured in fixed-function hardware circuitry to, for a plurality of predetermined interpolation positions which surround a sampling position within an array of data points, use corresponding sets of predetermined weights and a plurality of the data points to determine a plurality of surrounding interpolated values which represent results of performing a not linear interpolation at the surrounding predetermined interpolation positions, wherein the predetermined weights are set in the fixed-function hardware circuitry.