从军行
[唐代][王昌龄]
青海长云暗雪山， 孤城遥望玉门关。
黄沙百战穿金甲， 不破楼兰终不还。
本文是对雪崩工作室在SIGGRAPH2012上分享内容的学习总结。其PPT可以通过如下链接下载。
本文的内容主要可以分成如图中所示的四大块，下面将分别进行展开介绍。
Particle trimming
相较于CPU的性能增长，GPU的增长幅度更为迅猛。而在过去的十年之内，ALU（算法逻辑单元）以及TEX（贴图填充速率 Giga Texel /second）等组件的发展速度要远远高于BW（带宽）与ROP（raster operation，光栅化处理）组件的发展速度，达到数十乃至上百倍增幅，而现代GPU的ALU/ROP的能力则仅仅只是十数倍于十年前的版本，通常来说，ROP导致的性能瓶颈的解决方案目前还比较少：
1.最好的方法就是减少需要参与渲染的像素数目。
2.另一个解决方法就是通过优化shader来降低单个像素的渲染消耗，从而将瓶颈转移到ALU/TEX单元。不过呢，这种方法虽然能够在一定程度上减轻ROP的压力，但是在效果上其实并没有多大的帮助。
目前在游戏中，有如下一些情况可能会导致ROP问题：特效粒子，云层渲染，公告板，UI等。而在这些情况中，其对应的像素shader的计算都是非常简单的（也就是说通过优化像素shader，可能无助于减轻问题）。
之前有过一些trick之类的方法能够在某些条件满足的情况下能够应付这类问题：
1.设置一个低分辨率的RT，渲染完成之后再上采样到输出buffer（其实就是降分辨率）。这种方法对于一些低频数据（比如说粒子系统，大多比较柔和，不会有清晰的边界，即使因为上采样导致模糊，也不会有太大问题）可能不会有什么问题，但是对于高频数据，其表现可能就不尽人意了。
2.另一种方法就是使用MSAA技术用于提升光栅化的的吞吐量（怎么做到？还是用1/4分辨率的RT+MSAA得到全分辨率的输出buffer？），不过如果已经使用了MSAA方法来消除锯齿的话，那么这种方法就不可行了。
而本文给出的ROP bound的解决方法则是尝试消除无效渲染的方式来减少像素数目。这个技术从原则上来讲，还可以跟上面的两种trick方法结合起来使用，进一步降低ROP的消耗。
如图所示，一张典型的特效贴图通常都会存在一大片区域的alpha值为0，这些区域对应的像素的渲染都是会有ROP消耗（当然，不仅仅是ROP，还有其他的一些消耗）的，而且这些区域的渲染对最终结果也不会产生任何贡献。
那么要怎么减少这些区域的渲染消耗呢？一个简单的且有效的方法就是用更精细的多边形将有效的像素区域标记出来，从而尽可能的减少浪费。当然，这种工作如果是人工标记的话，会非常的耗时耗力，因此雪崩工作室这边为美术同学制作了一个自动生成最佳包围多边形的工具。
理论上来说，包围多边形的顶点数目越多，得到的包围形状也就越精细，像素填充的浪费也就越少。不过顶点数目过多也会存在一定的损耗，通常来说，多于8个顶点的包围多边形，已经很难做到利大于弊了，考虑多方消耗平衡的情况下，一般四个顶点的包围多边形的优化程度最高。
而在包围多边形顶点数较少的情况下，只有当贴图中的有效像素范围要远小于贴图尺寸的时候，这种优化才能得到较好效果，通常来说，像素shader是不太可能会成为瓶颈的。不过如果特效粒子是在CPU上生成，为之生成多个顶点的话可能会有不小的消耗。正因为这个原因，在《正当防卫2》中，我们才坚持只使用4个顶点的包围多边形来进行云层的ROP优化；不过由于特效渲染的顶点是在GPU上生成的，因此在顶点数不超过8个的情况下，提升的效果可以随着包围多边形顶点数目的增多而提高。
在制作自动剔除工具之前，雪崩工作室最先尝试的是手动进行剔除处理（在debug菜单中增加一个简单的临时剔除方法），并在云层贴图中进行了测试，发现这种方法确实是有效的，不过操作过程太过繁琐。不过因为测试结果的提升效果非常好，所以后面才决定将这种方法推广到所有的特效中。但是手动制作的方式成本过高。因此决定尝试给出一套自动化的提取方案。
自动化工具的目的是在给定的贴图，给定的顶点数，给定的alpha阈值的基础上，自动生成一个包裹住有效像素的最小多边形。这个工具目前是开源的，在网上可以找到。之后还会持续更新并融入当前的图形管线。
算法的第一步是根据待渲染区域的有效像素构建一个convex hull（凸多边形包围盒），而如果要对任何一个有效像素都进行convex hull的构建检测的话，整个实现过程可能会非常耗时，为了减少消耗，最终决定只对边缘像素进行检测计算。
构造出来的convex hull在顶点数目上会比我们预期的顶点数目要多一些。为了找到符合条件的最佳的包围多边形，我们会对convex hull的每条边都进行遍历测试，找出其中面积最小的一个。这实际上是一种暴力解法，为了提高速度，就需要提前去掉一些搜索选项。具体优化方法就是每次移除一个导致convex hull面积增加幅度最小的顶点。
最终的包围多边形可能会出现一些超出原贴图范围的像素，对于这些像素可以直接通过clamp剔除掉就行了，不会有什么问题。
而对于那些使用贴图atlas实现特效粒子的方案来说，这样的多边形结果可能就会导致超出部分使用了其他特效的贴图而出现效果异常。这种情况大多出现在顶点数较少的情况下，在《正当防卫2》中特效使用了8个顶点来制作包围多边形，并没有导致异常表现。而对于使用四个顶点的云层贴图，这个问题则是通过人工处理的方式来避免的。在《正当防卫2》之后的方案中，我们会在出现这种问题的时候直接放弃此方案，从而在放弃一些优化效果的前提下保证了效果的正确性。
Merge-Instancing
DP优化常用的手段有两种：
1.对于同一个模型的多个实例，可以通过实例化来降低DP
2.对于多个不同的模型实例，可以通过静态合批（合并到一个顶点buffer与index buffer中）来降低DP
对于由多个模型组成，每个模型对应多个不同的实例的情况来说，如果使用第一种方法，就需要使用多个DP（每个模型对应一个），而如果使用第二种方法，则会存在重复的顶点数据与索引数据
这里提出了一种只用一个DP就能完成多个不同模型的多个不同实例的渲染，且每个模型的顶点数据在内存中有且只有一份：命名为Merge-Instancing。
这张是《正当防卫2》中的截图，用红色圆圈标注的建筑都对应同一个模型，第一个想法就是最好采用合批的方式进行渲染，不过如果使用静态合批的话，那么这些模型组成的大模型的包围盒就会很大，从而导致部分不可见的部分的渲染消耗。而如果使用动态合批，逐个对这些建筑进行剔除处理，这个剔除的消耗的增加，可能会远高于DP减少带来的收益（这是什么意思，意思是由于剔除时间成本太高，不合批的话，可能时间消耗还更低一点？震惊？不过，感觉这是两件事情啊，即使不合批，也是需要逐个对物件进行剔除啊，这个消耗是固定的，除非是直接静态合批了，不过静态合批也有静态合批的问题），更何况还需要考虑在每帧中动态生成实例buffer的消耗。
通常来说，将周边聚集程度比较高的多个模型进行合批的收益比较高，这样一来，这些物体可以组成一个大的包围盒（动态合批会影响到相机剔除？看来是我孤陋寡闻了）在剔除的时候会更高效。不过聚集比较近的物体大多不是一个模型，因此需要借助Merge-Instancing方法来处理。
从代码层面对比：
1.传统实例化的实现是通过对每个实例的每个顶点，调用一遍顶点shader
2.Merge-Instancing技术的实现则是：
A.将不同模型的顶点数据放入到一个顶点buffer中
B.将各个模型的索引数据放入到一个索引buffer中，索引buffer需要按照freq进行分段，freq=maxIndexBufferSize（各个模型中最大的索引buffer的尺寸），对于那些索引buffer长度小于freq的，剩余空间填充0
C.将各个实例（不同模型的相同模型的功用）的数据放入到实例buffer中
D.vertex_count=freq*instance_count，对每个顶点数据进行顶点shader处理
这种算法对于那些indexbuffer空间填充不满的模型，可能会有部分计算消耗（可以通过将各个模型的indexbuffersize填入instancebuffer来解决）
《正当防卫2》中，这种技术只在Xbox 360中被应用了（性能最差的平台，且硬件与此技术十分契合），PS3性能比较好，且还有SPU的加成，不存在DP问题。
这里说到了对齐不同模型index buffer尺寸的问题。
Phone-wire Anti-Aliasing
在以前图形学刚起步的时候，锯齿问题通常通过mipmap和MSAA就能应付了，不过随着渲染效果越来越复杂，导致锯齿的原因也越来越多，使得当前这两种技术已经逐渐变得软弱无力：
MSAA在处理几何体边沿锯齿方面有比较好的效果（在几何体比较纤细的时候效果就会比较差，比如电线），mipmap在处理贴图缩放方面的效果也不错。不过对于越来越复杂的像素shader，其引入的锯齿（比如高光锯齿，阴影锯齿等）这两种方法已经变得力不从心。比较出名的方法是LEAN mapping（不太清楚是什么技术）。在几何体边沿锯齿处理用的MSAA技术在像素进一步细分到subpixel（比如电线这种比较纤细的）级别就不再适用了。
Phone-wire Anti-Aliasing(PWAA)技术主要是为了解决MSAA在处理较细物体锯齿时的力不从心而提出的。
游戏中经常会出现电线这类非常纤细的物体，这种物体随着距离的拉远很容易出现锯齿问题，且由于这种物体随着距离的推远其渲染的结果占据的尺寸就会接近于subpixel的size，导致MSAA对于这种问题的解决能力有限。这里给出的解决思路是，避免让物体的渲染结果进入subpixel尺寸。具体怎么做呢？
Phone-wires are essentially long cylinder shapes, and for the purpose of this technique they will be represented in the vertex buffer as a center point, a normal and a radius. This is so that we can dynamically adjust the radius of the wire. Note also that this technique works for any cylinder shape, not necessarily only phone-wires. There are other fairly common game content that it also applies to, such as antenna towers, railings, bars etc.
电线可以看成是多个圆柱的组合，而圆柱在顶点buffer中，可以用中心点，法线以及圆柱的半径来表示（长度呢？直接设定成定长的？），而通过调整圆柱的半径，可以避免圆柱渲染的结果处于subpixel尺寸，从而避免因此而导致的锯齿问题。
具体实现起来的思路也比较简单，在具体渲染的时候，我们将圆柱的半径设置成不小于对应距离的单个像素尺寸的大小即可。那么如果继续拉远距离，渲染出来的电线的尺寸不就是依然会维持不变，结果会不会显得异常？为了避免因此带来的问题，我们将电线的真实半径映射到alpha中，通过透明度来实现电线的渐隐效果。
1.先计算电线的距离w
2.根据距离，计算出当前距离情况下单个像素对应的尺寸
3.计算当前实际半径对应的alpha值
4.将各个像素沿着法线方向扩展一个半径的大小，就成为了一个圆柱体
下面给出各个技术的实施效果对比：
PWAA实际上并不能算是一种AA方法，只是调整了几何物体的尺寸，使之不因尺寸过小而导致的衔接异常，在使用了PWAA之后，还可以继续使用其他AA方法来对效果进行进一步增强提升。
Second-Depth Anti-Aliasing
2011年的Siggraph会议上有一个专门关于AA的course，涌现了大量的AA方法。这些AA方法大致可以分成两类：
1.Post AA方法，在后处理中对最终的pixel buffer进行处理。这种方法不关心pixel buffer是如何生成的，也不需要几何体的相关数据，其实现过程是与整个渲染管线相解耦的。
2.分析类AA方法，这种方法的实现是需要获取到pixel buffer生成过程中的一些中间数据信息，不过这些信息不是通过反向解析pixel buffer而得来，而是来自游戏渲染的过程中存储数据。
这里给出的SDAA方法，就是属于分析类AA方法，这种方法相对于Post AA方法而言，对于游戏引擎的侵入性会更小一点？（没太理解）
SDAA方法的实现是基于以下的一个观察而来：存储于深度buffer中的数据是通过光栅化插值而来，在屏幕空间中是线性的。这张图是将ddx(z)与ddy(z)作为输出结果的RG通道数据得来的，可以看到几何体的表面上的颜色是相同的，也就是说同一个表面上的像素之间的差异是常量。因此，利用这个特性可以对深度buffer进行处理以解析出几何体的边缘数据。
上面方法检测出来的边缘可以分成两类：褶痕与轮廓。褶痕只用一个深度buffer就可以解析出是否是边缘，而轮廓则需要一个第二深度buffer才能判定是否是边界，SD buffer可以通过进行Front Face culling（只渲染背面）得到。
在拿到边缘数据之后，就可以开始AA处理了。第一步就是将尝试边缘数据当成褶痕进行处理：计算两个斜坡之间的交点，如果交点位置距离当前像素小于一个像素（则认为是有效的，而只有当交点距离当前像素小于半个像素，才会被拿来对当前像素进行AA处理。之所以要这样做，是因为如果边界距离要大于半个像素的话，那么交点应该要归属到当前像素的下一个相邻像素。如果按照这种处理方法得不到一个交点的话，那么这个边界点就不是褶痕，而是轮廓。
对于轮廓点而言，仅仅依靠深度buffer，没有办法定位具体的边界点位置。如图中的紫色轮廓点，我们只知道蓝色线段的终点位于第二个采样点与第三个采样点之间的某个位置，具体的位置我们是不知道的。通过结合SD buffer的背面数据，我们是可以定位到紫色点的位置。之后的处理方法就跟褶痕点的处理情况一样了。
这种方法可以很精确的查找到场景中的边界线，从图中可以看到，结果是非常平滑的（下面的图是放大版本）
这种方法的精确度取决于深度buffer的格式，至少要24位的深度才能work。
