Mipmapping

因为最近做sss效果时，需要自己写模型厚度生成工具。厚度图的生成是使用反AO的方法，参考自GDC-2011。而AO的生成，其中有一种是利用到Mipmapper来做遮挡均值。以后有机会写一篇文章来具体描述一下吧。这篇文章主要详细讲一下Mipmapping的原理，以明白为啥能用它来做遮挡均值。

简述

当我们渲染一处细节更低，纹理质量更低的地方时，我们就需要mipmapping。mipmapping能节省内存和渲染时间，不过这思想动机的背后技术初始构想是通过减少锯齿来提升场景质量。锯齿的产生是因为要对包含像素中心，投影到视平面的表面的着色。可见的小细节都能填补像素中心，视点移动的时候，他们会显示或者消失。这样会导致粒状效应，像PS2游戏那样黏糊糊的。

我们很幸运，很多聪明的朋友都对这样的锯齿思考了很久了，我们必须站在巨人的肩膀上。

1805年，卡尔·弗里德里希·高斯发明了快速傅里叶变换，这是一种方法分解任意取样函数为一组正弦函数。傅里叶变换不只是数学运算的巫术配方。它经常传递给我们一个很棒的思考问题的框架。当处理一张图的时候，有时正弦波比任意形状更容易看到操作的效果。

所以傅里叶变换如何帮助我们？为了消灭锯齿，我么需要抛弃所有狭窄波长的正弦波——这表明这是唯一的东西能填充像素间并保证是宽峰值的波。这任务又数字滤波执行。详细介绍过滤和信号处理，看一下(Ken Steiglitz, A Digital Signal Processing Primer, Addison-Wesley)这本书。

一旦我么明白创建mipmaps是一项创建更小的纹理并消灭锯齿的任务，我们能利用大量的前人创立出来的信息处理的知识。已经完成了这么多工作了，一旦我们有了基础概念，我们的代码几乎都可以自己写了。

常见的Mipmapping方法

游戏程序员不用思考太多关于mipmap的创建。我们想让一系列的纹理减少到2的次方大小。因此我们打算取输入纹理每4个像素块的平均来产生1个像素的输出纹理。我们称之为像素平均过滤或者box filtering。

图1包含一个像素平均过滤的频率响应图表，x轴代表输入图片的波长，y轴代表它们相乘得出的输出幅度。

要完美地消灭锯齿，我们想要一个过滤器能匹配图1的棕色线————低频为0，高频为1。在信号处理项中，我们想要一个完美的低通滤波。这图表显示为像素平均没有滤波没有靠近此效果。它消灭的大块我们想保留的，让输出有点模糊。同时它也保留了我们更想扔掉的，这导致了锯齿。消灭不了锯齿是因为把锯齿烘到小纹理中，这一点很重要。

如何构建更好的滤波器

现在确定的是我们必须实现一个在我们输出纹理中的理想的低通滤波器。我们需要使用一个sinc函数组成的过滤器，sinc(x) = sin(πx)/ πx，x指滤波器中心的每个像素的偏移。（在中心，x = 0，lim x->0 sin(x)/x = 1。）sinc的问题是它是无限宽度，通过正负x它结果能要多远走多远，同时sinc会保持着上下浮动，当你向着无穷远放大时候，振幅会逐渐减小。使用sinc过滤一个纹理映射需要无限的CPU时间，太坑爹了。

我们能折个中。首先我们需要确定要消耗多少CPU来建立mipmap，这粗劣的确定这滤波器的宽度。然后构建一个sinc近似值，到达刚刚那个宽度，然后用这个近似值来过滤我们的图像。我们会创建我们的近似值，通过斩断sinc函数来获取我们的近似值，但是这会引到不大好的输出结果。我们通过乘一个窗口函数，它的工作是是将sinc的脉冲降低至0，所以当我们斩断它末端时候，能最小化它的坏影响。

《Jim Blinn’s Corner: Dirty Pixels》里面通俗易懂地描述了为什么sinc是最合适的滤波器，以及窗口函数如何工作的。

