图形并行绘制与多屏显示技术

1、图形并行绘制与多屏显示技术绘制 对于真实感图形绘制而言，指用数学模型模拟客观世界中物体与可见光的相互作用生成真实感图象的过程。对于非真实感图形绘制而言，指用数学模型或算法生成具有艺术风格的图象的过程。 数学模型算法集合软件包驱动程序硬件产生调用应用图形绘制的工业化过程图形绘制的工业化过程高端应用n需要高分辨率的场合，例如使用一个44的屏幕拼接实现4096 * 4096分辨率的大屏幕；n巨型几何场景，如场景数据规模超过10M数量级以上的三角形面片n反走样，例如33 走样，计算量增加9倍之多n大纹理数据量，利用并行/分布图形绘制可以满足纹理数据过大的问题，例如地球数据模型等n科学计算领域，例如有限

2、元计算，计算量非常大，一般使用大规模并行计算或者大规模分布计算环境，希望能够集中显示高端应用：超高分辨率科学计算可视化孤立系统性能的限制ncompute-limited：产生几何数据的能力ngraphics-limited：图形计算能力ninterface-limited：几何指令发射能力nresolution-limited：显示分辨率追求高性能绘制n利用某些CPU的SIMD扩展指令集能使几何变换速度提高2030nAGP总线规范n不断进步的ASIC硬件技术等n绘制流水线技术n多条流水线并行技术非并行手段并行手段经典的绘制流水线ModelingTransformationsBackfaceCu

3、llingLightingCalculationsViewingTransformationClippingRasterizationZ-bufferCompare &StoreGeometry PhaseRasterization Phase多条流水线并行绘制及其分类方式预变换和分布图元分布屏幕坐标图元图像合成GRGRGRGGGGGRRRGRGRGRGSort-firstSort-middleSort-last 按照图形对象的分布方式可分为sort-first、sort-middle、sort-last三种。Sort-first 输出图像被划分为一些不相交的区域，如小矩形或连续的扫描

4、线，每条绘制流水线负责一个或多个区域 图元在进入流水线之前，先进行必要的计算以确定其覆盖的区域，这种计算被称为“预变换” 通常方法为算出图元在屏幕上的外包围盒（bounding box）并进行比较 一个图元有可能覆盖多个区域而进入多条流水线 子图像（subimage）拼接为最终图像GGGG预变换和分布图元RRRRSort-first优缺点 各条流水线完整而独立，且相对sort-middle和sort-last需要的通讯带宽较小 有利于构建集群式或异构的并行绘制系统，如WireGL 预变换与部分几何变换单元的计算重复，是一个不可避免的开销 对负载平衡敏感Sort-middle 输出图像被划分成一

5、系列区域，并由多个子图像拼接而成 ,同sort-first 不同的是图元不考虑视点关系、任意地（比如按轮转序）进入各个几何变换单元 几何变换之后，图元被转换成了2D屏幕座标，再根据屏幕座标被传送到正确的光栅化单元GGRRGRGR分布屏幕图元乱序进入Sort-middle优缺点 几何转换和光栅化一般总是由不同的处理单元来处理，sort-middle在G、R之间打断流水线的方式是最“自然”的 直观和常用，有利模块化地实现 G与R的两两之间都需通讯，随着处理单元的数目增多，通讯开销将呈几何级数增长 对负载平衡敏感 Sort-last 图元任意地进入各条流水线，并独立完成几何变换和扫描转换 一直计算到

6、光栅化的最后一步：可见性判断（visibility） 每条流水线都产生了包含部分图元的完整分辨率的象素（样本） 在合成单元（compositing processor）进行深度合成或alpha混合，输出最终图像 GGGGRRRR图像深度合成乱序进入Sort-last优缺点 简明 ，易于利用已有的系统模块（尤其是硬件）实现 其性能不受图元分布的影响，对负载平衡不敏感 图像合成步骤易成为系统瓶颈 并行图形绘制的三种实现方式n基于ASIC技术的硬件实现nsort-middle的InfiniteRealitynsort-last的Pixel-Flown基于并行计算机的实现n基于共享内存并行机的sort

