Part III – Plane rendering

   

You can download the DistortedPlane class and examples here Distortedplane (1277).

In the previous example we saw how to render arbitrary triangles, and we showed an example of how to reduce the equations in right-angled cases. In this post we are going to look into rendering a plane. We will do so without any perspective correction for the z-axis, and as mentioned previously distortion is not perspective. (A good treaty on this can be found here http://zehfernando.com/2010/the-best-drawplane-distortimage-method-ever/.

So distorting a plane instead of a triangle. This has been done before and more than once, by Ruben, Sandy, Phillipe van Kessel and probably more.



I want to try to make it understandable how the plane works and show it's actually not that complex.
Dividing a plane is the same as cutting a lot of triangles from it. In the previous post we saw how to map arbitrary triangles from a bitmap to an arbitrary triangle on screen, and now we are simply going to do that a lot of times:

Plane rendering

So we are taking the unoptimized equations for mapping arbitrary triangles from the previous post:

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);

and modify them to accomplish the division of the plane into smaller rectangles, which are divided into triangles.

Below one such rectangle is shown. If you consistently apply the formula above to the triangles in this quad, it doesn't matter which way you divide the triangles, but I've chosen upper-left to lower-right. In addition, I've added UL = Upper-Left, UR = Upper-Right, LL = Lower-Left and LR=Lower-Right to each corner. After that you can arbitrarily choose the in and out points, as long as they are in the same order. In order words if in1 represents the Upper-Left corner in the piece of the bitmap you are going to map, out1 should represent the Upper-Left corner in the triangle you are going to map it to:

Triangle map

So what you can see is that for the upper right triangle OUT1,OUT2, OUT3 and IN1, IN2, IN3 are mapped to UL, LR, UR respectively and for the bottom one it's UL, LR, and LL. IN3 and OUT3 appear twice in the image, representing different points, once for the top and one for the bottom triangle, to clarify:

Quad division into triangles

In our first image our plane was subdivided in an 8 by 8 grid. This means the following holds for a rectangular piece from the source bitmap:

piecewidth = bitmapwidth/8
pieceheight = bitmapheight/8

In other words:

piecewidth = bitmapwidth/gridXCount
pieceheight = bitmapheight/gridYCount

Looking back at dIn32x = in3.x - in2.x, dIn13x = in1.x - in3.x, etc and in the image above at the lower left triangle (the IN-b coordinates), we see the following holds:

var dIn32x:Number = in3.x - in2.x => -piecewidth
var dIn13x:Number = in1.x - in3.x => 0
var dIn21x:Number = in2.x - in1.x => piecewidth
var dIn32y:Number = in3.y - in2.y => 0
var dIn13y:Number = in1.y - in3.y => -pieceheight
var dIn21y:Number = in2.y - in1.y => pieceheight

This means our denomAB and denomAC will become:

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

So what are our in1.x/y in2.x/y etc coordinates?

Well assume we are going through the grid to draw the rectangles/triangles, this will look something like:

for (var y:Number = 0; y < gridYCount; y++) {
	for (var x:Number = 0; x < gridXCount; x++) {
			//1. calculate coordinates and matrix lowerleft triangle
			//2. draw lowerleft triangle
			//3. repeat 1 & 2 for upperright triangle
			//4. now we have drawn a transformed rectangle
	}
}

So we see our In1 coordinate is simply (x*piecewidth, y*pieceheight), In2 is ((x+1)*piecewidth, (y+1)*pieceheight) and In3b is (x*piecewidth, (y+1)*pieceheight).

Putting this into denomAB will give us:
var denomAB:Number = 1/(((x+1)*piecewidth * -pieceheight) + (x*piecewidth * pieceheight));
var denomCD:Number = 1/((y*pieceheight * -piecewidth) + ((y+1)*pieceheight * piecewidth));

So if we define pieceArea as piecewidth*pieceheight we get:

var denomAB:Number = 1/(((x+1)*-pieceArea) + (x*pieceArea));
var denomCD:Number = 1/((y*-pieceArea) + ((y+1)*pieceArea));

Is the same as:
var denomAB:Number = -1/pieceArea;
var denomCD:Number = 1/pieceArea;

Inserting what we've got so far into:

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);

will give us:

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

Simplifying this further gives us:

matrix.a = (out2.x - out3.x) * pieceheight/ pieceArea;
matrix.b = (out2.y -out3.y) * pieceheight /pieceArea;
matrix.c = (out3.x - out1.x) * piecewidth / pieceArea;
matrix.d = (out3.y - out1.y) * piecewidth /pieceArea;
matrix.tx = out1.x - (matrix.a * x*piecewidth) - (matrix.c * y * pieceheight);
matrix.ty = out1.y - (matrix.b * x*piecewidth) - (matrix.d * y * pieceheight);

And further:

