四边形失真

• 版本 2 (双线性插值) - 38.2 KB
• 版本 1 (最近邻) - 13.8 KB

引言

我订阅 CodeProject 的信息流已经很久了。最近，我有点厌倦了上面发布的文章，充斥着 AJAX、WPF、WCF 等等，很少有硬核算法和底层编码。于是我决定翻翻我的代码仓库，为这个伟大的网站贡献我自己的东西。

背景

这段代码是我在尝试只用 C# 和 GDI 开发一个等距引擎时，在处理纹理投影时编写的。虽然纹理的变换可以用简单的矩阵变换完成，但我希望确保自己不会受到任何限制。于是我上网搜索了如何根据四个角的最新位置来扭曲位图。我找到的唯一算法和代码（可运行的代码）是在 http://www.vcskicks.com/image-distortion.php，这在 http://ryoushin.com/cmerighi/en-US/2006-09-30_21/Quadrilateral_Distortion_Algorithm 中得到了很好的解释。这种方法采用了几何方法，并且对于其主要目的来说，效果相当不错，但速度非常慢。所以我不得不自己想出一个算法。

Bresenham garis algoritmas

我的方法基于一个直线绘制算法，所以如果你不清楚如何绘制一条线，这里有一个示例函数

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

提供此示例是为了让你能够识别下面代码中的基本模式。

开始吧

首先，我们对顶线运行直线算法。我们计算从左上角点到右上角点之间的所有点。

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

但是，我们不绘制它们，而是将它们保存到一个数组中。这个数组包含一对点：源像素和目标像素。源像素很容易计算。由于我们正在“绘制”顶线，源像素的 Y 值为 0，X 值从 0 递增到 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;
}

下一步是重复同样的操作，但针对底线。“绘制”一条从左下角到右下角的线，此时目标像素的 Y 值将是 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;
}

接下来代码会变得更复杂一些。首先，我们需要选择较长的那条线。

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

然后，对于较长线上的每个像素，我们在较短线上增加“< 1”的量。现在我们有了交叉线的起点和终点，只需取这些点

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;

并计算绘制该线所需的变量。请记住，这次我们将进行两次递进：一次针对目标像素，一次针对源像素。

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;

最后绘制这条线上的所有像素

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

bug

如果像这样运行代码，你会发现某些图形中的一些像素没有被绘制。当我第一次注意到这一点时，我花了很长时间才弄清楚原因。最后，原因非常简单。如果你取一个简单的 2x2 正方形并将其旋转 45 度，你会注意到在工作时，某些像素会被跳过。我确信这有一个数学解释，很可能与坐标的舍入有关，但这超出了本文的范围。

但为什么会发生这种情况？

 

因为这个算法的工作方式是错误的。对于任何尝试实现过某种映射算法的人来说，请记住，**始终迭代**目标上的每个像素，并使用一个函数来从源进行插值、混合、猜测等等。在这个算法中，我们将源的水平线和垂直线转置到目标。正是这种方法论上的错误（从源到目标，而不是从目标到源）导致了这些伪影。要逆转这一点，我们需要实现上面链接中提供的方法，而这正是我们试图避免的。所以我们必须想出其他的解决方案。

解决方案 1

这是最基本、最懒惰的方法。只需找到变量 nNumOfPixels 的所有调用，然后添加以下行：

nNumOfPixels *= 2;

就这样。我们实际上是在让算法为每条线绘制两倍的像素，步长为 0.5。当坐标被舍入时，它们将覆盖“丢失”的像素，但如果你计算一下，这意味着我们绘制了图像宽度和高度的两倍。这意味着为了覆盖一些像素而绘制了图像像素总数的四倍。这似乎是一个糟糕的解决方案。

解决方案 2

第二个也是最快的方法是跟踪已绘制的像素，然后查找未被定位的像素并复制相邻的颜色。所以首先我们添加这个...

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

然后，在像素绘制代码中，我们添加这个：

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

我们算法的最后一步将是这样的：

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

结论

可能有更好的方法来完成这个结果，尤其是在 3D 方面。但对于用 GDI 实现的算法，我没有找到什么有趣的东西。所以也许这会帮助你，也许不会。但如果你学到了一些东西，或者这段代码能成为你开发东西的基础，我很乐意有所贡献。

备注 

在可下载的项目中，还包含了一些其他类，如 FastBitmap、RGBColor、FastPointF 等。这些类属于我的代码库，它们是为了提高算法性能而包含的，并且超出了本文的范围。但如果你对它们有任何疑问，请随时提出。 

 

版本 2 (双线性插值)    

 

由于有人要求提高图像质量，我上传了一个新版本，它实现了像素插值。因此，每次绘制一个像素时，它的颜色都是源像素及其周围像素的加权平均值。但请记住，要实现此操作，意味着我们不再只读取 1 个像素，而是读取 4 个像素，这使得算法慢了 4 倍。
为了减轻这个问题，我做了一些性能改进，并调整了部分代码。因此，第二个版本中的代码有所不同，但算法没有改变，技术也保持不变。