2D Interpolation

Hi,

I’m looking for a smart way to do two-dimensional remapping for xy-coords. The goal is to define a quad with four independant corner coords representing the new bounds for the original scale of -1 to 1 for x and y.
Any idea?

To make the task a bit clearer perhaps: I need something like homographic projection but with linear interpolation.
Please see the attached sample I quickly did.

projection.v4p (6.3 kB)

diki did something like that. google keyword would be ‘bilinear interpolation’.

Hi t., thanks for the hint, but dikis module only remaps a fixed grid. I’d like to have a flexible input for x and y instead. Do you know what I mean?

flexible projection.v4p (9.7 kB)

ahh, then check the help file of the plugin WarpPoints (2d). its in the addonpack. just change grid resolution to 2 in each dimension.

1 Like

Nice - thanks for pointing me towards that.
But just out of interest, don’t you think this could also be done with some matrix transformation?

hm, not sure, but here is a quick and dirty implementation of the formula on wikipedia:

Awesome! Thanks a lot, mate :)
I always feel more comfortable when I actually see how a routine works, being able to learn from it.

yea, but sorry, i messed up the vectors a bit, here again:

bilerp2.v4p (12.7 kB)

Works like a charm :) Thanks!

But just out of interest, don’t you think this could also be done with some matrix transformation?

no. i would say it is impossible to build a matrix which holds all the information.
in general the needed vector transformation is a function like this:

(x’, y’) = bilerp_transform( A, B, C, D, (x, y) )

with A, B, C, D being the 4 corners of the target surface
(x, y) a source vector which needs to be transfomed
(x’, y’) the destination vector

this bilerp_transform function (like patched by tonfilm or written in math terms on wikipedia) shows that the destination vector is dependant of x and y of the source vector, but also by x*y.

the standard multiplication of a vector with a matrix (ApplyTransform) doesn’t support this operation. There is no field inside a matrix to encode omegaxy.

i would say if you can insure that for each vector (x, y, z) is composed in a way (x, y, z=x*y) then you can build a matrix which (together with these prepared vectors) will result in a bilerp when applying those vectors to the matrix.

but i don’t know if it is worth the hack…

haha, morning, nice idea gregsn, i could not resist to write some matrics on my sketchbook… if we just add the xy as z-component and a w-component with value 1 to the vector, this actually works!

formula with x and y as interpolation factors for one value, if input space is in the range 0…1:

{CODE(ln=>1)}

p1 * (1-x) * (1-y) +
p2 * x * (1-y) +
p3 * (1-x) * y +
p4 * x * y

expands to:

{CODE(ln=>1)}

-p1 * x +
p2 * x +
-p1 * y +
p3 * y +
p1 * xy +
-p2 * xy +
-p3 * xy +
p4 * xy
p1 * 1 +

sorted by (x, y, xy, 1) vector:

{CODE(ln=>1)}

x * (p2 - p1) +
y * (p3 - p1) +
xy * (p1 + p4 - p2 - p3) +
1 * p1

this can be written in one column of a matrix/vector multiplication.
so we use two columns to interpolate x and y.

the matrix/vector multiplication in directX terms then is:

{CODE(ln=>1)}

|(p2x - p1x) ,(p2y - p1y) , 0, 0| | x |
| | | |
|(p3x - p1x) ,(p3y - p1y) , 0, 0| | y |
| | * | |
|(p1x+p4x-p2x-p3x),(p1y+p4y-p2y-p3y), 0, 0| | xy |
| | | |
| p1x , p1y , 0, 1| | 1 |

now is just left to modify the input space a little, that it does not have to be in 0…1 range.

bilerp_matrix.v4p (21.5 kB)

@tonfilm: yes! awesome!

now the only question is if the manipulation of vectors together with ApplyTransform is faster than the thre lerps (InputMorph).

the dirty part where the matrix is created could easily be hidden from the user (by modules)

Bilerp (2d CreateHack)
Bilerp (2d ApplyHack)

oder so. ;)

its probably the best to make two plugins. like

Bilerp (2d)
Bilerp (Transform 2d)

dont know whats faster…
the advantage of the matrix is, that it has only to be computed once and can then be used to transform any amount of values, while the lerps always have to be computed.

ok, now i added the bilerp functions to the math and color utils and made 2 plugins.

Your Tonfilmness,
Lord Gregsn,

I bow in deepest admiration…
The modules are of great use I think!
And although this is beyond my skills and will most likely reveal my ultimate ignorance of how things work, please let me ask one last question: How about cascading the above solution to achieve fast, multidimensional rasterization? Nonsense I guess…

… no text …

as the lerp can be used to define a bilerp, the bilerp can be used to define a trilerp:

lerp, unit line:

return a + x * (b - a);

bilerp, unit square:

//interpolate upper values in x direction
P1 = Lerp(P1, P2, Input.x);

//Interpolate lower values in x direction
P3 = Lerp(P4, P3, Input.x);

//interpolate results in y direction
return Lerp(P3, P1, Input.y);

trilerp, unit cube:

//interpolate the front side
V000 = Bilerp(Input.xy, V010, V110, V100, V000);

//interpolate the back side
V111 = Bilerp(Input.xy, V011, V111, V101, V001);

//interpolate in z direction
return Lerp(V000, V111, Input.z);

here Input is the interpolation position inside the unit space, range ~091~0…1~093~.

to interpolate at a particular position x inside a big grid of data, you first have to find the data at the nearest neighbour grid pionts, and then interpolate between them. the interpolation factor then is the position x relative to the positions of the nearest neigbour data.

1d example:
dataset with 5 values ~091~1, 3, 2, 5, 1~093~. so the range for the 1-d position x is ~091~0…4~093~. to sample the value at the position x = 2.8, you get the data of the nearest neighbours at index floor(x) = 2 and ceil(x) = floor(x) + 1 = 3 and the interpolation weight by frac(x) = x - floor(x) = 0.8.

so we have:

index = floor(2.8); // index = 2
x = x - index; // x = 0.8
n1 = data~091~index ~093~; // n1 = 2
n2 = data~091~index+1~093~; // n2 = 5

result = lerp(n1, n2, x); // result = 2 + 0.8 * (5 - 2) = 4.4

as i also added a trilerp plugin, you should now be able to build a 2d and 3d rasterizer ;).

and as a side note:
if you use cascaded inputmorphs to patch the trilerp, you don’t need to do the frac & floor stuff. however you would need to feed the values of dataset [1, 3, 2, 5, 1](1, 3, 2, 5, 1) into the different intput pins.

if you do lerp by resample with mode linear or with b-spline degree 1.0 then you can feed the data as a spread…

just cascade them to get into higher dimensions.