论文 关健词：虚拟现实 并行渲染 负载平衡 归属判断
论文摘要：虚拟现实应用要求图形系统具备实时渲染复杂、精细场景的能力。基于 pc机群的并行渲染系统具有性价比高、扩展性好的特点，适合虚拟现实应用。该文针对虚拟现实应用设汁并实现了一个保留模式的sort—first并行实时渲染系统，对影响渲染性能的关键因素进行研究，给出具体实现步骤、试验验证数据和结论。应用表明，该方法能够实现系统的高效并行 计算 及虚拟现实应用中的复杂场景实时处理。
1 概述
虚拟现实技术已广泛应用于车辆仿真、建筑预排、计算机辅助设计以及 科学 可视化等领域。随着图形图像硬件和软件的 发展 ，人们对应用的交互性和现实感提出了越来越高的要求：在满足实时性(每秒30帧)和低延迟的同时，需要构造更加逼真、精细的三维复杂场景，其数据规模日益膨胀，有时还需要满足多通道输出等特殊的应用要求。
基于pc机群的并行渲染技术以其性价比高、兼容性好、扩展灵活等特点，成为虚拟现实实时显示研究的新方向。随着 pc系统上图形卡渲染能力的提高和千兆 网络 的出现，建立在高速网络连接的 pc工作站集群上的并行渲染系统具有良好的性价比和更好的可扩展性，得到越来越广泛的应用。
图形计算任务的描述非常简单：给定一个环境下所有物体的数学模型，系统计算每个模型对于给定可视面上每个像素的作用 ，这就是图形流水线 。WwW.133229.Comsutherland，sproull和schurnacher于 1974年提出从数据分配(sorting)角度对并行渲染进行研究。依据从对象空间到屏幕空间转换过程中的渲染任务发生时间点， 文献 【1】将并行渲染方法分为 3类：sort—firstsort—middle和 sort—last，该理论成为并行图形渲染和分布图形渲染研究的里程碑。
sort—first方式在图形流水线的开始阶段就将图元分配到各渲染节点；sort—middle在几何变换与光栅化之间重新分布图元；sort—last则在流水线的最后重新分布像素。sort—middle和 sort—last方式都在一定程度上符合图形流水线的 自然 形态，因此，适合硬件实现，如 sgi的 reality engine和 infinitereality是 sort—middle系统，hp与unc合作的pixelflow是典型的 sort、last系统 j。sort—first方式能充分利用已有的渲染资源，相对其他 2种方式通信量较小，因此适合软件实现 ，构建 基于 机群 的分布式并行 渲染系统 。浙 江大学cad&cg国家重点实验室开发的 anygl是一个 sort—first和sort—last混合的支持大规模分布的并行渲染系统。
2 系统结构
本文设计了一个基于 pc机群的保留模式 sortfirst并行渲染系统。该系统的各个节点均配有高端普通图形显示卡，采用千兆以太网交换机进行互连，期望以较低的成本达到大型专有系统的性能，并且具有更强的灵活性和可扩展性。其基本工作模式为 “归属判断一渲染一同步显示”。这种设计能充分利用帧问相似性，减少网络开销。与另 2种方式相比，sortfirst最大的特点是对图形流水线介入较浅。
图 1为系统硬件结构，系统由一个用户服务节点和一个图形计算机子系统组成。后者包含很多处理节点，这些节点实时处理图像。
(1)用户服务节点：负责渲染节点之间的协调，接收用户输入，传送命令，执行负载平衡任务。
(2)渲染节点 ：拥有全部场景数据。根据视点的改变和负载平衡计算结果自适应地判断面片归属，根据统一位姿指令执行渲染任务，提取图像像素数据并发送给图像服务节点。
(3)图像服务节点 ：接收渲染节点输入像素数据，合成像素数据，输出图像信息到投影设备。
系统在原始数据输入后及顶点变换前对计算任务进行分配。其工作模式如下：
stepl用户服务节点执行负载平衡计算。
step2根据负载平衡结果，渲染节点确定图元归属。
step3渲染节点执行渲染服务，提取像素数据并发送。
step4图像处理节点接收像素数据，执行图像拼合。
step5输出到投影设备并显示。
负载平衡是 sort—first架构面对的最大问题。在实际应用中，图元的屏幕划分是高度可变的，为了达到很好的负载平衡效果，必须深入研究渲染节点的屏幕分配策略。另外，图元的跨屏幕分布带来的重复渲染也会导致渲染效率的降低。为了便于讨论 ，以一台应用主机和一个图形计算子系统为例。后者由几个渲染节点及一个图像处理节点组成，渲染节点实时渲染图像 ，图像处理节点负责显示。显示模型数据库开始即被分配到所有渲染节点，因此，为保留模式。
3 关键技术
3．1 系统并行性
多边形渲染是一种“近似易并行”的计算，其特点是适合并行，但需要计算任务的分布和收集计算结果，并用某种方式加以组合。对多边形渲染算法引入并行的方法有 2种：功能并行和数据并行。
3．1．1数据并行
并行渲染应用要求在图形流水线的几何转换和光栅化阶段都进行并行化。对于 sort—first，一旦确定了图元归属，渲染节点只要计算它负责的那部分屏幕的最终图像，节点之间几乎没有干涉，现有的多种并行渲染加速算法都能得到应用因此，系统具有很好的扩展性。
数据并行方式将数据剖分成多个独 立的数据流(datastreams)，在一些相同的处理单元上同时对这些数据流进行处理。这种方式的并行效果不受渲染流水线级数的限制，但受制于相同的处理单元的数目和系统内部的通信带宽。由于多边形渲染算法数据问的相关性很弱 ，因此数据并行方式有较大的潜力。
3．1．2 功能并行
渲染节点内流程主要分为图形渲染、数据通信和同步等待3个功能阶段。其中，图形渲染和数据通信耗时较多，也最有可能成为系统的瓶颈 ；系统同步等待本身花费不大，主要与节点的渲染和通信直接相关。为了有效地提高系统效率，在渲染节点主要实现图形渲染和数据通信的同步。
3．2 负载平衡技术
对 sort—first并行渲染系统而言，渲染任务分布策略一般基于屏幕的任务划分 ，负载平衡问题的研究焦点是屏幕的划分和屏幕分配的算法。根据屏幕划分是否固定，这些算法主要分为静态的和适应性的。对于静态算法，图形应用的有效性并没有得到保证；目前适应性负载平衡算法主要有：roble算法，median—cut算法，whitman自顶向下分解算法，madh算法l。j。这些算法都是基于图元数据分析的，将任务的负载用屏幕区域内的几何图元分布特性来度量。
上述适应性算法的缺点是节点需要遍历图元，遍历的过程中还需要同步，且算法本身耗时，这需要较大的时间开销，导致效率降低和延迟增加。此外，采用图元数据作为衡量负载的标准虽然能够精确地衡量负载，但在实际应用中，由于渲染节点计算能力的差异，或者即使计算能力相同而节点本身状态不同，都会导致渲染相同数量几何图元的时间不同，因此这些算法并不能很好地解决负载平衡问题。
下面结合基于图元数据分析算法的屏幕划分精细网格思想 提出一种基于网格划分的时间衡量负载算法。该算法以渲染时间直接衡量负载，利用仿真应用的帧问连续性，结合节点 历史 渲染时间数据，同时兼顾节点本身处理图元数据能力，建立渲染时间到屏幕区域负载权重的映射 ，计算屏幕区域负载权重表。以该屏幕区域负载权重表为依据进行任务分配。
图 2显示了 2种算法的不同工作模式。基于几何数据分析算法的共同模式可表示成图 2(a)，负载平衡控制模块输入几何数据和当前帧的几何变换矩阵(通常从客户端获得)，运算出新的屏幕剖分方式，作为重新分配渲染任务的依据。基于时间分析的算法如图 2(b)所示，不考虑几何数据，实时捕捉渲染节点渲染一帧的时间，结合前一帧的剖分方式，快速计算出新的剖分方式，控制下一帧的渲染。
由于避免了庞大的几何数据计算，因此这种算法花费很小，测试结果证明其非常实用和有效。另外，从图 2可以看出，由于增加了反馈回路控制，因此有利于快速达到平衡。负载平衡的根本目的是缩短各渲染节点渲染时间并使彼此尽可能接近，因此，以渲染时问衡量负载的平衡算法比基于几何数据分析的负载平衡算法更加接近问题的本质。
负载平衡模块运行在系统客户端的流程如下：
(1)用户服务节点发送统一位姿信息和屏幕划分方案到渲染节点，启动第 k帧渲染。
(2)渲染节点完成渲染，输出像素数据到图像服务节点。
(3)渲染节点记录自身渲染时间，发送给负载平衡节点。
(4)负载平衡节点汇总渲染时问，判断负载平衡条件，负载平衡系数(最重载／最轻载)是否超过限定值(根据试验确定)：未超过(表明负载平衡)，采用屏幕划分方案；否则看作负载不平衡，根据各节点渲染时间计算屏幕区域负载权值表，并确定屏幕划分方案。
(5)图像服务节点汇总像素数据，拼接输出。算法要点：
(1)屏幕划分为大小一致的精细网格(图 3)，每个网格赋初始权值 1(网格负载权重总值等于网格数)，以网格作为屏幕分配的单元。
(2)以渲染时间作为衡量渲染节点负载的指标，并作为计算区域负载权重表的依据。
(3)负载平衡模块根据区域负载权重表进行负载平衡计算，确定屏幕划分方案。屏幕以与 mediancut相同的层次方法沿着单元边界被划分。单元总计表允许通过二分查找操作决定划分的位置。或者，该算法可以通过选择合适的划分比率来允许使用非 2的整数次幂的处理器数，而不是每次等份划分，见图 3。
(4)各渲染节点根据屏幕划分方案执行渲染任务，记录本帧渲染时间并反馈给负载平衡模块作为负载平衡计算的依据。这借鉴了反馈控制的思想。
(5)在负载平衡计算过程中以网格负载权重总值对网格负载权值进行归一化计算的依据。
图形系统把大量图元组织在图元集中，采用各种优化措施提高图元处理速度。在并行渲染系统中，流水线是以图元集为单元根据屏幕位置进行裁减的，如果图元集包含图元过多，会带来重复渲染的问题。如图 4所示，分配方案已定，每个子屏幕分配给一个渲染节点。由于该模型只有一个图元集，虽然屏幕区域 2，4和 7并未完全包含模型，因此它们仍然要对整个模型进行渲染 计算 。在实际的并行渲染应用中，重复渲染会导致严重的效率损失。
为了解决这类问题，本文对模型进行预分割，将含有大量面片的图元集分割为含有较少面片的多个图元集，以减少图元集横跨多个屏幕的概率，从而减少渲染节点重复渲染的面片数量，充分发挥屏幕裁减功能的效用。模型预处理流程为：输入渲染模型文件结构树和边界条件——图元最大面片数，输出分割后的模型树结构，子节点大小均匀。
工作流程有如下 4步：
(1)遍历自定义的结构树，对每个叶子节点进行判断，如果满足条件(如面片数大于某一值)，依据该叶子节点的包围盒进行空间八叉分割。
(2)如果子空间不为空，则新生成一个叶子节点，挂在当前节点下，当前节点改为枝干节点。
(3)对新生成的叶子节点继续进行分割，直到条件不再满足(如面片数小于某一值)。
(4)保存结果模型文件。 实验证明，模型预分割办法能很好地解决模型图元集包含过多面片数带来的重复渲染问题。
4 试验结果与分析
原型系统利用千兆交换机连接 5个 pc节点。pc配置amd athlon 64 x2 dual core 4000+2，1 1 ghz，2 gb内存，nvidiageforce 7900 gs图形加速卡，千兆网卡。
4．1 通信能力测试
本测试是在 2个节点之间进行的，测试了单次发送数据量从 100 byte~50。byte时的传输速度。经测试，传输能力最高约为900 mb／s。考虑应用中采用1 027x768的分辨率，每帧接收1 024x768x3=2 359 296 byt数据 ， 网络 应用大概为83％，传输能力约为740 mb／s，单次传输约需26 ms。
4．2 并行性分析
系统模式：1个显示节点，2个渲染节点；模型面片总数400万。这里取 1 000帧数据的统计平均值进行分析。读帧缓存时问即渲染时间，发送的数据都是像素数据。采用时间测量函数精确度达到了微秒级。功能并行后效率提高了35％左右提升较明显。
从表 1和表 2可以看出，2种渲染方式花在读帧缓存上的时间差不多；未并行时，渲染节点有很多同步等待花费，图像处理节点是瓶颈(同步等待时间最少)；并行后渲染节点 2的渲染阶段是瓶颈 ；理想的情况是渲染节点与图像处理节点的同步等待花费最小。
4．3 基于渲染时间分析的负载平衡
可能影响负载平衡计算的因素主要有网格的划分、场景运动速度、模型面片数及负载平衡条件系数的选择。笔者对每一项进行了测试 ：测试帧数 200；取各指标平均值进行分析，同时给出了数据的标准偏差。主要考察指标有：最重载、最轻载比，标准偏差，负载平衡计算频率以及最重载、最轻载的分布。
模型选择：100个模型在场景中随机分布，每个模型分别取 0．5，1，2及 3个单位进行测试(44 800面片／单位)。由试验数据曲线(图 5)可以看出，渲染节点渲染时间与模型面片数呈近似线性关系，负载平衡效果随模型的增大变好；网格划分更精细对负载平衡改善不是很大，这与传统的网格划分算法相悖，这是因为采用屏幕区域权重的方式衡量负载远没有图元分析方法精确，只是一种近似(1~lj使重载子屏幕也存在轻载区域，而该轻载区域权重系数与重载子屏幕其他部分一样)。
场景变化越剧烈，负载越不平衡，这与直观相符；负载平衡条件系数越大，对负载平衡计算限制越小，负载平衡计算次数越少，当负载平衡条件系数选择得很小(如 13)时，宣鲁统频繁地进行负载平衡计算，效果反而不好。通过图 6的效果图得出，采用基于网格划分的时问衡量负载算法，负载平衡比达到 1．5，能够充分满足并行渲染系统的需要。
由于采用屏幕区域权重的方式衡量负载只是对负载的一种近似，因此有时负载平衡计算效果不是很好。另外 ，视点变化剧烈也会对负载平衡效率造成很大影响。
4．4 模型分割
应用本文提 出的方法进行测试 ，测试模型面片数为422 928。经测试，分割后图元集增加了 7倍 ；每个图元集包含的图元数为原来的 1／8；每个图元包含的三角形面片约为分割前的 1／3。经过模型预处理和分割，通过增加图元集数目，有效地减小了单个图元集的规模，从而降低了重复渲染的概率。
5 结束语
并行渲染的目的是充分利用多台 pc 的资源提高系统处理能力。数据分布型的 sort—first并行渲染系统能有效利用帧问相似性，降低并行开销，适合分布式交互图形应用。原型系统证明本文提出的方法可以构建高性能、低开销的并行图形渲染系统。渲染流水线本身固有的数据和功能并行性为构造高性能并行渲染系统提供了有效的保证。负载平衡是并行系统的核心技术，笔者在前人工作的基础上，提出了一种新的负载平衡算法并应用于原型系统，通过试验数据分析证明其具有良好的效果。
参考 文献
[1 1 molnar s，cox m，ellsworth d，et a1．a sorting classification of parallel rendenng[j]．ieee computer graphics and applications，1994，14(4)：23-32．
[21 akeley k．reality engine graphics[c]//proceedings of acm siggraph annual conference on computer graphics． anaheim ， california，usa：acm press，1993：109-1 16．
[3] olano m，lastra a．a shading language on graphics hardware：the pixel flow shading system[c]//proceedings of annual conference on computer graphics．orlando，florida．usa：1 998．
[4]杨 建．anygl：一个大规模混合分布图形系统[d]．杭州：浙江大学，2002．
[5]金哲凡，林 海，石教英．数据分布型 sortfirst并行图形绘制系 统的研究与实现[j1_计算机研究与 发展 ，2004，41(2)：376—382．
[61 muellerc．the sortfirst rendering architectureforhighperformance graphics[c]//proceedings of the 1995 symposium on interactive 3d graphics．monterey，california，usa：，1995
