第  40 卷  计  算  机  学  报  Vol.40 2017 论文在线出版号  No.31  CHINESE JOURNAL OF COMPUTERS  Online Publishing No.31 ——————————————— 本课题得到国家自然科学基金（61173067,61379085,61532002）、国家863计划项目（2015AA016401）资助.  周果（通讯作者），男，1987年生，博士生，主要研究领域为计算机图形学，E-mail: zhouguo@ict.ac.cn；朱登明，男，1973年生，博士，副研究员，是计算机学会（CCF）会员，主要研究领域为自然现象模拟和数据可视化，E-mail: mdzhu@ict.ac.cn；王兆其，男，1966年生，博士，研究员，博士生导师，是计算机学会（CCF）高级会员，主要研究领域为虚拟现实和智能人机交互，E-mail: zqwang@ict.ac.cn。 面向大规模场景的多片元效果高效绘制 周果1),2),3)    朱登明1),2)      王兆其1),2)  1)(中国科学院计算技术研究所  前瞻研究实验室,  北京  100190)  2)(  移动计算与新型终端北京市重点实验室,  北京  100190) 3)(中国科学院大学,  北京  100049) 摘  要  多片元效果具有例如实时透明等重要应用，它需要每个像素按深度顺序遍历对应的所有片元。深度剥离法将场景重复绘制多次来满足这个需求，故对显存带宽提出了很高的要求。本文针对大规模场景图元分布稀疏的特点，使用类体素八叉树在物体空间将场景近似剖分以减少图元读取总量。这允许场景能够按可见性顺序被分块加载、精确剖分和逐个绘制：通过光栅化对应的八叉树网格构造深度桶列表，在屏幕空间将场景块与网格布尔求交；通过为整个场景构造块的深度直方图，在剥取时利用它来避免硬件遮挡查询操作。由于为每块采取了不同的迭代次数，本文的两阶段剖分方法能够适应物体空间变化的深度复杂度。由于不依赖于面片的邻接信息，本文方法能够支持非流形网格和外存绘制。相比已有工作本文方法在每次剥取一层时绘制效率有百分之三十以上的提升。 关键词  八叉树；体素化；深度剥离；构造实体几何 中图法分类号  TP391   论文引用格式：   周果，朱登明，王兆其,  面向大规模场景的多片元效果高效绘制,2017, Vol.40,在线出版号  No.31 ZHOU  Guo，ZHU  Deng-Ming，WANG  Zhao-Qi,  Efficient  Rendering  of  Multi-Fragment  Effects  for Massive  Scene,  2017, Vol.40,Online Publishing No. 31    Efficient Rendering of Multi-Fragment Effects for Massive Scene ZHOU Guo1), 2), 3)  ZHU Deng-Ming1), 2)  WANG Zhao-Qi1), 2) 1)(Advanced Computing Research Laboratory, Institute of Computing Technology ,Chinese Academy of Sciences, Beijing 100190)  2)(Beijing Key Laboratory of Mobile Computing and Pervasive Device, Beijing 100190) 3)(University of Chinese Academy of Sciences, Beijing 100049)  Abstract  The multi-fragment  effects have  many  important  applications  such  as real-time  transparency,  where all the fragments per-pixel are required to be visited in depth order. The depth peeling is a fundamental method committed to this task. It resorts to drawing the whole scene multiple times until those fragments are enumerated exhaustively. However, each time only a small portion of the scene contributes to the framebuffer. Most of  the primitives  and fragments  are  discarded  after visibility  tests  such  as depth  comparison, thus  wasting  too  much bandwidth and computation resource. Building upon the sparsity of distributed primitives, we propose a 2-step method based on the divide and conquer strategy. Our goal is to effectively reduce the total amount of accessed primitives  and  generated  fragments given  a large scene  with  complex  geometry. In  the  first  step, the  scene is 网络出版时间：2017-03-28 13:21:16网络出版地址：http://kns.cnki.net/kcms/detail/11.1826.TP.20170328.1321.002.html2  计  算  机  学  报  2017年 approximately  decomposed into  parts  by  using a  voxel-like octree  in  object  space.  This  octree  and  its accompanying mesh is  constructed  in  a  depth-first  manner,  to shatter  scene primitives from  the  top  down and create scene parts from the bottom up. It enables the results to be serialized as a stream, thereby the peak memory usage is alleviated. With the aid of the octree mesh, all the parts can be loaded and processed in visibility order. We  render  a  frame  by  batching those parts  with  respect  to  the  depth  complexity  of corresponding sub-mesh. Every  time  the  largest  possible  batch  is  extracted  and  submitted  to  the  graphics  pipeline. A predefined  lookup table is introduced to resolve the visibility order of some or even all parts. Although it only encodes the visibility order for a  sub-mesh  template,  the full  solution  can be  obtained on  the  fly by  applying  this  table  recursively during traversal. In the second step, all the parts are exactly decomposed by applying bucket sort in screen space. To  render  each  batch  of  parts  in  visibility  order, we  rasterize  their  corresponding sub-mesh  beforehand. A per-pixel  list  of  depth intervals  are constructed  in  parallel. Then  they serve  as  buckets  to  gather  fragments resulting from those parts, according to the fragment depth and associated part index. This efficiently implements the  boolean  union  operation  over parts  and  their  octree  mesh. The  duplicate  fragments  can  be  discovered  and discarded  safely  without  any  performance  hit. To  determine  the  depth  complexity  of  each  part,  we  employ  the software  occlusion  operation  to  avoid of  the  hardware  synchronization. A  depth histogram  over  parts  is constructed  by  augmenting  each  bucket  with  a  depth  counter,  then  each  part is  allowed  to  be  peeled independently. Since a different number of iterations is adopted for each part, our method adapts to the spatially varying  depth  complexity.  As  the  adjacency  information  of  primitives is  not  required,  it  is  straightforward  to support  non-manifold  mesh  and  out-of-core  rendering. Since  the  primitives  do not  need  to  be  tessellated, the original  scene  mesh  parameterization  is  kept.  Only  the  primitive  index  is  duplicated, therefore  the  additional storage cost is insignificant and our 2-step decomposition procedure is free from numerical issue. Our approach improve the rendering performance over existing work for more than thirty percent without any visual artifact. Key words  octree; voxelization; depth peeling; bucket sort; constructive solid geometry  1  引言 图形处理器（graphics  processing  unit，GPU）通过光栅化将三角形网格转化为离散的片元，然后通过一系列测试决定帧缓存中像素的颜色。通过考察每个像素对应的多个片元，可以实现例如透明和半透明材质、构造实体几何布尔操作等效果[1]。对于这些应用，如何在GPU上有效地按相对视点的可见性（即屏幕空间的深度）顺序逐像素枚举片元是实时绘制的关键。 大规模场景在光栅化后，每个像素会对应大量片元，且像素之间的片元数量差异较大。这给单指令、多线程架构的GPU提出了挑战：针对高度变化的深度复杂度（即一个像素对应的片元总数），实现显存的高效管理和计算任务的负载均衡。 由于一次性缓存所有片元往往导致显存溢出，已有工作需要反复从显存中读取整个场景，每次光栅化后按可见性顺序仅剥取一层或者多层片元。这就需要按整个场景的最大深度复杂度（即所有像素中最多的片元总数）迭代多次来遍历所有层，每次缓存少量剥取到的片元。然而每次保留的片元只对应场景中的局部，大部分面片产生的片元在比较深度后被丢弃。这样的无效计算浪费了大量带宽和计算资源，当场景规模较大时严重了影响绘制效率。 本文的目标是高效、无瑕疵地为含有非流形几何的无组织面片集（triangle soup）绘制多片元效果，通过发掘场景中面片空间分布的稀疏性来降低每帧所需读取的面片总量。 我们采用深度优先后根序的方式构建八叉树，每个叶子节点记录了相交的所有面片，在物体空间将场景近似剖分成块。根据视点所在卦限深度优先遍历树就能获得场景块的可见性顺序，从而逐个加载并应用深度剥离。为了避免重复绘制被多个叶子节点共享的面片，在屏幕空间通过布尔求交操作实现准确剖分。该操作基于叶子节点对应的空间立方体所构成的八叉树网格（octree mesh），在绘制前将其光栅化来为每个像素构造深度桶列表，在绘制时以片元从属的叶子节点序号为键值进行桶排序。为了避免剥取每层时的硬件论文在线出版号  No.31  周果等：面向大规模场景的多片元效果高效绘制  3 遮挡查询，本文构建场景块的深度直方图后直接剥取。 该方法不需要在物体空间应用耗时的拓扑排序来获得面片的可见性顺序，能够直接处理遮挡环路甚至是非流形几何。由于完全避免了面片细分，我们可以逐块加载来实现外存（out-of-core）绘制。由于每块仅对应场景的局部，相比整个场景它包含的面片数量和最大深度复杂度都显著减小。 通过按块而不是整个场景的最大深度复杂度剥取相应次数，就减少了绘制场景时所需读取的面片总数，在每次剥取一层的前提下显著地提升了绘制效率。本文的主要贡献有： l  一种根据八叉树叶子节点的可见性顺序进行深度剥离的方法； l  一种利用桶排序在屏幕空间将八叉树网格与三角形网格布尔求交的方法； l  一种针对多片元效果构建深度直方图来避免硬件遮挡查询操作的方法。 本文章节安排如下，在第2节中介绍多片元效果绘制的相关工作，特别是实时透明方面；第3节描述剖分、可见性排序的方法和以此为基础的剥离方法；第4 节给出实现细节和绘制的效率和效果，展示在含有非流形几何的大规模场景上的加速效果；第5节对实验结果进行讨论和总结。 2  相关工作 经典的深度缓存（Z-buffer）技术以流的方式获得每个像素深度最小的单个片元。缓存被初始化为最大深度，它与每个抵达的片元比较深度来决定是否替换。而多片元效果需要每个像素按深度顺序考察多个片元，例如透明效果根据混合方程[2]逐个将片元合并。 已有方法尝试从屏幕空间的片元和物体空间的面片两个不同粒度解决可见性顺序问题，它们针对应用场景进行性能优化。 2.1 片元的高效存储   为了快速处理所有片元，一个直接的方法是单遍绘制场景，采用隐式或显式的表达描述逐像素可见性。   隐式表达包括维护逐像素片元链表进行深度排序[3]，分配逐像素数定长数组，然后使用硬件原子操作[4]或者片元临界区[5]更新。由于预先并不知道生成片元的数量，这些方法不能准确地分配显存，可能造成浪费或者溢出，必须按最大深度复杂度分配空间才能获得准确的绘制结果。   特别地对于透明效果等应用，混合方程可被重新整理得到可见性的显式表达。故可以直接对其应用近似表示，比如使用离散样本点[6]、位掩码[7]、分段函数[8-9]、三角函数[10]或者随机抽样[11-12]。显式表达侧重考虑对可见性贡献较大的片元，故主要适用于烟雾、毛发等包含低频可见性的场景，能够获得较好的近似绘制结果。   本文通过适应空间变化的深度复杂度来提高效率，这与以上两类可见性表达方式是正交的，处理每块场景时同样可以一次性剥取多层。 2.2 多遍绘制场景   大规模场景在光栅化后生成的片元往往超过显存容量，所以通常将场景多遍绘制而每次仅处理部分片元。   经典的深度剥离[13]从前往后采用两个深度缓存迭代实现逐层绘制，每次丢弃前面的片元来获得下一层片元。这里剥取每一层都要绘制整个场景，而场景规模较大、遮挡关系复杂时层数很多，这导致每个面片都要按最大深度复杂度来读取、绘制相应次数。   此外使用硬件遮挡查询判断是否结束剥取，需要GPU和中央处理器（central  processing  unit，CPU）同步而导致效率低下。通过在每次迭代中剥取多层片元、减少迭代次数来提高效率，比如双深度剥离[2]使用最大最小深度缓存每次剥取最前面和最后面两层，桶深度剥离[14]使用多绘制对象（multiple  render  targets，MRTs）扩展，通过桶排序在多个深度区间内执行双深度剥离。该方法预先光栅化整个场景，获得每个像素的深度直方图来构造深度桶，但映射到相同桶的不同片元会发生读写冲突而影响绘制质量。   本文根据叶子节点的深度直方图剥取，可以得到无瑕疵的绘制结果。此外多遍绘制的思想可以直接和上一节的存储方法结合提高迭代的效率，但每次仍需读取整个场景。 2.3 针对可见性组织场景   考察物体空间面片的可见性顺序可以减少屏幕空间片元的排序开销。例如文献[15]使用几何着色器对线段应用快速排序和裁剪，深度区间中每个样本点只需绘制附近的线段。虽然每次能够避免4  计  算  机  学  报  2017年 绘制所有线段，该方法在裁剪时难以处理顶点属性，故不适用三角面片。   一类方法借鉴了体绘制的思想，比如将场景体素化为均匀网格数据后使用逻辑或操作实现遍历[16]，虽然能够实现体阴影等效果，但丢失了准确的几何信息。观察到每个凸多面体光栅化后为每个像素最多贡献两个片元，文献[17]提出对三角网格进行凸多面体剖分，生成的每个部件的最大深度上界确定，故使用定长数组能够准确处理。然而准确的全局凸多面体剖分是NP困难问题，所以他们从一些种子面片开始生长局部构造凸多面体，将多个凸多面体合并为部件后加入到均匀网格中。在绘制时采用与体元投影法[18]类似的思想，按部件的可见性顺序依次光栅化，故仅需要读取一遍场景。   然而只有当网格由四面体元构成时，体元间的遮挡关系有向图存在拓扑顺序，对于其他多面体元有向图往往存在环路需要Delaunay三角剖分[19]。因此在部件互相遮挡时需要进行细分，故增加了场景的复杂度。而对于含有大量细小形状的场景，这种方法会生成过量的多面体，增加了绘制调用开销。此外构造凸多面体需要输入网格为二维流形（组），故无法处理含有悬点、悬面甚至自相交等非流形几何的场景。   本文在物体空间八叉树剖分并在屏幕空间布尔求交，不但能快速确定场景块的可见性顺序，而且能绘制非流形网格和避免环路遮挡。 2.4 使用包围体确定遮挡关系   绘制不透明表面时，使用例如包围体树层次化组织场景后，节点的包围体能够作为代理（proxy）进行遮挡剔除。在从前往后遍历树时，每个节点应用硬件遮挡查询，若包围体光栅化后没有片元通过深度测试，则跳过孩子节点或它包含的部分场景。   然而同步导致发起查询和结果可用间有很大延迟，文献[20]利用时间相关性跳过前一帧可见的内部节点来减少查询命令，为叶子节点发起查询并绘制场景、在广度优先遍历树的同时轮询最老查询的结果来补偿延迟。进一步多个节点的查询可被合并，以减少图形管线的状态切换。   软件遮挡查询[21]在CPU上光栅化包围体来决定是否向GPU提交绘制命令，能够大大减少两者的同步开销但受限于小规模场景。这些方法侧重解决重绘（overdraw）问题，对每个像素多片元的情况不适用。文献[22]从前往后将叶子节点的包围体光栅化，构造光线投射的深度区间以跳过空隙，减少了状态切换但只适用于体数据。   本文使用光栅化的包围体构造逐像素桶列表，桶排序丢弃包围体外的片元以实现布尔求交。据此将软件遮挡查询应用到多片元的情况，构造场景块的深度直方图，通过减少同步命令有效地降低了同步开销。 3  两阶段空间剖分的多片元效果绘制   我们使用八叉树将大规模场景剖分，使得每个叶子节点包含的部分场景（块）能够从前往后逐个加载。然后对每一部分从前往后应用深度剥离和布尔求交，在两个不同的粒度上都满足可见性顺序。根据每个场景块的最大深度复杂度迭代相应次数，从而局部适应场景的空间复杂度。整个处理流程如图1所示，总体上分成物体和屏幕两个阶段。 物体空间近似剖分屏幕空间精确剖分场景块深度直方图类体素八叉树八叉树网格光栅化图1 两阶段八叉树剖分的绘制流程 论文在线出版号  No.31  周果等：面向大规模场景的多片元效果高效绘制  5 本节安排如下，首先3.1节描述了根据场景块的可见性顺序深度剥离的方法，其次3.2节给出使用八叉树网格布尔求交的方法，最后3.3节介绍如何构造场景块的深度直方图和利用它来避免硬件遮挡查询。 3.1 按叶子节点的可见性顺序深度剥离   八叉树剖分过程与稀疏体素八叉树[23]类似，采用由莫顿（Morton）码给出的深度优先后根序方式构建。但在自底向上回溯创建内部节点、给指针赋值前，先自顶向下递归使用分离轴定理（separating axis theorem）将面片与孩子节点的（空间）立方体求交。   在递归过程中面片逐渐被分配到各个立方体，直至其中的面片数量小于给定的阈值，从而保证叶子节点的大小能够满足显存限制。在回溯过程中先创建每个节点的孩子节点，保证它们能被连续存储，从而存储偏移量来减少指针占用空间，而创建好的子树可被立即写入磁盘，以降低内存峰值。   最终所有叶子节点就构成了场景的近似剖分，它们对应的立方体就组成了八叉树网格。整个过程只需为树的每层提供长度为八的队列来记录未完成的节点，故其空间复杂度为树的最大深度。 (-,-) (-,+)(+,-) (+,+)xy0 12 3O图2 莫顿码顺序的孩子节点   根据视点位置从前往后遍历八叉树，就能获得透视投影下叶子节点和相应场景块的可见性排序。下面用四叉树来描述这个过程，它可被直接扩展到八叉树的情况。由于莫顿码定义了空间填充曲线，每个节点的四个孩子按如图2所示莫顿顺序存储，每个孩子节点对应一个象限。   给定二维平面中节点正方形中心o到视点v的向量v - o，由它各个分量的符号能够确定v所在的象限。在每个象限构造查找表，能够定义从前往后访问孩子节点的顺序  ( , ) (0,1, 2, 3)( , ) (1, 3, 0, 2)( , ) (2, 0, 3,1)( , ) (3, 2,1, 0)---++-++    (1) 这里首先访问与v同一象限的孩子节点，其次访问与它共边的孩子节点，最后访问与它共点的孩子节点。从(1)可以看到当v和第零个孩子节点在同一象限时，四个孩子节点的访问顺序正好符合莫顿码。   对于八叉树的情况，需要首先访问与v同一卦限的孩子节点，然后依次访问与它共面、共边和共点的其他孩子节点。如果采用类似[17]的体元投影法确定叶子节点的可见性顺序，就需要为每两个共面的八叉树网格单元（即叶子节点的立方体）定义偏序（遮挡）关系，然后为生成的有向图应用拓扑排序获得全序关系。这种方法无法保证在有环的情况下有正确结果，且需要遍历所有网格单元的共享面来创建和存储有向图。  图3 按近似剖分绘制的错误结果    在使用查找表给出的顺序深度优先遍历树时，如果直接对每个叶子应用深度剥离并混合，不能得到正确的绘制结果，如图3所示光标指向的位置。这是由于建树时部分面片被多个网格单元共享，导致它们被重复绘制。将共享的面片相对单元的边界进行细分是一个直接的解决方式，但6  计  算  机  学  报  2017年 这会引起额外的存储开销，需要记录新的顶点位置、颜色和纹理坐标等属性。本文进一步在屏幕空间通过布尔求交，丢弃重复的片元来实现精确剖分。 3.2 八叉树网格的布尔求交 立方体光栅化后每个像素由前、后面生成两个片元，它们逐像素地定义了深度区间（即桶），给出了立方体内部的深度范围。如图4所示输入面片产生的片元在比较深度后，通过保留范围内的片元就实现了它和立方体的布尔求交。 将每个叶子节点的立方体和它包含的场景在屏幕空间进行布尔求交就能实现精确剖分。对于存在可见性顺序的多个立方体，一个片元就需要考察多个桶。在从前往后遍历八叉树绘制每帧时，给定逐像素桶列表01 ( , ) dd = d，将这个方法依次应用到每个叶子节点的过程如下： 1.  绘制覆盖全屏幕的矩形，令(1, 0) = d表示区间为空； 2.  开启背面剔除绘制立方体，记录片元深度到0d得到起始深度； 3.  开启正面剔除绘制立方体，记录片元深度到1d得到终止深度； 4.  对包含的面片应用深度剥离，每次迭代丢弃深度在01 ( , ] dd外的片元。 由于d在图形管线上采用非一致（incoherent）的存储访问方式，前三步每一步之后都需要插入存储屏障（barrier），保证d被顺序写入和在执行下一步前被更新完成、被所有线程可见。对于大规模场景叶子节点很多的情况，这种方式不仅引入了很大的同步开销，而且引起图形管线状态频繁变化故效率很低。  图1 八叉树网格与三角网格布尔求交结果   为了一次性记录多个叶子节点的立方体来减少管线状态变化，通过延长逐像素桶列表以使它最多能包含L个桶有  01 ( , , , )Ld d d = d K    (2) 此时立方体边界上的面片可能覆盖不同节点生成的桶，抵达的片元利用桶排序找到从属的叶子节点。为了区分不同叶子节点对相同桶贡献的片元，分配逐像素序号列表  0 1 1( , , , )Ln n n-= n K    (3) 来记录每个桶从属的叶子节点的序号。给定逐像素桶计数器l，对叶子节点应用深度剥离的过程如下： 视点图像立方体图4 预先光栅化立方体构造逐像素桶列表 论文在线出版号  No.31  周果等：面向大规模场景的多片元效果高效绘制  7 1.  绘制覆盖全屏幕的矩形，令0 l =表示桶列表为空而令00 d =表示近裁剪平面； 2.  开启正面剔除绘制L个叶子节点的立方体，每绘制一个需首先将叶子节点序号记录到ln，然后令1 ll=+，最后将片元深度记录到ld； 3.  依次对这L个叶子节点包含的面片应用深度剥离，每次迭代从头到尾遍历d中所有桶，找到片元从属的桶1( , ]ii dd+。若片元从属的叶子节点序号不等于in则丢弃； 4.  绘制覆盖全屏幕的矩形，令0 ldd=将终止深度作为起始深度后令0 l =。 这里通过递增桶计数器保证d中元素以升序排列。其中第一步只执行一次，遍历树每得到L个叶子节点执行后面三步。第二步每绘制一个立方体和第四步都需要插入存储屏障保证数组更新完成。第三步通过保证叶子节点包含的面片和桶的序号一致，实现了八叉树网格布尔求交。第四步将已访问叶子节点的终止深度提前，作为剥取后续叶子节点的起始深度。 图5展示了距离视点最近的一个叶子节点的求交结果，立方体体外部的片元以较暗的颜色显示（见光标指向）而每个像素的1d以灰色呈现。 0 12 345 67 8109图2 访问前四个叶子节点的情况 通过利用八叉树网格光栅化后的形式构造深度桶，避免了在GPU上进行低效的树的遍历。图6以四叉树类比展示了当4 L=时，两个像素都有三个桶的情况。这里四叉树采用前面提出的方式剖分，直到每个叶子仅包含两个面片为止。 3.3 使用深度直方图避免硬件遮挡查询 虽然可按逐像素列表的长度L访问叶子节点，每次处理多个立方体来减少图形管线状态变化，但是逐像素列表利用率低，仍导致迭代次数多。图7展示了当4 L=时，遍历4、5、6和7号四个叶子时两个像素的情况。此时d并没有被充分利用，因为这种方法只考虑了L个立方体在屏幕空间的二维投影相互重叠的最坏情况。虽然使用视景体剔除可能跳过部分叶子节点，但仍需要一次迭代来处理9号叶子节点。   在透视投影下立方体的最大重叠次数没有解析结果，这里根据叶子节点的立方体遮挡关系，确定它们在屏幕空间的最大深度复杂度，从而一次性访问尽可能多的叶子节点。一个直接的方法是借鉴文献[17]中根据视点位置合并部件的思想，即部件的包围体投影到屏幕空间，然后将凸多边形求交。但需要额外维护相交区域和相交次数，这就要将所有立方体的凸多边形投影求交，实现复杂且难以并行化。 8  计  算  机  学  报  2017年 0 12 345 67 8109图3 访问紧接的四个叶子节点的情况   本文使用光栅化构造深度直方图和软件遮挡查询来解决这个问题。读取逐像素桶计数器l记录的桶数量，然后使用原子操作或并行约减（reduce）操作获得八叉树网格中已访问单元的深度maxl（即所有像素l的最大值），根据它来确定后续的绘制命令。 按可见性顺序光栅化每个立方体后，可以直接使用硬件遮挡查询判断是否有像素l等于L。但是这需要图形管线处理完之前的绘制命令、处理查询命令和向CPU返回结果三个阶段，会引入很大的同步开销，导致CPU挂起和GPU饥饿。因此在光栅化立方体时，从第L个叶子节点开始进行查询，决定是否继续光栅化立方体。 每个立方体在被视景体剔除后、提交给GPU前，将它在CPU上光栅化来直接查询得到maxl，然后继续处理紧接的maxLl-个叶子节点的立方体。重复这个过程直到maxl为L为止。如图8所示右下角和右上角的节点为空，故它们对应的网格单元不会被光栅化，此时9号叶子节点在软件遮挡查询后也被处理而不需要额外进行迭代。 0 12 345 67 8109图4 改进的访问方式 表1 场景属性和绘制每帧耗时（毫秒）比较 论文在线出版号  No.31  周果等：面向大规模场景的多片元效果高效绘制  9 软件遮挡查询的流程与文献[21]类似，每个面片被模型、视点和投影变化后，计算它对像素的覆盖（coverage）情况：首先进行视景体剔除、裁剪和透视除法；其次计算每个面片的二维投影，找到覆盖的像素贴片（tile）；然后多个线程依次拾取有面片覆盖的贴片，判断其中每个像素中心是否被覆盖，相应地将逐像素计数器递增；最后执行操作atomicMax或reduce直接查询结果得到最大覆盖次数。其中每个线程使用单指令多数据操作进一步加速计算。 这里我们并不关心片元的深度等信息，因此不需要对图元顶点的属性应用线程插值。对于一个被变换到屏幕空间的面片，每个像素中心判断相对于各个边的位置，进而确定是否在面片的二维投影内 部。传统的遮挡查询基于深度缓存，只关心距离视点最近的片元。本文将这个概念针对多片元的情况进行引申，采用类似模板缓存的思想获得面片光栅化后的最大深度复杂度。 虽然使用软件遮挡查询尽可能减少了图形管线状态变化，但是在把每个立方体提交给GPU后仍需要插入存储屏障防止读写冲突。然而现有图形管线只在片元着色器后同步，使得逐像素片元顺序符合图元提交顺序后执行逐像素操作。 本文使用硬件原子操作实现了片元着色器临界区[5]，插入延迟以保护每个片元在逐像素桶列表上的更新操作，保证完成后才继续处理下一个立方体产生的片元。这使得多个立方体在某些情况（比如在屏幕空间不重叠）下能被并行地记录，避免存储屏障来提升效率。这里需要分配逐像素标志量m作为互斥锁。虽然新出现的图形扩展能原生支持，但目前只有NVIDIA的第二代麦克斯韦和后续架构实现（例如ARB_fragment_shader_interlock）。 5 10 15 20 25 30 35 40 4500.511.522.533.54场景块序号最大深度复杂度   面片总数  最大深度  面片上限  深度剥离    逐块剥离  块直方图  两者结合 TEAPOT  2464  6  256  16.70  33.40 (-0.50) 16.70 (0.0) 16.70 (0.0) DRAGON  871306  10  258048  33.40  33.40 (0.0) 28.91 (0.16) 24.19 (0.38) BUDDHA  1087304  12  258048  50.10  37.57 (0.33) 41.32 (0.21) 29.96 (0.67) CITY  2339137  52  258048  233.80  209.41 (0.10) 225.58 (0.04) 123.53 (0.89) HAIRBALL  2880000  194  258048  1469.61  669.60 (1.19) 1454.24 (0.01) 477.24 (2.08) POWERPLANT 11891501  354  258048  7882.47  2298.58 (2.43) 13093.36 (-0.40) 1262.83 (5.24) MANIX  602405  82  64512  205.14  183.73 (0.09) 208.39 (-0.02) 116.92 (0.75) CENOVIX  517013  64  64512  158.83  168.55 (-0.06) 163.81 (-0.03) 124.02 (0.28) VIX  554158  42  64512  82.45  108.69 (-0.24) 83.67 (-0.01) 70.12 (0.18) 10  计  算  机  学  报  2017年 图5 叶子节点的深度直方图 类似地该方法被用来为所有叶子节点构造深度直方图，得到各个场景块的最大深度复杂度。图9展示了构建直方图的结果，其中横坐标为叶子节点的序号。显然只有少部分最大深度较高，利用这种稀疏性在物体空间进行剖分，使得局部最大深度较高时，减少读取和光栅化场景的其他部分。 这个过程可在遍历树时进行，在剥取当前叶子节点提交绘制命令后，将下一个叶子节点光栅化并进行软件遮挡查询，从而直接得到它所需的剥取次数。这允许查询和绘制的时间发生重叠，就进一步提高了CPU和GPU的利用率。 4  实现和结果 我们使用OpenGL  4.5和C++实现了提出的方法，八叉树剖分和逐块遍历代码见GitHub1，使用了GLM库提供的向量、矩阵数据类型。逐像素数据l、m、d和n使用视口大小的无符号整型图像（uimage2D）或它的数组形式（uimage2DArray）存储，其中对于数组令16 L=，浮点数以二进制形式直接存储。使用顶点数组对象（vertex  array object）存储单位立方体3[ 1,1] -，每个叶子节点的立方体用相对它的变换矩阵表示，其中的放缩和平                                                                 1  https://git.io/vXwQV 图10 本文方法的绘制结果 图11 场景DRAGON漫游时每帧耗时（毫秒）比较 论文在线出版号  No.31  周果等：面向大规模场景的多片元效果高效绘制  11 移使用四维向量压缩存储后上传到顶点着色器。 绘制每一帧时迭代多次遍历八叉树：首先每次使用软件遮挡查询访问尽可能多的叶子节点，其次将它们的立方体提交构建桶，最后构建叶子节点的深度直方图按每块场景的最大深度剥取相应次数。 4.1 实验设置 通过绘制透明效果[2]来验证本文提出的方法，这需要每个像素的所有片元按深度顺序从前往后计算混合方程  dst dst src src dstdst src dst()(1 )C A A C CA A A=+=-    (4) 这里( )dst dst, CA给出了帧缓存中记录的颜色和不透明度，其中dstA初值为1而其他为0，而输入片元的颜色和不透明度为( )s src rc, CA。在混合剥取叶子节点得到的每层时，仅光栅化相应立方体的背面而只读取局部区域。这样就避免混合整个纹理而节省了访存带宽。 在同样每次剥取一层的前提下，本文方法（表1最后一列）与经典的深度剥离算法（表1第五列）比较。当然由于每块场景的最大深度已知，每次剥取多层的方法也可以直接应用。 为了单独评价本文提出的逐块深度剥离和深度直方图的作用，我们又分别实现了在分块剥取时使用硬件遮挡查询（表1第六列逐块深度剥离），和整个场景作为一块应用原子操作获得最大深度和硬件遮挡查询（表1第七列块深度直方图）的情况。实验在微机上进行，配置为Intel  Q9550  2.83GHz的CPU，4GB内存和驱动版本为359.00的NVIDIA  GTS  450显卡（费米架构）。 这里选取了TEAPOT、DRAGON、BUDDHA三个常规场景，CITY、HAIRBALL、POWERPLANT三个大规模场景以及MANIX、CENOVIX、VIX三个遮挡复杂场景进行测试。其中最后三个场景使用OsiriX医学图像库集提供的DICOM体数据得到，平滑滤波后从外向内提取八个等值面并赋予了不同的颜色。 图10 展示了它们被放缩平移到单位围盒中后进行透明效果的绘制，前六个场景的不透明度为0.5而后三个场景的不透明度为0.2。所有绘制的图像分辨率为640*480，并以棋盘格作为背景。我们使用NVIDIA Nsight 5.0度量绘制每帧的平均耗时（单位为毫秒），这里不包括场景被读取到内存和被上传到显存所花费的时间。表1中括号中的数值给出了各个方法相对于深度剥离的加速比，即深度剥离耗时减去本文方法耗时后再除以后者。 图12 场景BUDDHA漫游时每帧耗时（毫秒）比较 图13 场景CENOVIX漫游时每帧耗时（毫秒）比较 12  计  算  机  学  报  2017年 4.2 绘制效率讨论 由实验结果可以得知，对于小规模的TEAPOT本文方法不会引入较大的开销，而对于其他场景特别是大规模场景，本文方法的绘制效率有显著提升。特别是对CITY和POWERPLANT场景，分离的物体（比如楼体）邻接引入了非流形几何（比如悬点），使用凸多面体剖分需要额外维护场景中的物体信息以逐个处理。而MANIX等场景更是包含了大量细微的形状，会剖分为过量的凸多面体。这里使用本文方法可以直接剖分并绘制，不需要做任何特殊处理。 对于TEAPOT场景仅使用逐块深度剥离的情况（表1第五列），每块包含的面片数量太少故反而引入了过多的绘制调用开销。对于面片分布密集的场景HAIRBALL和POWERPLANT，仅使用块深度直方图的方法没有明显改进或出现严重倒退（表1第七列）。 我们通过性能分析发现，大量的时间被消耗在图像纹理操作上。此时每个像素只有一个深度桶，故在计算叶子节点的深度直方图时，对应了非常多的片元，这导致在使用原子操作时发生严重碰撞。由于每个GPU线程都只能串行累加，此时构建直方图的开销比硬件遮挡查询本身还要大。虽然八叉树剖分使得每个像素拥有多个桶，一定程度上缓解了这个问题，但是这个代价仍然削弱了剖分带来的好处。所幸的是NVIDIA后续推出了开普勒和麦克斯韦架构，大大改进了原子操作的性能。 此外使用约减操作能避免多个线程碰撞后串行化的缺陷，但这需要分配额外的存储记录中间结果。通过使用构建深度直方图和软件遮挡查询，就能够直接根据结果提交相应的绘制命令，减小同步开销而显著地提高了绘制效率。 4.3 剖分结果分析 对于BUDDHA场景，错误！未找到引用源。给出了剖分后每块场景的情况。将每块的面片数量乘以它的最大深度，就能得到剥取此块所读取的面片数量。 表2 剖分BUDDHA场景的结果 面片数量  最大深度 91511  5 184016  8 150019  8 48119  5 155098  7 132071  6 158029  6 178041  8 图14 场景MANIX漫游时每帧耗时（毫秒）比较 图15 场景VIX漫游时每帧耗时（毫秒）比较 论文在线出版号  No.31  周果等：面向大规模场景的多片元效果高效绘制  13 故所有块累积的面片数量为7621044，再加上构建块的深度直方图时读取整个场景的面片数量1087304，这就显著小于使用经典深度剥离需要读取13047648个面片（表1的BUDDHA所在行第二列乘以第三列）的情况。对于这类面片分布稀疏的场景，本文能充分发挥出读取数据总量较小的优势来提高绘制效率。 随着视点变化每个场景块的最大深度复杂度发生变化，相应地块的深度直方图发生变化，进而会影响绘制每帧时的效率。图11、图12、图13、图14 和图15 展示了漫游相应场景时每帧的耗时（毫秒）变化，比较了完全剥取时的深度剥离与本文基于八叉树空间剖分（即结合逐块剥离与块直方图两者）的方法。可以观察到在同样每次剥取一层的情况下，两种方法都受整个场景的最大深度复杂度影响故大体趋势接近，但本文方法稳定地提高了绘制效率。 进一步我们使用BUDDHA场景考察了不同面片上限有不同剖分结果对绘制效率的影响。图16给出了采取不同大小的面片上限来绘制每一帧的耗时（单位为毫秒）。  图16 不同面片上限对每帧耗时（毫秒）的影响   这里考察了从4096到51200，以4096为步进的面片数量上限。实验结果表明数量足够大时，本文方法能够显著提高绘制效率。理论上面片数量上限越小时，每块的最大深度复杂度减小，但此时每块的绘制时间较短、绘制调用开销较大故降低了效率。而面片数量上限越大时，每块的最大深度复杂度增大，构建直方图和软件遮挡查询开销增大，但剥取每块时的同步开销被大大减少，反而较好地进行了弥补。 4.4 存储消耗 在显存消耗方面，除了存储所有叶子节点的面片的数据之外，还要存储逐像素数据l、m、d和n。当16 L=时对于640*480分辨率的视口，总的显存消耗只有1200*35KB，这是本文方法主要的显存开销。在内存消耗方面，只需要分配视口大小的字节数组。对于大部分场景此时有较好的性能表现，故本文方法所需的存储是有界的。 4.5 方法缺陷 虽然本文的剖分过程能被并行化，但远不能满足动态场景的要求。对于局部发生变化的场景，可以检测受到影响的叶子节点，然后重新剖分并更新块的可见性顺序。对于特定的动画序列，可以把时间看作一个维度，然后在四维空间进行剖分。此外虽然八叉树便于剖分大规模场景，但它不能很好地适应物体的形状，故基于表面积启发的k维树有希望能获得更好的剖分结果。这些我们将在未来的工作中进一步尝试。 5  总结   本文利用八叉树剖分来提高大规模场景多片元效果的绘制效率。首先提出了一种按八叉树叶子节点的可见性顺序进行深度剥离，其次通过光栅化对应八叉树网格，在屏幕空间实现了三角网格和八叉树网格的布尔求交操作，得到了准确的剖分结果，最后根据叶子节点的深度直方图应用深度剥离避免了硬件遮挡查询。由于发掘了大规模场景面片分布的稀疏性，我们的方法能显著地减少读取的面片数量，从而提高了绘制的效率。本文方法不需要面片的邻接信息，不仅节省了存储空间，还能够直接处理非流形网格。   由于八叉树对空间采用中间划分的方式，因此它不能较好地适应场景的实际形状。下一步将尝试本文方法与文献[17]的凸多面体剖分法结合以提高效率。实际上本文提出的八叉树网格布尔求交法可以直接用来解决他们的工作中的环路遮挡问题，避免对部件进行细分。另一方面，如何自动地为叶子节点选取合适的面片数量上限以获得最佳性能仍是一个开放性的问题。 致  谢  我们感谢cgtrader网站的Mostusk免费提供CITY场景，感谢Morgan McGuire提供其他场景。  14  计  算  机  学  报  2017年    参 考 文 献 [1] Bavoil L, Callahan S  P, Lefohn A,  et  al. Multi-fragment  effects  on  the GPU using the k-buffer//Proceedings of the Symposium on Interactive 3D Graphics and Games. New York, USA, 2007: 97–104 [2] Bavoil  L, Myers  K. Order  independent  transparency  with  dual  depth peeling. Santa Clara, USA: Nvidia Corperation, 2008 [3] Yang  J  C, Hensley  J,  Grun  H,  et  al.  Real-time  concurrent  linked  list construction  on  the  GPU.  Computer  Graphics  Forum, 2010, 29(4): 1297–1304 [4] Liu F, Huang M  C, Liu X  H,  et  al. FreePipe:  a  programmable parallel rendering  architecture  for  efficient  multi-fragment effects//Proceedings  of  the  Symposium  on  Interactive  3D  Graphics Games. Washington , USA, 2010: 75–82 [5]  Vasilakis  A  A,  Papaioannou  G,  Fudos  I. k+-buffer:  An  Efficient, Memory-Friendly  and  Dynamic  k-buffer  Framework.  IEEE Transactions  on  Visualization  and  Computer  Graphics,  2015,  21(6): 688-700 [6]  Salvi  M,  Vaidyanathan K.  Multi-layer  alpha  blending//Proceedings  of the  Symposium  on  Interactive  3D  Graphics  and  Games.  San Francisco, USA, 2014: 151-158 [7] Sintorn E, Assarsson U. Hair self shadowing and transparency depth ordering using occupancy maps//Proceedings of the Symposium on Interactive 3D Graphics and Games. San Francisco, USA, 2009: 67-74 [8] Salvi M, Montgomery J, Lefohn A. Adaptive transparency//Proceedings of  the  Symposium  on  High  Performance  Graphics.  Vancouver, Canada, 2011: 119–126 [9]  Maule  M,  Comba  J,  Torchelsen  R,  et  al.  Hybrid transparency//Proceedings  of  the  Symposium  on  Interactive  3D Graphics Games. Orlando, USA, 2013: 103–118 [10] Pascal  G, Cyril  D, Jean-Eudes  M,  et  al.  Boundary-Aware  Extinction Mapping. Computer   Graphics Forum, 2013, 32(7): 305-314 [11] Enderton E, Sintorn E, Shirley P, et al. Stochastic Transparency. IEEE Transactions  on  Visualization  and  Computer  Graphics,  2011, 17(8): 1036-1047 [12]  Wyman  C.  Exploring  and  Expanding  the  Continuum  of  OIT Algorithms//Proceedings  of  the  Symposium  on  High Performance Graphics. Saarbrücken, Germany, 2016: 1–11 [13] Everitt  C. Interactive  Order-Independent  Transparency.  Santa  Clara, USA: Nvidia Corporation, 2001 [14] Liu F, Huang M C, Liu X  H, et  al.  Efficient depth peeling  via bucket sort//Proceedings  of  the  Symposium  on  High  Performance Graphics. Saarbrücken, Germany, 2009: 51–57 [15] Sintorn E, Assarsson U. Real-time approximate sorting for self shadowing and transparency in hair rendering//Proceedings of the Symposium on Interactive 3D Graphics and Games. San Francisco, USA, 2008: 157-162 [16]  Eisemann  E,  Decoret  X.  Fast  Scene  Voxelization  and Applications//Proceedings  of  the  Symposium  on  Interactive 3D Graphics and Games. San Francisco, USA, 2006: 71-78 [17] Wang  W, Xie  G. Memory-efficient  single-pass  GPU  rendering  of multifragment  effects. IEEE  Transactions  on  Visualization  and Computer Graphics, 2013, 19(8): 1307-1316 [18]  Maximo  A,  Marroquim R,  Farias R.  Hardware-Assisted  Projected Tetrahedra. Computer Graphics Forum, 2010, 29(3): 903-912 [19] Williams P. Visibility-Order Meshed Polyhedra. ACM Transactions on Graphics, 1992, 11(2): 103-126 [20] Mattausch O, Bittner J, Jaspe E, et al. CHC+RT: Coherent Hierarchical Culling  for  Ray  Tracing. Computer  Graphics  Forum,  2015, 34(2): 537-548 [21] Hasselgren  J,  Andersson  M, Akenine-Möller  T. Masked  Software Occlusion  Culling//Proceedings  of  the  Symposium  on  High Performance Graphics. Saarbrücken, Germany, 2016: 51–57 [22] Liu B, Clapworthy G, Dong F, et al. Octree Rasterization: Accelerating High-Quality  Out-of-Core  GPU  Volume  Rendering. IEEE Transactions  on  Visalization  Computer  Graphics,  2013,  19(10): 1732-1745 [23] Baert  J,  Lagae  A,  Dutré  P. Out-of-Core  Construction  of  Sparse  Voxel Octrees. Computer Graphics Forum, 2014, 33(6): 220-227                  论文在线出版号  No.31  周果等：面向大规模场景的多片元效果高效绘制  15    ZHOU  Guo,  born  in  1987,   Ph.D.  candidate.His  research interests focus on computer graphics. ZHU Deng-Ming, born in 1973, Ph.D.,associate professor. His research interests focus on fluid simulation. WANG  Zhao-Qi,  born  in  1966,  Ph.D.,professor,Ph.D. supervisor.  His  main  research  interests  include  virtual  reality and intelligent human-computer interaction techniques.      Background The GPU converts the triangle mesh into fragments using rasterization.  The  multi-fragment  effects  such  as  the  real-time transparency and the boolean operation over constructive solid geometry  require  multiple  fragments  per  pixel  to  be depth-sorted.  To  implement  it  on  the  GPU  using  bounded memory, multiple passes over the scene are necessary to visit a limited number of fragments each time. Since the whole scene geometry  is  rendered  but  only  a  portion  produces  useful fragments in each pass, much memory bandwidth is wasted on retrieving all the scene data. We present  a new  approach to reduce the total amount of data  being  required  to  render  the  multi-fragment  effects.  By exploiting  the  sparsity  of  distributed  faces,  we  are  able  to decompose the scene into regular parts. Then each part  can be processed with respect to its maximum depth, thus adapting to the spatially varying depth complexity. The group has been working on virtual reality for over 20 years.  They  have  published  many  papers  on  journals  such  as the  Journal  of  System  Simulation,  Chinese  Journal  of Computers, Journal  of  Computer-Aided  Design  and  Computer Graphics, and on conferences like China CAD&CG, Computer Animation  and  Social  Agents,  Computer  Graphics International.