分类： LINUX
2011-04-27 16:50:13
文档简介：
FSAA 是 full scene anti-alias 的缩写，有些人将其译为全景反锯齿，还算是合理。不过，倒底 FSAA 是什么呢？为什么要「全景」（full scene）？「半景」不行吗？（其实相对于 FSAA 的是 edge AA，「边缘反锯齿」）反锯齿（anti-alias）又是怎么回事呢？
文档内容：
[Part 1]
要弄清楚什么是 FSAA，就得先从 AA（anti-alias）开始。要弄清楚 AA，只好说明一下取样（sampling）这个麻烦的东西了。对于电脑绘图有些瞭解的读者，应该已经知道，目前的电脑绘图使用的是 2D raster 的显示方式。也就是说，画面是由一大堆有不同颜色和不同亮度的小点，组成一个大的方阵。这些小点称为像点，即 pixel，pixel 是 picture element 的缩写。很明显的，像点的数目愈多，图形就会愈细緻。我们常说的解析度就是指这些像点的数目。例如，640×480 这个解析度，就表示画面是由 307,200 个像点所组成的。
注：解析度在某些领域有不同的意义。在印刷的情形下，一般所谓的解析度，通常是以 DPI（dots per inch）为单位，即每英吋中含多少个点。像是某个印表机，若有 600 DPI 的解析度，就表示它每英吋可以包含 600 个点。所以，在一张 8.5"×11" 的纸上，就会有 5,100×6,600 = 33,660,000 个点。当然，纸愈大的话，点的数目就可以愈多，这是因为点的大小是固定的。在显示幕的情形下，不管萤幕有多大，使用 640×480 这个解析度时，像点的数目都是 307,200 个，这和印刷的情形是不同的。当然，通常愈大的萤幕能容许愈高的像点数目。
当然，像点的数目是有限多的。不幸的是，这个世界并不是由有限的小点组成的。好吧！也许它是由有限的小点组成，但是这些小点的数目非常的多，所以以人类巨大的眼睛来看，就好像是完全连续的一样。这样一来，用有限的像点来表现画面，就会出现问题。但是，只要像点的数目够多，而且像点的大小够小，小到人类的眼睛无法分辨的情形下，不就没问题了吗？当然会有问题，不然就不需要 FSAA 了。
问题在哪裡呢？问题在于取样的方式。取样是指把一个连续的讯号，转换成不连续（离散）的讯号的动作。因为像点的数目是有限多的，所以它一定是不连续的，所以当然就需要这个取样的动作了。下图是一个取样的例子：
上图中，黑色的曲线是原始讯号，灰色是直线是取样点，下图则是取样的结果。简单的说，就是把曲线上面每个取样点（就是那些灰色直线所在的地方）的数值取出来，这样就是取样的动作。一般来说，取样点之间的距离是固定的。以电脑图形的例子来看，每个像点就是取样点。不过，电脑图形是从一个二维的讯号中，取样得到一个二维的阵列。所以，取样看起来是会损失资讯的。另外，因为电脑是以数位的方式存放资料，所以还要把取样的结果进行数位化。数位化可以看成是「转成整数」的动作。例如，假设讯号的范围是 0 ~ 1 之间，想要数位化成 8 位元的资料，就是先把它乘上 255（8 位元数字可以表示 0 ~ 255 的范围），然后把结果以四捨五入或是直接捨去的方式转成整数。这个动作当然也会损失资讯。不过，这部分和我们的主题无关。
取样会牵扯到很多複杂的定理。例如，在做取样之前，如果先经过一个 low pass filter，把高频的部分滤掉，再设定适当的取样频率（通常是比是最高频率的两倍还大）。这样处理过的讯号再去取样，就可以完整还原到原来的讯号（指经过 low pass filter 后的讯号，而不是最原始的讯号）。当然，这篇文章并不是什麽教材，所以不会深入这些地方。不过，low pass filter 等一下会用到，所以先记着比较好。
[Part 2]
现在我们来看看，在电脑绘图中，取样的情形是什麽样子。为了简单起见，我们用两个三角形来做例子。如下图：
上图中，灰色的线是像点的边界，当然，实际上像点是不会有什麽边界的，就算有也很细，不会这麽粗。这些边界只是示意用的。每个像点中的小黑点就是取样点。取样的时候，就是取这些小黑点上面的颜色，做为整个像点的颜色。所以，取样的结果如下图：
我想大家应该都看到锯齿现象了吧！这就是一般 3D 绘图中所遇到的情形。为什麽会这样呢？其实，这是因为我们在取样之前，少了一个步骤：low pass filter。因此，原来讯号中的高频部分并没有去掉，所以才会出现锯齿现象。对了，所谓的 low pass filter，就是指一个只能让低频成分通过的过滤器。详细的细节就不在这裡说明了。现在只要记住一件事就够了：box filter 是一种 low pass filter。也就是说，如果我们把一个像点的范围内，所包含的讯号取其平均值的话，这样就会是一个 low pass filter。经过这样的动作，再来做取样，会得到下图：
把上面的两个例子都缩小到实际的大小，会得到下图：
两者之间的差异应该是相当明显吧！
有些读者可能会对 low pass filter 有疑问。为什麽用了 low pass filter 消除高频成分就会有比较好的效果呢？实际的理论相当複杂，所以不在这裡多说。不过，如果以人眼实际上的观察方式来看，倒是很合理的。因为，人眼内部的感光细胞，是会收集它的感光范围中的所有能量，再送到脑部。所以，可以看成感光细胞其实就已经包含了一个 box filter。因此，在进行取样之前，先做 box filter 是很合理的做法。
有一点要特别注意：如果显示系统的解析度非常的高，远远超出人眼可以分辨的范围，那麽 anti-aliasing 的效果就会慢慢消失。以一般习惯上的阅读距离来说，人眼很难分辨超过 300 DPI 以上的彩色点。也就是说，对一个对角线为 15" 的显示器来说，如果解析度高达 3,600×2,700 的话，那就没有做 anti-alias 的必要了，反正人的眼睛也没办法看到这麽细的像点。不过，贴图的 filtering 是不同的事，无论解析度有多高，都需要适当的贴图 filtering 才不会出现不正常的情形。
[Part 3]
现在来看看 3D 绘图晶片要怎麽处理这个问题。目前的 3D 晶片，几乎都是用 by primitive 的方式画出整个画面的。所谓的 by primitive，就是指一次画一个 primitive，把每一个 primitives 都画好之后，整个场景就画好了。Primitive 是指三角面和由许多三角面组成的简单东西。这种方法和 ray tracing 或是 scanline renderer 是不一样的。这两者都是分别对画面上的每个像点，去决定它应该会是什麽颜色。
另外，现在的 3D 绘图晶片通常是利用 Z buffer 来去除隐藏面（即被其它三角面盖住的部分），而不对三角面做任何排序动作。这当然是有原因的，因为如果对三角面做排序，再以「由后面往前面画」的方式来去除隐藏面的话，有时就需要把某些三角面切开，还有一些很麻烦的东西，这样的工作并不适合由记忆体很少的 3D 绘图晶片来做。当然，让 CPU 来做这个工作，速度也不会很快。无论如何，Z buffer（或是其它类似的方法）还是目前最有效率的方法之一。
现在来看看 3D 晶片要怎麽做到 anti-alias。一个最简单的想法是，让 3D 晶片在画三角面的时候，就自动产生适当的「佔有率」数字，即这个三角面在某个特定的像点上，所佔有的面积的比例，而该像点的颜色则会乘上这个比例。这样一来，就可以画出平滑的三角面了。当然，对于三角面来说，三角面的内部像点所佔的面积比例当然都是 100%，只有在边缘的地方才会有小于 100% 的佔有率。所以，这个方法也称为 edge anti-alias。
不过，这个方法有一些问题。例如，当两个三角面有重叠的时候，「佔有率」的计算就会出问题，因为 3D 晶片只知道将被盖住的三角面，其佔有率的数字；但是，它却没办法知道被盖住的三角面，倒底是佔有哪些部分。最严重的问题，则是出现在三角面有交叉的时候。这时，因为交叉的地方是由 Z buffer 算出来的，所以根本没办法算出正确的「佔有率」数字。所以，除非三角面都没有交叉，而且重叠的情形都还在合理范围，不然的话，这个方法是不能用的。如果三角面都已经排序且切割过，那就可以使用这个方法。但是，就如同前面所说的，目前不太可能即时做这些动作。
如果需要画的东西不是三角面，而只是线框的话，那麽 edge anti-alias 就很适用了。因为，线框很少会有交叉的现象（两条线就算是交叉，也没人会注意到吧！），而且，两条线重叠的情形也不多。所以，edge anti-alias 非常适用在线框绘图。某些应用像是 CAD/CAM 等等，特别常用到线框绘图，所以他们会喜欢用 edge anti-alias。不过，对于模拟、视觉化、或是 3D 游戏来说，线框绘图很少用到，所以 edge anti-alias 就不太适用。
另外有一点要注意的是，edge anti-alias 只处理三角面的边缘部分。当然高频成分也是在边缘最为明显。但是，如果三角面有贴图的话，还是可能会出现高频成分。不过，一般来说，贴图的 anti-alias 通常可以很容易用双线性内插（bilinear interpolation）和 mipmap 来解决。这部分比较複杂，以后再特别讨论。
说了这麽多，终于要说到 FSAA 了。为什麽叫 full scene 呢？它就是指对整个画面做 anti-alias，而不是像 edge anti-alias 只是对某个 primitive（如三角面或是线）做 anti-alias。那麽，要怎样对整个画面来做 anti-alias？
一个简单的方法，就是使用在每个像点中，取几个 sub-sample 点，然后把这些 sub-sample 的颜色取平均值，做为这个像点的颜色。这样的方法就称为 super-sampling。很明显的，这种做法完全不需要什麽特别的设计，不用切三角面，不用排序，直接就可以得到 anti-alias 的效果。所以这是一种 FSAA 的方法。
最简单的 super-sampling 方法是 ordered grid super-sampling，简称 OGSS。所谓的 OGSS，就是把直接把解析度提高，再用 box filter 把它缩小。例如，假设要对 640×480 的解析度，做 4 个 sample 的 FSAA，那就把解析度提高为 1280×960，画出整个画面，然后再用 box filter 把它缩小到 640×480。为什麽称为 OGSS 是因为它的 sub-sample 点等于是排成方形，如下图所示：
上图中，左边是原来的解析度方式，大的灰色圆点是原来的取样点。放大解析度为四倍之后（每边各两倍），会变成右边的情形。这时，在新的解析度下，新的取样点是红色小点。对每个原来的像点来说，它会取内部的四个红色小点的平均值，做为它的取样值。所以，这些红色小点就是它的 sub-sample 点。可以看出，它的 sub-sample 点正是排成方形，所以才会叫做 OGSS。
[Part 4]
OGSS 有什麽缺点吗？要看出它的缺点，得先看下面这张图：
上图中的这些三角面，显示出边线的角度和 aliasing 程度的关联。从最左边的三角形来看，可以看出完全垂直线、完全水平线和 45°的斜线，都不太会显示出 aliasing。但是，接近垂直或接近水平的线，会显示出最明显的 aliasing。不幸的是，因为 OGSS 的 sub-sample 点是垂直和水平的排列，所以在处理接近垂直或水平的线时，通常只有两个 sub-sample 会发生作用。如下图所示：
如果把 sub-sample 点稍微转动一下，情形就会改观了。如果不希望在接近 45° 的时候会有较好的结果，那只要把 sub-sample 点转动一些角度，就会让接近垂直或水平的线对每个像点的 sub-sample 点「看起来」像是 45° 了。在上面的图中就可以看到明显的结果。因为 sub-sample 被转动某个角度，所以这个方法称为 rotate grid super-sampling，简称 RGSS。
很明显的，RGSS 是不能用「提高解析度」这个方法来达成的。那要怎麽做到 RGSS 呢？基本上，方法并不难。只要在画三角面的时候，把每个三角面稍微移动位置，这样就和移动像点的取样点，是同样的效果。所以，要做到像上图的 RGSS，只要把整个场景画四次，每次都稍微移动每个三角面，到适当的取样点位置（移动的范围会小于一个像点的大小）。最后，再把这四张图合起来，对每个像点取平均值，就可以得到结果了。传统上，这可以利用 accumulation buffer 来达到。不过，accumulation buffer 需要很大的频宽（每次从 frame buffer 複製到 accumulation buffer 需要两次读取和一次写入），而且 accumulation buffer 通常需要比一般 frame buffer 更高的精确度才行，所以又需要更多频宽。再加上 4 samples 的 FSAA 已经需要把整个场景画出四次了，所以速度一定会很慢。
另一个方法是利用多个 frame buffer，这也是 3dfx 的 T-Buffer 的原理。这个方法是让显示晶片保有四个不同的 frame buffer，并把四个 sub-sample 的图分别画到这四个 frame buffer 中。而显示晶片的 RAMDAC（把 frame buffer 输出到萤幕上的装置）则自动把这四个 frame buffer 的内容做平均。这样一来，就不需要高精确度的 accumulation buffer，而且也没有明显的额外频宽需求。因此，对于 sample 的数目很少的情形下，这的确是个取代 accumulation buffer 的好方法。
现在 DirectX 8 中的 DirectGraphics 也加入了 multi-sample buffer 的支援，基本上就和 3dfx 的 T-Buffer 是完全相同的。所以，将来的 3D 显示晶片都很可能会支援这样的功能。
附注：对这个主题有兴趣的读者，可以参考由 Beyond3D 的 Kristof Beets 和 Dave Barron 所写的 Super-sampling Anti-aliasing Analysis 这篇 whitepaper。
