Barycentric Coordinates算法,即“重心坐标系插值算法”,本质是通过计算2D空间中任意一点到三角形三边的相对距离,来确定点是否在三角形内部。这个算法比起常见的扫描线插值算法,编程更容易(不需要判断三角形类型),而且具有更高的精确度(避免了计算斜率时带来的误差)。Barycentric Coordinates算法不但可以判断像素点是否需要绘制,而且可以直接插值计算出需要绘制的像素点的颜色或纹理映射坐标。不过,我不知道计算量是否要比扫描线插值算法大,希望有感兴趣的朋友能比较一下。

本文首先简单讲一下算法的原理,然后给出代码实现。

算法原理

1、设2D空间中,三角形三个顶点分别为P1,P2,P3,则任意一点P均可表示为P = P1 + b(P2-P1) + c(P3-P1)。

展开上式得P = (1-b-c)P1 + bP2 + cP3,设a = 1-b-c,则P化简为P = aP1 + bP2 + cP3。

简单计算可知,对于P2,有a=0,b=1,c=0,其它点同理。那么,如果点P同时满足了0<a<1,0<b<1,0<c<1的话,点P即必在三角形P1P2P3内部。实际上a代表了P到边P2P3的距离相对于P1到边P2P3的距离的比值,b、c同理。若a,b,c中的一个为1另两个为0,则P是某个顶点;若a,b,c中的一个为0另两个不为0,则P是在某条边上。记住a+b+c始终等于1。因此,若点P满足0<=a<=1,0<=b<=1,0<=c<=1,则可以画出此点。

这个结论得出得有些仓促,没有进行严格的证明,不过从直观上来看确实是如此。如果有哪位朋友能帮忙证明一下,实在是不胜感激。

2、若已知直线上两点(x1,y1)和(x2,y2),则平面直线方程为(y1-y2)x + (x2-x1)y + x1y2 – x2y1 = 0。

令f(x,y) = (y1-y2)x + (x2-x1)y + x1y2 – x2y1,则f(x,y)表示点(x,y)所在的平行线到上述直线的相对距离(与绝对距离成正比例,不过没有仔细推导,如有错误欢迎指正)。

于是,我们可以很方便地将b定义为相对于(x1,y1)、(x3,y3)所在直线的f(x,y)/f(x2,y2),将c定义为相对于(x1,y1)、(x2,y2)所在直线的f(x,y)/f(x3,y3),将a定义为1-b-c。

既然a,b,c分别表示P到三边的相对距离,那么既然P在三角形内部,远离一条边则表示接近一个顶点,所以a,b,c可以直接用来计算颜色的插值,或者纹理映射的坐标。不过需要注意的是,在计算纹理映射的u,v坐标时不可以直接使用和计算颜色插值一样的线性插值方式,因为透视变换是非线性变换,需要对顶点原始的u,v坐标进行透视矫正后才能进行线性插值。这个问题下次再研究。

代码实现
for (int x = 0; x < width; x++)
{
    for (int y = 0; y < height; y++)
    {
        c = ((y1-y2)*x+(x2-x1)*y+x1*y2-x2*y1)/((y1-y2)*x3+(x2-x1)*y3+x1*y2-x2*y1);
        b = ((y1-y3)*x+(x3-x1)*y+x1*y3-x3*y1)/((y1-y3)*x2+(x3-x1)*y2+x1*y3-x3*y1);
        a = 1-b-c;
        if (a >= 0 && a <= 1 && b >= 0 && b <= 1 && c >= 0 && c <= 1)
        {
            Color c = a*c1+b*c2+c*c3;
            DrawPixel(x, y, c);
        }
    }
}

参考资料:
[1] Barycentric coordinate system (mathematics)
[1] Triangle Rasterization

» 转载请注明来源及链接:未来代码研究所

Related Posts:

4 Responses to “使用Barycentric Coordinates算法进行三角形光栅化”

  • Key says:

    请问楼主 这个 width 和 height指的是??
    画布宽高?
    还是围绕三个顶点的最小矩形的宽高??

    • 暗影吉他手 says:

      是屏幕宽高,因为要遍历所有的像素点,确定每个pixel是否在三角形内部。当然也可以优化,先算出包围三角形的矩形再遍历矩形内部。不过即使这样优化之后效率也很低,可能由于浮点计算过多,在PSP上fps只有3左右。

Leave a Reply

World Line
Time Machine
Online Tools