三角形光栅化是传统图形渲染管线的最后一步,也是最重要的一步,需要插值计算出三角形内部每个像素的颜色值,并根据z值进行深度测试以决定像素的远近关系。

光栅化的算法用掉了我好几天的时间,一开始是用Barycentric Coordinates算法进行的,结果帧率只有杯具的3,想办法把很多的乘除法改成了加减法还是没有起色,看来浮点数运算还是坑爹啊,于是决定用经典的Bresenham算法了。但是Bresenham算法是用来画线的,对于光栅化三角形来说还要考虑三角形内部针对顶点颜色的插值,于是我将其变成了Bresenham插值算法……

Bresenham插值算法

Bresenham算法本质上其实就是实现均匀的整数插值,其原理、优化及伪代码请参考wiki[1]。

任意三角形都可以拆分为平底三角形和平顶三角形。对于平底三角形,可以看成由左下点-顶点、右下点-顶点和左下点-右下点三条直线围起来的封闭区间。将y从底到顶进行遍历,每次遍历都通过Bresenham算法确定出左边直线的x1值和右边直线的x2值,然后将x从x1遍历到x2即可。

平顶三角形同理,不过要也将y值从底到顶进行遍历(而非一般想到的从顶到底),并且单独处理顶边。原因是,设想一个平底三角形和一个平顶三角形有邻边(非顶边或底边),由于这条边上的x值分别是由y值从底到顶和从顶到底插值出来的,所以很可能不完全相同,这样就会出现缝隙,所以我们必须让所有的直线的y值都向一个方向遍历,以保证相同的直线上的x值完全相同。不过这样会导致一个问题,平顶三角形的顶边的左右端点可能出现毛刺,虽然可以在循环中判断x是否小于整个三角形的左端点x值或大于整个三角形的右端点x值,但是为了进一步优化干脆y只递增到ytop-1,然后单独处理ytop,这样就能够消除循环中的条件判断,提高效率。

对于颜色的插值,可以首先将color看做x值随y值进行遍历,确定出每行直线x1点的color和x2点的color,然后将color看做y值随x值进行遍历,确定出每个像素的颜色值。

平底三角形核心代码,考虑到篇幅省略了处理color值的部分:

int dx1 = xtop - xleft;
int dy1 = ytop - ybtm;
int dx2 = xtop - xright;
int dy2 = ytop - ybtm;
int xstep1 = 1, xstep2 = 1;
if (dy1 <= 0 || dy2 <= 0)
    return;
if (dx1 < 0)
{
    xstep1 = -1;
    dx1 = -dx1;
}
if (dx2 < 0)
{
    xstep2 = -1;
    dx2 = -dx2;
}

int error1 = 2*dx1 - dy1, error2 = 2*dx2 - dy2;
int x1tmp = xleft, x2tmp = xright;

for (int y = ybtm; y <= ytop; y++)
{
    while (error1 > 0)
    {
        x1tmp += xstep1;
        error1 -= 2*dy1;
    }
    while (error2 > 0)
    {
        x2tmp += xstep2;
        error2 -= 2*dy2;
    }
   
    int dx = x2tmp - x1tmp;
   
    for (int x = x1tmp; x <= x2tmp; x++)
    {
        drawPixel(pVram, x, y, RGBA(r,g,b,0));
    }
   
    error1 += 2*dx1;
    error2 += 2*dx2;
}

使用该代码的时候需要保证xleft ≤ xright。

平顶三角形算法相似,不再列出。

完成两个三角形的光栅算法后,对于任意一个三角形,先判断是不是这两种三角形,不是的话找出y值居中的顶点,然后将三角形一分为二分别光栅化即可。对于y值居中的顶点所在那行的另一边的端点,x值和颜色值都可以用直线方程解出,虽然引入了浮点运算不过这一两个应该影响不大吧,毕竟核心的光栅化代码中可是只有整数加减法和乘2操作。

截图示意:

z值计算与深度测试

还记得如何由三个点确定出平面方程吗?平面可以由Ax + By + Cz + D = 0来表示,因此z = f(x,y) = (-Ax-By-D) / C。可以观察到,f(x+1,y) – f(x,y) = -A/C,f(x,y+1) – f(x,y) = -B/C,因此不必针对每个点都计算z值,只要有了三角形一个顶点的z值就可以用加减法算出其它点的z值。

接下来用一个缓冲区保存屏幕每一个点的z值并进行深度测试即可,不过别忘了渲染新帧之前要先清空z值缓冲区。事先准备好一个空的缓冲区,清空的时候直接用memcpy拷贝过来即可,千万别用循环去一个点一个点地赋值。

附上计算由三个点确定平面方程四个参数的代码:

float A = (y2 - y1) * (z3 - z1) - (z2 - z1) * (y3 - y1);
float B = (z2 - z1) * (x3 - x1) - (x2 - x1) * (z3 - z1);
float C = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1);
float D = -(A*x1 + B*y1 + C*z1);
程序运行截图

顺便提一句,我现在用的模拟器是Jpcsp v0.5,效果还算不错,只是有时候fps会比实机上低很多,果然又是一个证明Java龟速的例子么= =

===========cotaku的分割线===========

下一篇会提一下光栅化之前的各种矩阵变换和帧率的计算方法。

参考资料:
[1] Bresenham’s line algorithm

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

Related Posts:

Leave a Reply

World Line
Time Machine
Online Tools