Help Understanding these equations?

Question

I asked a question regarding Bi linear transformations and received this answer:

From that very page you posted, there's a link to the source code. I'll explain the bilinear transformation in

http://www.antigrain.com/__code/include/agg_trans_bilinear.h.html

The idea here is to find a transformation of the form:

output_x = a * input_x + b * input_x * input_y + c * input_y + d
output_y = e * input_x + f * input_x * input_y + g * input_y + h

The term "bilinear" comes from each of those equations being linear in either of the input coordinates by themselves. We want to solve for the right values of a, b, c, and d. Say you have the reference rectangle r1, r2, r3, r4 which you want to map to (0,0), (1,0), (0,1), (1,1) (or some image coordinate system).

For a,b,c,d:

0 = a * r1_x + b * r1_x * r1_y + c * r1_y + d
1 = a * r2_x + b * r2_x * r2_y + c * r2_y + d
0 = a * r3_x + b * r3_x * r3_y + c * r3_y + d
1 = a * r4_x + b * r4_x * r4_y + c * r4_y + d

For e,f,g,h:

0 = e * r1_x + f * r1_x * r1_y + g * r1_y + h
0 = e * r2_x + f * r2_x * r2_y + g * r2_y + h
1 = e * r3_x + f * r3_x * r3_y + g * r3_y + h
1 = e * r4_x + f * r4_x * r4_y + g * r4_y + h

You can solve this however you like best. (If you're familiar with matrix notation, these are two matrix equations for which the matrix is the same, and then you simply need to find the LU decomposition once, and solve the two unknown vectors). The coefficients are then applied to map the interior of the rectangle to the position in the rectangle.

---

The problem is, I have input_x and input_y aswell as r1, r2, r3, r4, but I'm not sure how to achieve output_x and output_y. How do I solve such an equation? I'm only familiar with solving equations with 2 variables.

Thanks

Answer 1

That's a terrible explanation you've found. Hopefully I can help you understand what's going on under the bonnet.

What you want to do is map a rectangular area (one quadrilateral) into another (arbitrarily shaped) quadrilateral. Let's start with a simpler case: Linear interpolation (finding values that lie along a line)

If you have a line from a to b, then you can find any point 'c' on that line by using this equation:

c = ((1 - p) * a) + (p * b);

This 'mixes' (interpolates) the values of the two positions along the straight line between them (linearly). If you use p=0 then the equation turns into

c = (1 * a) + (0 * b)   = a

so at p=0 the equation gives you the point 'a'.

When p=1, the equation becomes:

c = (0 * a) + (1 * b)   = b

so at p=1, the equation gives you the point 'b'.

At intermediate values of p, you get points on the line between a and b. (so at p=0.5 you get the point exactly half way between a and b)

So, to copy the pixels from one line on the screen to another line on the screen, we can use linear interpolation to find the positions on the lines to read from and write to.

for (float p = 0.0; p <= 1.0; p += 0.1)    // copy 10 pixels from line 1 to line 2
    DrawPixelOnLine2(p, GetPixelFromLine1(p));

These two methods would just use linear interpolation to calculate the correct positions to read and draw the pixels, like this:

int ax = 0, ay = 100, bx = 50, by = 170;   // line a-b goes from (0,100) to (50,170)

int px = ((1-p) * ax) + (p * bx);          // calc the x and y values separately
int py = ((1-p) * ay) + (p * by);

(Note that I have to use the calculation twice to do a 2D position. I could interpolate in 3D by simply adding the same calculation agaian for the az/bz/pz coordinates)

So, now you can copy points from one arbitrary straight line to another.

bi-linear interpolation is exactly the same, except we want to find a point within a rectangle rather than within a line, so we need two dimensions to describe where the point is in the rectangle (px along the bottom of the rectangle, and py up the side of the rectangle). Now you can locate any point in the rectangle with an (px,py) coordinate pair.

To do the above mapping, we simply do the linear interpolation calculation in two dimensions: first we interpolate along the bottom and along the top to find two endpoints of a line that passes vertically through the middle of the rectangle. then we interpolate along this vertical line to find the final point in the middle of the rectangle.

The "rectangle" doesn't need to be rectangular. The two dimensions can be used on any 4-sided shape (i.e. you can move the corners of your rectangle anywhere you like and the equations will still find the positions between the corners to fill in the area enclosed by the shape)

In the example you have found, the author is using four points to describe the source shape (a,b,c,d) and another four points to describe the destination shape (e,f,g,h)

In addition, they have made the calculations more efficient by solving the equations to populate a transformation matrix which can be multiplied against points to do the mapping process. However, the effect is the same as what I've described above. Hopefully my explanation makes it a bit easier for you to 'see' what the equations are doing.

Answer 2

If you want to map a rectangle to another you will need simple linear transformation. To map point r to point q you have:

qx = a*rx + b*ry + c
qy = d*rx + e*ry + f

There is 6 variables, you'll need 6 equations (3 points). To map rectangle r to rectangle q:

q1x = a*r1x + b*r1y + c
q1y = d*r1x + e*r1y + f
q2x = a*r2x + b*r2y + c
q2y = d*r2x + e*r2y + f
q3x = a*r3x + b*r3y + c
q3y = d*r3x + e*r3y + f

From above you have to solve 2 systems of 3 linear equations with 3 variables each. They will have exactly 1 solution as long as points are different and not collinear (in case of rectangle corners this is fulfilled).