（精密仪器及机械专业论文）基于CUDA的三角形并行处理.pdf

摘要 摘要 虚拟现实、游戏等应用通常使用三角形作为渲染图元。几何着色器的引入 使得当前图形流水线支持三角形图元的并行处理。但是，数据必须经过整个图形 流水线才能得到最终运算结果。同时，基于图形a p i 的算法实现也不利于运算 结果的重用。本文提出基于c u d a 的三角形并行处理，本文的主要工作为以下两 个部分： 1 三角形网格预处理算法 使用c u d a 实现三角形并行处理的瓶颈是顶点数据的读取。基于当前g p u 硬 件特性，数据在合并访问( c o a l e s c e da c c e s s ) 时有最高效率。本文针对g p u 内 存模型提出了一个两步骤的三角形网格预处理算法：首先将三角形网格划分为 大小一致的三角形组( c l u s t e r ) 。然后基于分组结果将顶点缓存( v e r t e xb u f f e r ) 重新排序。 预处理算法使得在运行时能够以合并读取的方式将三角形组的所有顶点一 齐读入共享内存( s h a r e dm e m o r y ) ，随后的顶点读取操作便可以在高速的共享内 存中执行。 2 优化实时渲染算法 基于高效的顶点读取方法实现了背向面剔除及边缘边提取算法，并将c u d a 运算的结果与图形流水线结合以优化实时渲染应用。实验数据显示，该方法对 基于三角形图元的实时渲染应用有显著的加速效果。 关键词：c u d a 并行算法三角形网格实时渲染 a b s t r a c t v i r t u a lr e a l i t ya n dg a m ea p p l i c a t i o n sn o r m a l l yu s et r i a n g l e sa st h e i rr e n d e r i n g p r i m i t i v e t h ec u r r e n tg r a p h i c sp i p e l i n ei n t r o d u c e st h eg e o m e t r ys h a d e r t os u p p o r t p a r a l l e lt r i a n g l ep r o c e s s i n g h o w e v e r , d a t ah a st of l o wt h r o u g ht h e e n t i r ep i p e l i n e b e f o r et h ef i n a lr e s u l t sa r ea c q u i r e d ；b e s i d e s ，u s i n gg r a p h i c s a p it oi m p l e m e n t g r a p h i c sa l g o r i t h m si si n e f f i c i e n tf o rr e u s i n gt h ec o m p u t a t i o n r e s u l t s w ep r o p o s et o p r o c e s st r i a n g l e si np a r a l l e lw i t hc u d a 。t h e m a i nc o n t r i b u t i o n sa r e ： 1 ) ap r e p r o c e s s i n ga l g o r i t h mf o rt r i a n g l em e s h e s v e r t e xf e t c hi st h eb o t t l e n e c k w h e nu s i n gc u d at oi m p l e m e n tp a r a l l e lt r i a n g l ep r o c e s s i n g b a s e do nt h ec u r r e n t g p u ，sh a r d w a r ea r c h i t e c t u r e ，c o a l e s c e da c c e s si st h em o s t e f f i c i e n tw a yt or e a d w r i t e t h eg p um e m o r y t h i sp a p e rp r e s e n t sat w o - s t e pp r e p r o c e s s i n ga l g o r i t h ma c c o r d i n g t om ec u r r e n tg p um e m o r ym o d e l ：t h et r i a n g l em e s h i sf i r s ts e g m e n t e di n t ot r i a n g l e c l u s t e r so fe q u a ls i z e ，a n dt h e nt h e v e r t e xb u f f e ri sr e o r d e r e db a s e do nt h e s e g m e n t a t i o nr e s u l t s a tt h en m t i m e ，t r i a n g l ec l u s t e rv e r t i c e s a r er e a da l t o g e t h e ri n t ot h es h a r e d 1 3 r l e m o z ，a sar e s u l t ，t h ef o l l o w i n gv e r t e xf e t c ho p e r a t i o n sc a nb ep e r f o r m e di nt h e f a s ts h a r e dm e m o r y 2 ) o p t i m i z i n gr e a l t i m er e n d e r i n gi m p l e m e n t a t i o n s w ei m p l e m e n tb a c k - f a c e e u l l i n ga n ds i l h o u e t t ee x t r a c t i o nw i t ho u rv e r t e xf e t c he f f e c t i v ea p p r o a c h e sa n du s e t h er e s u l t s 谢t ht h eg r a p h i c sp i p e l i n et oo p t i m i z er e a l - t i m er e n d e r i n gi m p l e m e n t a t i o n s t h ee x p e r i m e n tr e s u l t ss h o ws i g n i f i c a n ts p e e d u p sa c h i e v e db yi n t e g r a t i n g o u r b a n d w i d t he f f e c t i v ea p p r o a c h e sf o ra n yr e a l t i m er e n d e r i n ga l g o r i t h mi n v o l v i n g t r i a n g l e s k e yw o r d s ：c u d a b a s e dp a r a l l e la l g o r i t h m ，t r i a n g l em e s h ，r e a l t i m er e n d e d n g i i i 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成 果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写 过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确 的说明。 作者签名：血 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学拥 有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交 论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入中国学 位论文全文数据库等有关数据库进行检索，可以采用影印、缩印或扫描等复制 手段保存、汇编学位论文。本人提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 蟛忪开 口保密( - 年) 作者签名： 隘均 签字日期：迎! ! ：翌! 二! ， 导师签名： 签字日期： 第1 章序言 1 1 实时渲染图形流水线 第1 章序言 目前，虚拟现实、游戏等实时渲染应用通常使用基于实时渲染图形流水线( 以 下简称为流水线或图形流水线) 架构的图形a p i 实现。当前最常使用的图形a p i 系统为o p e n g l ( s e g a le ta 1 2 0 0 9 ) 和d i r e c t x ( b l y t h e 2 0 0 8 ) 。三角形图元是目前实 时渲染应用最常使用的图元类型。为了降低模型的存储开销和避免重复的顶点运 算，模型的三角形网格通常以顶点缓存( v e r t e xb u f f e r ) i l l 序号缓存( i n d e xb u f f e r ) 的 形式保存。因此，当前的g p u ( g r a p h i c sp r o c e s s i n gu n i t ) 硬件和流水线架构均是 以高效的三角形网格渲染为目标设计。支持更高级效果的实时渲染算法的不断提 出促进了g p u 硬件的发展，g p u 硬件架构的改进也促进了流水线的不断演进。 输入收集器 ( i n p u t - a s s e m b l e r ) 旦 顶点着色器 【v e r t e x s h a d e r ) 几何着色器 ( g e o m e t r y s h a d e r ) l 栅格器( r a s t e r i z e r ) l o _ 一 l _ - - - - - _ _ _ _ _ _ _ _ _ _ - _ _ _ _ _ _ _ _ - - - _ _ _ - _ 一 旦 ，。、 i像素着色器l l ( p i x e i - s h a d e r l l 1 - _ - - - - l o _ _ _ _ o o f 输出组合 il o u t p u t - m e r g e r ) 1 g p u 内存 ( 缓存、 纹理、 常量缓存 图1 1 当前图形流水线的结构简图 1 1 1 基于可编程着色器( p r o g r a m m a b les h a d e r ) 的图形流水线 早期g p u 硬件仅支持固定功能( f i x e d f u n c t i o n ) 的图形流水线。通过调用相应 的图形a p i 以设置顶点的坐标、颜色、纹理坐标，模型的空间变换矩阵，光源 及模型材质的光照参数，纹理的读取方式，颜色混合运算函数等相关参数，固定 第1 章序言 功能流水线能够支持有限的三维渲染效果。在支持更逼真渲染效果的高级图形算 法不断提出的同时，半导体制造工艺及g p u 硬件架构设计也在不断改进。当前 流水线( b l y t h e 2 0 0 8 ；s e g ne ta 1 2 0 0 9 ) 使用基于可编程着色器的架构通过着色器 编程结合固定功能硬件模块实现实时渲染算法。 图1 1 为当前流水线的结构简图。图形流水线可以分为可编程着色器和固定 功能硬件两大部分。可编程着色器部分通常包含项点、几何、像素等着色器单元。 通过使用着色器语言( s h a d i n gl a n g u a g e r o s tr je ta 1 2 0 0 9 ；m i c r o s o f tc o r p o r a t i o n 2 0 l o ) 编程可实现对顶点、图元、像素的自定义运算。基于三角形网格渲染的图 形流水线有相当部分工作是固定不变的，例如三角形的剪裁( c l i p ) 、栅格化 ( r a s t e r i z i n g ) ，三角形顶点参数的插值运算，深度缓存中数值的比较和更新等。这 类工作的共同点是控制参数较少且基于硬件的实现有绝对优势的性能表现。因 此，目前流水线仍然包含了部分实现固定功能的硬件单元。虽然固定功能部分无 法用编程的方式完全控制其工作行为，但可以通过图形a p i 对其功能参数进行 设置。 输入收集器( i n p ma s s e m b l e r ) 负责向流水线提供图元( 三角形、直线或点) 的顶 点数据。最近流水线中添加了包含相邻图元顶点信息的图元类型以支持一些高级 渲染算法。基于特别设计的硬件机制，输入收集器能以极高的效率攫取( f e t c h ) 顶 点数据。顶点着色器负责处理图元的顶点数据，典型的工作内容为空间变换，基 于顶点混合( v e r t e xb l e n d i n g ) 或蒙皮( m o r p h i n g ) 的动画计算( t o m a se ta 1 2 0 0 8 ； k a v a nle ta 1 2 0 0 7 ；k a v a nle ta 1 2 0 0 9 ) ，基于顶点的光照计算等。顶点着色器的输入 输出均为单个顶点并且无法删除顶点或访问其他顶点的数据。几何着色器( b l y t h e 2 0 0 8 ) 以整个图元为处理对象，新引入的图元类型能够支持相邻图元的顶点数据 访问。几何着色器能够输出可变数量的图元，甚至输出图元类型可以与输入图元 类型不同。另外，几何着色器的输入与输出必须保持一致的顺利。栅格器( r a s t e r i z e r ) 是固定功能单元，主要负责图元的剪裁与栅格化并决定如何调用像素着色器。像 素着色器负责像素对象的计算，其输入为经过栅格器对三角形内顶点数据插值运 算得到的像素信息，输出通常为像素的颜色、深度等数据。输出合并阶段 ( o u t p u t m e r g e r ) 是另一个主要的固定功能单元，主要负责将像素着色器的输出与 当前颜色缓存及深度模版缓存( d e p t h s t e n c i lb u f f e r ) 中的相应值进行比较和运算， 并生成最终显示于屏幕的像素颜色值。有一些多遍渲染算法使用输出合并阶段生 成中间数据并将其保存入纹理对象，运算结果并不显示在屏幕上。后续渲染步骤 通过绑定纹理对象访问之前的运算结果。 2 第1 章序言 112 统一着色器( u n i f i e d s h a d e r ) 架构 顶点着色器由于包含空间变换、动画等三维坐标的线性运算而对运算的精度 要求较高；像素着色器则需要频繁地访问纹理数据因而更加注重对g p u 内存的 读取能力。针对不同着色器单元的运算特性，传统g p u 硬件采用不同的单元设 计以分别支持顶点着色器与像素着色器。随着高级图形算法的不断提出，图元数 据变得越来越庞大，顶点计算也可能需要读取纹理数据而像素计算也可能包括高 精度要求的复杂数学运算。不同的图形渲染算法可能表现为是几何瓶颈 ( g e o m e t r y - b o u n d ) 的或是像素瓶颈( p i x e l - b o u n d ) 的。在采用不同的着色器硬件单元 的架构下权衡不同色器单元占据的硬件资源比例十分困难，同时这种架构也非常 不利于引入新的着色器单元( 例如几何着色器) 。针对上述限制，当前g p u 硬件 通常采用统一着色器架构( l i n d h o l me t a l 2 0 0 8 ；d o g g e t t2 0 0 5 ) 。 在统一着色器架构下硬件上不再区分不同的着色器单元。着色器单元以流处 理器( s 帆村np r o c e s s o r ) 酐j 集合的形式实现。集合内流处理器的数目决定了g p u 硬 件上并行计算的最小颗粒度。针对图形渲染算法的特性，每个流处理器组通常还 共享一定数量的特别运算单元以支持常见的数学计算( 例如正、余弦运算) 。纹理 存取单元的硬件开销很大，因此通常被多个流处理器集合共享。在统一着色器架 构下主要依赖硬件的调度机制来实现不同着色器单元间的负载平衡，因此对于不 同瓶颈特征的图形算法有更强的适应性。同时，在这种架构下简单地提高流处理 器集合的数量便可以实现硬件性能的提升。 圈1 2 统一着色器架构下的着色器单元实现 图l2 展示了当前统一着色器架构通常采用的硬件组织形式。8 个流处理器 单元“骶a i r ip r o c e s s o r ) 集台为一组，同时共享两个特殊功能单元( s p e c i a lf uu n i t ) 流处理器通常执行单、双时钟周期的指令，特殊功能单元通常执行多时钟周期的 指令。每一个流处理器组还包含了一个高速的共享内存机制( 详细叙述见第2 章) 第1 章序言 以存储频繁使用的数据和进行组内流处理器间的数据共享与同步。两个流处理器 组又进一步组合为一个整体并共享4 个纹理存取单元( t e x t u r ef e t c h ) 。g p u 硬件实 际运行时，两个流处理器组始终同步执行相同的指令。采用图1 2 中的统一着色 器结构的g p u 硬件上线程并行执行的最小颗粒度是1 6 。 1 2 g p u 硬件优化机制 如上节所述，当前g p u 硬件及流水线架构均是针对三角形网格的高效渲染 设计。图形渲染算法如果使用大规模的三角形网格且需要执行复杂的几何运算则 可能在几何运算阶段( 即顶点着色器或几何着色器阶段) 耗费绝大部分时间，这类 算法被称为是几何瓶颈的。当前g p u 硬件通过顶点缓存( v e r t e xc a c h e ) 硬件机制 ( h o p p e 1 9 9 9 ) 来避免重复的顶点计算以提高几何运算阶段效率。另一方面，如果 像素着色器需要执行大量的纹理读取或执行复杂的像素计算，则往往会在像素阶 段耗费绝大部分时间，这类算法被称为是像素瓶颈的。流水线使用深度缓存( d e p t h b u f f e r ) 进行像素的深度剔除并且最终仅绘制距离当前视点最近的像素。为了避免 不必要的对更远处像素的计算，当前g p u 硬件实现了提前深度剔除( e a r l y z c u l l i n g ；n v i d i ac o r p o r a t i o n 2 0 0 8 ；m o r e i ns 2 0 0 0 ) 硬件机制：若待计算像素的深度 值比其在深度缓存中的对应位置处深度值大，则可以直接剔除当前像素而不必进 行后续的像素着色器计算。如何充分利用这两种硬件优化机制( n v i d i a c o r p o r a t i o n 2 0 0 8 ) 是实时渲染领域非常重要的研究方向。 1 2 1顶点高速缓存( v e r t e xc a c h e ) 流水线绘制三角形网格时运算对象实际是由各三角形顶点组成的序列。该序 列是以三角形顶点在序号缓存中的顺序通过输入收集器读取输入至流水线。由于 三角形网格中顶点通常被多个三角形所有，顶点着色器阶段可能存在大量的重复 计算。顶点高速缓存的功能是保存一定数量的最近的顶点着色器运算结果，如果 当前需要计算的顶点已经保存在顶点高速缓存中，那么就不再需要执行顶点着色 器而可以直接使用顶点高速缓存中的结果。h o p p e 的工作( h o p p e 1 9 9 9 ) 证明一个 能够保存少量顶点运算结果的f i f o ( f i r s ti nf i r s to u t ) 缓存即可以获得接近最优的 顶点运算效率( c h o w 1 9 9 7 ) 。l i n 等人( l i na n dt h o m a s 2 0 0 6 ) 通过模拟在一个可控 的f i f o 顶点高速缓存硬件上的顶点序列生成过程进一步优化了序列的顶点局部 性( v e r t e x _ l o c a l i t y ) 。p e d r o 等人( p e d r oe ta 1 2 0 0 7 ) 采用将三角形以顶点的o n e r i n g 形式加入三角形序列以优化顶点局部性。上述两种方法均采用了贪婪算法的思想 设计算法来优化顶点高速缓存效率。s a n d e r 等( s a n d e re ta 1 2 0 0 9 ) 提出将l i n 等和 4 第1 章序言 p e d r o 等( l i na n dt o m a s 2 0 0 6 ；p e d r oc ta 1 2 0 0 7 ) 论文中方法推广至包含相邻顶点 的三角形图元( t r i a n g l ew i t ha d j a c e n c yp r i m i t i v e ，以下简称相邻三角形图元) 。 1 2 2 提前深度剔除( e a ri y - z0 u li i n g ) 理想状态下，三角形网格以相对当前视点的由近至远顺序绘制时提前深度剔 除机制有最优效率。实际应用中模型网格与视点均处于不断变化中，因此无法在 渲染前预先得知网格相对视点的远近关系。一种简单的方法是先在仅允许修改深 度缓存设置下绘制，然后再进行实际的渲染，这种方法对于场景稍微复杂的情形 便不再实用。目前主流的做法( n e h a be ta 1 2 0 0 6 ；p e d r oe ta 1 2 0 0 7 ) 是对网格分块后 再进行与视点无关的排序。p e d r o 等( p e d r oe ta 1 2 0 0 7 ) 还探讨了如何选取参数来平 衡顶点高速缓存和提前深度剔除两种优化机制。 1 3 c u d a 简介 c u d a ( c o m p u t eu n i f i e dd e v i c ea r c h i t e c t u r e n v i d i ac o r p o r a t i o n 2 0 0 9 ) 是 n v i d i a 公司推出的基于其g p u 硬件产品的通用计算平台。c u d a 采用c 语言 语法编程并添加了控制g p u 硬件并行特性的语句。由于能够对g p u 底层硬件特 性进行直接访问，使用c u d a 实现并行算法的效率远大于先前基于流水线及图 形a p i 的g p g p u 方法( o w e n se ta 1 2 0 0 7 ) 。c u d a 实现并行算法的优势主要来源 于其s i m t ( s i n g l e i n s t r u c t i o n ，m u l t i p l e t h r e a d ) 模型与共享内存机制( n i c k o l l se ta 1 2 0 0 8 ) ： 在s i m t 模型下，g p u 硬件同时维护大量的并行线程组，并行线程组通过 流处理器集合( 见1 1 2 节) 并行执行同一条指令。由于内存存取指令的时间开销 远大于算术运算指令，当某个并行线程组由于内存指令操作阻滞时，g p u 硬件 会自动保存当前并行线程组状态并切换至能够向下执行的并行线程组。因此，基 于c u d a 的并行算法实现获得高性能的关键之一是要保持有大量的并行线程组 来抵消内存指令的开销。 共享内存类似于c p u 上的c a c h e 机制，其访问速度接近于寄存器而远大于 g p u 内存( n v i d i ac o r p o r a t i o n 2 0 0 9 ) 。通过将频繁使用的数据读入共享内存中进 行访问可大大降低对g p u 内存的直接读取操作。另外，并行算法的运算结果在 最终输出前通常先以输出顺序保存在共享内存中，然后再以合并写的方式输出到 g p u 内存。 第1 章序言 1 3 1c u d a 与d ir e c t x 、o p e n g l 协同工作 基于统一着色器硬件架构，无论是c u d a 并行计算程序还是流水线着色器 程序都是基于相同的指令集并转化为硬件指令在流处理器组上并行执行。因此， c u d a 能够方便地与d i r e c t x 或o p e n g l 进行协同工作。由于流水线中栅格器部 分不具备可编程性，c u d a 并不能访问其功能。因此使用c u d a 与图形a p i 协 同工作局限于几何阶段运算，可以利用c u d a 的灵活性与高效性替代实现部分 顶点着色器或几何着色器功能。 1 4 基于g p u 的并行三角形处理 许多图形算法以网格中的三角形为处理对象，例如背向面剔除算法。当前视 点下网格中某三角面，若其法线向量与当前视线向量的点积值大于或等于零，则 该三角面为背向面。由于实际渲染时只需绘制朝向视点的部分，在渲染前施行背 向面剔除可大大降低输入收集器、几何处理阶段和栅格器的工作量。另外有一些 基于网格中边的图形算法也可以通过三角形图元或相邻三角形图元实现，例如基 于边缘边( s i l h o u e t t e ) l 拘技术图示绘$ 1 j ( t e c h n i c a li l l u s t r a t i o n g o o c he ta 1 19 9 9 ) 和反 走样线框绘制( b a e r e n t z e ne ta 1 2 0 0 6 ) 等。 50 - 、 4 1 一 2 、， ， 、， ， ， 、， 、， 、， 、， v 3v 图1 3 相邻三角形图元( t r i a n g l ew i t ha d j a c e n c yp r i m i t i v e ) 示意图 1 4 1基于几何着色器的并行三角形处理 几何着色器的引入使得当前流水线支持三角形相关图元类型的并行处理。几 何着色器的处理对象是整个图元，因此需要在着色器程序执行前准备好所有的顶 点数据。冗何着色器支持可变数量的图元输出甚至改变输出图元的类型。图元在 输出时必须保持与输入图元相同的顺序。以上特征极大限制了基于几何着色器的 渲染算法实现的效率( n v i d i ac o r p o r a t i o n 2 0 0 8 ) 。在当前g p u 硬件上，当输出为 6 第1 章序言 0 - 2 0 个4 字节数据对几何着色器有最高的效率，当输出为2 0 4 0 个4 字节数据时 效率便降为一半。由于几何着色器是图形流水线的中间步骤，使用其能够处理整 个图元的功能实现图形算法时图元必须经过整个流水线才能产生最终结果，并且 当前流水线缺乏对渲染结果重用的高效实现方法。因此，几何着色嚣通常并不适 合实现三角形相关图元类型的并行处理。 42 基于相邻三角形图元的改进算法 许多基于网格中三角形边的高级图形算法可以通过相邻三角形图元的遍历 操作实现，例如阴影体积算法( s h a d o w v o l u m ec r o w f c1 9 7 7 ；b r e n n a n c 2 0 0 2 ) 、 动态模糊算法( m o l i o nb l u r ；w 1 0 k ai v i ma n dz e l c z n i kr c1 9 9 6 ) 以及基于边缘边提 取的线条绘制算法( g o o c h 虬a l1 9 9 9 ) 等。基于几何着色器的实现除了有上文中拙 述的由于其流水线架构导致的限制外，还存在大量的重复计算。 围1 3 为相邻三角形图元的示意图。每个相邻三角形圈元由其中心三角形的 三个顶点( 图13 中的顶点0 、2 、4 ) 以及相邻三角形的三个顶点( 图13 中的顶点1 、 3 、5 1 组成。在这样的数据结构下，每个相邻三角形图元可以完成对4 个三角形 图元的处理。基于相邻边( b t y t h c2 0 0 8 ) 图元形式的边运算在相邻三角形图元中实 现后，与其相邻的相邻三角形图元便不再需要包含上述顶点。因此，基于相邻边 图元或三角形圈元的渲染算法均可以通过相邻三角形图元实现，并且可以进一步 设计厨格压缩算法以避免重复读取顶点数据和执行重复的顶点运算。 圈i 顶点疆盖( r e l - r e xc o v e r ) 步珥结果 s a n d e r 等( s a n d e rc t a l 2 0 0 9 ) 提出使用可缟程几何着色器并行处理相邻三角 形图元以实现网格中边与三角形的高效遍历处理。该文的主要工作是提出两步骤 的三角形网格压缩算法以使用尽可能少的相邻三角形图元包含网格中所有的边 与三角面。 算法的第一步骤是选取尽可能少数量的网格三角形以包含网格中所有的顶 第1 章序言 点。即图论中的顶点覆盖问题。网格中的顶点覆盖算法属于n p 完全问题，作者 基于相邻三角形图元提出使_ i ； j 随机) 厦近( s t o c h a s t i ca p p r o x i m a t i o ng r o s s oe ta l2 0 0 7 ) 算法求解。作者研究并计算拇出实现三角形网格顶点覆盖的三角形数目下限并将 计算结果与随机逼近算法的结果进行对比，实验数据表明该文中提出的算 圭能得 到非常接近最优解的顶点覆盖三角面。 由于需要具备处理网格中所有三角形的能力，算法第二步骤将该目标转化为 两个b i p a r t i t em a t c h i n g 问题的求解( h o p c r o rj ea n dk a r l ) r m1 9 7 3 ；r o t h b e r ge 1 9 8 5 ) 。通过第二步骤将所有未指定三角形( 图中白色三角形) 分配给合适的经由第 一步骤选取的顶点覆盖三角形( 图中蓝色- _ - 角r e ) 。图1 5 为剩余三角面分发步骤 示意图。红色线段表示将相应的未分发三角形指定至相邻的顶点覆盖三角形。 图1 5 剩余三角面分靛( f a c e a s s i g n m e a t ) 步骤示意图 经过上述两步骤算法，作者指出使用网格。p5 5 左右的三角形便能够覆盖所 有的网格顶点，并且与理论最优解相比仅多出3 左右的三角形。作者进一步提 出拓展现有的基于三角形图元序列的顶点局部性优化算法( l i na n dt o m a s2 0 0 6 ； p e d r oe ta l2 0 0 7 ) 优化相邻三角形图元序列的顶点局部性。最后，论文使用网格 经过相邻三角形图元压缩后的形式实现了阴影体积、特征线条图示、动态模糊等 算法。作者指出基于该方法的实时渲染应用能够得到相对几何着色器直接实现 5 0 1 0 0 的速度提升。 作者在论文最后指出基于相邻三角形图元的改进算法的效率主要受几何着 色器硬件性能的限制，并期望随着硬件架构的改进能有更好的着色器执行效率。 但如上文分析指出，几何着色器本身的特性极大限制了基于该单元的实时渲染算 法实现的性能，硬件性能的提升无法根本改变架构上的局限性。 1 4 3 使用c u d a 实现并行三角形处理 采用统一着色器架构不但便于向流水线引入新的着色器单元，硬件结构上的 第1 章序言 通用性也促进了使用g p u 进行通用计算( g e n e r a lp u r p o s ec o m p u t i n g ；o w e n se ta 1 2 0 0 7 ) 这一新兴研究领域的发展。很多研究人员致力于使用( 3 p u 的通用计算能力 实现和改进不同领域的非图形应用，这类算法通常有明显的并行特性并且数据吞 吐量较为庞大。相比较使用g p u 实现非图形算法，本文的研究内容是优化实时 渲染图形算法。基于g p u 硬件特性，并行颗粒度i e ( 甚p 算法本身能够产生大量的 并行处理线程) 、分支同步控制语句较少的算法适合在该平台实现。由于不存在 c p u 上高效的多级c a c h e 机制，使用g p u 实现并行算法时要特别注意内存的存 取操作。 网格中大量的三角形能够产生足够数量的并行线程以保证g p u 硬件以满负 荷运转。很多基于三角形图元或相邻三角形图元的图形算法不需要了解相邻图元 的状态或运算结果，这类算法被称为是局部型( 1 0 c a l ) 的。局部型算法非常合适以 并行算法的形式实现。以三角形为处理对象的局部型算法的处理对象通常为顶点 的坐标、法线等数据，分配到每个线程的数据量较为适中因而不会有大量的数据 读取操作。因此，处理网格中三角形的局部型算法通常适合使用c u d a 实现。 使用c u d a 实现并行三角形处理的主要挑战是在优化顶点读取性能的前提 下如何最大程度配合g p u 硬件优化机制。据此，本文提出两步骤的网格预处理 算法以提高运行时顶点读取的效率，同时在预处理算法框架下考虑支持g p u 硬 件优化机制。使用l h l 等或p e d r o 等( l i na n dt o m a s 2 0 0 6 ；p e d r oe ta 1 2 0 0 7 ) 论文 中方法生成的三角形序列的顶点在使用输入收集器硬件读取时不存在g p u 内存 读取特性导致的性能瓶颈，因此顶点在序号缓存中的顺序仅考虑如何最大化促进 两种硬件优化机制。而使用c u d a 处理三角形前必须首先读取所有的顶点数据， 直接采用上述两种算法生成的三角形序列会产生大量的内存读取操作，重降低 算法效率。本文的主要工作之一是针对g p u 内存的合并读取模型提出预处理算 法，实现将三角形序列以适合c u d a 并行处理的方式排列保存。 9 第2 章预处理算法 第2 章预处理算法 2 1 一g p u 内存的合并访问( c o aie s c e da c c e s s ) 当前g p u 硬件以1 6 个流处理器为一组并行执行相同的指令( 参考1 1 2 节) ， 在同一流处理器组上并行执行的线程间不需要任何的人工同步机制。使用c u d a 并行编程时，称上述由1 6 个流处理器组成的集合为一个h n f - w a r p 。另一方面， g p u 内存也是采用以字节为单位的线性地址表示数据的存取位置。为了提高数 据的存取效率，g p u 硬件通常将整个线性内存空间逐字节地对应到1 6 个不同的 内存堆( m e m o r yb a n k ) 上。例如，对于地址为16 处的单字节数据，g p u 硬件是通 过第o 号堆的某一个内存控制器进行读取的；对于地址为7 处的单字节数据， g p u 硬件是通过第6 号堆的某一个内存控制器进行读取的。基于上述两项硬件 设计，当前g p u 硬件实现了一种基于h a l f - w a r p 的高效内存存取机制，称为合并 访i b - j ( c o a l e s c e da c c e s s ) 方式( n v i d i ac o r p o r a t i o n 2 0 0 9 ) 。 当h a l f - w a r p 内线程满足一定的限制存取g p u 内存数据时，每个线程对g p u 内存单独的存取操作( 共1 6 项) 能够合并至1 或2 项对成块内存数据的存取操作， 这种以合并形式存取内存数据的方法称为基于h a l f - w a r p 的数据合并访问。由于 1 条对g p u 内存的存取指令会带来4 4 0 个左右指令周期的开销( n v i d i a c o r p o r a t i o n 2 0 0 9 ；w o n ge ta 1 2 0 1 0 ) ，而硬件设计要求h a l f - w a r p 内线程的执行必 须同步，因此未合并的内存存取操作需要阻滞当前h a l f - w a r p 大约7 0 0 0 个左右的 指令周期。即使基于s i m t 架构的g p u 硬件能够通过切换至其他可以往下执行 的h a l f - w a r p 来避免阻滞，但是实际的等待时间是无法避免的，整个流处理器集 合仍然会有大量的指令周期内是处于等待数据存取完成的阻滞状态。若能够采用 合并访问的方式存取数据，那么阻滞的情形将大为改善。设计算法实现h a l f - w a r p 的数据合并存取再结合g p u 硬件的s i m t 执行机制是使用c u d a 进行并行编程 获得高效率的关键。 2 1 1 合并访问规则 当完全满足以下规则时h a l f - w a r p 内的1 6 项内存存取指令能够合并至1 或2 项对于成块内存数据的存取指令： 1 ) 所有1 6 个线程必须访问 a ) 4 字节数据，将促成一项6 4 字节数据块的访问操作， l o 第2 章预处理算法 b ) 8 字节数据，将促成一项1 2 8 字节数据块的访问操作， c ) 1 6 字节数据，将促成两项1 2 8 字节数据块的访问操作； 2 ) 所有的1 6 项数据必须位于同一个内存数据块中，且该数据块的地址必须 按照其大小地址对齐。 3 ) 所有1 6 个线程必须依次访问数据，即第k 号线程必须访问第k 项数据。 例如，当h a l f - w a r p 内所有线程依次访问一个对齐到6 4 字节地址的6 4 字节 大小的内存数据块中的4 字节数据时，1 6 项4 字节的内存访问操作便能够以一 条读取6 4 字节数据块的合并访问指令的形式实现。如果h a l f - w a r p 内线程的存取 操作不满足上述规则中任意一条，则只能使用1 6 项单独的内存存取指令完成数 据读取。 目前g p u 硬件上存在这样的特例情形，当h a l f - w a r p 内某些线程并不访问数 据( 通常由分支语句导致) 而其他线程对数据的访问满足上述三项限制时，仍然能 够保证以合并访问的形式执行内存操作。新的g p u 硬件放宽了对合并访问的限 制，为了实现最佳的向后兼容性，本文工作均是基于最严格的合并访问规则。 2 1 2 选取合适的合并访问方式 本文的处理对象三角形网格中的三角形，其顶点数据通常包含位置坐标、纹 理坐标、法向量、切向量等。因此三角形顶点的数据结构为4 字节浮点数或整数 的结构体形式。另一方面，由于g p u 硬件对内存施行合并的4 字节访问时有最 高的效率( n v i d i ac o r p o r a t i o n 2 0 0 9 ) ，本文实现均将顶点数据以4 字节为单位分别 存取，即采取合并存取6 4 字节对齐数据块的形式访问顶点数据。为了符合这样 的合并访问要求，必须将网格中顶点数据由包含众多4 字节数据结构的数组的形 式转化为4 字节数据数组的结构体的形式，即由a o s 型转化为s o a 型。 2 2 网格分块算法简介 使用网格分块( m e s hs e g m e n t a t i o n ) 算法以一定的规则将三角形网格划分为三 角形块的形式是计算机图形学领域的一个基础问题。分块结果不但能够提供网格 的结构信息还可以帮助进行其他网格处理算法，例如骨骼提取( s k e l e t o ne x t r a c t i o n b i a s o t t ie ta 1 2 0 0 3 ；k a t za n dt a l2 0 0 3 ) ，建模( m o d e l i n g f u n k h o u s e re ta 1 2 0 0 4 ) ，蒙 皮( m o r p h i n g z o c k l e re ta 1 2 0 0 0 ；g r e g o r ye ta 1 19 9 9 ) ，纹理映射( l e v y e ta 1 2 0 0 2 ) 等。由于具体的分块规则通常针对计算任务的要求设计，不同算法往往使用不同 的分块策略，例如k - m e a n s ( s h l a f m a ne ta 1 2 0 0 2 ) ，图的切$ i ( g r a p hc u t s g o l o v i n s k i y a n df u n k h o u s e r2 0 0 8 ；k a t za n dt a l2 0 0 3 ) ，h i e r a r c h i c a lc l u s t e r i n g ( g a r l a n d - e ta t 2 0 0 1 ； 第2 章预处理算法 g l e a n e da n do u i b a s2 0 0 4 ；g o l o v i n s k i ya n d f u n k h o u s e r2 0 0 8 ) 等。一些论文研究评价 不同分块算 法( c h e nx b ，g o l o v i n s k i ya ，f u n k h o u s e rt 2 0 0 9 ) 的分块质量，这些工 作通常都是将算法分块的结果与人工网格划分的结果进行比较。 0 2 5 - 4 、， 、， 、， v 3 图2 1 相关顶点与相关三角形 2 3 预处理算法 与几何着色器相似，使用c u d a 处理网格中三角形时也将三角形以固定数 量划分为组，再以组为单位对三角形进行并行处理。顶点数据保存在顶点缓存 ( v e r t e xb u f f e r ) 中，顶点的序号指明数据的存放位置。如果能够将三角形组的顶点 首先以合并读取的方式一次性全部读入共享内存中，那么随后便可以在共享内存 中执行每个线程对应的三角形顶点读取操作，从而避免大量的未合并4 字节数据 读取操作。共享内存的容量有限，在当前的o p u 硬件上每流处理器组仅1 6 k 字 节，对于每个三角形组则仅有4 k 8 k 字节的共享内存可用。 由于采取合并读取对齐到6 4 字节边界的6 4 字节数据块( 以下简称对齐数据 块) 的顶点读取形式，顶点缓存便可被视为是一个对齐数据块的数组。三角形组 内所有三角形顶点所在的对齐数据块数量决定了对共享内存的空间需求。因此， 本文提出的预处理算法的目标是重新排列顶点缓存，使得三角形组内顶点对应的 对齐数据块数量最小。预处理算法通过两步骤实现： 1 ) 网格分块。首先将网格划分为包含相同数目三角形的三角形组。组内三 角形数目取决于并行处理算法的复杂程度以及顶点数据的规模，通常三角形数目 为2 5 6 或5 1 2 。三角形通过其相关顶点被划分至三角形组，三角形组按照串行形