Quadrilateral Distortion

• Version 2 (Bilinear interpolation) - 38.2 KB
• Version 1 (Nearest Neighbor) - 13.8 KB

Introduction

I have been a subscriber of the CodeProject feed for a long time.. lately I've been a bit bored with the articles that have been posted.. too much AJAX, WPF, WCF, etc.. and not many hardcore algorithms and low level coding. So I decided to look up on my code stash and make my own contribution to this great site..

Background

This code was developed when I was trying to do na isometric engine only using C# and GDI when it came to the point of projecting textures. Even though the transformations of the textures could be done by simple matrix transformations, I wanted to make sure I wasn't limited in any way. So I searched the web for a way to do distortion of a bitmap, given the new position of the four corners. The only algorithm and code (working code) that I could find was at http://www.vcskicks.com/image-distortion.php which is well explained in http://ryoushin.com/cmerighi/en-US/2006-09-30_21/Quadrilateral_Distortion_Algorithm. This method used a geometric approach, and for its main purpose, it works quite well but it is is extremely slow. So I had to come up with my own algorithm..

Bresenham's line algorithm

My method is based on a line drawing algorithm, so in case you are not aware of how to draw a line, here goes a sample function:

public void DrawLine(Color color,Point start, Point end)
{
    //calculate the difference between the two points
    int nDeltaX = end.X - start.X;
    int nDeltaY = end.Y - start.Y;
    //Work with positive values
    int nSizeX = Math.Abs(nDeltaX);
    int nSizeY = Math.Abs(nDeltaY);
    //calculate the maximum amount of pixel that need to be drawned
    int nNumOfPixels = Math.Max(nSizeX, nSizeY);
    //how much we need to increment at each time
    float nIncrementX= nDeltaX; 
    float nIncrementY= nDeltaY;
    if (nSizeX > nSizeY)
    {
        nIncrementX/= nSizeX;//will equal 1
        nIncrementY/= nSizeX;//will be < than 1
    }
    else
    {
        nIncrementX/= nSizeY;//will be < than 1 
        nIncrementY/= nSizeY;//will be 1
    }
    PointF oPoint = start;
    for (int nCurrentPixel = 0; nCurrentPixel <= nNumOfPixels; nCurrentPixel++)
    {
        // Draw the current pixel (coords will be rounded)
        SetPixel((int)oPoint.X, (int)oPoint.Y, color);
        //increment
        oPoint.X += nIncrementX;
        oPoint.Y += nIncrementY;
    }
}

This sample is provided so you can identify the base patterns in the code below.

Let's start

First, we run the line algorithm for the top line. We calculate the points between the top-left point and the top-right point.

//the vars needed to draw a line
float nDeltaX = topRight.X - topLeft.X;
float nDeltaY = topRight.Y - topLeft.Y;
float nNumOfPixels = Math.Max(Math.Abs(nDeltaX), Math.Abs(nDeltaY));
float nOffsetX = nDeltaX / nNumOfPixels;
float nOffsetY = nDeltaY / nNumOfPixels;
PointF oPixel = new PointF(topLeft.X, topLeft.Y);  

But instead of painting them, we save them to an array. This array contains a pair of points: the source pixel and the destination pixel. The source pixels are very easy to calculate. Since we are "drawing" the top line, the source pixels are Y=0 and the X goes from 0 to texture.width.

//how much will the texture X increment for each target Pixel
float nTextureIncrementX = (oTexture.Width / (nNumOfPixels + 1));
float nTextureX = 0;
PointMap[] oTopLine = new PointMap[(int)(nNumOfPixels + 1)];
for (int nCurrentPixel = 0; nCurrentPixel <= nNumOfPixels; nCurrentPixel++)
{
    oTopLine[nCurrentPixel] = new PointMap(new PointF(nTextureX, 0), oPixel);

    nTextureX += nTextureIncrementX;
    oPixel.X += nIncrementX;
    oPixel.Y += nIncrementY;
}

The next step is to repeat the same but for the bottom line. "Draw" a line from bottom-left to bottom-right and at this time, the destination pixel Y will be texture.height.

