Part II – Arbitrary bitmapfill transforms

Recap

In the first post in this series, I discussed and explained matrix transforms and how they could be used to map a bitmap into an arbitrarily drawn triangle. However we saw that if we are ever going to render larger planes in 3d, mapping a single bitmap onto a single rectangle (or 2 triangles) will not cut it, since in order to counter the gruesome texture distortion created by the affine transforms, we will have to subdivide a plane into smaller planes. Note that this is still not perspective correct, it is simply a distorted bitmap with less texture distortion through subdivision. A grid that respects the perspective or rather z-depth of the vertices is up for another post.

Subdividing the plane means we end up with smaller rectangles, that contain smaller pieces of the texture (bitmap). So we are no longer mapping a complete bitmap to a rectangle or triangle, but just pieces of that bitmap.

subdivision sample

Looking back at the first post, we derived the transform for a complete bitmap fill using the following formulas:

a = (p1.x-p0.x)/width
b = (p1.y-p0.y)/width
c = (p2.x-p0.x)/height
d = (p2.y-p0.y)/height
tx = p0.x
ty = p0.y

To be precise we derived these formulas by looking at the a, b, c, d, tx and ty required to map the P1 (0,0) P2 (bitmap_width, 0) and P3 (0, bitmap_height) coordinates of the bitmap to a triangle at P1’ (x1’,y1’), P2’ (x2’,y2’) and P3’ (x3’, y3’).

Inserting all these points into the equation:

P(x,y) => (a*x+c*y+tx, b*x+d*y+ty) => P’(x’,y’)

allowed us to derive the aforementioned formulas.

However we can see now that if we map other points than the (0,0), (bitmap_width,0) and (0, bitmap_height) points, these equations are going to be more complex, since we won’t be able to extract the tx and ty solely based on the (0,0) point.

Before we continue let’s call the points in the bitmap the input points for our transformation, and the points of the drawn and filled triangle the output points. We could call them Pn and Pn’, but I feel in1.x and out1.x are easier to distinguish than P1.x and P1’.x.

complete mapping
(mapping a complete bitmap, with the in points at the corner of the bitmap to arbitrary outpoints)

So although we only need to map rectangles (or rather right angled triangles) within the bitmap to arbitrary triangles, let us take a detour in which we map an arbitrary triangle from the source bitmap to an arbitrary drawn triangle filled with this bitmap data. In other words let us examine transforming one triangle into another triangle and derive more general cases from there. Although a bit more work, it provides us with a more powerful tool if we ever want to perform more complex texture mapping, so why not do it right away.

Arbitrary triangle mapping

arbitrary mapping
(mapping an arbitrary triangle from a bitmap to an arbitrary triangle fill)

More precisely, given:

in1(x,y) => (a*in1.x + c*in1.y + tx, b*in1.x + d*in1.y + ty) => out1(x,y)
in2(x,y) => (a*in2.x + c*in2.y + tx, b*in2.x + d*in2.y + ty) => out2(x,y)
in3(x,y) => (a*in3.x + c*in3.y + tx, b*in3.x + d*in3.y + ty) => out3(x,y)

what are the values of a,b,c,d,tx and ty?

Let’s put this in a slightly different form yet again:

a*in1.x + c*in1.y + tx = out1.x
b*in1.x + d*in1.y + ty = out1.y
a*in2.x + c*in2.y + tx = out2.x
b*in2.x + d*in2.y + ty = out2.y
a*in3.x + c*in3.y + tx = out3.x
b*in3.x + d*in3.y + ty = out3.y

So given these equations, if we can solve these for a, b, c, d, tx and ty, we have found the matrix to map the in points to the out points.

Rewriting and sorting gives us:

tx = out1.x – a*in1.x – c*in1.y
tx = out2.x – a*in2.x – c*in2.y
tx = out3.x – a*in3.x – c*in3.y

ty = out1.y – b*in1.x – d*in1.y
ty = out2.y – b*in2.x – d*in2.y
ty = out3.y – b*in3.x – d*in3.y

