（计算机应用技术专业论文）基于jpvm的分布式实时可视化系统的设计.pdf

摘要 摘要 本文主要研究在j p v m 的基础上，构建一个可交互的实时分稚式可视化系统， 我们的目标是利用簇计算资源，把实时的三维渲染作为一个标准的i c m 应用程序。 充分利用带有硬件图形加速的通用计算机组成的簇资源，提高实时渲染的性能 由于该系统是由多台个人计算机组成的计算机簇来对三维的场景进行渲染， 当前大量的簇计算的工作主要是研究响应时间驱动计算方面的问题，而i c m 由于具 有实时的特点，对于簇计算提出了新的要求：要以低时延低抖动生成一个具有细 致纹理的连续帧序列。另外，l c m 应用软件需要更快的礴络带宽因为他们使用像影 像、声音、与用户交互产生的图像等媒体。 在通用计算机平台上构建一个分布式三维实时渲染系统，面临着很多的问题： 1 、要构建一个分布式的渲染器，该渲染器能充分利用各台计算机的三维图象硬件 加速资源 2 、在场景复杂度增加时，能控制系统对网络带宽的要求 3 、当用于调度任务的通信时间占有很大帧时时，怎样调度不可预先估计执行时间 的任务以减少抖动 为了满足上述需要，我们首先研究分布式系统上在不可预知的服务请求下怎 样调度相似的任务尽可能的满足实时要求。针对通用计算机平台，我们设计一个 分布式实时渲染框架( d r r s ) 。我们设计了一个面向通用计算机平台的分布式渲 染框架，特别是采用了新的工作分区和分配技术：图像分层的分解技术( i d ) 。 图像分层分解能与图像加速硬件协调工作并且网络带宽的请求与场景的复杂度无 关。 本文主要的工作包括：( 1 ) 把交互的媒体流技术引入到分布式实时渲染中。 ( 2 ) 研究新的分区技术，图像层分解技术，它可以采用硬件加速的渲染功能，减 少因场景复杂度的增加而引起的通信请求。( 3 ) 设计分布式实时渲染系统d r r s 的框架。 关键词：j p v m ，分布式实时渲染，通用计算机簇，i l d a b s t r a c t t h i st h e s i si n v e s t i g a t e si s s u e so nb u i l d i n gs y s t e mo fi n t e r a c t i v er e a l t i m e v i s u a l i z a t i o ns y s t e mo nc o m m o d i t yc l u s t e r so nt h eb a s i so fj p v m t h eg o a li st o l e v e r a g ec o m m o d i t yd u s t e r sa n dw ef o c u so nr e a l - t i m e3 dr e n d e r i n ga sac a n o n i c a l i c ma p p l i c a t i o n 。i np a r t i c u l a r , o u rg o a li st oc x p l o i tc l u s t e r so fc o m m o d i t yc o m p u t e r s ， w h e r ee a c hm a c h i n ei se q u i p p e dw i t hah a r d w a r eg r a p h i c sa c c e l e r a t o r , t oi m p r o v et h e r e a l t i m er e n d e r i n gp e r f o r m a n c e w h i l et h e r eh a sb e e nc o n s i d e r a b l ew o r ko nt h eu s eo fc l u s t e r st os u p p o r tr e s p o n s e t i m ed r i v e nc o m p u t a t i o n s ，i c ma p p l i c a t i o n s p l a c en e wr e q u i r e m e n t so nc l u s t e r c o m p u t i n gb e c a u s eo ft h e i rr e a l t i m en a t u r e ：t h ea p p l i c a t i o np r e s e n t s ac o n t i n u i n g s e q u e n c ef r a h r e st h a tm u s th ec o m p l e t e dw i t hl o wl a t e n c ya n dl o wj i t t e r a d d i t i o n a l l y , i c ma p p l i c a t i o n sa r eb a n d w i d t hi n t e n s i v eb e c a u s et h e yu s em e d i as u c ha sv i d e o , a u d i o , a n dc o m p u t e rg e n e r a t e di m a g e st oi n t e r a c tw i t hu s e r s t h ec h a l l e n g e sf o rb u i l d i n gad i s t r i b u t e d3 dr e n d e r i n gs y s t e mo nt h ec o m m o d i t y p l a t f o r mi n c l u d e ： 1 、h o wt os t r u c t u r ead i s t r i b u t e dr e n d e r e rt ol e v e r a g eh a r d w a r e - a s s i s t e dr e n d e r i n g 2 、h o wt oc o n t r o lb a n d w i d t hd e m a n dw h i l es u p p o r t i n gt h er e n d e r i n go f i n c r e a s i n g l yc o m p l e xs c e n e so nm o d e r a t e l ys i z e dc l u s t e r s 3 、h o wt os c h e d u l et a s k sw i t hp o t e n t i a l l yu n p r e d i c t a b l ee x e c u t i o nt i m e st oi n i m i z e j i t t e rw h e nt h ec o m m u n i c a t i o nc o s tf o rd y n a m i cl o a db a l a n c i n gc a l lb eas i g n i f i c a n t f r a c t i o no ft h ef l a m et i m e 。 t oh e l pm e e tt h e s ec h a l l e n g e s ，w ef i r s te x p l o r ep o l i c i e sf o rs c h e d u l i n gs i m i l a r t a s l 岱w i t hu n p r e d i c t a b l es e r v i c ed e m a n d so nad i s t r i b u t e ds y s t e mw i t ht h eg o a lo f m a x i m i z i n gt h ep r o b a b i l i t yo fm e e t i n ga r e a l t i m ed e a d l i n e i np a r t i c u l a r , w et h e nd e s i g n ad i s t r i b u t e dr e n d e r i n gf r a m e w o r k ( d r r s ) t a r g e t e ds p e c i f i c a l l yt ot h ec o m m o d i t y p l a t f o r m i np a r t i c u l a r , w ee m p l o yan e ww o r kp a r t i t i o n i n ga n da s s i g n m e n tt e c h n i q u e c a l l e di m a g el a y e r e dd e c o m p o s i t i o n ( 1 l i ) ) i l di sc o m p a t i b l ew i t hh a r d w a r e - a s s i s t e d r e n d e r i n ga n di t sb a n d w i d t hr e q u i r e m e n ti si n d e p e n d e n to fs c e n e t h em a i nw o r ki n c l u d e ：( 1 ) i n t r o d u c ei n t e r a c t i v ec o n t i n u o u sm e d i at od i s t r i b u t e d n a b s t r a c t r e a lt i m er e n d e r i n g ( 2 ) e x p l o r ean o v e lp a r t i t i o n i n gt e c h n i q u e ，i l d ，t h a ti sc o m p a t i b l e w i t hh a r d w a r e a s s i s t e dd i s t r i b u t e dr e n d e r i n g , d e c o u p l e sc o m m u n i c a t i o nr e q u i r e m e n t f r o ms o n oc o m p l e x i t y ，a n ds i g n i f i c a n t l yr e d u c e sc o m m u n i c a t i o nr e q u i r e m e n t ( 3 ) d e s i g naf r a m eo fd i s t r i b u t e dr e a lt i m er e n d e r i n gs y s t e m ( d r r s ) k e y w o r d s ：j p v m ，d i s t r i b u t er e a l - t i m er e n d e r i n g ，c o m m o d i t yc o m p u t e rc l u s t e r , i l d i l l 独创性声明 本人声明所呈交的学位论文是本人在导师指导下迸行的研究工作及取得的研 究成果据我所知，除了文中特别加以标注和致谢的地方外。论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得电子科技大学或其它教育机构 的学位或证书而使用过的资料与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示谢意 签名日期：2 0 0 7 年月2 8 日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文的规定，有 权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借 阅本人授权电子科技大学可以将学位论文的全部或部分内容编入有关数据库进 行查阅，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文 ( 保密的学位论文在解密后应遵守此规定) 签名 日期；2 0 0 7 年略月2 8 第一章绪论 第一章绪论 个人计算机的性能发展迅速，通常3 到5 年c p u 的速度就能提高一倍。采用 高性能的大型计算机价格昂贵，并不能在各行业进行广泛的应用。随着网络带宽 的增加，利用多台个人计算机或工作站的集群式的并行计算成为可能。集群式并 行机计算与采用高性能的计算机相比，可以得到更好的性价比。 三维图象处理技术也随着计算机的发展f 1 趋完善，出现了用于专用于三维图 像处理的软件包，像o p e n g l ，d i r e c t x ，j a v a 与o p e n g l 的捆绑一j o g i 【1 1 。特别是 个人计算机的硬件三维图形加速功能组件发展迅速，大部分的硬件都对o p e n g l 、 d i r e c t x 等进行支持，通过局域网将这些计算机连接成计算机簇进行分布式计算可 以充分的利用多台计算机的图形处理能力 1 1 研究的目的 随着个人计算机的发展，硬件组件像三维图象加速功能、影像编解码技术也 不断的得到提高，一些应用程序可以运行在这些通用计算机上。但是，交互式的 连续媒体流( i c m ) 应用出现后，与以往的应用程序有很大的不同，i c m 应用程序 不采用请求，相应模式。一个i c m 程序一般连续的同用户实时交互，交换的数据包 括声音、视频、计算机产生的图像、文本，特别是在建立大的世界表面模型时， 对计算和网络资源消耗很大。通用计算机平台上运行i c m 应用程序时( 如在实时的 三维渲染时) 经常还是力不从心。随着硬件图形加速组件性能的不断提高，原来 越多的三维应用程序被用在这些通用计算机上，像虚拟现实系统1 2 】、c a d 系统【3 】， 科学数据可视化系统【4 】【5 l ，三维游戏等1 6 l 。同时，为了更真实的表现现实世界，对 计算机的渲染性能的要求也是无止境的。在多边形渲染【7 l 时，模型的大小已达到几 百万个多边形，远远超出现在的通用计算机甚至是工作站嗍的处理能力。并且模型 的大小的增长速度要高于通用计算机实时渲染性能的提高，这主要是人们对模型 精度要求越来越高，没有止境，所以计算能力永远跟不上人们对渲染能力的要求。 因此，可以用计算机簇来增加i c m 应用程序的性能。由于通用计算机随处可见， 所以通用计算机簇很容易组成，而大部分专业的计算环境【9 l 则只在一些特殊领域可 以见到。这样，我们可以充分利用已有的计算机资源来提高i c m 应用程序的性能而 电子科技大学硕十学位论文 不用额外的投资，所以比专业系统有更好的性价比。当然就单独从性能而言，通 用计算机簇不一定要比专业的计算机的性能高，比如在3 d 渲染中，当前基于通用 计算机簇的分布式渲染技术无法与专业的机器相比，像s g i 的无限真实机l l o 】或者 p i x e l f l o w 机【1 1 l 相比。所以本文的目的并不是要取代专业的工作站，而是充分的利 用已经存在的通用计算机簇来提高实时i c m 应用程序的性能，获取更高的性价比。 以往对分布式研究已经进行很长时问了，但是大部分主要集中于请求，响应或 者是硬实时的应用程序，而i c m 应用采用软实时技术，因此对簇计算提出了新的要 求： 用户以事件( 如鼠标或键盘等) 的方式向系统提出请求，系统向用户提供一 个可视的帧序列。 研究结果表明，在构建一个虚拟现实系统时，响应时间如果很大( 如l o o m s 或者更大) 将影响用户对虚拟世界的感知，甚者变得非常迷茫而无法操纵虚拟世 界【1 2 1 1 1 3 1 。同样如果帧的完成时间不一致就会导致图像的抖动，尽管没有象帧响应 时间那样重要，也会影响用户对虚拟世界的感知【1 4 1 。另外用户希望在不同的场合 能对响应时间、帧率、抖动、媒体的保真度进行协调，如当一个用户在一个虚拟 的世界漫游，希望通过降低渲染的精度来换取更小的响应时间，当他停下来时仔 细观察虚拟世界的某一部分时，他希望获得该部分更高的渲染精度，也增加了系 统的复杂度。 当前的系统设计采用一般意义上的吞吐量和平均的响应时间方法来评价系统 的总体性能，但这并不能达到i c m 应用程序的对于低响应时间、低抖动l 划的要求。 另一方面，在硬实时系统中，如果由于达到时限引起的错误通常被认为是系统出 错，会导致灾难性的后果。这样系统资源管理是保守的，一般采取交替使用系统 的空闲来确保在最坏的情况下都可以使请求得到满足。i c m 应用程序可以调整计算 请求来适应可用的资源，并且能容忍偶尔超越时限错误，如果采用保守的资源分 配方式将会导致资源使用效率比较低【1 6 1 。此外，系统采用的算法和策略，特别是 分布式系统，主要集中在对原来像处理器、内存、磁盘等一般的资源的使用上，i c m 应用程序还要充分利用额外的硬件资源像图形加速器、视频编解码器等。新的算 法要能支持基于通用计算机簇的i c m 应用程序 分布式计算技术进行渲染不是新出现的技术，分布式计算被用到大多数产生 图像的技术，包括多边形渲染，卷积渲染，光线追踪等方面。本文主要是研究怎 样使响应时间和抖动达到最小，通过调整硬件辅助的分布式渲染来增加帧率本 文研究的目标包括以下几个方面 2 第一章绪论 1 采用硬件图形加速：大部分以i i 的分布式渲染器仅用软件实现。即使使用性能 比较低的硬件加速器，软件实现的分布式渲染器也是无法相比的，不管这个分布 式软渲染器是多么有效。 2 减少因场景复杂度的增加和节点数目增加而引起的网络带宽的增加：在一个通 用系统中，网络带宽有可能成为影响系统性能的瓶颈。尽管局域网的速度在不断 的提升，对于更大和更高分辨率图像的需求使网络带宽成为宝贵的资源。这有两 个要求：随着模型越来越复杂，分布式渲染对带宽的请求不能依赖于模型的大小， 那就是说在网络中传输的数据块应该是渲染后的点数据，而不应该是描述场景的 原数据；随着通用计算机节点数目的增加，必须想办法减少节点对网络带宽的请 求，需要一个节点产生的点信息与另外节点产生的点信息的重叠要尽量的少。 3 可以预先估计响应时间：目前，大部分的分布式渲染强调的是最大程度的获取 帧率。帧率影响着动画的平滑效果，对于交互式应用程序来说，帧率是不严格性 能评价标准。如果渲染实行管线化，不断增加帧率可能增加响应时间。并且人们 对于图像的抖动感觉更加敏感，更愿意牺牲性能来减少抖动。 本文主要是把实时的三维渲染作为一个标准的i c m 应用程序，目的是充分利用 带有硬件图形加速通用计算机组成的簇资源，把实时渲染的性能提高到为用单台 通用计算机的i n 2 倍。本文采用一套新的方法来调整计算机簇资源以提高实时渲 染的性能。在j p v m 7 l 的基础上，利用分布式的硬件加速，设计一个分布式渲染系 统来实时渲染o b j 场景。 1 2 局域网的带宽 对于i c m 应用程序的研究，特别是基于通用计算机簇的分布式三维实时渲染， 首先要考虑到当前的网络带宽是否能满足需要。表1 1 显示显示了以不同的分辨率 和压缩比( 1 0 帧何3 0 帧) 进行渲染后的图像所需的带宽。他们都是在理想的状况 下传输的最小的数据量在原来带宽是1 0 m b s 时，如果能以压缩比为5 ：1 压缩数 据，可以传输分辨率为6 4 0 x 4 8 01 6 位颜色的图像，因此局域网的带宽可以满足分布 式实时渲染渲染需要。 鉴于目前网络速度的不断提高，可以达到1 0 0 m b s 或1 0 0 0 m b s ，我们传输以 3 0 f p s 的帧率传输1 0 2 4 x 7 6 83 2 位色的图像，并且不用采用压缩【1 8 j 1 1 9 1 技术是可以达到 的。如果能以5 ：1 的压缩比的压缩比压缩数据t 2 0 1 | 2 ，可以以3 0 f p s 的帧率传输 2 4 0 0 x 1 8 3 2 位色的图像。 电子科技大学硕+ 学位论文 i c m 应用程序是以用户的感觉为基础的，因此真实度受到用户感觉的限制。这 些感觉的限制可以决定带宽请求的上限。对于三维渲染，没有必要超出人视觉分 辨能力而一味的增加分辨率。1 5 英寸的显示屏完美的显示图像，需要3 4 5 m b s ，如 果帧率为x o f p s ，则为3 4 5 m b s ，以3 0 f p s ，1 0 3 5 m b s 。如果以5 ：1 压缩数据，带宽 请求减少到6 9 m b s 和2 0 7 m b s ，6 9 m b s 目前已经很平常了，如表1 1 ，可以满足要 求。 因此，关键是在构建分布式实时渲染时，通信量与渲染后图像的大小和真实 度成正比，而不应该随着场景模型或计算机簇的大小成正比，随着网络技术的发 展，通用计算机簇在运行i c m 应用程序时，变得越来越有吸引力。 表1 - 1 不同情况网络带宽的占用 1 6 b i t s p i x e l3 2 b i t s p i x e i 视口的大小 1 珊p s 的带宽 3 0 f p s 的带宽l o f p s 的带宽3 0 私的带宽 无压缩5 ：l 压缩无压缩5 ：1 压缩无压缩5 ：l 压缩无压缩5 ：l 压缩 6 4 0 x 4 8 05 91 21 7 73 51 1 7”3 5 47 1 1 0 2 4 x z 韶1 5 o3 04 5 o 9 o3 0 0 6 o9 0 o1 8 o 1 6 0 0 x 1 2 3 6 67 31 82 1 9 67 3 21 4 6 42 1 9 64 3 9 2 2 4 x l 湖8 2 41 6 4 82 4 6 94 9 41 6 4 83 z 4 9 4 49 8 9 1 3 研究内容 在构建一个分布式实时渲染系统时，会遇到很多问题。有一些是分布式并行 程序共有的，如根本的问题是工作分区问题，因为这会影响到负载均衡，又会影 响到通信量。有些是渲染系统专有的，如在完成渲染后要对图像数据进行重组， 又要考虑很多方面的问题。本文主要集中在两个问题上，一是怎样把每一帧图像 进行分区【捌口l ，二是怎样在分布式系统中调度这些分区以满足实时渲染 1 、工作的分区和分配。在构建一个分布式渲染系统时怎样划分工作，这是分 布式渲染系统的基础，由于我们还要根据可见度进行排序，导致渲染领域更加复 杂。分区的策略对渲染的计算量及通信的数据量都有很大的影响。由于要使用硬 件图形加速设备限制了我们分配工作的方法，他要求不能使用需要访问传送给图 形设备数据的方法，因为这些数据很有可能不可用或者访问这些数据的代价很大。 4 第一章绪论 本文采用一个新的称为图像分层分解 2 4 j ( i m a g el a y e r e dd e c o m p o s i t i o n ) ，简 称i l d ，用于分布式多边形渲染的方法，它采用图像层合成的方法产生最终的图像。 i l d 的基本要求是：给定需要渲染的场景对象的集合，一个视点，在对场景集合分 配时，分配到不同节点计算机上的场景不能相互遮挡。例如，一个场景包括5 个 要显示的对象a ，b ，c ，d 和e ，如图1 - 1 ( a ) 所示对于一个两个节点的分布 式渲染系统，i l d 分区的结果是 a ，b ， c ，d ，e ，因为第一个子集中的对象 a ，町距离视点比第二个集合中的对象更近，通过组合分层把 a ，阱放在分层 c ，d ，e ) 上就构成了最终的图像。相反，把对象分解成 a ，c ) 和 b ，d ，e 在l i d 中则是错误的分解方式。 a 、 、 b c f 、 ，l 乜_ o 图1 - 1 遮挡图的示意图 刀特别适合构建分布式可视化的原因有以下几个： ( 1 ) 分布式渲染系统中的每个节点运行时，看起来好像是一个独立的渲染应用 程序。每一个节点中的资源好像一个黑盒子一样，使用硬件渲染和各种优化 更加容易。 ( 2 ) 使用少量的预处理，预先估计出每个节点要发送的数据量，当分区工作需 要进行最小化负载均衡的计算时，可以做为各个节点的传送时间的参数用以预 先估计响应时间。 ( 3 ) 把场景数据预先分发到各个渲染节点，可以避免传递多边形数据，减少了 场景复杂度对网络带宽的影响。但目前大多数分布式渲染器，他们的渲染过程 被分布在不同的节点 z s l 2 * i ，因此计算机间需要传递多边形的数据。 ( 4 ) 每个渲染节点仅需要发送渲染过的点数据，例如图1 1 ( c ) 显示 a ，b 和 c ，d ，e 两个子集的覆盖区域。一个自己的覆盖区域是指把对象投影到子 5 电子科技人学硕十学位论文 集后的边框的大小。把每个渲染节点的覆盖区域中的点发送到显示节点，在那 里合成产生最后的图像。最理想的状况分布式渲染系统需要的网络带宽与视口 的大小而不是计算机簇的大小成比例。 ( 5 ) 渲染节点不需要发送渲染场景对象后深度缓冲的数据( z - b u f f e r ) ，因为i l d 采用图像重组的方法，因此i l d 能节省将近5 0 的网络带宽。 ( 6 ) i l d 是与采用使用图像层构建的算法相兼容【2 7 1 1 2 8 1 ，这些算法把场景中的对象 被分成不同的层。这些技术准许模型设计者、用户或者渲染系统可以牺牲渲染 的质量来换取计算时日j ，从而提高帧率。 2 、任务的调度。 先要把所有的工作被预先分配成一定数目的具有几乎相同渲染时间的任务。 我们讨论两种类型的分配策略：一种是静态的，它仅仅在特定的时间进行任务的 再分配，种是动态的，由空闲的节点触发。 3 、分布式实时交互式渲染的实现。 这一部分我们主要实现实时分布式可视化系统d r r s 。在j p v m 的基础上，用 j a v a 语言和o p e n g l 三维图形库来设计实时渲染的软件系统。由两部分组成，渲染 部分和显示部分。显示部分允许用户通过键盘和鼠标来浏览o b j 场景，渲染器分布 在计算机的各个节点上，对用户来说是透明的。 1 4 论文组织 第一章，绪论章。该章主要描述了研究的目的，内容。简单介绍了任务的分区和 分配。 第二章，背景知识章。这一章主要介绍了分布式渲染的一些背景知识，包括o p e n g l 管线，并行的多边形渲染，j p v m ，j o g l 。 第三章，分布式实时渲染的任务调度方法。 第四章，详细的介绍了图像层分解，如何利用图像层分解进行场景的分解及分配。 第五章，d r r s 的具体实现细节，详细介绍了分布式实时渲染系统的实现细节。 第六章，对全文总结，并提出了下一步的工作。 6 第二章研究的背景知识 第二章研究的背景知识 这一章要讨论实现三维多边形渲染相关的背景知识例，他是实现三维分布式 实时可视化的基础。其中包括三维可视化的执行管线，以前的分布式渲染所作的 工作，实时系统的有关问题等。 2 1 三维可视化执行管线 三维图形处理分成很多部骤，称为管线。我们以o p e n g l 为例来介绍三维可 视化管线。o p e n g l 是开放图形库的缩写，大部分的图形处理器都支持o p c n g l 协 议。从一个三维点v o c s 开始，v o c s 表示在对象作标系中的点。o p e n g l 中有几类 作标系系统：对象作标系( o c s ) ，世界作标系( w c s ) ，视点作标系( v c s ) ，对象 坐标系用于对单个对象建模时用，世界作标系用于对整个场景进行管理，视点作 标系是相对于视点，o p e n g l 的管线执行如图2 1 下： i 帧缓存 l 捧 2 1 1 模型变换 图2 - i 三维可视化管线 对象作标系( o c s ) 中的点在缺省状态下与世界作标系( w c s ) 原点重合 有时对象作标系需要变换后到世界作标系中，这些操作包括了平移、旋转、放缩。 顺序是先放缩、旋转、平移，因为矩阵操作是不可交换的，所以执行顺序非常重 7 电子科技大学硕士学位论文 要，不同的执行顺序可以导致不同的结果。我们用t 代表平移变换，r 代表旋转 变换，s 代表放缩变换，t 、r 、s 都是4 x 4 的矩阵，o 表示要被变换的对象，对象 转换操作为：o w c s = f r r s l o 。相应的对象中的点都要进行上述变换： v w c s = ( t r s ) v o c s 。 2 1 2 视点变换 假设摄像机的原点被定为在世界作标系的p 点，用三个向量来表示他的直觉 坐标系 o ，z ：r t ( o ，v ) 8 、映射s 到网格单元( 舢1 ) ： 一 f p g 毛x ，y ，v ) - v f p ( o ，x ，y ，v ) o s , 0 x w ，0 y j 时，就能确保s i j 对象不能遮挡s 矿中的对象，满足正确性。为了满足最优化， 我们采用两个探索： 1 、当我们把u 中的对象移动到s “中的时候，我们选择了s i f 足迹增加最小的。 2 、停止s 。的分配的条件是当增加另一个对象到s ，使负载超出平均负载的 r 一倍，r 一略微大于1 o ，如可选择1 1 ，由我们自己设定。 为了更加详细的描述该算法，把u 中的一个子集的f r o n t i e r 定义为： f r o n t i e r ( u ) 一 a i a e ua w b e u ，( b a ) 隹e f u m ( 倘) 计算m 的p 路分区的算法的伪代码如下： s “- 妒 f 型竺掣1 ij c a n d i d a t e s a i a e f r o n i t e r ( u ) r t ( a ，v f ) + 郇i j ) t 鲫 i f ( c a n d i d a t e s - o ) t h e nb r e a k c h o o s ec h o i c e c a n d i d a t e sw h e r e f p s ( s u c h o i c 七) ，v f ) - m i n 唧。蚰f p s ( & u a 】v f ) s i fi l l s i ，fu c h o i c e r e t u r np a r t p lf ( s 如f ，s lf s - - lf ) 对于给定的分区，p a r t 荫p h l - s 嘟s l ，f 咖s 蛐l ，在第一阶段产生，如果 损耗是由负载组件决定( 如果唧a r t “阻) - m 瓿叫。r l ( s i f ) ) ，我们就做第二步， 我们可以在这阶段简化优化的问题： 1 、首先我们假设经过第一阶段，已经按照场景对象被选中的顺序给出了一个 场景对象的排序 2 、使用一个简单的损耗函数：c o s t s i m p l e = m a x 0 = i 。p i 鹪“) 根据以上的假设我们查找一个更好的负载平衡的分区：假设我们知道了了最 优值为b ，对于所有的分区p a 古完全捧序相一致，c o s t s i m p l e ( p a r t 时) 乏b ( 本文 中，与完全捧序相一致的是，不存在o 。e s o y e s ，使的当p i 时， 电子科技大学硕十学位论文 o 。在排序中位于0 。的前面) 。自始至终的贪婪算法，尽可能的寻找一个最优化的分 区。让每个子集都逼近于b 值。为了寻找b ，我们首先在 【c o s t s i m p i e 嘁f ，c o s t s i m p l p a n p p h i ) l 之间执行一个二分搜索，c o s t s i m p l e 表示我 们获取最大负载平衡的状况。可以用降6 ) 表示： c o s t s i m p l 。盖塑坠业苹叠型坠业( 4 - 6 ) 最后，假如p a r t 。是在第二阶段计算出来的分区，如果 c o s t ( p a r t 舭) c o s t ( p a r t p ，f p h l ) ，我们就选择p a n 坤，否则我们就选择p 眦，p h l 。 4 0 第五章d r r s 的实现 第五章d r r s 的实现 本文的前两章，我们已经讨论了两个构建分布式实时渲染系统重要的问题， 第一是怎样分区和分配每一帧的渲染工作，第二是怎样执行帧间的负载平衡，因 为单独的任务有不可预计的执行时间。我们采用了新的方法来解决这些问题，图 像层分解技术和动态的全局分配，这些方法适合我们的应用程序的需要实时渲染 和通用计算机网络连接起来的通用计算机簇环境。 在本章，我们解决实现d r r s 特定问题。我们描述一个分布式实时渲染系统， d r r s ，可以支持三维可交互的连续的媒体流，1 c m 应用程序使用计算机渲染同用 户交互。 d r r s 是以o p e n g l 三维图形处理库和j p v m 为基础，可以渲染w a v e f r o n t 的0 瑚。本章主要描述系统的基础架构和具体的实现细节。 5 1 基本的实现 d r r s 包含了一个显示节点，一个或多个渲染节点。在显示节点中，运行一个 d r r s 的实例。在系统启动时，显示节点负责几个方面： 1 、创建一个窗口，正确配置窗口以便让d r r s 能在上面渲染。 2 、用一个w a v a f r o n t 的o b j 文件构成的场景初始化d r r s ，把0 b ，文件转换到内 部d r r s 可以识别的格式。 在正式的执行时，通过调用调用一个正确的带有视点和渲染状态的入口点进 行帧渲染。d r r s 渲染相应的图像并给指定的窗口显示 在d m 塔中，在系统启动时显示节点通过读取和分析0 w 文件，创建场景的 静态八叉树。显示节点要创建一个窗口，并且用这窗口分解场景和初始化d r r s 。 在执行时，显示节点控制应用程序的图形用户界面，并且负责与用户交互，跟踪 用户在场景中的运动。用户可以通过键盘来浏览场景 当用户事件到达时( 如敲击键盘) ，显示节点开始渲染新的帧。当这样一个事 件到达时，显示节点计算新的视点，并把他提供给d r r s 。显示节点还要傲一些特 殊的工作，如计算i l d 分区，把新的视点和任务分配给渲染节点，接受图像层， 组建和显示最后的图像 电子科技人学硕十学位论文 在每一个渲染节点，d r r s 通过j p v m 让显示节点的实例和渲染节点的实例连 接在一起，接受渲染命令和任务的分配，发送渲染后的图像层。如图5 - 1 所示； 图5 1 d r r s 系统框架图 传送当前的帧可以和渲染下一帧交替进行。 显示节点不执行任何的渲染工作，对于计算机簇比较少，而场景复杂度在渲 染时问中占很大比例时这可能会影响到系统的性能。可以想象，当计算机簇逐渐 增大时，显示节点最终会因为协调渲染工作而使c p u 达到饱和。在这种情况下， 给定一般的通用系统，当通信和渲染都占有很大的c p u 时问的时候，显示节点不 可能再拿出空闲来进行渲染工作。随着网络接口卡和图形加速卡变得越来越强大 时，他们对占有c p u 的资源越来越少所以，根据当前的发展形势，值得重新考 虑我们的设计。特别是对于渲染离视点非常近的对象。这些对象通常足迹很大， 可能导致不同渲染节点的图像层的交叠很大，增加了通信时间。这样我们可以考 虑把他们放到显示节点上进行渲染 计算l id 的分区和分配需要计算每一个对象的足迹，他需要大量的计算。另 外这个计算可以让我们快速的剔除那些完全不在视体内的对象，节省了大部分转 换时间和剔除每一个对象中的多边形的时间。对大的场景中仅有- - 4 , 部分需要被 显示的情况的处理是十分有效的。 5 2 动态的场景分解 根据第四章，当进行场景分解时，如果一个多边形位于多个八叉树子节点中， 必须对多边形进行剖分。多边形的剖分代价是昂贵的，因为他引进了额外的顶点， 这些顶点必须被转换并进行光照计算。 第五章d r r s 的实现 如果c p u 的主频比较低，如果对有大数目多边形的大场景进行渲染，多边形 转换阶段有可能成为系统的瓶颈。当用户尽心浏览时，通常仅有场景的一部分需 要进行渲染，像以前提到的，八叉树剖分能够快速的剔除那些完全位于视体外的 对象，因此能大大缩小多边形的转换，因此能大大提升系统的性能。另外一个能 减轻c p u 负担的因素是为来通用计算机系统将更加平衡硬件厂商已经在图形加 速器上安装了专业的图形转换单元或者多个处理器，以增加多边形的转换速度。 尽管相对来说剖分多边形的损耗将会降低，但是我们还是要减少这个性能的 损耗，既然我们想在仅有一部分可以显示的场景中达到精确的负载平衡。虽然我 们进行剖分，但仍有可能被剖分的对象还是很大，不能达到实时帧率。 d r r s 中，不是一直把八叉树的叶子节点作为对象，我们有时从八叉树中选择 分解的层。在启动时，我们首先静态的剖分场景成为十分小的精细的对象。在运 行时，我们从第一层开始使用八叉树的节点，这个八叉树的节点要多于计算机的 节点，这样能保证至少一个计算机可分得一个八叉树节点对于每一个后续帧， 如果一个八叉树节点在最后一帧被渲染的时间与整个帧时相比的比率大于动态工 作分解的极限( t h r e s h o l d ) ，我们就选择他的孩子节点作为对象来进行这一帧的渲 染。同样，如果对象的足迹的大小与栅格单元的比大于动态空间的剖分极限，我 们也要动态的选择他的子节点。 当然，如果八叉树的节点是原来静态分解的叶子节点，那么我们就不能选择 他的子节点了。即使渲染时间或足迹很大我们不能动态的计算新的八叉树子节 点。当动态分解时，我们可以把子节点的渲染时间看作是父亲节点的1 8 。图5 2 显示了动态的选择八叉树的节点作为作为场景对象。 l” 么。 。 当前帧的场量对量 ，e c ，l 工l 图5 - 2 ( a ) 为场景图( b ) 为八叉树的动态选择图 另一方面，如果所有的八叉树的节点的对象在最近一帧被渲染，在这帧中， 电子科技大学硕士学位论文 我们就考虑使用这个八叉树节点作为被渲染的对象，条件是： 1 、预计对孩子节点的渲染时间与整个帧时相比要低于动态工作集合规定的极 限。 2 、孩子集合的足迹的大小与视口网格数目相比要低于动态空间规定的极限。 当聚合时，我们评估一个八叉树节点的渲染时间为他的孩子节点渲染时甸的 和。有一个细节应当考虑，当聚合时，如果节点的一些孩子超出视野而另外一些 没有，我们则考虑不聚合成父亲节点，因为这可能降低裁剪的效率。一方面，我 们聚合以减少多边形裁剪。另一方面，因为聚合，我们没有删除超出视野的孩子 节点( 因为父亲节点有部分区域在视野里) ，因此我们就要以多边形转换的消耗来 换取删除超出视野的孩子节点) ，如图5 - 3 所示： 图5 3 删除超出视点的八叉树节点 如果这些予节点包含很多多边形，有可能比裁剪他们花费的代价更大，导致 八叉树节点的渲染时间比上一帧采用的他的孩子的渲染时间还要长。这样，如果 没有足够的孩子节点在视野内，我们不用聚合为父亲节点，如我们可以采用当至 少有五个孩子节点在视野区内，我们就聚合成父亲节点。要靠经验根据在一定的 范围内测试场景的平均帧时才能决定极限的值。 我们的动态分解聚合极限值要依靠节点的数日，我们使用下面的( 5 - l x 5 - 2 ) 两 个公式来表示极限值： 1 分解极限。疆臻孺焉西昂焉高诓卜礓霸西甄陌( 5 - 1 ) 聚合极限。殖耍蕊耳谭露再焉素赢罹f 疆藁丽( 5 - 2 ) 第五章d r r s 的实现 m i n n u m o c t a n t s p e r r e n d e r e r = 1 2 5 ，m a x o c t a n t s p e r r e n d e r e r = 2 0 0 d e c o m p t h r e s h o l d 和a g g r e g a t e t h r e s h o l d 被用于工作和空间的动态分解和聚合。 除了在上面提到的动态的场景对象的选择，下面的几个细节也能影响到d r r s 的性能： 1 、一般目前比较通用的网络是1 0 0 m b s 的交换以太网络，渲染节点在发送到显示 节点的时候压缩每一图像层，我们采用软件游程编码。 2 、再进行八叉树分解一个场景时，我们通常需要分解多边形。对于包含纹理和平 滑阴影的场景，多边形的剖分包括计算新的每个顶点的纹理坐标和法向量。由于 剖分很复杂，我们只关心系统层面的问题而不是渲染方面的问题。我们采用了 o p e n o l 的动态剪切技术来裁剪超出八叉树节点的多边形。这让我们在计算纹理和 阴影时可以绕过静态多边形的剖分，这可能会使性能有所所降低。多边形的转换 阶段执行动态裁剪，根据场景的不同，一般要占用1 0 - 2 0 的处理时间。 5 3 实现的细节 5 3 1d r r s 中的公共部分 d r r s 系统包括显示节点和渲染节点，在实现时我们首先要把每个场景文件分 发到显示节点和各个渲染节点，这样以后我们在任务传输时仅传输任务的标识号， 具体就仅传输八叉树的子节点号，这就需要在显示节点和渲染节点初始化时都要 先输入场景文件，然后生成八叉树。 八叉树的类可以表示为： p u b l i cc l a s so c t r c ci m p l e m e n t sd r a w a b l e p r i v a t e v e c t o rt r i a n g l e l i s t ； p r i v a t eb o o l e a ni m t ； p r i v a t ei mn u m b e r o f f r i a n g l e s ； p r i v a t ei mn u m b e r o 饿o d e s ； p r i v a t ev 删m i n b o u n d s , m a x b o u n d s ； p r i v 砒ef l o a tw i d t h ； p r i v a t ei n tn u m o f d r a w n o d e s ； p r i v a t ei mr e n d e r e d t r i s ； p r i v a t es t a t i ci n tn o d e n u m = o ； 电子科技入学硕+ 学位论文 p r i v a t en o d er o