转载

OpenGL中一种高效的线段反走样技术

令人讨厌的“走样”

我在日常工作中通过传统的OpenGL绘制函数绘制线段时，发现绘制出的线段边缘充满了“锯齿”，而这种“锯齿”在线段运动和旋转时往往会更加明显（图 1）。这种我们不希望看到的“锯齿”被成为“走样”，而消除这种“锯齿”的过程就是我们所说的“反走样”。虽然OpenGL提供了诸如设置 GL_LINE_SMOOTH 属性、多重采样等线段反走样的方法，但效果和质量受到很多方面的限制，而且不同的硬件厂商使用不同的反走样算法，所以使得反走样的结果在不同的GPU上有着不同的效果。因此我们需要一种更为高效和通用的线段反走样技术。

图1 采用传统OpenGL绘制方法绘制的线段

为什么会“走样”？

在介绍如何对线段反走样之前，我们必须了解为什么我们绘制的线段会产生“走样”。

我们都知道，在数学的定义中一条线段是由两个端点确定的，而线段是没有宽度和面积的。但在计算机图形领域中，为了让人的肉眼能够看到，必须给线段一定的宽度，所以我们的线段通常是由两个端点和一个宽度参数确定的，而我们计算机中图形的宽度通常都是以像素为单位的，因此我们的线段宽度有可能是1像素也有可能是n像素。

如果需要在白色的背景下绘制一条宽度为1像素的黑色线段，从信号处理的观点上来看，我们可以把这条线段看做一个值为1的信号，而线段外部的区域信号值为0，而线段的边界是个阶梯函数（图2）。因为帧缓存和显示器所能容纳的像素点是有限的，所以我们需要对这个信号进行采样。

图2 线段信号采样示意图

我们可以看到：离散采样（图2 中用蓝色虚线表示）的间隔无论多么的小都无法精确的表达它的不连续性，因此我们无论怎么提高分辨率，都无法彻底消除走样。而根据耐奎斯特的信号采样定理：要重构一个不走样的信号，采样率至少是信号最高频率的两倍。

即：C = B * log2 N ( bps )

因此，从理论上来说要绘制一条没有走样的线段，我们必须拥有足够大的信号频率，也就是我们需要无限放大我们的屏幕分辨率才能彻底消除走样。

图3 通过提高分辨率减轻走样现象

从图3我们可以看出，虽然我们提高了分辨率，但是走样依然存在。因此，一味地提高分辨率是无法彻底解决掉线段走样问题的，而且在时间、空间以及金钱有限的情况下是不允许我们这么做的。

解决之道

计算机图形学领域中广泛采用的一种方法是：限制信号的带宽。也就是说既然无法提高分辨率，我们可以将信号中无法还原的高频部分去掉以达到“反走样”的目的。这样线段就不再有明显尖锐的边界了，相反，线段的边界处将变得模糊，这种将边界模糊的过程我们称之为“过滤”。我们可以让信号通过一个低通过滤器，来过滤掉信号中的高频部分，以达到过滤的效果，这样的过滤器有很多，可以是简单的线性过滤器也可以是稍微复杂一点的盒状过滤器或高斯过滤器。本文将以高斯过滤器为例，为大家介绍整个过滤的过程。

图4 低通高斯过滤器对2D信号的过滤效果

图4演示了高斯过滤器对一个2D信号进行过滤操作的整个过程，首先图4(a)表示未处理的线段信号，其中x和y轴表示线段所处平面坐标系，z轴表示图像信号的强度，可以认为是RGBA颜色中的alpha值。其中左半部分z=1表示位于线段内部，右半部份z=0表示位于线段外部，这里z=0和z=1边界处是不连续的。图4(b）所表示的是一个高斯地同过滤器，将它与图4(a)中的某一段信号做卷积后就得到了图4(c)中的效果。卷积在这里等效于求出过滤器与信号相交部分的体积，图4(d)就是将所有信号与过滤器卷积后得到的最终过滤效果。

图5 经过半径为2的高斯过滤后的线段信号示意图

从图5可以看到：经过过滤后的线段边界将不再是一段不连续的阶梯函数，而是一段连续的平滑曲线。

预处理

至此，我们似乎已经解决了困扰我们的反走样问题，但是我们需要注意到的是：在程序运行时我们的GPU会逐像素地进行复杂的卷积计算，这种大规模的计算对我们来说无疑是一笔很大的开销，会直接影响我们程序运行的效率。因此，我们需要将这部分的计算放在渲染之前进行，我们称之为预处理。

如图6所示，在预处理过程中，我们将半径为R的过滤器和宽度为W的线段进行卷积，所得到的强度值根据过滤器的位置变化而变化。当过滤器刚好位于直线上（图6a）时，我们得到的强度值最大，因为此时过滤器与直线重叠部分最多，（在图4所示坐标系中）重叠部分的体积也就越大。相反的，当过滤器位于距离直线w/2+R的位置（图6b）时，卷积所得强度值最小，因为此时过滤器与直线没有重叠。而在过滤器从距离为0移动到w/2+R处的过程中，强度值在慢慢变小。

图6 过滤器位置影响卷积值

有了这个关系，我们就可以根据到直线的距离提前为像素计算出对应的强度值而建立一个距离与强度值对应的查找表，在渲染时只需要根据像素与线段的距离从查找表中取出强度值即可，而无需进行即时的计算，大大提高了我们渲染的速度。而同一平行线上的所有像素强度值是一样的，这样理论上来说我们就只需要算W/2个像素的强度值就可以绘制出整条直线了，计算量也大大减少。

然而，我们并不希望计算量会随线段宽度变化，我们希望我们的渲染过程的效率是稳定的，因此，我们需要一张固定宽度的查找表。通过实践发现，一张32个强度值的查找表已经足够应付任意宽度的直线了（图7），如果觉得这样不够精细，你还可以使用64个强度值的查找表，因为对于GPU来说，处理一个32或64元素的1D纹理实在是小菜一碟。