We have now pairs we can compare. We can take any two pairs, but let’s take tx for the 1-2 pair first with => denoting ‘follows from’:

out1.x – a*in1.x – c*in1.y = out2.x – a*in2.x – c*in2.y =>
a*in2.x – a*in1.x = out2.x – out1.x + c*in1.y – c*in2.y =>
a = (out2.x – out1.x + c*(in1.y – in2.y)) / (in2.x – in1.x)

So now we’ve found a but we are not done yet, since a is defined in terms of c. Plugging a back into what we’ve got so far is not going to work since (and feel free to try this for yourself) we will end up with 0=0, which although undoubtedly true in this universe, isn’t very useful.

So we take the pair 1-3 and plug the a we’ve found back into that. For 1-2 we found:

a = (out2.x – out1.x + c*(in1.y – in2.y)) / (in2.x – in1.x)

Logically 1-3 will give us:

a = (out3.x – out1.x + c*(in1.y – in3.y)) / (in3.x – in1.x)

This in turn provides us two different values for a we can compare:

(out2.x – out1.x + c*(in1.y – in2.y)) / (in2.x – in1.x)
=
(out3.x – out1.x + c*(in1.y – in3.y)) / (in3.x – in1.x)

Multiplying by (in2.x – in1.x)* (in3.x – in1.x) gives us:

(out2.x – out1.x + c*(in1.y – c*in2.y)) * (in3.x – in1.x)
=
(out3.x – out1.x + c*(in1.y – c*in3.y)) * (in2.x – in1.x)

Rewriting this:

(out2.x – out1.x)* (in3.x – in1.x) + c*(in1.y – in2.y)* (in3.x – in1.x)
=
(out3.x – out1.x) * (in2.x – in1.x) + c*(in1.y – in3.y) * (in2.x – in1.x)

which is the same as (combining the c’s and non c’s)

c*(in1.y – in2.y)* (in3.x – in1.x) – c*(in1.y – in3.y) * (in2.x – in1.x) =
(out3.x – out1.x) * (in2.x – in1.x) – (out2.x – out1.x)* (in3.x – in1.x)

in which we can isolate c:

c * ((in1.y – in2.y)* (in3.x – in1.x) – (in1.y – in3.y) * (in2.x – in1.x)) =
(out3.x – out1.x) * (in2.x – in1.x) – (out2.x – out1.x)* (in3.x – in1.x)

finally giving us:

c = ((out3.x – out1.x) * (in2.x – in1.x) – (out2.x – out1.x)* (in3.x – in1.x)) /
((in1.y – in2.y)* (in3.x – in1.x) – (in1.y – in3.y) * (in2.x – in1.x))

Now as a last step we are going to expand this and factor it again on different values:

Expanding:

c = (out3.x*in2.x – out3.x*in1.x – out1.x*in2.x + out1.x*in1.x – out2.x*in3.x + out2.x*in1.x + out1.x*in3.x – out1.x*in1.x) / (in1.y * in3.x – in1.y*in1.x – in2.y*in3.x + in2.y*in1.x – in1.y*in2.x + in1.y*in1.x + in3.y*in2.x – in3.y * in1.x)

Removing out1.x*in1.x – out1.x*in1.x and – in1.y*in1.x + in1.y*in1.x:

c = (out3.x*in2.x – out3.x*in1.x – out1.x*in2.x – out2.x*in3.x + out2.x*in1.x + out1.x*in3.x) / (in1.y * in3.x – in2.y*in3.x + in2.y*in1.x – in1.y*in2.x + in3.y*in2.x – in3.y * in1.x)

And now factoring out the Out fields:

c = (out1.x*(in3.x-in2.x)+out2.x*(in1.x-in3.x)+out3.x*(in2.x – in1.x)) /
(in1.y *(in3.x-in2.x)+in2.y*(in1.x-in3.x)+in3.y*(in2.x – in1.x)))

So now we have c, which means a is found quickly as well:

