《转载》二维图像的三角形变形算法

原文网址：http://blog.csdn.net/duanwuqing/article/details/5458286

最近在工程的技术过程中不断的遇到图像变形的问题，特别的是三角形变形问题。前一段时间为了图省事，偷工减料，采用了OpenGL的纹理映射后渲染的方法来得到变形后的图像，当然这是一种投机取巧的方法，而且对于要得到大尺寸的图像来说，由于OpenGL的窗口限制，通常需要根据尺寸的大小动态分块渲染然后组合（或者采用FBO离屏渲染的方式），这带来了相当的弊端，实际上，这应该是图像处理上的一个基本算法。在参照别人提出的方法后，我决定自己实现了这个三角形变形算法。在整个变形过程中，采取的是四像素双线性插值的方法实现的变形效果。

      难得闲暇，于是趁此时整理出来，也可供有同样需求的朋友参考指正。

      下面概述该方法的主要过程，鉴于文字表述的局限，结合图形并伪码的方式介绍：

      1. 确定三角形的映射关系

      对于熟悉矩阵的朋友来说，两个空间位态的变换用矩阵的表示是再简便不过了，矩阵在图形图像中大量使用，这里也利用矩阵来表示两个三角形的映射关系。

      用齐次坐标来表示一个二维点坐标，比如A点的坐标为(x0, y0),则其齐次坐标为(x0, y0, 1),对于三角形变形来说，如下图所示，矩阵的变换相当于将△ABC中的每个点映射到△A'B'C'，由于已经存在了三个顶点的对应关系，即A->A',B->B',C->C',则可以定义一个3×3的矩阵M，则有M•(A, B, C) = (A', B', C'),由于三角形的三个顶点不共线，因此(A, B, C)组成的矩阵存在逆矩阵，从而得到矩阵M=(A', B', C') •(A, B, C)^-1 ，该矩阵M决定了△ABC到△A'B'C'的映射关系。

 

      有了变换矩阵后，△A'B'C'中的任何一点在△ABC都存在原象，也就是说，△A'B'C'中存在的任意一个像素都能匹配到△ABC中的某一点，由于该点未必恰好为某个像素位置，因此还需要进行插值得到适合的颜色值，下面介绍如何插值。

      2. 双线性插值

      因为三角形变形后不能保证像素之间的一一对应关系，因此采取一定的插值方式可以尽可能的保证图像像素的连续性。这里采用较为常见的四像素双线性插值。

 

      如图中是简单的图像缩放变形，右图是左图放大了5/3倍后的图像，那么右图中的像素如(3, 3)点经过逆变换后对应于原图像中的(1.8, 1.8)，如果取该结果的最近一个像素，那么就应该是(2, 2)像素点，这也就是传说中的最近点(nearest)方法，众所周知，这种方法并不好，它会造成像素不连续的现象。而双线性插值的方法认为，该点的颜色值应由它上下左右四个像素值确定，即(1.8, 1.8)像素的颜色值应该由(1, 1)、(2, 1)、(1, 2)、(2, 1)四个像素共同决定，而这四个像素的加权关系则由该点到四个像素的距离决定。所谓双线性插值，这里可以在横纵向双次线性插值。

      首先进行横向插值（其中C(x, y)表示(x, y)处的颜色值）：

                     C(1.8, 1) = C(1, 1) + 0.8 * (C(2, 1) - C(1, 1))

                     C(1.8, 2) = C(1, 2) + 0.8 * (C(2, 2) - C(1, 2))

      再进行纵向插值：

                     C(1.8, 1.8) = C(1.8, 1) + 0.8 * (C(1.8, 2) - C(1.8, 1))

      经过双线性插值后得到的像素值是通过其上下左右四个像素进行插值得到的，通常可以保证颜色的连续性，注意，对于颜色分离R,G,B,A，要分别进行插值。

      综上所述，对于变形后图像的任意像素点P'(x', y')，经过M矩阵逆变换可以找到其在源图像上的象点P(x,y)，通过双线性插值的方法得到P(x, y)的颜色值，则变形后像素点P'的像素即为该颜色值。

      形式化表述为：

 

                     C(x, (int)y) = C((int)x, (int)y) + (x - (int)x) * (C((int)x + 1, (int)y) - C((int)x, (int)y))                      C(x, (int)y + 1) = C((int)x, (int)y + 1) + (x - (int)x) * (C((int)x + 1, (int)y + 1) - C((int)x, (int)y + 1))                      C(x, y) = C(x, (int)y) + (y - (int)y) * (C(x, (int)y + 1) - C(x, (int)y))

 

      3. 扫描线技术

      已知变换方法和线性插值方法之后，不难得到变形后的图像，现在的问题剩下，如果遍历变形后三角形覆盖的像素。我们总不能遍历图像上的每一个像素，然后判断其是否在三角形中，然后为在三角形中的像素提取其原象中的像素值。这样不是不可以，而是效率太低，很明显，我们要尽可能少的遍历像素，因此，需要一种扫描手段，能够快速准确的扫描所有包含在该三角形内的像素，扫描线技术正源于此。

      在进行扫描线方法介绍之前，先来对三角形形状进行分类，并且需要就三角形顶点的排序进行某种规定。如下图所示：

 

 

       三角形的形状大致可以分为三类，第一类为平顶三角形，第二类为平底三角形，第三类为不同于前两类的一般三角形。我们首先来介绍一下平顶三角形的扫描方法：

       (1) 首先对三角形顶点进行排序，纵坐标越大，排序越考前，如果纵坐标相等，则横坐标越小，排序越考前。经过排序后的三角形顶点顺序如图标注。排序后的三角形顶点为(v₁ , v₂ , v₃ )，坐标分别为(x₁ , y₁ ), (x₂ , y₂ ), (x₃ , y₃ )。

       (2) 从三角形底部开始沿横向的线段向上扫描。扫描的纵向范围从(int)y₃ 开始，到(int)y₁ 结束。问题转换为当y=y0时，扫描线段的起点和终点确定问题。

            计算扫描线从v₃ 点移动过程中扫描线起点的变化情况。dy = y₁ - y₃ , dx_left = x₁ - x₃ , 从而扫描线起点在X轴上的步长dxl = dx_left / dy;同理，dx_right = x₂ - x₃ , dxr = dx_right / dy表示扫描线终点在X轴上的步长。因此可以计算得到当y = y0时，起点和终点分别为

            x_start = x₃ + (y0 - y₃ ) * dxl

            x_end = x₃ + (y0 - y₃ ) * dxr

            然后沿扫描线绘制像素:DrawLine(x_start, x_end, y0);

       同理，平底三角形可以同样的方法进行扫描：从底部开始扫描，纵向范围为(int)y₂ 到(int)y₁ ,计算起点步长为dxl =

