显示器是由一个个像素组成的，这种离散量导致绘制出的直线会出现下图所示的锯齿现象，这种由离散量来表示连续量而引起的失真称为走样（Aliasing）。走样问题只能减轻，无法消除，用于减轻走样现象的技术称为反走样（Anti-Aliasing），游戏中也叫抗锯齿。

Wu反走样算法

1991年，Wu Xiaolin在An efficient antialiasing technique论文中提出了一种反走样算法，称为Wu反走样算法。

相对于Bresenham画线算法，Wu反走样算法使用两个相邻像素来表示一个点，它通过计算相邻像素与理想直线的偏差来调节像素亮度。如上图所示，e表示扫描线上方像素与理想直线的距离，则1-e则表示下方相邻像素与理想直线的距离，两个数之和为1。e越小表示越接近理想直线，该像素的颜色应越接近直线的颜色，反之1-e就越大，就应接近背景颜色，因此可以通过e和1-e来调节颜色的亮度，达到模糊锯齿边界的效果，最终画出的直线看起来效果仍然和一个像素差不多。

类似于Bresenham算法，Wu反走样算法也是一种增量算法，e显然可以通过累加dy/dx（斜率）进行计算，当e大于1时，两个像素坐标增加或减少1，偏差e也减去1。

代码示例

以下为JavaScript语言实现的Wu反走样画线算法示例，支持任意斜率的直线。为避免干扰，其他辅助代码未给出，这里稍作说明：

• p0、p1为Point类对象，包含坐标x、y以及颜色属性color；
• color为Color类对象，tostr()方法将颜色转换为字符串"rgba(r,g,b,a)"的形式传给html canvas的绘图方法，setOpacity方法设置通道a的值，1表示完全不透明，0表示完全透明；
• linearInterp为线性颜色插值，可以实现绘制颜色渐变的直线；

function draw_line(p0, p1) {
    let x0 = p0.x;
    let y0 = p0.y;
    let xEnd = p1.x;
    let yEnd = p1.y;
    let e = 0;
    let color, c0 = p0.color, c1 = p1.color;
    x0 = Math.round(x0);
    y0 = Math.round(y0);
    xEnd = Math.round(xEnd);
    yEnd = Math.round(yEnd);
    // x变化快于y，则x作为主位移
    if (Math.abs(xEnd - x0) >= Math.abs(yEnd - y0)) {
        let x, y;
        if (x0 > xEnd) {
	        // 交换起点
            x = xEnd;
            y = yEnd;
            xEnd = x0;
            yEnd = y0;
            x0 = x;
            y0 = y;
            c0 = p1.color;
            c1 = p0.color;
        } else {
            x = x0;
            y = y0;
        }
        let dx = xEnd - x;
        let dy = yEnd - y;
        let m = dy / dx;
        let signX;
        // 正斜率
        if ((yEnd - y) * (xEnd - x) >= 0) {
            signX = 1;
        } else {
            // 负斜率
            signX = -1;
        }
        while (x < xEnd) {
            // 计算颜色插值
            color = linearInterp(x, x0, xEnd, c0, c1);
            // 绘制两个相邻像素
            color.setOpacity(e);
            setPixel(x, y + signX, color.tostr());
            color.setOpacity(1 - e);
            setPixel(x, y, color.tostr());
            x += 1;
            e += signX * m;
            if (e >= 1.0) {
                e -= 1;
                y += signX;
            }
        }
        
    } else {
        // y变化快于x，则y为主位移
        let x, y;
        if (y0 > yEnd) {
	        // 交换起点
            x = xEnd;
            y = yEnd;
            xEnd = x0;
            yEnd = y0;
            x0 = x;
            y0 = y;
            c0 = p1.color;
            c1 = p0.color;
        } else {
            x = x0;
            y = y0;
        }
        let dx = xEnd - x;
        let dy = yEnd - y;
        let m = dx / dy;
        let signY;
        // 正斜率
        if ((yEnd - y) * (xEnd - x) >= 0) {
            signY = 1;
        } else {
            // 负斜率
            signY = -1;
        }
        while (y < yEnd) {
            color = linearInterp(y, y0, yEnd, c0, c1);
            color.setOpacity(e);
            setPixel(x + signY, y, color.tostr());
            color.setOpacity(1 - e);
            setPixel(x, y, color.tostr());
            y += 1;
            e = e + signY * m;
            if (e >= 1.0) {
                e -= 1;
                x += signY;
            }
        }
    }
}

利用上面的画线方法绘制了反走样时钟和金刚石图案，绘制的直线已没有明显的锯齿感了。

参考文献

[1] - Wu, Xiaolin (July 1991). "An efficient antialiasing technique". [Computer Graphics](https://en.wikipedia.org/wiki/Computer_Graphics(newsletter) "Computer Graphics (newsletter)"). 25 (4): 143–152. [doi](https://en.wikipedia.org/wiki/Doi(identifier) "Doi (identifier)"):10.1145/127719.122734. ISBN 0-89791-436-8.
[2] -《计算机图形学--理论与实践项目化教程》孔令德著，第33页；