a = (out2.x – out1.x + c*(in1.y – in2.y)) / (in2.x – in1.x)

So (we might think) we don’t have to expand the whole equation again, since c is known at this point. We do have to repeat this process for b and d however. This is easily done now that we know how. It irks however to start with c, so instead let’s assume we solved for a and b, and define c and d in terms of them.
After solving a,b,c,d, the tx and ty follow directly from:

tx = out1.x –a*in1.x – c*in1.y
ty = out1.y – b*in1.x – d*in1.y

Putting this all together, refactoring and simplifying the equations so that we reduce the number of computations, we can say that given 3 In points and 3 Out points the transformation from In to Out points is given by:

var dIn21x:Number = in2.x – in1.x;
var dIn32y:Number = in3.y – in2.y;
var dIn13y:Number = in1.y – in3.y;
var dIn21y:Number = in2.y – in1.y;

var denomAB:Number = 1/((in1.x * dIn32y) + (in2.x * dIn13y) + (in3.x * dIn21y));

var matrix:Matrix = new Matrix();
matrix.a = ((out1.x * dIn32y) + (out2.x * dIn13y) + (out3.x * dIn21y)) * denomAB;
matrix.b = ((out1.y * dIn32y) + (out2.y * dIn13y) + (out3.y * dIn21y)) * denomAB;
matrix.c = ((matrix.a * dIn21x) + out1.x – out2.x) / -dIn21y;
matrix.d = ((matrix.b * -dIn21x) + out2.y – out1.y) / dIn21y;
matrix.tx = out1.x – (matrix.a * in1.x) – (matrix.c * in1.y);
matrix.ty = out1.y – (matrix.b * in1.x) – (matrix.d * in1.y);

But although we nicely reduced these equations, we see that c and d are NaNs when point 1 and 2 are on the same y. That can’t be right! So although these equations work when they aren’t, we’ve got ourselves a problem.
The only way around that is to rewrite the equations to a less reduced form:

var dIn32x:Number = in3.x – in2.x;
var dIn13x:Number = in1.x – in3.x;
var dIn21x:Number = in2.x – in1.x;
var dIn32y:Number = in3.y – in2.y;
var dIn13y:Number = in1.y – in3.y;
var dIn21y:Number = in2.y – in1.y;

var denomAB:Number = 1/((in1.x * dIn32y) + (in2.x * dIn13y) + (in3.x * dIn21y));
var denomCD:Number = 1/((in1.y * dIn32x) + (in2.y * dIn13x) + (in3.y * dIn21x));

var matrix:Matrix = new Matrix();
matrix.a = ((out1.x * dIn32y) + (out2.x * dIn13y) + (out3.x * dIn21y)) * denomAB;
matrix.b = ((out1.y * dIn32y) + (out2.y * dIn13y) + (out3.y * dIn21y)) * denomAB;
matrix.c = ((out1.x * dIn32x) + (out2.x * dIn13x) + (out3.x * dIn21x)) * denomCD;
matrix.d = ((out1.y * dIn32x) + (out2.y * dIn13x) + (out3.y * dIn21x)) * denomCD;
matrix.tx = out1.x – (matrix.a * in1.x) – (matrix.c * in1.y);
matrix.ty = out1.y – (matrix.b * in1.x) – (matrix.d * in1.y);

Looking when denomAB or denomCD are NaNs now, show us that all the in points have to be on a straight line for that to happen (which sounds reasonable).

Below is a simple example which shows what we’ve got so far in practice. A UV mapping tool 🙂 (about 1% done that is), unlike the previous images, this one is interactive, drag the handles:

Download this example: Map Example (384).

So with these equations in hand we can start to look at the more general cases.

Right triangle mapping

Let’s only evaluate cases that are actually meaningful. The equations we have found so far are meaningful since they allow arbitrary uvw mapping. Another meaningful variant is where we want to map a right triangle from the source bitmap to a destination triangle (which is usually not right sided). This is meaningful because a lot of times our textures will be rectangular and we will be cutting pieces with right angles from them.