为此，要设计我们的mipmap创建滤波器，需要选择一个滤波器宽度（以纹理映射得像素为单位），以及一个窗口函数。当你绘制窗口函数时，他们都看起来很相似，但是他们的差异很重要。滤波器很有趣：他们是一组实数，但是对它们小小的调整能显著地改变输出。（如果你从一个好的过滤器开始并任意地调整其系数，输出结果都很坏。）

每个窗口函数都表示一个不同的模糊和锯齿的权衡。我们预测到窗口函数能通过绘制结果滤波器的频率响应来做的事，如图1。或者我们能写一些实验性代码，通过任意的滤波器来构建mipmaps，并观察结果。

尝试的滤波器

我们试用了几种滤波器。第一种是point filter，它能获得通过从4个像素中取一个值并在低级mipmap中使用（每个屏幕像素显示一个缩放单位的纹理像素，等于说没有mipmapping）。

第二个滤波器是像素平均pixel-averaging，又称为box-filter，清单1是其算法。

Listing 1: A common method of building mipmaps, known as "pixel-averaging" or "box-filtering".

 

void build_lame_mipmap(Mipmap *source, Mipmap *dest) {

    assert(dest->width == source->width / 2);

    assert(dest->height == source->height / 2);

 

    int i, j;

    for (j = 0; j < dest->height; j++) {

        for (i = 0; i < dest->width; i++) {

            int dest_red, dest_green, dest_blue;

 

            // Average the colors of 4 adjacent pixels in the source texture.

 

            dest_red = (source->red[i*2][j*2] + source->red[i*2][j*2+1]

                     + source->red[i*2+1][j*2] + source->red[i*2+1][j*2+1]) / 4;

            dest_green = (source->green[i*2][j*2] + source->green[i*2][j*2+1]

                     + source->green[i*2+1][j*2] + source->green[i*2+1][j*2+1]) / 4;

            dest_blue = (source->blue[i*2][j*2] + source->blue[i*2][j*2+1]

                     + source->blue[i*2+1][j*2] + source->blue[i*2+1][j*2+1]) / 4;

 

            // Store those colors in the destination texture.

                    

            dest->red[i][j] = dest_red;

            dest->green[i][j] = dest_green;

            dest->blue[i][j] = dest_blue;

        }

    }

}

第三种我们试试Lanczos的sinc窗口函数，Jim Blinn在它的书上说是好东西，图形程序员也是很流行的玩意。

第四种是Kaiser窗口。Don Mitchell最近做了一些实验来揭露Kaiser窗口，通过alpha参数4，在图像显示方面明显优于Lanczos。 Don做的事足够让这个滤波器用他的名字命名了，我们用它是很明智的。

图2显示所有频率响应。Kaiser滤波器和Lanczos滤波器的系数区别微妙，所以它们的频率响应函数几乎一样。每种率滤波器都mipmapped过的图，我看着实在是看不出区别。尽管mipmapping在图像过滤中不是十分费力，Don的测试更严格。我认为，只要计算开销是一样的，我们就应该养成一个使用稍微好一点的过滤器，为了未来碰到更加难的问题做准备。

避免涟漪

看看图2，在高质量的频率响应是会有点涟漪的。信号处理数学说明我们能通过提高宽度来增加滤波器的质量。当我们这么做，我们获得一个近似于理想低通滤波器的曲线，但是有点涟漪，同时每个波峰和凹槽是集中在一个更紧密的频率组内。图3包含一个16和64大小的Kaiser滤波器的图表。

在音频处理的世界中，这种程度的涟漪是可以忽略的，但是我们眼睛是比耳朵挑剔的。因为这些涟漪更紧密（连贯）集中在频率组中，他们会创建更加连续的锯齿快在图像中。去除一个足够宽的滤波器，应用到一个有个巨大连续颜色区域的纹理中，你会看到很多地方有锯齿块（振铃）。

在我开始看到测试图像中明显的锯齿块之前，我只能先把Kaiser滤波器设置宽度为14采样。要显示之后发生了啥，我在一个路标纹理上运行了一个宽滤波器。图4是14个取样和64个取样的锯齿块对比。