(x₁ - x₂ ) / (y₁ - y₂ ),终点步长为dxr = (x₁ - x₃ ) / (y₁ - y₂ )。当y = y0时，起点和终点分别为：

            x_start = x₂ + (y0 - y₂ ) * dxl

            x_end = x₃ + (y0 - y₂ ) * dxr

       得到起点和终点后，决定了该扫描线段，沿该线段绘制:DrawLine(x_start, x_end, y0);

      

void DrawFlatTopTri(DPoint2 v1, DPoint v2, DPoint v3)
{
     float dy = v1.y - v3.y;
     float dxl = (v1.x - v3.x) / dy;
     float dxr = (v2.x - v3.x) / dy;
     float x0, x1;
     x0 = x1 = v3.x;
     for(int i = (int)v3.y; i < v1.y; i++)
     {
          DrawLine((int)x0, (int)x1, i);
          dy = (i + 1) - v3.y;
          x0 = v3.x + dy * dxl;
          x1 = v3.x + dy * dxr;
     }
}
void DrawFlatButtomTri(DPoint2 v1, DPoint v2, DPoint v3)
{
     float dy = v1.y - v2.y;
     float dxl = (v1.x - v2.x) / dy;
     float dxr = (v1.x - v3.x) / dy;
     float x0, x1;
     x0 = v2.x;
     x1 = v3.x;
     for(int i = (int)v2.y; i < v1.y; i++)
     {
          DrawLine((int)x0, (int)x1, i);
          dy = (i + 1) - v2.y;
          x0 = v2.x + dy * dxl;
          y0 = v3.x + dy * dxr;
     }
}
void DrawLine(int x0, int x1, int y0)
{
    int pixel = 0;
    for(int i = x0; i <= x1; i++)
    {
         pixel = GetOriginPixel(i, y0);         //获取其对应源图像中的像素
         SetPixel(i, y0, pixel);
    }
}

      至此，平顶三角形和平底三角形的扫描方法均已获得，同时，对于第三类三角形，我们不难发现，它肯定可以分解为两个三角形，并且这两个三角形分别为平顶三角形和平底三角形，切分如上图中(3)所示。因此说，解决了平顶三角形和平底三角形的扫描方法之后，我们就可以处理任意一个三角形。

 

      总结

      通过上面的介绍，我们已经可以进行任意三角形的变形了。当然，变形过程中当然可能存在着像素或细节损失，这是不可避免的，我想对于变形算法来说，大家不会想着变形后再原模原样地恢复成原来的图像吧。从连续性角度来说，双线性插值已经满足一般的需求。OpenGL纹理的linear过滤贴图方式大概用的也就是这种线性方法，可见，该方法满足一般的应用需求了。由于项目的需要，我分别用C++和JAVA实现了该变形算法，复杂度不高。至于效果，也就那样吧。