Looking at this triangle:

in1 --- in2
|
|
in3

We see in1.x-in3.x = 0 and in1.y – in2.y = 0 and in3.y-in2.y = in3.y-in1.y this gives us:

var dIn32x:Number = in3.x - in2.x;
var dIn13x:Number = 0;
var dIn21x:Number = -dIn32x;
var dIn32y:Number = in3.y - in2.y;
var dIn13y:Number = -dIn32y;
var dIn21y:Number = 0;

var denomAB:Number = 1/((in1.x * dIn32y) + (in2.x * dIn13y) + (in3.x * 0));
var denomCD:Number = 1/((in1.y * dIn32x) + (in2.y * 0) + (in3.y * dIn21x));

var matrix:Matrix = new Matrix();
matrix.a = ((out1.x * dIn32y) + (out2.x * dIn13y) + (out3.x * 0)) * denomAB;
matrix.b = ((out1.y * dIn32y) + (out2.y * dIn13y) + (out3.y * 0)) * denomAB;
matrix.c = ((out1.x * dIn32x) + (out2.x * 0) + (out3.x * dIn21x)) * denomCD;
matrix.d = ((out1.y * dIn32x) + (out2.y * 0) + (out3.y * dIn21x)) * denomCD;
matrix.tx = out1.x - (matrix.a * in1.x) - (matrix.c * in1.y);
matrix.ty = out1.y - (matrix.b * in1.x) - (matrix.d * in1.y);

Which is, staying in actionscript modus:

var dIn32x:Number = in3.x - in2.x;
var dIn32y:Number = in3.y - in2.y;

var denomAB:Number = 1/((in1.x * dIn32y) - (in2.x * dIn32y) );
var denomCD:Number = 1/((in1.y * dIn32x) - (in3.y * dIn32x));

var matrix:Matrix = new Matrix();
matrix.a = ((out1.x * dIn32y) - (out2.x * dIn32y)) * denomAB;
matrix.b = ((out1.y * dIn32y) - (out2.y * dIn32y) ) * denomAB;
matrix.c = ((out1.x * dIn32x) - (out3.x * dIn32x)) * denomCD;
matrix.d = ((out1.y * dIn32x) - (out3.y * dIn32x)) * denomCD;
matrix.tx = out1.x - (matrix.a * in1.x) - (matrix.c * in1.y);
matrix.ty = out1.y - (matrix.b * in1.x) - (matrix.d * in1.y);

Rewriting this with a further reduction/simplification:

var dIn32x:Number = in3.x - in2.x;
var dIn32y:Number = in3.y - in2.y;

var denomAB:Number = 1/(dIn32y * (in1.x-in2.x));
var denomCD:Number = 1/(dIn32x * (in1.y-in3.y));

var matrix:Matrix = new Matrix();
matrix.a = (dIn32y*(out1.x-out2.x)) * denomAB;
matrix.b = (dIn32y*(out1.y-out2.y)) * denomAB;
matrix.c = (dIn32x*(out1.x-out3.x)) * denomCD;
matrix.d = (dIn32x*(out1.y-out3.y)) * denomCD;
matrix.tx = out1.x - (matrix.a * in1.x) - (matrix.c * in1.y);
matrix.ty = out1.y - (matrix.b * in1.x) - (matrix.d * in1.y);

And the last step, eliminating the dIn32x/y’s:

var denomAB:Number = 1/ (in1.x-in2.x);
var denomCD:Number = 1/ (in1.y-in3.y);

var matrix:Matrix = new Matrix();
matrix.a = (out1.x-out2.x) * denomAB;
matrix.b = (out1.y-out2.y) * denomAB;
matrix.c = (out1.x-out3.x) * denomCD;
matrix.d = (out1.y-out3.y) * denomCD;
matrix.tx = out1.x - (matrix.a * in1.x) - (matrix.c * in1.y);
matrix.ty = out1.y - (matrix.b * in1.x) - (matrix.d * in1.y);