7、-last系统Parallel-Mesan基于分布式内存消息传递并行机的sort-middle系统PGLn基于集群机的实现nsort-first的WireGLnsort-last的Sepiansort-first/sort-last混合型的AnyGLWireGLnSiggraph 2001 by Stanford University n解决了分布并行图形系统系统关键问题：指令编码传输和状态跟踪 n第一个基于sort-first体系结构并且独立于硬件平台的图形集群绘制系统 n第一次对所有关键技术问题提出了完整、实际的解决方案 WireGL系统WireGL的后续：ChromiumnSiggrap

8、h 2002n明确地提出了“流处理” 的概念，图形绘制过程被看作数据流在SPU（Stream Process Unit）间流动的过程 n各种类型SPU的连接组合可以生成各种结构的并行绘制系统 Chromium：绘制指令分布多屏幕拼接输出的SPU组合 ApplicationTile sortChromium ServerRenderChromium ServerChromium ServerRenderChromium ServerRenderRender. . .应用程序GNodeRNodeCNodeDNode应用程序GNodeRNode应用程序GNodeRNode应用程序GNodeRNode

9、CNodeDNode网络网络网络立即模式并行绘制系统AnyGL立即模式并行绘制系统AnyGLnAnyGL实现了大规模混合分布图形体系结构，实现了sort-first与sort-last的混合分布图形体系结构，解决了分布图形计算的可扩展性问题，系统节点数目不受限制 nAnyGL实现了一个分布的虚拟并行图形流水线，可划分为四类逻辑节点：几何数据分配节点，几何图形绘制节点，深度图像合成节点和图形显示节点。AnyGL允许一个物理节点支持多个多种类型的逻辑节点，能够利用SMP系统的多图形加速卡实现并行计算。 并行图形绘制方法分类的新思路:两种API应用程序应用程序立即模式绘制器立即模式绘制器应用程序应用

10、程序保留模式绘制器保留模式绘制器进程A进程A进程B进程B(a) 立即模式API(b) 保留模式API模型数据模型数据并行图形绘制方法分类的新思路：两种并行绘制体系结构进程D进程D进程C进程C应用程序应用程序立即模式绘制器立即模式绘制器应用程序应用程序保留模式绘制器保留模式绘制器进程A进程A进程B进程B局域网局域网(a) 立即模式并行绘制(b) 保留模式并行绘制模型数据模型数据并行图形绘制方法分类的新思路n传统上图形绘制API分为立即模式和保留模式两种 n立即模式系统数据存储于客户端，保留模式系统数据存储于服务器端n并行绘制系统可分为立即模式并行绘制系统和保留模式并行绘制系统 客户节点绘制节点几

11、何数据归属判断数据调整负载平衡显示设备对象分布策略拼接输出几何数据几何数据几何数据绘制节点绘制节点绘制节点保留模式并行绘制系统的构架保留模式系统的数据分布存储立即模式并行绘制系统： 数据集中几何指令分布，对网络带宽高度依赖，网络带宽和归属计算易成为系统瓶颈 数据都在客户端，每绘制一帧，所有几何数据就作为指令的参数分布到服务器上，服务器绘制完毕，即将数据丢弃，绘制下一帧时重复同样的过程 结构缺乏弹性，无法有效利用图形应用程序的帧间相似性 对策n交互式图形应用程序普遍存在帧间相似性（frame-to-frame coherence），完全突兀的帧是少的，理论上两帧之间只需进行少量的数据调整 n保留

12、模式系统中几何数据分布于绘制节点n只要能实现一种数据分布帧间调整的系统构架，就可能降低网络数据流量，避免带宽瓶颈系统流程n客户端读入几何数据集G，对G进行剖分并构造Cell结构 n在绘制第一帧之前，客户端以Cell为单位作归属判断，并根据归属关系将Cells分布到各个绘制节点 n绘制第一帧 n如用户改变视角，客户端计算新的几何变换矩阵并发指令到各个绘制节点，不重发G 5.绘制节点根据新的变换矩阵对本机所拥有的图元作归属判断。若某一图元归属于另一绘制节点，则将此图元发送到该绘制节点。若某一图元不再归属于本绘制节点，则将其删除。多个绘制节点之间发送和接收图元的过程称为调整（adjust）。调整之后

