Click here to Skip to main content
15,868,292 members
Articles / Multimedia / GDI+

Quadrilateral Distortion

Rate me:
Please Sign up or sign in to vote.
4.92/5 (21 votes)
30 Aug 2011CPOL5 min read 45.6K   1.9K   25   15
Non-affine transformations, four-point distortions, or whatever you want to call it.

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

Quadrilateral_Distortion/App.png

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:

C#
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;
    }
}

Quadrilateral_Distortion/Bresenham.png

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.

C#
//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.

C#
//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;
}

Quadrilateral_Distortion/Step1.png

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.

C#
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;
}

Quadrilateral_Distortion/Step2.png

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

C#
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:

C#
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.

C#
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:

C#
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;
}

Quadrilateral_Distortion/Step3.png

The bug

Quadrilateral_Distortion/Artifacts.png

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

Quadrilateral_Distortion/Bug.png 

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:

C#
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..

C#
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:

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

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

C#
//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)));
    }

Quadrilateral_Distortion/Correct.png

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)    

Image 9 

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.  

   

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


Written By
Software Developer
Portugal Portugal
From the age of 15 I started programing in QBasic at home after several jobs I realized that what I wanted was to work with computers, so I joined a IT company, originally as a web designer, but thanks to my self learning abilities I made my way into the programmers team. Today I know VB, VBScript, Javascript, HTML, SQL , C# and C++... even if I never went to college.. Smile | :)

Comments and Discussions

 
QuestionTransparency handling and interpolation Pin
Member 1117223125-Feb-18 22:04
Member 1117223125-Feb-18 22:04 
AnswerRe: Transparency handling and interpolation Pin
CaldasGSM4-Apr-18 1:44
CaldasGSM4-Apr-18 1:44 
QuestionReverse Quadrilateral Distortion? Pin
airbiscuity11-Feb-18 3:59
airbiscuity11-Feb-18 3:59 
AnswerRe: Reverse Quadrilateral Distortion? Pin
CaldasGSM4-Apr-18 1:54
CaldasGSM4-Apr-18 1:54 
GeneralWell Done Pin
Alan Burkhart29-Nov-17 15:28
Alan Burkhart29-Nov-17 15:28 
QuestionThe same Operation for a Polygon (GraphicsPath)? Pin
KingSora14-Aug-15 1:22
KingSora14-Aug-15 1:22 
AnswerRe: The same Operation for a Polygon (GraphicsPath)? Pin
CaldasGSM14-Aug-15 5:12
CaldasGSM14-Aug-15 5:12 
GeneralRe: The same Operation for a Polygon (GraphicsPath)? Pin
KingSora16-Aug-15 20:30
KingSora16-Aug-15 20:30 
BugBug in GetAngle method (loss of precision) - quck fix Pin
krenakrama15-Nov-13 1:18
krenakrama15-Nov-13 1:18 
QuestionThat is not even my code :( Pin
CaldasGSM25-Nov-13 12:30
CaldasGSM25-Nov-13 12:30 
BugQuality Pin
Member 99581675-Jun-13 22:37
Member 99581675-Jun-13 22:37 
SuggestionRe: Quality Pin
CaldasGSM6-Jun-13 8:49
CaldasGSM6-Jun-13 8:49 
QuestionMy vote of 5... Pin
Blubbo6-Sep-11 2:04
Blubbo6-Sep-11 2:04 
GeneralMy vote of 5 Pin
Paul M Watt1-Sep-11 20:20
mentorPaul M Watt1-Sep-11 20:20 
GeneralMy vote of 5 Pin
Dave Kerr30-Aug-11 23:03
mentorDave Kerr30-Aug-11 23:03 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.