有人会想，如果你想消耗大量的CPU时间，你能使用巨大的滤波器，会趋近理想低通响应，你就不会看到涟漪了。我尝试这个滤波器1000采样宽度，大量的锯齿块都消失掉了。

避免变形的传播

所以我们限制了相对狭小的滤波器，他们频率响应由于box filter，但是会有一些变形无法避免。幸运地，我们能减少图像变形的影响。

当我们创建一个mipmap生成器，我们一般是考虑下面程序：输入一张有一定宽度的图比如256，通过mipmapping函数的处理为128的像素宽度。然后取其结果，用相同的函数处理，获得一个64宽的纹理。重复步骤到你想要的大小。

这技术导致一个问题，因为每一步滤波步骤的输出，都因为不完美的滤波器而包含变形，来作为下次的输入。因此下一阶段会有两层的变形，第三阶段会有三层的变形……

我们可以通过每次用先最具细节的顶层图像作为创建每个阶段的mipmap来解决这个问题。我们仍然想要一个理想低通滤波器，但是希望能改变滤波器的截断频率（第一个mipmap等级，我们扔掉1/2的频率，第二等级，我们抛弃3/4，第三等级，抛弃7/8……）。我们持续地让我们宽度乘以2，并调整参数直到sinc脉冲和窗口让其更加宽（使滤波器更加宽是没问题的，会引出更多涟漪，因为原图像跟目标图像的大小比例会变大）。这过程会产生最高质量的结果。

结果对比

Kaiser滤波器的效果看起来一般比较好点。一些例子：

图5中，像素平均的版本，三个mipmap等级下去，下面的版权文字都没了，且女人的嘴巴有时候会显得模糊。Kaise滤波器中，版权文字则可见且女人的牙齿可辨。

图6中显示另外的一个公告版。在box filter版本中，文字是模糊难辨的，瓶标显得不大清晰。

深度优化

我们认为这涟漪是因为滤波器的响应频率震荡造成的。但是就算用巨大的滤波器和响应频率接近理想，涟漪还是没有消失。这样会导致问题会潜在于场景中。事实上，识别这种罪恶现象是很重要的，对于我们明白图形学来说，而不单单mipmapping。

宽Kaiser滤波器是近似无限宽的sinc脉冲，或者说是从图中移除高频。sinc做了我们所需要的因为他的傅里叶变换就是一个矩形脉冲，当应用傅里叶变换到我们的信号中死后，这个脉冲会对低频乘以1，高频乘以0。

有些应用程序像音频处理，你想响应通过低延迟的电线过来的信号，这种例子由锯齿构建的滤波器就很合适。但是因为我们mipmaping是批处理，我们可以选择在纹理图中演算傅里叶变换，手动地将高频设置为0，再将其转换回来。

以数学意义来说，这里是跟无限宽度的sinc有着相同的过滤效果。因为我们是完美 模拟矩形脉冲的频率响应，没有一个由一个有限滤波器产生的涟漪的频率响应会给我们带来问题。因此我们输出是完美的，或者是我们预想的。

但是我们输出并不是完美，纹理贴图然后是有可怕的涟漪，就像图7那样。这看起来跟之前用64采样Kaiser filter处理结果一样，看起来就像之前说的“振铃”那样。

最大的问题是我们纹理映射的概念定义就是不明确。纹理映射的目的是要唤起观察者脑中要显示出来的表面的自然效果。我们呢要思考一下保存早纹理贴图的数学结果，并比较一下我们对应表面的数学心理模型，我们看到其实这是冲突的。

图8显示一张简单纹理：每一个像素都是绿色，除了一个白点。我们可以解释为了除了白点之外都是同一个绿色。理想情况下，我们所有演算的数学原理都与这种心理解释保持一致，固然这种图像处理是我们所预期的。

我们的图像表面的心理模型是连续函数，但是我呢里映射不是连续的。它存在于一系列的采样，就像图8右边所画的那样。