13、，每个绘制节点都拥有且只拥有归属于它的图元 6.绘制新的帧 ApplicationAFServerAFServerAFServerAFServerAF ProtocolAF ClientAPI callingimage outputAF Protocol communication原型系统结构多机加速和调整率调整率c：通过网络的数据量和全部数据量之比保留模式并行绘制系统受控的归属判断n立即模式并行绘制通过传送几何指令包分布绘制任务n由于立即模式并行绘制系统不拥有数据，几何数据发射的顺序完全由应用程序决定，而后者的行为是不可预测的n如果应用程序发射的几何数据在空间排列上是混乱的，可能使外包围盒过

14、大，导致不必要的传输和绘制开销 123456123465(a) 理想情况(b) 不利情况对策n保留摸索并行绘制系统拥有特殊的优势：对数据的控制能力n对模型数据进行预处理，对模型进行剖分，生成紧凑的外包围盒n按合理的顺序发射数据n可降低图元归属于多个绘制服务器的概率。 Dragon模型的box剖分Ball：比Box更进一步nBall = (Pcenter, R, Geometry) nPcenter为中心点，R为半径，Geometry为Ball内的几何图元数据 n一个Ball包含了空间上相近的一组几何元素 n与立方体外包围盒相比，Ball定义了一个球，能更快的进行归属判断 Dragon模型的ba

15、ll剖分负载不平衡的情况实用有效的并行绘制负载平衡算法负载平衡的情况实用有效的并行绘制负载平衡算法静态并行绘制负载平衡算法1111222233334444问题n屏幕配置一旦完成，系统就处于被动等待的状态 n依据“图元更易出现在屏幕中央”这一统计规律，因此其有效性也是统计意义上的 n针对具体的图形应用的适应性差，不能满足高性能图形并行绘制的需要 动态并行绘制负载平衡算法1234567812345678（b） Whelan算法(c)Whitman算法125(d)MADH算法346784241234(a) Roble 算法13动态方法特点 利用所有图元的顶点位置、几何变换矩阵等几何数据作为输入计算负

16、载平衡状态最佳的屏幕剖分，因此可以将统称为“基于几何数据分析”的方法。这些方法能根据应用程序的实际行为动态调整绘制负载的分配，具有较高的智能性。 基于几何数据分析的动态方法的不足 n负载估算的精确度不足 n计算开销过大 n实施难度较大 基于时空转换的并行绘制负载平衡算法的原理1s2s3s(a)(b)(c)基于时空转换的并行绘制负载平衡算法的原理 n以绘制服务器的工作时间作为其负载的度量n通过适当的算法将时间值转换为空间值n空间值控制对绘制服务器的任务分配n放弃了庞大的几何数据n一种相对 “轻量”的算法 流程n客户端发送几何变换矩阵和屏幕区域Aik到绘制节点Si，启动第k帧绘制，并通知负载平衡模

17、块；nSi完成Aik像素的绘制，通知客户端；n客户端主程序通知负载平衡模块，后者记录绘制时间tik；n所有Si绘制结束，拼接图像并输出；n负载平衡模块进行计算，得出屏幕剖分方式Aik+1，用做下一帧绘制任务分配。 (a)(b)(c)(d)32145678t1wihit2t3t4t5t6t7t8屏幕剖分的三种方式校区漫游程序实际效果横轴为绘制帧数，纵轴为时间（秒），蓝线不使用负载平衡控制（固定分割屏幕），红线使用负载平衡控制。 横轴为绘制帧数，纵轴为最短绘制时间和最长绘制时间之比，蓝线不使用负载平衡控制（固定分割屏幕），红线使用负载平衡控制 实用的多屏并行绘制系统MSPRn保留模式的分布并行绘制系统 n类OpenGL的保留模式编程APIn对应用程序透明的图形对象分布策略，包括图形对象定义、删除、远程调用、绘制同步等机制n多屏高分