Walk between pixels
This post relates to my article on the calculation of points on Bezier curves using linear texture interpolation. The extended method extends to Bezier surfaces and (multidimensional) polynomials.
The initial observation was that if you sampled diagonally a 2 × 2 texture, then the output data would be points on a quadratic Bezier curve, and the reference points of the curve are pixel values, as in the image below. When I say that you get a quadratic Bezier curve, I express it literally and accurately. What is happening can be represented as follows: texture interpolation is literally performed by the de Castelgio algorithm. (Note: if in the example below the “B” values are not equal, then the second reference point will be the average of these two values: the extension will overuse it to fit more curves into fewer pixels).
My plans have long been to see what happens when sampling pixels in other directions, except for the 45 ° diagonal. In particular, the following interests:
')
When I stumbled upon the answer to the first question, it was time to look at the others!
P. S. What is the use of it? The best thing that comes to mind is data compression on the GPU. If approximated by piecewise rational polynomials, then the ideas of this method are useful for compressing data (pixels in a texture) that are quickly and easily decoded by the GPU. The ideas from this article allow the use of other types of curves for approximation and data storage, except for piecewise rational polynomials. In addition, curves and surfaces of a higher order occupy a smaller amount of textures.
Bilinear interpolation is available on modern GPUs as a way to get subpixel detailing. In earlier times, when scaling a texture, square pixels simply increased, because interpolation was used for the nearest neighboring points. Nowadays, bilinear interpolation fills the space between pixels better than interpolation at the nearest neighboring points.
Bilinear interpolation can be described as interpolation of two values along the x axis and interpolation of the results along the y axis (or in the reverse order). Mathematically, it looks like this:
Where x and y are values from 0 to 1, describing the location of the point between the pixels, and A, B, C and D are the values of the four nearest pixels that form a rectangle around the point that we calculate. A = (0,0), B = (1,0), C = (0,1) and D = (1,1).
After some transformations, this equation is represented as a power series, which is better suited for our experiments:
For more information on bilinear interpolation, study these materials: 1 , 2 , 3 , 4 .
With the formula on hand, you can begin!
So, we know that if the sample goes diagonally from A to D, then we get a quadratic equation. What happens on the other lines?
Before I knew the answer, I assumed that if a line at an angle of 45 ° gives a quadratic equation (degree 2), and horizontal and vertical lines are linear (degree 1), then the sample along other lines must be a polynomial with a degree between 1 and 2 The answer was not so, but I was interested, can I interpret the "real answer" in the form of a polynomial with a degree between 1 and 2?
Anyway, Wikipedia prompted me:
This means that the horizontal or vertical line will be a linear equation. Any other line gives a square.
Let's check.
Remember that the equation for a linear function so literally replace on and see what happens.
So, let's start with the power series of the bilinear interpolation polynomial:
After replacement it turns out:
After some expansion and simplification, we get the following:
This formula reports the value of bilinear interpolation A, B, C, and D (that is, the bilinear surface bounded by these points), and we sample along the x, y line defined by .
This is a very generalized function, about which it is difficult to argue a lot, but one thing is clear: this is a quadratic function! Whatever constant values you choose for A, B, C, D, m, and b, you get a quadratic polynomial (or lower degree, but never higher).
This shader shows curves generated by random sub-pixel line segments on a random RGB (white noise) texture.
(Note that the jagged edges of the curve are related to the fact that interpolation occurs in the fixed-point format X.8, so the accuracy is rather limited. See the above-mentioned scientific work for more information and ways to solve this problem).
Go ahead, specify some values for and and see what happens for different types of lines.
m = 0, b = 0
What will happen if m and b are equal to 0. In other words, what happens when sampling along the line .
Substituting these values gives:
Interestingly, this is simply linear interpolation between A and B, which makes sense when looking at a graph with a sample on a bilinear surface.
This is consistent with what Wikipedia told us: when one of the coordinates is unchanged (horizontal or vertical line), the result is linear.
m = 1, b = 0
Let's try m = 1 and b = 0. This is the line . The graph shows where the sample is taken from on the bilinear surface:
Substituting these values gives the following equation:
We obtained a quadratic equation, which should not be too surprising. It is also a formula for a quadratic Bezier curve with control points. , , .
m = 2, b = 1
Let's try the line Here is a graph where we sample on a bilinear surface:
The substitution of values gives us the equation:
Again we got a quadratic function.
You may be surprised that the equation ends. instead , but if you look at the graph, it makes sense. The line literally starts at point C when x is zero.
x = 2u, y = 3u
In the examples above, we only change the variable y as a function of x. What if you also change the variable x?
One option is to enter the third variable. which takes values from 0 to 1. Then you can express x and y through this variable.
Let's see what happens if you use these two equations:
The sample runs along such a line on the bilinear surface.
Substitution of u functions for x and y gives:
It's still a quadratic equation!
So now we know that when moving in a straight line on a bilinear surface, a quadratic function is obtained, except for the case when the line is horizontal or vertical. Note: if the bilinear surface is a plane, then all the lines on this surface will be linear functions, so this is another way to get a linear result. It can also degenerate to a point. You will never get a cubic result (or higher) when moving in a straight line.
What happens if instead of selecting along straight lines, you choose other shapes, such as quadratic curves?
y = x * x
Let's start with the function . Here is the resulting curve:
Returning to the form of bilinear interpolation in the form of a power series, let's substitute instead and see what happens.
Initial equation:
becomes like this:
It turns:
This is a cubic equation!
Here is a shader that displays this trajectory for random pixels:
The specific elegance of this example is that the cubic equation has four coefficients, which are based on four reference points, so that “everything goes into business”, so to speak.
This is not similar to the sample along the line segments, where the three control points are stored in four pixel values. One of them in this case is a bit superfluous.
You can use this fact, but sampling along a quadratic trajectory to produce a cubic curve seems like a natural approximation.
x = u * u, y = u * u
Let's see what happens if we move x and y quadratically.
As in the linear case, we have our third variable u, which changes from 0 to 1, and we have x and y based on this variable. We will use the following equations:
The sample path is as follows:
When we substitute the values, we get the fourth degree equation:
You may be surprised by looking at a linear path. The simple fact is that x is always equal to y, even if they change non-linearly on the graph: a shader .
Let's frolic a bit by taking these equations:
What corresponds to such a sample trajectory:
If we substitute the values, then the equation of bilinear interpolation ...
... turns into a sixth degree equation:
The Shadertoy shader generator renders it at random pixels as usual, but if u changes from 0 to 1, then x changes from 0 to 3 (y is still in the range from 0 to 1), which leads to some obvious discontinuities at the pixel boundaries. In a purely mathematical formulation, nothing would have happened, but we sample on a real texture, so when we leave our safe house (0.1) we get to a completely new territory with different reference points .
Let's try the function which follows this path on a bilinear surface:
The equation of bilinear interpolation becomes a trigonometric polynomial:
There are gaps due to going beyond the initial pixel domain, so in this case, this shader , generated for . It scales and shifts the values of y so that they are between 0 and 1.
Finally, the sample is on a circle.
Here is its trajectory:
Substitute in the bilinear equation:
Corresponding shaders .
A remarkable feature of the sample in a circle is its continuity. Notice how the left side of the curve goes imperceptibly into the right. This seems like a pretty useful feature.
We have gone a bit to the wilds, but I hope you saw a lot of possibilities for encoding and decoding data in a very small number of pixels, if you carefully select the sample path.
This is more complicated than the simple “sampling diagonally” method, and shader instructions are required. In particular, in the shader, any change of x or y needs to be encoded before transferring linear textures to the interpolator. Hence, the method requires more ALU resources. But it saves texture memory.
The last question from those listed at the beginning of the article: how will the sampling patterns change in higher dimensions, like trilinear or quadrilinear interpolation?
Well, here the mechanism is about the same as in bilinear interpolation, only more measurements.
In two-dimensional bilinear interpolation, we saw that after turning x and y into functions (either from each other or from the third variable u), the resulting polynomial had a degree equal to the sum of the degrees x and y.
In three dimensions with trilinear interpolation, the resulting polynomial will have a degree equal to the sum of the degrees x, y and z.
In the four dimensions with quadrilinear interpolation, add another degree z.
Consider the case when we need not a curve, but a surface or (hyper) volume.
As we saw in the extension, which works with surfaces and volumes, if we have a polynomial of degree N, then it can be divided into a multidimensional polynomial (also known as a surface or overvolume), if the sum of the degrees of each axis is added to N.
This is about what we were just talking about, just the opposite.
There is something that seems to me interesting to study in the future - to see what restrictions arise if you go "too far".
For example, a 2 × 2 texture can give a quadratic function if you sample along any straight line in uv coordinates. If you first express the u coordinate through the cubic function, and the v coordinate through another cubic function, then I think you can make a bicubic surface.
The surface will be limited to a subset of the possible forms of a common bicubic surface, but you will actually get a bicubic surface (basically there will be implicit reference points that you do not control if you do not add more pixels and make additional sampling or linear interpolation of a higher dimension).
I would like to see what restrictions there are and whether there is a chance to get real benefits from something like that.
Anyway, thanks for reading! Any ideas, corrections, use cases - drop me!
@ Atrix256
The initial observation was that if you sampled diagonally a 2 × 2 texture, then the output data would be points on a quadratic Bezier curve, and the reference points of the curve are pixel values, as in the image below. When I say that you get a quadratic Bezier curve, I express it literally and accurately. What is happening can be represented as follows: texture interpolation is literally performed by the de Castelgio algorithm. (Note: if in the example below the “B” values are not equal, then the second reference point will be the average of these two values: the extension will overuse it to fit more curves into fewer pixels).
My plans have long been to see what happens when sampling pixels in other directions, except for the 45 ° diagonal. In particular, the following interests:
')
- What if you try another line?
- What if you sample along a quadratic curve, for example, ?
- What if you try a circle or a sine wave?
- How will the sampling patterns change in higher dimensions, like trilinear or quadrilinear interpolation?
When I stumbled upon the answer to the first question, it was time to look at the others!
P. S. What is the use of it? The best thing that comes to mind is data compression on the GPU. If approximated by piecewise rational polynomials, then the ideas of this method are useful for compressing data (pixels in a texture) that are quickly and easily decoded by the GPU. The ideas from this article allow the use of other types of curves for approximation and data storage, except for piecewise rational polynomials. In addition, curves and surfaces of a higher order occupy a smaller amount of textures.
Quick Setup: bilinear interpolation formula
Bilinear interpolation is available on modern GPUs as a way to get subpixel detailing. In earlier times, when scaling a texture, square pixels simply increased, because interpolation was used for the nearest neighboring points. Nowadays, bilinear interpolation fills the space between pixels better than interpolation at the nearest neighboring points.
Bilinear interpolation can be described as interpolation of two values along the x axis and interpolation of the results along the y axis (or in the reverse order). Mathematically, it looks like this:
Where x and y are values from 0 to 1, describing the location of the point between the pixels, and A, B, C and D are the values of the four nearest pixels that form a rectangle around the point that we calculate. A = (0,0), B = (1,0), C = (0,1) and D = (1,1).
After some transformations, this equation is represented as a power series, which is better suited for our experiments:
For more information on bilinear interpolation, study these materials: 1 , 2 , 3 , 4 .
With the formula on hand, you can begin!
Sampling by other lines
So, we know that if the sample goes diagonally from A to D, then we get a quadratic equation. What happens on the other lines?
Before I knew the answer, I assumed that if a line at an angle of 45 ° gives a quadratic equation (degree 2), and horizontal and vertical lines are linear (degree 1), then the sample along other lines must be a polynomial with a degree between 1 and 2 The answer was not so, but I was interested, can I interpret the "real answer" in the form of a polynomial with a degree between 1 and 2?
Anyway, Wikipedia prompted me:
“The interpolant is linear along lines parallel to x or y, that is, if x or y are constants. Interpolant is quadratic along any other straight line. ”
This means that the horizontal or vertical line will be a linear equation. Any other line gives a square.
Let's check.
Remember that the equation for a linear function so literally replace on and see what happens.
So, let's start with the power series of the bilinear interpolation polynomial:
After replacement it turns out:
After some expansion and simplification, we get the following:
This formula reports the value of bilinear interpolation A, B, C, and D (that is, the bilinear surface bounded by these points), and we sample along the x, y line defined by .
This is a very generalized function, about which it is difficult to argue a lot, but one thing is clear: this is a quadratic function! Whatever constant values you choose for A, B, C, D, m, and b, you get a quadratic polynomial (or lower degree, but never higher).
This shader shows curves generated by random sub-pixel line segments on a random RGB (white noise) texture.
(Note that the jagged edges of the curve are related to the fact that interpolation occurs in the fixed-point format X.8, so the accuracy is rather limited. See the above-mentioned scientific work for more information and ways to solve this problem).
Go ahead, specify some values for and and see what happens for different types of lines.
m = 0, b = 0
What will happen if m and b are equal to 0. In other words, what happens when sampling along the line .
Substituting these values gives:
Interestingly, this is simply linear interpolation between A and B, which makes sense when looking at a graph with a sample on a bilinear surface.
This is consistent with what Wikipedia told us: when one of the coordinates is unchanged (horizontal or vertical line), the result is linear.
m = 1, b = 0
Let's try m = 1 and b = 0. This is the line . The graph shows where the sample is taken from on the bilinear surface:
Substituting these values gives the following equation:
We obtained a quadratic equation, which should not be too surprising. It is also a formula for a quadratic Bezier curve with control points. , , .
m = 2, b = 1
Let's try the line Here is a graph where we sample on a bilinear surface:
The substitution of values gives us the equation:
Again we got a quadratic function.
You may be surprised that the equation ends. instead , but if you look at the graph, it makes sense. The line literally starts at point C when x is zero.
x = 2u, y = 3u
In the examples above, we only change the variable y as a function of x. What if you also change the variable x?
One option is to enter the third variable. which takes values from 0 to 1. Then you can express x and y through this variable.
Let's see what happens if you use these two equations:
The sample runs along such a line on the bilinear surface.
Substitution of u functions for x and y gives:
It's still a quadratic equation!
What about a quadratic trajectory?
So now we know that when moving in a straight line on a bilinear surface, a quadratic function is obtained, except for the case when the line is horizontal or vertical. Note: if the bilinear surface is a plane, then all the lines on this surface will be linear functions, so this is another way to get a linear result. It can also degenerate to a point. You will never get a cubic result (or higher) when moving in a straight line.
What happens if instead of selecting along straight lines, you choose other shapes, such as quadratic curves?
y = x * x
Let's start with the function . Here is the resulting curve:
Returning to the form of bilinear interpolation in the form of a power series, let's substitute instead and see what happens.
Initial equation:
becomes like this:
It turns:
This is a cubic equation!
Here is a shader that displays this trajectory for random pixels:
The specific elegance of this example is that the cubic equation has four coefficients, which are based on four reference points, so that “everything goes into business”, so to speak.
This is not similar to the sample along the line segments, where the three control points are stored in four pixel values. One of them in this case is a bit superfluous.
You can use this fact, but sampling along a quadratic trajectory to produce a cubic curve seems like a natural approximation.
x = u * u, y = u * u
Let's see what happens if we move x and y quadratically.
As in the linear case, we have our third variable u, which changes from 0 to 1, and we have x and y based on this variable. We will use the following equations:
The sample path is as follows:
When we substitute the values, we get the fourth degree equation:
You may be surprised by looking at a linear path. The simple fact is that x is always equal to y, even if they change non-linearly on the graph: a shader .
Higher order curves: x = 3u ^ 2, y = 2u ^ 4
Let's frolic a bit by taking these equations:
What corresponds to such a sample trajectory:
If we substitute the values, then the equation of bilinear interpolation ...
... turns into a sixth degree equation:
The Shadertoy shader generator renders it at random pixels as usual, but if u changes from 0 to 1, then x changes from 0 to 3 (y is still in the range from 0 to 1), which leads to some obvious discontinuities at the pixel boundaries. In a purely mathematical formulation, nothing would have happened, but we sample on a real texture, so when we leave our safe house (0.1) we get to a completely new territory with different reference points .
Trigonometric function: y = sin (2 * pi * x)
Let's try the function which follows this path on a bilinear surface:
The equation of bilinear interpolation becomes a trigonometric polynomial:
There are gaps due to going beyond the initial pixel domain, so in this case, this shader , generated for . It scales and shifts the values of y so that they are between 0 and 1.
Circle
Finally, the sample is on a circle.
Here is its trajectory:
Substitute in the bilinear equation:
Corresponding shaders .
A remarkable feature of the sample in a circle is its continuity. Notice how the left side of the curve goes imperceptibly into the right. This seems like a pretty useful feature.
Moving on
We have gone a bit to the wilds, but I hope you saw a lot of possibilities for encoding and decoding data in a very small number of pixels, if you carefully select the sample path.
This is more complicated than the simple “sampling diagonally” method, and shader instructions are required. In particular, in the shader, any change of x or y needs to be encoded before transferring linear textures to the interpolator. Hence, the method requires more ALU resources. But it saves texture memory.
The last question from those listed at the beginning of the article: how will the sampling patterns change in higher dimensions, like trilinear or quadrilinear interpolation?
Well, here the mechanism is about the same as in bilinear interpolation, only more measurements.
In two-dimensional bilinear interpolation, we saw that after turning x and y into functions (either from each other or from the third variable u), the resulting polynomial had a degree equal to the sum of the degrees x and y.
In three dimensions with trilinear interpolation, the resulting polynomial will have a degree equal to the sum of the degrees x, y and z.
In the four dimensions with quadrilinear interpolation, add another degree z.
Consider the case when we need not a curve, but a surface or (hyper) volume.
As we saw in the extension, which works with surfaces and volumes, if we have a polynomial of degree N, then it can be divided into a multidimensional polynomial (also known as a surface or overvolume), if the sum of the degrees of each axis is added to N.
This is about what we were just talking about, just the opposite.
There is something that seems to me interesting to study in the future - to see what restrictions arise if you go "too far".
For example, a 2 × 2 texture can give a quadratic function if you sample along any straight line in uv coordinates. If you first express the u coordinate through the cubic function, and the v coordinate through another cubic function, then I think you can make a bicubic surface.
The surface will be limited to a subset of the possible forms of a common bicubic surface, but you will actually get a bicubic surface (basically there will be implicit reference points that you do not control if you do not add more pixels and make additional sampling or linear interpolation of a higher dimension).
I would like to see what restrictions there are and whether there is a chance to get real benefits from something like that.
Anyway, thanks for reading! Any ideas, corrections, use cases - drop me!
@ Atrix256
Source: https://habr.com/ru/post/354766/
All Articles