nDeltaX = bottomRight.X - bottomLeft.X;
nDeltaY = bottomRight.Y - bottomLeft.Y;
nNumOfPixels = Math.Max(Math.Abs(nDeltaX), Math.Abs(nDeltaY));
nIncrementX = nDeltaX / nNumOfPixels;
nIncrementY = nDeltaY / nNumOfPixels;
oPixel = new FastPointF(bottomLeft.X, bottomLeft.Y);

nTextureIncrementX = (oTexture.Width / (nNumOfPixels + 1));
nTextureX = 0;

PointMap[] oBottomLine = new PointMap[(int)(nNumOfPixels + 1)];
for (int nCurrentPixel = 0; nCurrentPixel <= nNumOfPixels; nCurrentPixel++)
{
    oBottomLine[nCurrentPixel] = 
      new PointMap(new PointF(nTextureX, oTexture.Height - 1), oPixel);
    oPixel.X += nIncrementX;
    oPixel.Y += nIncrementY;
    nTextureX += nTextureIncrementX;
}

Next the code gets a little bulkier. First we need to choose the biggest line.

PointMap[] oStartLine = oTopLine.Length > oBottomLine.Length ? oTopLine : oBottomLine;
PointMap[] oEndLine = oTopLine.Length > oBottomLine.Length ? oBottomLine : oTopLine;
float nFactor = (float)oEndLine.Length / (float)oStartLine.Length;

and for each pixel of the biggest line, we will increment "< 1" in the smaller line. Now that we have the start and end of the cross lines, just take the points:

