Where to get pseudo code algorithm for projecting a RGB parallelogram into an RGB triangle

Question

What would be pseudo code algorithm fo projecting a parallelogram (2d array of (RGB) points) into a triangle (2d array of (RGB) points) (in my particular case a Rectangle into a Right Triangle with same side size (isosceles) and in my case Hypotenuse is same size that has biggest side of a Rectangle) qualyty may be lost. So how to perform such thing in pseudocode?

So generally we had for example 300x200

We eant to distort it into 150 height and 200 width triangle

with fireworks CS5 - not correct result for me

With photoshop CS5 correct result

So I wonder what would be pseudocode for transformations photoshop does?

Answer 1

I'm not sure if I am misinterpreting your question, however here are my thoughts. I am assuming that the projection will be such that the hypotenuse of the triangle is oriented in the same direction as the longest side of the rectangle, since you said they will be the same size. Some crude pictures (not to scale):

Rectangle H=4, W=10

---------
|       |
|       |
---------

Triangle Hyp=10, S1=8, S2=6

      .
   .   |
.      |
--------

So my suggestion is to do the mapping such that "blocks" of the rectangle are equated to points with the triangle, and each triangle point is an RGB average of the associated rectangle blocks, noting that the blocks may overlap depending on the scale of the original objects.

More concrete, back to the above example first the ratios, the height ratio will be fixed, the rectangle is height 4, the triangle is height 6, so for each pixel vertically in the triangle consider 6/4, or 1.5 in the rectangle. Now there are two options to deal with the ".5", you could either consider rounding up, or down and using only whole blocks, or you could use weights for fractional sections. Since the latter case is less trivial we will look into it further.

As we move vertically any fractional portion will be converted to a fractional weight of that row's pixel so if we are averaging vertically and our pixels are 128 and 137 (only looking at one component for simplicity) then our average would be

(128+(0.5*137))/1.5 = (128+68.5)/1.5 = 196.5/1.5 = 131

Now, since we are looking fractionally we need to keep track of the fractional portion we haven't used, so if the next pixel above is 100 we would want to look at

((137*0.5)+100)/1.5 = (68.5+100)/1.5 = 168.5/1.5 = 112.3

Now we follow a similar strategy moving line by line vertically up the triangle adjusting the ratio as the width of the triangle decreases, so for the base where hypotenuse=rectangle this would trivially be 1. Farther up you may have a ratio such as 1.23 and can do the calculations as above.

Finally some rough pseudocode:

map(rectangle, triangle) {

  decimal yRatio = triangle.height / rectangle.height
  decimal lastY = 0;//we need decimal indeices for fractional averages

  for each line in dest height (yIndex, 0 based) {
    //here you could even find the average width of the rectangle
    //over the block height, but we won't bother
    decimal xRatio = triangle[yIndex].width / rectangle[floor(yIndex*yRatio)].width
    decimal lastX = 0;    //again a decimal for fractional averages

    for each pixel in dest line width (xIndex, 0 based) {

        decimal pixelAverage = 0;
        decimal tempYRatio = yRatio;
        decimal destY = yRatio * yIndex;

        //Here we calculate the source pixel block average
        while(tempYRatio > 0) {
          //the portion of this row of pixels we use is the minimum
          //of the distance to the next integer, and what we need
          decimal yFraction = minimum(tempYRatio, nextInt(destY) - destY);

          decimal tempXRatio = xRatio;
          decimal destX = xRatio * xIndex;
          while(tempXRatio > 0) {
            decimal xFraction = minimum(tempXRatio, nextInt(destX) - destX);
            //now add the weighted pixel to the average
            average += rectangle[floor(destY)][floor(destX)]*xFraction*yFraction;

            tempXRatio -= xFraction;  //reduce the block size
            destX += xFraction;       //and shift the source index
          }

          tempYRatio -= yFraction;  //reduce the block size
          destY += yFraction;       //and shift the source index
        }

        destination[yIndex][xIndex] = average / (xRatio*yRatio);
    }
  }
}
//a helper function to find the next integer value
integer nextInt(decimal d) {
  integer ret = ceiling(d);
  return d == ret ? d+1 : ret;
}

This is off the top of my head, so I can't guarantee it is completely correct, but it should be a good start at the very least performing the averages as appropriate with each of the RGB components of the individual pixels.