BUT note that this will only work for triangles out of a bitmap with a right triangle between in1-in2 and in1-in3. If you create the angle between different points, you will have to write other optimized equations (or swap the in values so that in1-in2 and in1-in3 form a right triangle, and swap the out points accordingly). You can also see how some of the x’s and y’s of the input values are simply ignored, since these equations ‘assume’ these ignored x’s and y’s are equal to other x’s and y’s that are kept in the equations.

Complete bitmap mapping

So the next simplification on our list is mapping a complete bitmap to a triangle/rectangle. If our equations are correct this will result in:

a = (p1.x-p0.x)/width
b = (p1.y-p0.y)/width
c = (p2.x-p0.x)/height
d = (p2.y-p0.y)/height
tx = p0.x
ty = p0.y

since that is what we found when previously deriving this through another way.

If our complete bitmap is used, with right angles that is (so we continue our previous context), the following holds:

in3.x – in2.x = -bw
in3.y – in2.y = bh
in1.x-in2.x = -bw
in1.y-in3.y = -bh
in1.x = in1.y = 0

Where bw and bh are the bitmap width and height respectively. This results in:

var dIn32x:Number = -bh;
var dIn32y:Number = bh;

var denomAB:Number = 1/(dIn32y * (-bw));
var denomCD:Number = 1/(dIn32x * (-bh));

var matrix:Matrix = new Matrix();
matrix.a = (dIn32y*(out1.x-out2.x)) * denomAB;
matrix.b = (dIn32y*(out1.y-out2.y)) * denomAB;
matrix.c = (dIn32x*(out1.x-out3.x)) * denomCD;
matrix.d = (dIn32x*(out1.y-out3.y)) * denomCD;
matrix.tx = out1.x;
matrix.ty = out1.y;

Simplifying further gives us:

var denomAB:Number = 1/(bh * (-bw));
var denomCD:Number = 1/(-bh * (-bh));

var matrix:Matrix = new Matrix();
matrix.a = (bh*(out1.x-out2.x)) * denomAB;
matrix.b = (bh*(out1.y-out2.y)) * denomAB;
matrix.c = (-bh*(out1.x-out3.x)) * denomCD;
matrix.d = (-bh*(out1.y-out3.y)) * denomCD;
matrix.tx = out1.x;
matrix.ty = out1.y;

And further:

var denomAB:Number = 1/(bh * (-bw));
var denomCD:Number = 1/(-bh * (-bh));

var matrix:Matrix = new Matrix();
matrix.a = (bh*(out1.x-out2.x)) / (bh * -bw);
matrix.b = (bh*(out1.y-out2.y)) / (bh * -bw);
matrix.c = (-bh*(out1.x-out3.x)) /(-bh * (-bh);
matrix.d = (-bh*(out1.y-out3.y)) /(-bh * (-bh);
matrix.tx = out1.x;
matrix.ty = out1.y;

Which is:

var matrix:Matrix = new Matrix();
matrix.a = (out2.x-out1.x) / bw;
matrix.b = (out2.y-out1.y) / bw;
matrix.c = (out3.x-out1.x) / bh;
matrix.d = (out3.y-out1.y) /bh;
matrix.tx = out1.x;
matrix.ty = out1.y;

Which is exactly what we already derived in the first post (although we used p0-p2 instead of out1 to out3).

Identity mapping

So one last not so useful insight: mapping a complete bitmap to a rectangle of the same size without any transformations. For that transformation the following holds:

out2.x-out1.x = bw
out2.y-out1.y = 0;
out3.x-out1.x = 0;
out3.y-out1.y = bh;
out1.x = out1.y = 0;

Inserting them in the equations above results in the identity matrix. Isn’t that beautiful!

So this concludes our post on how we are going to map texture coordinates to subdivided plane coordinates. Rendering an actual plane will be up in the next post!

0 replies

Leave a Reply

Want to join the discussion?
Feel free to contribute!

Leave a Reply

Your email address will not be published. Required fields are marked *