for (int s = 0; s < oStartLine.Length; s++)
{
    PointF oStart = oStartLine[s].To;
    PointF oStartTexture = oStartLine[s].From;
    float nEndPoint = (float)Math.Floor(nFactor * s);
    PointF oEnd = oEndLine[(int)nEndPoint].To;
    PointF oEndTexture = oEndLine[(int)nEndPoint].From;

and calculate the variables needed to draw the line. Keep in mind, this time we are going to make two progressions: one on the target pixels, and a second one on the source pixels.

nDeltaX = oEnd.X - oStart.X;
nDeltaY = oEnd.Y - oStart.Y;
nNumOfPixels = Math.Max(Math.Abs(nDeltaX), Math.Abs(nDeltaY));
nIncrementX = nDeltaX / nNumOfPixels;
nIncrementY = nDeltaY / nNumOfPixels;

float nTextureDeltaX = oEndTexture.X - oStartTexture.X;
float nTextureDeltaY = oEndTexture.Y - oStartTexture.Y;
float nTextureIncrementX = nTextureDeltaX / (nNumOfPixels + 1);
float nTextureIncrementY = nTextureDeltaY / (nNumOfPixels + 1);
PointF oDestination = oStart;
PointF oSource = oStartTexture;

and finally draw all the pixels in this line:

for (int nCurrentPixel = 0; nCurrentPixel <= nNumOfPixels; nCurrentPixel++)
{
    Color c = oTexture.GetPixel((int)oSource.X, (int)oSource.Y);
    oCanvas.SetPixel((int)oPixel.X, (int)oPixel.Y, c);
    
    oPixel.X += nIncrementX;
    oPixel.Y += nIncrementY;
    oSource.X += nTextureIncrementX;
    oSource.Y += nTextureIncrementY;
}

The bug

If you try to run the code like this, you will notice that in some figures, some pixels are not painted. When I noticed this for the first time I really scratched my head, trying to figure out why.. and after all, the reason is really simple. If you take a simple 2x2 square and rotate it 45 degrees, you will notice that while working, some pixels will be skipped. I am sure that there is a mathematical explanation for this, that most probably has to do with the rounding of the coordinates.. but that is out of the scope here..

But Why Does This Happen

 

Because this algorithm works the opposite way that it should.. and for any of you that ever tried to implement any kind of mapping algorithm, remember, always iterate over every pixel on the target, and use a function to interpolate, blend, guess, whatever.. from the source. And on this algorithm, we are transposing the horizontal and vertical lines from the source to the target. It is this error in methodology (source to target, instead of target from source) that causes the artifacts. To invert this, we would have to implement something like the method provided in the links above, which is what we are trying to avoid.. so we must come up with some other solution.

Solution 1

This is the most basic, and lazy one. Just find every call to the variable nNumOfPixels and add the following line:

nNumOfPixels *= 2;

and that is it. What we are actually doing is making the algorithm draw twice the amount of pixels for each line, making increments of 0.5.. and as the coordinates get rounded, they will cover the "lost" pixels, but if you do the math, this means we are drawing the double of the width and the double of the height. This means drawing 4 times the amount of pixels in the images just to cover a few.. this seems a bad solution.

Solution 2

The second and fastest solution is to keep track of the pixels that have been painted, and afterwards find the pixels that weren't targeted and copy the neighboring colors. So first we add this..

Rectangle oBox = _ComputeBox(topLeft, topRight, bottomLeft, bottomRight);
Boolean[,] oPainted = new Boolean[oBox.Width + 1, oBox.Height + 1];

then in the pixel painting code, we add this:

oPainted[(int)(oDestination.X - oBox.X), (int)(oDestination.Y - oBox.Y)] = true;

and the final step in our algorithm will be something like this:

//paint missing pixels
for (int ny = 0; ny < oBox.Height; ny++)
    for (int nx = 0; nx < oBox.Width; nx++)
    {
        if (oPainted[nx, ny] == true)
            continue;

        int nNeigh = 0;
        Color oColor;
        int R = 0;
        int G = 0;
        int B = 0;
        if (nx > 0 && oPainted[nx - 1, ny] == true)
        {
            oColor = oCanvas.GetPixel((nx + oBox.X) - 1, (ny + oBox.Y));
            R += oColor.R;
            G += oColor.G;
            B += oColor.B;
            nNeigh++;
        }
        if (ny > 0 && oPainted[nx, ny - 1] == true)
        {
            oColor = oCanvas.GetPixel((nx + oBox.X), (ny + oBox.Y) - 1);
            R += oColor.R;
            G += oColor.G;
            B += oColor.B;
            nNeigh++;
        }
        if (nx < oCanvas.Width - 1 && oPainted[nx + 1, ny] == true)
        {
            oColor = oCanvas.GetPixel((nx + oBox.X) + 1, (ny + oBox.Y));
            R += oColor.R;
            G += oColor.G;
            B += oColor.B;
            nNeigh++;
        }
        if (ny < oCanvas.Height - 1 && oPainted[nx, ny + 1] == true)
        {
            oColor = oCanvas.GetPixel((nx + oBox.X), (ny + oBox.Y) + 1);
            R += oColor.R;
            G += oColor.G;
            B += oColor.B;
            nNeigh++;
        }
        if (nNeigh == 0)//no painted neighbors
            continue;
        oCanvas.SetPixel((nx + oBox.X), (ny + oBox.Y), 
          Color.FromArgb((byte)(R / nNeigh), (byte)(G / nNeigh), (byte)(B / nNeigh)));
    }

Conclusion

There may be better ways to accomplish this result, specially with 3D.. but for algorithms implemented in GDI, I couldn't find anything interesting. So maybe this will help you.. maybe it won't.. but if you have learned something, or if this code serves as a base for you to develop something.. I'm glad I could help.

Remarks 

In the downloadable project, there are some other classes included like FastBitmap, RGBColor, FastPointF, etc.. these classes belong to my code library, they are included for the performance of the algorithm, and are out of the scope of this article. But if you have any questions about them, go ahead and post them.. 

 

Version 2 (Bilinear Interpolation)    

 

Since a request was made to increase the quality of the images.. I uploaded a new version that does interpolation of the pixels. So every time a pixel is drawn, it's color, is a weighted average of the source pixel and its surrounding pixels.. but keep in mind that for this operation to happen it means that instead of reading 1 pixel, we are now reading 4.. which make the algorithm 4 times slower..
To lessen that, I made a few performance improvements and moved some code around, so the code in the second version is different, but the  algorithm was not changes and the technique remains the same.