Coarse-Z Filter 图形算法.doc

栏目：图形算法与技术Coarse-Z Filter:降低深度带宽的图形流水单元高 可,杨珂1,石教英,刘真(浙江大学CAD&CG国家重点实验室，浙江 杭州 310027. 1: )摘要： 本文提出Coarse-Z Filter（CZF）图形流水单元，在象素级深度测试前进行Tile级深度测试以减少读Z-Buffer的次数，从而有效地降低图形流水线的带宽。CZF提供单缓存和双缓存两种模式，前者由一个低分辨率过滤缓存组成，存储扫描转换后Tile内所有采样点的最大深度值；后者增加了一个辅助缓存和掩码位平面，以获得更高的剔除效率。测试结果表明，在当前渐趋复杂的场景中，使用CZF可降低30%40%的带宽。关键词：图形流水线、深度缓存、Tile、Coarse-Z Filter中图法分类号：TP391Coarse-Z Filter: A Graphics Pipeline Unit to Reduce Depth BandwidthGao Ke, Yang Ke1, Shi Jiaoying, Liu Zhen(State Key Lab of CAD&CG, Zhejiang University, Hangzhou 310027,China. 1: )Abstract: We proposed a graphics pipeline unit, namely Coarse-Z Filter (CZF), for tile-level depth culling prior to per-pixel test, to reduce depth reading and thus reduce the pipeline bandwidth. CZF provides two modes, namely Single CZF, which employs a low-resolution Filter Buffer storing the maximum depth of a scan-converted tile; and Double CZF, which adds an auxiliary buffer and a bit mask plane to gain a higher culling ratio. Test results shows that CZF can reduce up to 30-40% pipeline bandwidth in todays scenes being more complex.Key Words：Graphics Pipeline, Z-Buffer, Tile, Coarse-Z Filter7 引言在三维图形流水线中，硬件Z-Buffer算法是目前最为常用的消隐算法。其最大的优点是算法简单，可轻易地消除隐藏面，而计算量却呈线性复杂度O(n)。但是，当渲染类似城市建筑群这样的高复杂度的场景时，绘制每一帧都需要读写Z-buffer非常多次，而且往往要求比较高的Z值精度，因此，读写Z-Buffer将耗费相当可观的图形流水线带宽。例如，在场景复杂度为10，Z值精度为32bits，屏幕分辨率为2048x1536的情况下，为达到实时绘制的效果（30fps），仅读取Z-Buffer需要的带宽达到3.6GB/sec（30x2048x1536x10x32/8=3.6GB/sec）。若60%的采样点通过深度测试，则写Z-Buffer的带宽为2.16GB/sec（3.6GB/sec x60%=2.16GB/sec）。针对此种情况，主要有两种解决思路。一种是对象空间的方法。在几何处理阶段，通过建立场景数据库对场景进行有效组织排序，使渲染尽可能的遵循由近及远的顺序。这样，可有效降低场景复杂度，大幅减少绘制面片的数量1,2,3。虽然这种方法可大量节约带宽，但由于场景组织工作开销过大，目前很少有硬件支持。另一种是图象空间的方法。在Z-Buffer算法前使用某种保守的深度测试先行剔除部分被遮挡的采样点，这些被剔除的点不需要读取Z-Buffer，从而降低带宽。代表性的方法是层次Z-Buffer（HZB）算法。HZB的思想由4提出，在许多保守的消隐算法中被采用5,2，并由ATI在其Hyper-Z6技术中商用。该算法将象素点按其Z值组织成分层结构，每层Z-buffer存储下层Z-Buffer中对应2x2大小的方形区域内的最大Z值（图1）。这样，通过低分辨率的保守深度测试，可快速剔除大部分本应被传统Z-Buffer剔除的象素点，降低读取Z-Buffer的带宽，例如，图1中，若某象素点被第三层Z-Buffer剔除，则所需带宽仅为传统Z-Buffer的1/16。该算法的不足是更新HZB需要很高的代价。例如，图2中，当Z值为7的象素写入第一层Z-Buffer时，须计算该象素所在Tile的最大Z值以更新第二层Z-Buffer，并用同样的方法更新第三层Z-Buffer。（a）第一层（b）第二层（c）第三层图1 三层HZB快照（a）第一层（b）第二层（c）第三层图2 更新HZB除HZB算法外，Depth Filter7采用一组简单的深度位平面做在早期的深度测试。该算法中，若某象素点小于特定的某个深度值d（例如d=0.55），则将位平面相应的位置1，此后，相同屏幕坐标下深度值大于d的采样点可直接被剔除而不必访问Z-Buffer。这种方法的优点是算法简单，易于硬件实现，同时弥补了HZB算法更新代价大的不足，但由于d是经验深度值，无法在各种不同场景中广泛适用。本文提出的Coarse-Z Filter（CZF）综合吸收了HZB 算法与Depth Filter的思想。CZF使用一个类似HZB的低分辨率的过滤缓存器，置于逐象素深度测试之前，通过Tile级深度测试以剔除大量被遮挡的采样点。3Dmark03测试结果表明，一般情况下，可节省流水线带宽10%左右，而在高Z剔除率情况下，可节省30%40%。CZF算法简单，结构简约，极易硬件实现，一般仅需不到1MByte额外硬件开销，即可获得很高的带宽收益。1 Coarse-Z Filter相对于传统图形流水线，当前消费级显卡的图形流水线有以下三个特点：（1）Pre-Depth。如无-Test等特殊情况，则在扫描转换后立即做深度测试，以减少不必要的纹理读取（图3）。图3 图形流水线（2）Z-Bottleneck。为渲染一个采样点，通常需要四次访问显存，分别是读写Z-Buffer、读取纹理、写颜色缓存。平均每个采样点每次访问占用4 Byte带宽6。定义rz为Z剔除率，即被深度测试剔除的片元占所有片元的百分比。一般场景中，rz为40%左右。此时RZ占流水线带宽的1/3强（表1）。而在某些由近及远的复杂场景中，rz可达80%以上。此时RZ占流水线带宽的60%以上（表1）。由此可见，读取Z-Buffer所需带宽占据流水线带宽的主要部分，容易成为瓶颈所在。带宽分布rz读Z-Buffer写Z-Buffer读纹理写颜色缓存40%37%21%21%21%80%62%13%13%12%表1图形流水线带宽分布（3）Tile-Based。使用基于Tile的寻址模式8, 9代替线性寻址模式以优化纹理映射（图4）。容易在扫描转换时获得当前Tile内象素点的最大深度值（TileZmax）、最小深度值（TileZmin）和有效点的分布掩码（TileMask）（图5）。图4 两种寻址模式（a）TileMask=0xFFFF （b）TileMask=0x8DEE图5 图4-a中两Tile内采样点分布掩码TileMask本文提出的Coarse-Z Filter（CZF）在Z-Buffer测试之前做Tile级深度测试（图3），以降低读取Z-Buffer所需带宽，进而降低图形流水线带宽。CZF的结构类似2层HZB，但不同的是HZB基于方形区域组织、进行多边形级别的剔除，而CZF基于Tiled扫描转换的结构，基于Tile组织、进行Tile级别的剔除。CZF处理的对象是扫描转换后的Tile，处理结果是判断该Tile是被整体剔除还是需要由传统Z-Buffer算法进一步裁决。CZF有两种模式，即单缓存模式（SCZF）和双缓存模式（DCZF）。1.1 SCZFSCZF（Single Coarse-Z Filter）由一个低分辨率的过滤缓存（Filter-Buffer，简称FB）构成，其中存放的每个深度值FBZ对应一个Tile。我们采用的Tile的尺寸为4x4，FB的分辨率为Z-Buffer的1/16，FBZ精度为16bits，并初始化为无穷远（图6-a）。SCZF根据以下原则处理扫描转换的Tile： （1）若TileZmax = FBZ，意味着Tile内的最近的采样点比FBZ还要远，说明当前Tile内的所有采样点都在Z-Buffer内对应象素点的后面，所以整个Tile被剔除掉（图6-c）。（3）若TileZmin FBZ TileZmax (在这里设无效片元的深度为无穷远），如图6-d、e，说明FBZ无法剔除Tile内的部分象素点，它非常保守地认为此Tile通过测试，必须把它送进逐象素的深度测试单元。（4）若TileMask不为全1（图5-b），则认为TileZmax为无穷远。图6给出了SCZF的算法演示，方便起见，Tile尺寸采用2x2。（a）中两图分别表示初始化时刻的FBZ和Z-Buffer，（b）到（d）中，自左向右的三幅图分别是相同屏幕位置下的扫描转换的Tile、与之对应的FBZ和Z-Buffer。 F表示无穷远，黑色块表示该屏幕位置处没有被扫描转换的采样点。（a）初始化（b）TileZmax=7，小于FBZ（F），更新FBZ（c）TileZmin=8，大于FBZ（7），剔除Tile（d）TileZmin=1，TileZmax=F。通过Tile级深度测试，但不更新FBZ。（e）TileZmin =4，TileZmax=F。通过Tile级深度测试，但不更新FBZ。图6 SCZF算法演示1.2 DCZFSCZF根据扫描转换的Tile内采样点的最大Z值（TileZmax）和采样点的分布情况（TileMask）更新对应的FBZ，其必要条件是（1）TileZmax = FBZ，则与SCZF一样，剔除整个Tile。（2）若TileZmin ABZ或（b）AB初始化状态这两种情况下，更新ABZ。（图7-b）（3）若DBM为全1，则用ABZ更新FBZ，并重新初始化ABZ和DBM（图7-d）。图7给出了DCZF在先后处理图6-d、e两个Tile下的算法演示，自左向右的五幅图分别是相同屏幕位置下的扫描转换的Tile、FBZ、Z-Buffer、ABZ、DBM。（a）某时刻快照（b）TileZmin=1，小于FBZ，记录采样点分布情况到DBM。ABZ为初始化，故更新ABZ。（c）TileZmin=TileZmax=4，TileZmin小于FBZ，记录采样点分布情况。TileZmax= FBZ)Discard the tile;return;DBM |= TileMask;if (TileZmax ABZ)ABZ = TileZmax;if (DBM = 0xFFFF)FBZ = ABZ;Do per-pixel depth test;return;SCZF伪代码：if (TileZmin = FBZ)Discard the tile;return;if (TileMask = 0xffff)&(TileZmax FBZ)FBZ = TileZmax;Do per-pixel depth test;return;1.3 SCZF和DCZF的比较SCZF和DCZF互有优缺点，我们从以下三个方面对两者做比较：（1）硬件开销。SCZF中，由于一个Tile内的16个采样点共享一个16bits的深度值FBZ，平均每个采样点只需要1bits。 DCZF中，16个象素共享一个16bits的FBZ、一个16bits的ABZ和一个16bits的DMB，平均每个象素需要3bits，也就是说，相同分辨率下，DCZF需要3倍于SCZF的额外内存。（2）CZF效率（E）。定义CZF效率为CZF剔除的采样点占Z-Buffer算法剔除的采样点的百分比。对于同一场景，E越高，则CZF剔除的象素点越多，所节省的带宽也就越多。由于使用了更为积极的FB更新策略，DCZF可剔除很多SCZF无法剔除的象素点，所以其效率要高于SCZF。（3）CZF的带宽负担。加入CZF后，CZF所占的带宽成为流水线带宽的组成部分。相同情况下，CZF的带宽越小，对流水线带宽的优化越明显。最好的情况是扫描转换的Tile内16个采样点均被剔除，此时，两种模式下均只需要读取FB，平均每个象素占用1bits，带宽负担相同。最坏的情况下，两种模式有所不同，对应于SCZF的是扫描转换的Tile内只有一个采样点，此时也需要读取FB，该采样点占用16bits；对于DCZF的是扫描转换的Tile内只有一个采样点，而且该采样点导致FBZ、ABZ和DBM均需要更新，此时该采样点占用96bits（读写FB、AB、DBM各32bits）带宽。可见，DCZF的带宽负担为SCZF的16倍。综上所述，DCZF比SCZF高效，但是也需要更多的硬件开销和带宽负担。2 测试结果及分析3DMark是FutureMarkTM出品的专业3D测试软件，从发布以来一直引领3D游戏行业的发展，由于其最新版本往往领先实际游戏一代，所以我们选择3DMark03中的三个Demo（Wings of Fury、Battle of Proxycon和Trolls Lair， 图9），在我们的参考光栅器(reference rasterizer)上进行测试。测试时，每个Demo选取100-150帧，屏幕分辨率设置为1024x768。测试结果见表2，其中DRZ、DB分别是使用CZF后读取Z-Buffer降低的带宽和整条图形流水线降低的带宽占各自原带宽的百分比。在Wings of Fury 和 Battle of Proxycon中，rz约为40%；在Trolls Lair中，rz约为80%。测试表明，在rz接近的场景下，HZB在3Dmark中的E为44%6，而Depth Filter很难设置统一的经验值d，当d=0.35时，仅在最好场景下E为70%7，而这是难以推广的。相比之下，CZF的效率E在单缓存模式下超过60%,在双缓存模式下约为90%，效率高于HZB，实用性优于Depth Filter。 (a) Wings of Fury (b) Battle of Proxycon (c) Trolls Lair图9 3DMark03 测试用例测试用例Wings of FuryBattle of ProxyconTrolls Lair单缓存(SCZF)E65.08%67.59%63.74%DRZ22.91%23.91%47.87%DB8.48%8.85%29.68%双缓存(DCZF)E89.13%88.50%90.51%DRZ24.48%24.20%65.83%DB9.06%8.95%40.81%表2 CZF测试结果根据表2的测试结果，可知：（1）由于使用了更为积极的FB更新算法，DCZF的效率明显高于SCZF。（2）在rz较小的情况下，由于读Z-Buffer并不是图形流水线带宽的瓶颈，Coarse-Z Filter的优化效果并不十分明显（DB小于10%）。（3）在rz较大情况下，读Z-Buffer成为流水线带宽的瓶颈，此时Coarse-Z的优化效果十分明显（30%-40%）。CZF对复杂场景的贡献率更大，这顺应了当前的应用程序的深度复杂度不断增大的趋势。（4）在rz较小情况下，虽然DCZF的效率高于SCZF，但由于DCZF自身所占的额外带宽也较多，所以两种模式下对带宽的优化基本持平。这表明在简单场景下用单缓存较有利于节省硬件计算开销。在rz较大的情况下，相对于提前剔除象素点所节省的带宽，CZF自身所需的带宽很小，所以DCZF对带宽的优化作用大于SCZF。这表明在复杂场景下双缓存模式的优势。3 结论和展望复杂场景中，尤其是高剔除率的复杂场景中，读写Z-Buffer耗费了大量内存带宽。我们提出的Coarse-Z Fitler既拥有金字塔的剔除高效性，又有标志位平面的维护方便性。CZF在逐象素级深度测试前进行Tile级深度测试，剔除了60%以上被遮挡的采样点。CZF算法简便，维护代价小，可同场景组织算法结合使用，易于硬件实现，能够有效地降低流水线带宽，具有良好的实用价值。3Dmark03的测试结果表明，理想情况下，节省的图形流水线带宽高达30%-40%。CZF的两种模式中，SCZF更为简单，DCZF更为高效。硬件设计者可结合具体所需要的情况做出相应的选择。今后的工作主要包括两个方面：一是测试不同分辨率下的场景，从而为嵌入式图形硬件也提供借鉴；二是加入CZF的片上Cache，以进一步降低CZF本身所带来的带宽负担。参考文献1. J. T. Klosowski , C. T. Silva, Efficient Conservative Visibility Culling Using the Prioritized-Layered Projection AlgorithmJ, IEEE Transactions on Visualization and Computer Graphics, v.7 n.4, p.365-379, October 20012. H. Zhang, , D. Manocha, , T. Hudson et al. Visibility culling using hierarchical occlusion mapsC. Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH 97, Los Angeles, CA, p.7788, 1997.3. X. Lu, Method based on Painters Algorithm for moving polyhedrons hidden-surface removalJ, Journal of Computer-aided design and computer graphics, Vol.11(2), Nov. 1999 (In Chinese). p. 125-128 (吕旭东，基于画家算法的运动多面体的消隐方法J，计算机辅助设计与图形学学报 11(2), 1999年11月：125-128.)4. N. Greene, M. Kass, G. Miller, Hierarchical Z-buffer visibilityC. Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH 93, Anaheim,