matrix.a = (out2.x-out3.x)/piecewidth;
matrix.b = (out2.y-out3.y)/piecewidth;
matrix.c = (out3.x-out1.x)/pieceheight;
matrix.d = (out3.y-out1.y)/pieceheight;
matrix.tx = out1.x - (matrix.a * x * piecewidth) - (matrix.c * y * pieceheight);
matrix.ty = out1.y - (matrix.b * x * piecewidth) - (matrix.d * y * pieceheight);

And even further:
matrix.a = (out2.x-out3.x)/piecewidth;
matrix.b = (out2.y-out3.y)/piecewidth;
matrix.c = (out3.x-out1.x)/pieceheight;
matrix.d = (out3.y-out1.y)/pieceheight;
matrix.tx = out1.x - ((out2.x-out3.x) * x) - ((out3.x-out1.x) * y);
matrix.ty = out1.y - ((out2.x-out3.x) * x) - ((out3.y-out1.y) * y);

We could store the out pairs into variables, but the storing and lookup probably costs just as much as calculating it again.

A slight rewrite might save a bit more, using invPieceWidth = 1/lPieceWidth and invPieceHeight = 1/lPieceHeight, or in other words:

invPieceWidth = gridXCount/bitmapwidth
invPieceHeight = gridYCount/bitmapheight

And then:
matrix.a = (out2.x-out3.x);
matrix.b = (out2.y-out3.y);
matrix.c = (out3.x-out1.x);
matrix.d = (out3.y-out1.y);
matrix.tx = out1.x - (matrix.a * x) - (matrix.c * y);
matrix.ty = out1.y - (matrix.b * x) - (matrix.d * y);
matrix.a *= invPieceWidth;
matrix.b *= invPieceWidth;
matrix.c *= invPieceHeight;
matrix.d *= invPieceHeight;

But as it turns out this is slower then simply keeping it as we had.

So we can do that for the other triangle as well, I'll leave that up to you. One thing we haven't talked about though are the coordinates of the out points. What are the coordinates for the out points?

Take a look at the next image:

interpolation across 4 points

All the colored dots are out points. So for a specific triangle, the dots on the corners of a triangle represent the triangle's out points. When rendering a plane we have to provide the coordinates for it's four corner points. Those points are represented by the green dots.

Now we have to interpolate the coordinates for all the other points. We do that by simply first interpolating all coordinates on the top row between the upper-left and upper-right point, and then all the coordinates on the bottom row between the lower-left and lower-right point.

Remember that linear interpolation between two values is done through this simple formula, with t a value from 0-1: (1-t)*startvalue+t*endvalue

When we have all the coordinates for the top and bottom rows, we can interpolate all the coordinates in between, for example if we pick the top middle coordinate and the bottom middle coordinate, we can interpolate all the red dots etc.

Of course you don't have to do it this way, you can also directly interpolate the value of a single point, but pre-calculating them this way is faster. If you do want to interpolate them directly, you get an equation for 4 points and two interpolation values. Assume you have pUL, pUR, pLL, pLR and ix and iy, where ix and iy are the x and y interpolation values.
First interpolate the upper and lower values, to get a top interpolated value and a bottom interpolated value:

pTop.x = (1-ix)*pUL.x+ix*pUR.x;
pTop.y = (1-ix)*pUL.y+ix*pUR.y;
pBottom.x = (1-ix)*pLL.x+ix*pLR.x;
pBottom.y = (1-ix)*pLL.y+ix*pLR.y;

and then interpolate these over y where pIP is the interpolated point:

pIP.x = (1-iy)*pTop.x-iy*pBottom.x;
pIP.y = (1-iy)*pTop.y-iy*pBottom.y;

Put together:
pIP.x = (1-iy)*((1-ix)*pUL.x+ix*pUR.x)-iy*((1-ix)*pLL.x+ix*pLR.x);
pIP.y = (1-iy)*((1-ix)*pUL.y+ix*pUR.y)-iy*((1-ix)*pLL.y+ix*pLR.y);

But as said I split this in a couple of steps, to avoid re-interpolation for all the non edge points.

So what did we cover so far?

  • using the basic arbitrary triangle mapping formulas
  • calculating the coordinates of the IN and OUT points through interpolation and simplifying our formulas based on that
  • the basics of the render loop

Now in order to get this code as fast as possible I did some other things:

  • only use local variables
  • precalculate anything that being used more than twice (!).
  • create NO objects during rendering

One other thing I tried with no success was converting the point coordinates to a linked quad list so I could unroll the for loops. Another thing I tried was looping using while (x--) and while (y--) instead of incrementing for loops, but there was practically no difference in performance, at least no consistent improvement.

I ran some tests again Sandy's DistortImage class, and preliminary tests show about a 45 to 50% speed improvement. I haven't ran it against any of the other distort classes since my main concern was simply that I wouldn't write something that was way slower. That it is almost twice as fast is simply a bonus, but since I do not completely grasp the distortimage class there might be some hidden stuff that I'm not taking care of.
(Which is just my way of saying 'Use at your own risk' :)).

You can download the DistortedPlane class and examples here Distortedplane (1277).
If you haven't done so try out the two interactive examples at the top of this 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 *