让我们聊聊采样和重构。当我们采样任意（无带宽限制）联系函数于点n，这个点是我们仅有的信息。假设我们去一系列的采样，尝试构建一个连续函数。我们需要对每一个值进行插值，但是因为我们抛弃了大部分原生数据，没有插值算法能还原我们最开始的值。我们不知道这些样本之间是什么。

这就是数字滤波器的作用。香农采样定理是信息理论的基石。它说：如果你限制你的输入函数来包含仅仅一个确定的正弦范围的频率（又称“限制带宽”），那么你能从这个样本中准确地重构为连续函数。那是一个强大的思想。

但是这思想有个后果。当重构它时，我们不允许口述这个函数在每个采样点中做了啥，我们必须给什么就拿什么。因为连续函数必须是限制带宽的，这样会在样本间摇摆，不是我们预期的。图9显示绿白点图的1D横截面，且我们使用正弦函数作为我们的重构基础表现为连续函数。注意到连续版本在绿色区域不是扁平的，跟我们想的不大一样。它是涟漪的。它不可能扁平，因为带宽限制的影响，这意味着函数是不能将斜率降为0。

只要我们以数学的角度来看这问题，这里会产生：为了创建我们的纹理，我们从一些带宽限制的到处是涟漪的函数开始，但是当对它采样，我们的采样点会在涟漪中击中红点，来创建常数密度值。因为采样显示整个连续函数，涟漪仍然在这里，我们的信号处理控制器会准确地复现出来。当我们收缩纹理来建立mipmap，我们本质上是缩放我们视角的连续函数。可见的涟漪会显示因为缩放的改变和增加低通滤波器会破坏了我们采样点位置的微妙的“一致性”。

如果放大源纹理而不是缩小它，我们会看到在新的采样点会有涟漪。因为我们的像素会越来越高，我们会在极限连续函数中收敛。

之前我们提及到Don Mitchell，不是有一个以他来命名的滤波器么。Mitchell filter是通过实验让图像放大起来又不会很难看来得出的。Mitchell从信号重构角度来看有是一个故意不完美的，因为完美的重构跟我们脑海中想的东西不大一样。但是Mitchell filter不会偏离完美上采样，因为这样会有那些讨厌的失真。

我们真的要抗锯齿吗

这里有其他重要的点。限制带宽连续函数的表现，无法接受的涟漪，是一个数字采样的先决条件。如果你在一个有一个白点的真实的绿墙向上走，你希望从它创建一个纹理，这样为了避免锯齿，你在数字化它之前你必须低通输入这张图。滤波器产生不可接受的涟漪函数，且涟漪会在你的采样中显示。因为数字摄像机不会反锯齿，你不会收集这些采样点作为上相的图片。如果将图像当作限制带宽的采样点的集合，这做法好像很流行，但是我们会在自然光场中引入了一些不存在的涟漪。

抗锯齿导致涟漪。我们不想要涟漪。因此，抗锯齿不是我们想要的。

我们所有图像都有无限的解决方案才是我们想要的，所以我们能以任意缩放和方向来绘制平面而不会出问题。不幸的是我们还没有这个意思这么做，所以我们使用数字采样图来替代。抗锯齿是一个重要的工具帮助我们对付数字采样造成的限制。但是它同时导致问题，所以它自身不会被视为最终目标。

你不会普遍地听到这么说：抗锯齿常常被吹捧为仅有的解决问题方法，并没有缺点。那是因为相当多从事计算机图形（和游戏编程）每天都使用一套他们并不明白的理论来工作。他们重复从别人听到的，这就变成了一个电话游戏——我们在彼此耳朵间耳语，经过数次的信息传递“我周五和皮特踩自行车”变成了“我喜欢吃煎鸡蛋”。

这不是要责怪谁，这玩意是无法完全理解。我也是写了这篇文章才明白。但是这你必须明白：反锯齿不是我们想要的。我们要的是“消灭讨厌的失真”，这是不一样的东西。抗锯齿在这些方面有所帮做，但是不是完整解决方案，它还会带来伤害。

