This is Words and Buttons Online — a collection of interactive #tutorials, #demos, and #quizzes about #mathematics, #algorithms and #programming.
This is a crossover episode between polynomial interpolation and projective transformations. With projective transformations, you can turn any quadrilateral on a plane into any other quadrilateral with a single matrix multiplication! Yey! However, even in 3D, you can't do the same to hexahedron. Well, not every hexahedron to be precise.
You see, projective transformations not only translate a straight line into a straight line in 2D; in 3D, they translate a plane into a plane as well. And since not every hexahedron has its sides made of perfectly straight planes, there is only a subset of them that are perfectly projectable.
You need tri-linear transformation to transform all the possible hexahedrons into each other. Or tri-quadratic if you want curvy hexahedrons. Or tri-cubic. Tri-polynomial. On 2D, of course, the corresponding transformations will be bi-polynomial, and in other dimensions, well, let's just omit the prefix and call them polynomial.
With polynomial transformations, you get to pick features that you want to preserve while transforming. You can preserve the straightness of lines, or you can guarantee that a parabola will translate into another parabola, or a curvy surface into another surface equally or less curvy than the original. You have options.
In 2013, I wrote the Unpager. It's a tool for unbending the pages from the pictures taken by a phone or a pocket camera. The idea was, if you lack a proper scanner, you can simply take a few pictures of the pages you want. They will, of course, appear all skewed and curvy but that's ok. That's where the Unpages comes in. You unpage the pages, and they look just like if they were scanned.
The points are moveable ↑
I wrote the thing by making a polynomial transformation do what I want: bend pages. This page shows that as soon as you know what you want mathematically, you can probably achieve it with a polynomial transformation, too.
A standard cube is an n-dimensional generalization of the [0..1] range. On a plane, it's an axis-aligned square that has four corners in (0, 0), (1, 0), (1, 1), and (0, 0).
It doesn't bring much mathematical sense into the whole business of transformations, you can still transform from an arbitrary entity to another arbitrary entity, but since the standard cube all consists of ones and zeroes, transforming in and out of this cube requires much simpler equations.
On this page, all the transformations are translating line segments from a standard square to a particular figure on a plane, and they are all ruled by sets of points. This is only a convention, you can still transform any shapes you want.
Ok, so you want to translate a thing by moving 4 points around. Wherever these points go, the neighbors shall follow. This implies that for every transformative equation you'd have to have at least 4 coefficients, too. For the polynomial transformation, this means a 4x4 system of linear equations.
4 points, 4 equations, 4 coefficients, it all comes together nicely.
The idea of bilinear transformation, or bi-anything, or even whatever-anything for that matter, is: you can decompose an n-dimensional translation into n 1-dimensional ones.
For the bilinear transformation, it works the most transparent. Let's say we have a function that linearly interpolates from one value to another as the parameter travels from 0 to 1. Here it is:
// linear interpolation by the two values in 0 and 1
function lerp(y1, y2, x) {
return y1 * (1. - x) + y2 * x;
}
|
Just to reiterate, this is a linear interpolating function. You give it two values and a parameter. When the parameter is 0, it returns the first value, when the parameter is 1, — the second one. When it's something in between, it returns something in between but in such a way that all these inbetweeners form a straight line.
Now you can use two of these to compose a bilinear interpolation. It will also give you back the values you supply it with in the points (0, 0), (1, 0), (1, 1), and (1, 1); and it will also give you the values between these poitns so they will form straight lines along the parametric axes.
function l_transform(points, x, y) {
const x1 = lerp(points[0][0], points[1][0], x);
const x2 = lerp(points[2][0], points[3][0], x);
const x_transformed = lerp(x1, x2, y);
const y1 = lerp(points[0][1], points[1][1], x);
const y2 = lerp(points[2][1], points[3][1], x);
const y_transformed = lerp(y1, y2, y);
return [x_transformed, y_transformed];
}
|
All and all, what it does looks exactly like on the plot below. This is a live plot, the guiding points are draggable.
If mapping a straight quadrilateral to another quadrilateral isn't enough for you, if you need curves, you should go biquadratic.
The main idea remains, we just need another interpolator.
// quadratic interpolation by the three values in 0, 0.5, and 1
function qerp(y1, y2, y3, x) {
const a = 2.0*y1 - 4.0*y2 + 2.0*y3;
const b = -3.0*y1 + 4.0*y2 - y3;
const c = y1;
return a*x*x + b*x + c;
}
|
This is a quadratic interpolation. You give it points in 0, 0.5, and 1, and it computes all the other points so they form a parabola passing through these three points.
And the biquadratic transofrmation looks almost the same as the bilinear one except for the few extra lines and a few extra arguments.
function q_transform(points, x, y) {
const x1 = qerp(points[0][0], points[1][0], points[2][0], x);
const x2 = qerp(points[3][0], points[4][0], points[5][0], x);
const x3 = qerp(points[6][0], points[7][0], points[8][0], x);
const x_transformed = qerp(x1, x2, x3, y);
const y1 = qerp(points[0][1], points[1][1], points[2][1], x);
const y2 = qerp(points[3][1], points[4][1], points[5][1], x);
const y3 = qerp(points[6][1], points[7][1], points[8][1], x);
const y_transformed = qerp(y1, y2, y3, y);
return [x_transformed, y_transformed];
}
|
And it behaves like this:
And, of course, a 2D polynomial transformation doesn't have to be just bi-something. For instance, it can be linear along one axis and cubic along the other. That's how I modeled pages in the Unpager.
The cubic-linear transformation code looks like this:
// cubic interpolation by the four values in 0, 1/3, 2/3 and 1
function cerp(y1, y2, y3, y4, x) {
const a = -9*y1/2 + 27*y2/2 - 27*y3/2 + 9*y4/2;
const b = 9*y1 - 45*y2/2 + 18*y3 - 9*y4/2;
const c = -11*y1/2 + 9*y2 - 9*y3/2 + y4;
const d = y1;
return a*x*x*x + b*x*x + c*x + d;
}
function cl_transform(points, x, y) {
const x1 = lerp(points[0][0], points[1][0], x);
const x2 = lerp(points[2][0], points[3][0], x);
const x3 = lerp(points[4][0], points[5][0], x);
const x4 = lerp(points[6][0], points[7][0], x);
const x_transformed = cerp(x1, x2, x3, x4, y);
const y1 = lerp(points[0][1], points[1][1], x);
const y2 = lerp(points[2][1], points[3][1], x);
const y3 = lerp(points[4][1], points[5][1], x);
const y4 = lerp(points[6][1], points[7][1], x);
const y_transformed = cerp(y1, y2, y3, y4, y);
return [x_transformed, y_transformed];
}
|
And the transformation itself — like this:
The formulas for the interpolants are well known. You can google them up or you can just deduce them with pen and paper. Or, if you're too lazy to google things, you can simply use SymPy.
SymPy is a Python library for symbolic computations. It does your math for you. E. g. the cubic interpolant formula can be deduced automatically by stating that you want your interpolation function through the points you want. Once you get the problem expressed, you run the solver and it does the rest.
For instance, that's how you get the formula for the cubic interpolant.
from sympy import *
y1, y2, y3, y4, a, b, c, d = symbols('y1 y2 y3 y4 a b c d')
print(solve([
d - y1,
a * 1/27 + b * 1/9 + c * 1/ 3 + d - y2,
a * 8/27 + b * 4/9 + c * 2/ 3 + d - y3,
a + b + c + d - y4,
], (a, b, c, d)))
|
Yes, it's that simple. Of course, you can tailor this code to produce a polynomial interpolant you want.
And you can combine interpolants to make the transformation you want.
And you can make it work in 2D, 3D, or kD by adding more interpolants one on top of another.
Have fun!
| Index #mathematics #demos | ← there's more. |
+ Github & RSS |