解释问题

傅里叶变换是所有关于对待数据为了一个巨大容器并映射为一组（复数）正弦波，它被认为是基础函数。每个正弦波有不同的频率。容器在每个基础函数方向的的长度告诉我们一些关于该频率信号的“频率含量”。

但是它告诉我们的并不是频率内容。如果你用一个单一的余弦曲线作为基础函数，你对它进行傅里叶变换，你会得到你想要的：在合适的频率中出现了一个单一的尖刺。但是如果基础函数间余弦波有一个频率，你不会再产生一个尖刺。你通过整个光谱获得一个频率斑点。图10和图11可描述出来。傅里叶变换的峰值是在正确的位置，不过有什么事情发生了？

尽管傅里叶基础函数又单一的频率组成，最终他们仍然是基础函数。如果你将转换后的数据归为除“我的输入数据与每个基函数的内积”之外的任何解释，那么你这样做风险自负。“信号的频率内容”只是一种解释，有点误导人。

当我们为了抗锯齿而进行低通滤波时，我们是在对这种错误的解释进行操作。注意到图10的余弦波能下采样为mipmap在它的角度来看还不错。但是当我们过滤它，我们裁剪所有红线右边的高频信号。这些频率不是真的在这里，当我们用余弦波减去他们，形状就会变化。我们这是自食其果。这一点很重要:某种假想的“真实”反锯齿会让余弦函数毫发无损，但是我们所知道的是当傅里叶变换通过它自己独特的隧道视觉来看待它的时候如何抗锯齿。这样导致了问题。

能量转换

一个重要的mipmaping滤波器的目标是他们不增加或减少一张图的能量，一张纹理的所有mapmap等级亮度要一致。这相当于说，当你在一个给定的样本上扫过一个过滤器时，该样本的所有贡献的总和不会超过样本的原始大小。换句话说，Σfi*s = s，fi是滤波器系数，s是取样值。当Σfi = 1，滤波器的系数和为1。

图12演示了这一点。左边是高对比度的清晰纹理，右边是低分辨率通过简单方法构造的mipmap：包含精细特征的区域明显变暗。

简单介绍一下gamma：除非我们对显卡做了奇怪的调整，CRT显示器出来的光的亮不是帧缓存值“p”的正比，而是p^γ的正比，γ（gamma）是一个依赖设备的值一般大于2。我们的眼睛描述光能量是对数级的，所以指数级的能量迸发到我们大脑时，我们才看起来有点线性。

我们保存所有纹理为非线性的方式：他们希望取幂CRT以看起来正确。这是一种压缩机制，我们会需要多于8位每通道，如果每个通道保持正比于光能量的话。

假设我们传递一个简单的box filter，常数[.5 .5]，通过一个量级的样本。我们得到图的2个贡献值，量为.5s和.5s。再次增加，越多越好。现在CRT提高gamma能量。现在我们有两个相邻的像素量为.5^γs^γ。简单假设gamma值是2.最终的光能量是.25s^γ + .25s^γ = .5s^γ，但是只有一般的量度，未经过滤的像素就会输出为s^γ，图像会变暗。

我么能修复这个问题通过在一个像素值正比于光能量的空间过滤。我么转换纹理为此空间，通过γ次幂来提高每个像素值。然后我们将滤波器应用到纹理，确保能量转换。我们然后提高每个像素为1/γ取回ramped空间再把纹理写入帧缓存（CRT会提高每个像素到gamma输出）。

现在我们很清晰了，设置帧缓存保证所有保存的值都是光能量的线性相关的，RAMDAC将执行任何必要的求幂运算。高端电影和科学渲染都会用线性光，近来游戏渲染也普及了。当帧缓存是线性光，你能通过在帧缓存增加像素值来增加表面的辐射（现在当表面被多个光照射时，我们能把他们加在一起，但是gamma的ramp是不对的。这就是为什么PC游戏呆滞无光。）

参考： http://number-none.com/product/Mipmapping,%20Part%201/index.html http://number-none.com/product/Mipmapping,%20Part%202/index.html