（计算机科学与技术专业论文）基于pc集群机的并行图形绘制系统研究.pdf

摘要 摘要 随着计算机图形学理论的不断完善和计算机图形处理软、硬件的持 续发展，图形绘制技术已经深入应用到人类生产、生活的方方面面，在 工业设计、大众娱乐、科学研究等各个应用领域发挥着重要作用。同时 社会的进步电使褥各个应用领域持续不断地对图形绘制技术提出挑战； 更强的真实感，更快的处理速度，更复杂的场景模型，更高的显示尺寸 和分辨率等。因此将并行计算理论和方法引入图形处理领域而成的并行 绘制技术成为高性能图形处理的必要手段。 历经二f 多年的高速发展，个人计算机( p c ) 的图形处理能力日益强 大。当前，在p c 组成的集群机上构建并行图形绘制系统实现高性能图形 绘制，具有高性价比、使用灵活、扩展性好等特点，成为并行绘制技术 的研究热点。 本文对基于p c 集群机的并行绘制系统的研究中在三个方面做出了 创新。 首先，对并行绘制体系结构这一核心问题进行了研究，传统上并行 绘制体系结构按照图形处理流水线的并行方式可以分为s o r t f i r s t 、 s o r t i d d l e 和s o r t l a s t 三种基本类型。在p c 集群机的并行绘制系统 中一般采用s o r t f i r s t 和s o r t l a s t ，或者它们的混合式体系结构。本 文提出了基于动态绘制组的混合式自适应并行绘制体系结构。动态绘制 组是本体系结构的基本绘制功能单元，由数目可变的p c 节点机组成，包 括一个主节点和数量可变的从节点。各动态绘制组之间按s o r t f i r s t 并行绘制流程工作。动态绘制组内部主从节点问的并行绘制工作流程由 主节点确定，可以在s o r t f i r s t 和s o r t l a s t 两种工作流程之间切换来 适应不同的工作条件，以求得最佳的绘制性能。切换是自适应的，体现 了本文并行绘制体系结构支持两种s o r t 工作方式的混合和自适应切换 的特点。 其次，提出了支持异构数据的场景组织框架一s c e n e f r a m e w o r k 。并行 绘制系统按照对场景数据的控制方式可以分为立即模式和保留模式，其 中保留模式并行绘制系统对场景数据有一定控制权，有利于减少通信开 销和优化绘制，更适合基于p c 集群机的并行绘制系统。保留模式的场景 组织形式主要解决在并行工作环境下如何表达场景逻辑关系、几何数据 采用何种结构等问题，与并行绘制系统工作流程密切相关。本文提出 摘要 s c e n e f r a m e w o r k 的场景组织框架，它用场景图结构表达场景各部分的逻 辑关系，但与普通场景图= _ i 同的是它本身不定义具体场景数据结构，只 基于面向对象的继承和重载规则定义了场景组织框架，给出并行绘制所 需的与场景操作相关的最小接口集。不同数据结构的场景定义只需重载 这些接口就可以融入s c e n e f r a m e w o r k 定义的场景图，并在并行绘制流程 中协同工作。因此，s c e n e f r a m e w o r k 是一个通用数据结构的高层场景图 实现框架，为综合利用现有丰富的场景定义提供了可能，拓宽了并行绘 制系统的应用范围。 再次，对与并行绘制系统性能密切相关的负载平衡问题做了深入研 究。结合本文混合式自适应并行绘制体系结构提出基于节点迁移的负载 平衡策略。与传统负载平衡算法基于图像空间划分的模式不同，基于节 点迁移的负载平衡策略下图像空间的划分固定不变，而通过调整对应图 像空间子区域的动态绘制组的整体计算能力来适应负载变化。动态绘制 组计算能力通过各从节点在各动态绘制组之间的迁移进行调节，传统负 载平衡算法因图像空间划分改变需要进行数据调整带来额外计算负担， 本文平衡策略具有算法开销小、速度快的优点。 最后，本文给出了基于以上各项技术的并行绘制原型系统 p a r a l1 e 卜s g 的具体实现，列出了相关测试数据，并讨论可以改进的环 节和下一步研究的方向。 关键词：并行绘制，体系结构，动态绘制组，场景组织，负载平衡 a b s t r a c t w i t ht h ed e v e l o p m e n to ft h e o r i e sa n dt e c h n o l o g i e so fc o m p u t eg r a p h i c s ，t h e t e c h n o l o g yo fg r a p h i c sr e n d e r i n gg o e sd e e pi n t om a i nf i e l d so fh u m a nb e i n g s p r o d u c t i o na n dl i f es u c ha sd e s i g n ，e n t e r t a i n m e n t ，s c i e n c ea n de t c o nt h es a m e t i m e t h ep r o g r e s s i v es o c i e t yk e e p sc h a l l e n g i n gt h et e c h n o l o g i e so fg r a p h i c s r e n d e r i n go nv a r i o u sa s p e c t s ：m o r er e a l i s t i c ，h i g h e rs p e e d ，c o m p l e xs c e n ed a t a s e t ， h i g h e rd i s p l a ys i z ea n dr e s o l u t i o na n ds oo ns o ，b yi n t r o d u c i n gt h e o r i e sa n d m e t h o d so fp a r a l l ec o m p u t i n gi n t ot h ef i l e do fg r a p h i c sp r o c e s s i n g ，t h ep a r a l m r e n d e r i n gb e c a m e a ni m p o r t a n tt e c h n o l o g yt o i m p l e m e n th i g hp e r f o r m a n c e g r a p h i c sr e n d e r i n g p e r s o n a lc o m p u t e r ( p c ) i sb e c o m i n gm o r ea n dm o r ep o w e r f u li ng r a p h i c s p r o c e s s i n gw i t hh i g hs p e e dd e v e l o p m e n to fm o r et h a nt w e n t yy e a r s n o w a d a y s ， p a r a l l e lg r a p h i c sr e n d e r i n gs y s t e m sb a s e do np cc l u s t e rb e c o m eh o t s p o t i th a s m a n ya d v a n t a g e ss u c ha sh i g h e rr a t i oo f p e r f o r m a n c ea n dp r i c e ，m o r ef l e x i b l ea n d s e a l a b l e t h i sd i s s e r t a t i o nm a k e sc o n t r i b u t i o no nt h r e ea s p e c t st ot h er e s e a r c ho f p a r a l l e lg r a p h i c sr e n d e r i n gs y s t e mb a s e do np cc l u s t e r f i r s t ，p a r a l l e lr e n d e r i n ga r c h i t u r e ，t h ec o r ei t e mo fp a r a l l e lr e n d e r i n gs y s t e m ， i sr e s e a r c h e d t r a d i t i o n a l l y , p a r a l l e lr e n d e r i n ga r c h i t u r ec a nb ec a t e g o r i z e di n t o t h r e ec l a s s e s ，s o r t f i r s t ，s o r t m i d d l ea n ds o r t l a s t ，b ym e a n so fm u l t i p l er e n d e r i n g p i p e l i n e sa r eo r g a n i z e d p a r a l l e lr e n d e r i n gs y s t e m sb a s e do np cc l u s t e ru s u a l l y a d o p t s o r t f i r s ta n ds o r t l a s ta r c h i t e c t u r e s ，o rh y b r i do n e t h i sd i s s e r t a t i o n p r o p o s e sah y b r i da d a p t i v ea r c h i t u r eb a s e do nd y n a m i cr e n d e r i n gt e a m d y n a m i c r e n d e r i n gt e a m a c t sa st h eb a s i c r e n d e r i n g u n i to ft h e p a r a l l er e n d e r i n g a r c h i t e c t u r e ，a n di ti sc o m p o s e do fm u l t i p l ep cn o d e s ，i n c l u d i n gam a s t e ra n d v a r i o u sn u m b e r so fs l a v e s t h ed y n a m i cr e n d e r i n gt e a m sw o r ku n d e rt h ep a r a l l e l r e n d e r i n gw o r k f l o wo fs o r t f i r s ta r c h i t e c t u r e a n di nt h et e a mi t s e l f , t h em a s t e r s w i t c h e st h ew o r k f l o wb e t w e e ns o r t f i r s ta n ds o r t 1 a s tb yc o n d i t i o n si no r d e rt o c h a s eh i g h e rp e r f o r m a n c e t h es w i t c t li sp r o c e s s e da d a p t i v e l yw h i c hr e f l e c t st h e c h a r a c t e r i s t i c so fh y b r i da d a p t i v ea r c h i t u r e s e c o n d ，t h ed i s s e r t a t i o np r o p o s e ss c e n e f r a m e w o r kw h i c hi sa s c e n e o r g a n i z a t i o ns u p p o r t i n gh e t e r o g e n e r i cd a t as t r u c t u r e s p a r a l l e lr e n d e r i n gs y s t e m s 1 1 a b s t r a c t c a nb ec l a s s i f i e da si m m e d i a t e m o d ea n dr e t a i n e dm o d e ，a n dr e t a i n e dm o d em o r e s u i t a b l ef o rp cc l u s t e nt h ed i s s e r t a t i o nr e s e a r c ho nt h es c e n eo r g a n i z a t i o nw h i c h i sa k e y i s s u eo fr e t a i n e dm o d e p a r a l l e lr e n d e r i n gs y s t e m s ，a n d t h e s c e n e f r a m e w o r ks u p p o r t i n gh e t e r o - g e n e r i cd a t as t r u c t u r e s i s p r e s e n t e d t h e s c e n e f r a m e w o r kd o e s n td e f i n ean e ws c e n ed a t as t r u c t u r e ，b u ts u p p l i e sa n i n t e r f a c e ss e tr e l a t et os c e n eo p e r a t i o nu n d e rt h ei n h e r i t a t i o na n do v e r l o a d i n g p r i c i n p l e so fo o d s c e n ed e f i n i t i o n sw i t hd i f f e r e n td a t as t r u c t u r e sc a nc o o p e r a t e u n d e rt h i ss c e n e f r a m e w o r k a f t e r t h e yi m p l e m e n tt h e i n t e r n c e w i t ht h e s c e n e f r a m e w o r ks u p p o s i n gh e t e r o g e n e r i cd a t a ，p a r a l l e lr e n d e r i n gs y s t e m sc a n u t i l i z ea b u n d a n te x i s t i n gs c e n ed e f i n i t i o n sa n de x t e n dt h ea p p l i c a t i o na r e a t h et h i r d ，d e e p l yr e s e a r c hi sd o n eo nl o a db a l a n c es t r a t e g y ，a n dal o a d b a l a n c es t r a t e g yb a s e do ns l a v em i g r a t i o ni sp r e s e n t e d t h i sl o a d b a l a n c es t r a t e g y i sd i f f e r e n tf r o mt r a d i t i o n a ll o a db a l a n c ea l g o r i t h m sw h i c hb a s e do nc h a n g i n gt h e p a r t i t i o no f i m a g es p a c e u n d e rt h i ss t r a t e g yt h ei m a g es p a c ep a r t i f i o ni sc o n s t a n t ， b u ta d j u s t i n gt h er e n d e r i n ga b i l i t yo fd y n a m i cr e n d e r i n gt e a m sc o r r e s p o n d i n gt o s u b t i l e so fi m a g es p a c et h r o u g hc h a n g i n gt h en u m b e ro fs l a v e si nt e a m s l o a d b a l a n c es t r a t e g yb a s e do ns l a v em i g r a t i o nh a sl o w e rd a t aa d j u s t a t i o na n dh i g h e r s p e e d a tl a s t t h ed i s s e r t a t i o ni n t r o d u c e sp a r a l l e isg a ni m p l e m e n t a t i o no ft h e p a r a l l e lr e n d e r i n gs y s t e mb a s e do np cc l u s t e r ，a n ds o m ee x p e r i m e n t sd a t aa r e s u p p l i e d a 1 s o ，i t e m sn e e dt ob ei m p r o v e da n d t h ef u t u r ew o r k sa l ed i s c u s s e d k e y w o r d s ：p a r a l l e lr e n d e r i n g ，a r c h i t e c t u r e ，d y n a m i cr e n d e r i n gt e a m ，s c e n e o r g a n i z a t i o n ，l o a db a l a n c e 笫l 章绪论 第l 章绪论 在图形处理硬件日益强大的今天，并行图形绘制技术仍然受到研究者们 的广泛重视，因为社会的进步推动着应用领域不断地对图形处理技术提出更 高的要求，总是超出了单个图形硬件的处理能力。基于p c 集群机的并行图 形绘制系统主要研究在p c 集群机环境下的并行图形绘制技术，它是实现高 性能图形绘制的重要手段之一。本章从研究背景开始，遮两讨论并行图形绘 制系统的分类和研究重点，最后给出本文的研究内容和章节安排。 1 。i 研究背景 i i i 并行绘制的必要性 计算机图形学是训算机科学与技术的一个重要分支，它的目的是利用计 算机的计算能力，将用数学方法描述客观世界中物体与可见光相互作用的模 型生成具有真实感或非真实感的图象。从2 0 世纪6 0 年代 1 ( 】1 末期开始，计 算机图形学理论不断完善，图形处理的软、硬件技术持续进步，经过近4 0 年的发展，图形绘制技术已经深入地应用到设计、娱乐、科学研究等各个方 面，成为了人类生产、生活不可缺少的一个部分。 计算机图形学的发展历程伴随着三大趋势： 第一、更强的真实感绘制，表现为包括光线跟踪算法和辐射度方法在内 的大量复杂真实感绘制算法的出现和迅速发展。1 9 8 0 年w h i t t e d 提出了第一 个整体光照w h i t t e d 模型 1 1 1 ，提出了一般性光线跟踪算法的范例，综合考 虑了光的反射、折射透射、阴影等因素，相对简单光照模型具有更逼真的绘 制效果。1 9 8 4 年，美国c o r n e l l 大学 3 4 的学者将热辐射工程中的辐射度方 法引入到计算机图形学中，用辐射度方法成功地模拟了理想漫反射表面问的 多重漫反射效果，将真实感图形绘制推进到一个新的阶段。经过二十多年的 发展，光线跟踪和辐射度模型成为当今真实感图形学中最重要的两个图形绘 制技术，以它们为基础衍生出大量的真实感图形绘制算法 4 ，1 0 ，4 8 ，8 1 ， 算法复杂度越来越高，所模拟的场景越来越复杂，图形效果越来越真实，在 计算机辅助设计和图形学领域得到了广泛的应用。 第二、更高的模型复杂度。随着c a d 软件的进步和，一些先进的精密建模 浙v e 大学裤 ：学位论文：基于p c 集群帆的并行蹦形绘制系统研究 设备如核磁共振、c t 和激光扫描仪等的出现，模型的精度和复杂度大为提高。 同时场景范围迸一步扩大，包括大范围的地形和环境，使得模型复杂度和数 据量进一步增加。如北卡大学w a l k t h r o u g h 计划 “6 的d o u b l ee a g et a n k e r 模型有8 千3 百万面片，而斯坦福大学数字米开朗基罗计划 5 3 中的大卫雕 像更多达2 0 亿面片，数据量十分惊人。 第三、更快的图形处理速度。直接反映为计算机图形处理硬件的迅猛发 展。计算机图形处理硬件的发展大致经历了五代 2 ，1 1 2 ，每一代中都有代表 性的关键技术得到突破和应用。上个世纪7 0 年代末到上个世纪8 0 年代初， 随着集成电子线路的发展，出现了第一代图形体系结构，能够完成几何变换 和裁剪，绘制基于线框图表示的几何对象。到了上个世纪8 0 年代后期，第 二代图形芯片功能得到了提高，支持显示内存并且拥有很强的计算能力，支 持深度缓冲区和背面删除，能够生成光滑的g o u r a u d 光照的图像。上个世纪 9 0 年代，图形芯片增加了更多的图形功能，包括纹理映射和反走样，增强了 图形显示的真实感，使得虚拟现实技术和仿真技术向其它领域发展并得到了 推广应用。到本世纪初计算图形芯片已经发展到了第四代，主要特点是以局 部光照模型算法为基础，支持硬件光源和多种纹理贴图( 凸凹纹理贴图、压 缩纹理贴图，并行纹理通道支持) ，s i m d 指令，该代图形芯片的主要目标是 支持更快的三角形处理和实时的真实感图形绘制 5 6 ，7 5 ，7 7 ，8 0 。目前的第五 代以可编程图形处理芯片一现代“o p u ”一的兴起和蓬勃发展为标志 1 1 2 。 现代“g p u ”将图形处理流水线中的顶点处理和像素处理交由芯片内的顶点处 理器和像素处理器完成，分担了原来必须由c p u 完成的大量计算任务，使得 图形处理性能大为提高。同时，现代“o p u ”提供了高级语言编程接口供用户 灵活操纵图形处理流水线，可以方便高效地实现大量特效渲染。历经五代的 发展，无论是应用于专业图形处理机的高端图形硬件还是应用于个人计算机 ( p c ) 的消费级图形处理卡，都获得了长足的进步。尤其是后者，随着个人计 算机的大规模普及，受庞大市场的驱动在最近十余年得到了飞速发展，性能 6 9 个月就翻一倍，发展速度两倍于摩尔定律。2 0 0 6 年最新的图形处理卡一 以n v i d i a 公司的g e f o r c e7 系列e 7 3 和a t i 公司的r a d e o nx 系列 3 为例一 的制造工艺达到0 0 9um ，晶体管数量超过3 亿个，核心频率达到6 5 0 m h z ， 最大显存容量5 1 2 m b ，显存带宽超过5 0 g b s e c ，具有8 个顶点处理单元和4 8 个像素渲染单元。它i t 的顶点处理速度超过1 6 s e a ，像素填充率超过l o ( ； p i x e l s s e c ，分辨率达到2 5 6 0 1 6 0 0 ，性能已经超过了几年前专业图形工作 站的高端图形处理硬件。因此近年来采用便宜的p c 来满足部分图形处理领域 第j 章绪论 的要求已经成为现实。 虽然图形处理硬件的处理能力和处理速度都提高迅速，但是面对越来越 复杂的绘制算法和庞大而复杂的场景模型数据，独立图形硬件处理起来仍然 捉襟见肘，面向个人用户设计的p c 的图形处理能力更加难以应对。而且从二 十年来的发展趋势看，图形处理硬件技术的提高总是无法跟上社会应用领域 需求的增长，因此并行图形处理技术作为一种高性能图形绘制的解决方案一 直受到研究者的重视，而基于p c 集群机的并行图形绘制系统因为诸多优点成 为近几年来的研究热点。 基于p c 集群集的并行图形绘制系统用便宜但功能日益强大的p c ，依托 高速网络( 千兆局域网、m y r i n e t 等) 组建为p c 集群机作为硬件平台，在此 硬件平台上构建并行图形绘制系统作为软件平台，可以将单个p c 无法完成的 绘制任务分布到集群机的多个p c 节点上完成，实现高性能图形绘制。相对于 昂贵的专业图形工作站，基于p c 集群机的并行绘制系统具有以下优势 9 0 ： 1 高性价比：一个3 2 个p c 节点的p c 集群机只需百万人民币左右，而同 级别处理能力的高端专业图形工作站需要数百万美元，组建p c 集群 * j l * h 对便宜许多； 2 升级方便：p c 集群机的每个节点都是独立的p c ，可以花很小的代价 按照当前最新技术成果更换配件，使p c 集群机性能保持最新。相对 而言，传统专业图形机内部共享内存和i o 子系统，更新换代的代价 常高得难以接受。 3 高可扩性：p c 集群机的计算速度、存储容量等性能在一定范围内大 致随其拥有的p c 节点数量的增民而线性增长，这使它易于扩展以满 足更高的处理要求。而专业图形机的扩展性逊色不少。 4 使用灵活：p c 集群机中的节点相互依赖性小，可以相对独立的完成 不同任务，并且可以不局限于图形处理领域，而图形工作站是专为 图形处理设计，应用领域受限制。 5 多屏拼接显示墙：通过在指定p c 节点上连接投影仪，基于p c 集群机 的并行图形绘制系统可以方便地构建多屏拼接显示墙，提供更广的 视域范围和更高的分辨率，营造沉浸式的虚拟环境。 1 1 2 典型的图形流水线 图形处理过程通常用流水线模型进行描述。图形处理流水线与c p u 流水 浙江大学博1 一学位论文基于p c 集群机的并行幽形绘制系统研究 线的概念相似，它将整个图形处理过程划分为多个流水阶段，以流水作业的 方式分阶段实现图形计算。当前工业界占主导地位的两个图形处理库一 o p e n 6 t 和d i r e c t 3 d 一具有类似的流水线模型，其中o p e n g l 更接近硬件底层， 使用灵活，技术标准透明更易于取得技术支持，所以当前绝大多数的并行图 形绘制系统是在o p e n g l 的基础上进行并行扩展。图卜l 是o p e n g l 的典型图 形流水线 9 5 ，它描述了场景数据经过几何处理( g e o m e t r yp r o c e s s ) 和光 栅化( r a s t e r i z a t i o np r o c e s s ) 后转化成可在显示设备上显示的像素的过程。 其中，应用程序作为发出指令的数据源，是整个流水线的起点，在应用程序 和显示之间阴影部分的操作由o p e n g l 完成。 黎兰姜篓l i 蒸鬻愁蹇。麟攀篓寨 。囊。7 。”t。瓣鬃黝静萝麓瓣“。囊、。耄。“ 6 。g 。誊曩 寨鬻蒸鬻辫凳剖鬻黍i 寨鬈蒸鬻鬻辫纂剩寨纂 黼焉黧震 ；t _ 6 10 。 - 。”， 黧鬻攀麟鬻i 澍帧缓存j i 纛i i | 蘩l 兰垦垒垡 图1 1 典型的图形流水线。 o p e n g l 定义了一组面向应用程序与硬件无关的应用程序接口规范，并包 含了一个o p e n b l 状态机，硬件体系结构设计者必须实现o p e n g l 状态机并支 持o p e n g l 接口规范。下面简单介绍图l1 所示的图形流水线的几个基本过程 9 5 。 第1 审绪论 命令处理( c o m m a n dp r o c e s s i n g ) 。命令处理阶段负责处理应用程序产生的 几何命令数据流。命令大致可划分为两种，种是用来设置和改变o p e n g l 的 状态，但是这些命令的使用频率比较低。另外一类命令为几何图元命令，顶 点参数定义与三角形定义，这类命令的使用频率非常地高。三角形定点属性 包括位置、法向量、纹理坐标、颜色信息、材质。这些顶点属性位置属性以 外，其它属性都保存在当前顶点的状态变量中。命令处理器将顶点组合为3 维空间的三角形，并且将这些三角形发送到随后的流水线单元，同时它还负 责维护纹理对象与显示列表的定义。显示列表是一组经过编译的o p e n g l 命 令，提供快速的三角形组绘制能力。纹理映射用于模拟物体表面丰富的色彩 图案，提高计算机图形绘制的真实感。第四代的图形加速卡支持多种真实感 图形绘制的纹理映射方式，包括凸凹纹理，多重纹理，3 d 纹理和立方体环境 纹理映射。 几何变换( t r a n s f o r m a t i o n ) 。该流水线单元接受三维对象空间的三角形， 根据模型视图4 4 矩阵变换到世界空间坐标系统。这个4 4 的矩阵将对象 空间的矩阵变换到世界空间坐标系统，该坐标系统眼睛位于原点，眼睛观察 方向为z 轴的负方向。模型视图的4 4 矩阵可以表达任意序列的几何变换， 平移，旋转，缩放，剪切，投影操作。经过模型视图矩阵变换得到的世界坐 标，根据透视投影矩阵变换到裁剪坐标系。裁剪坐标系的范围为( 一l ，一1 ，一1 ) 到( 1 ，1 ，1 ) ，范围之外的三角形被裁减，不再送到下一级流水线。法向量 直接被变换到世界坐标。纹理坐标利用纹理变换矩阵生成最终的纹理坐标。 当所有的变换都完成之后，得到归一化的设备坐标系的三角形。这些三角形 将经过光照处理和片断处理最终转化为像素而被写入缓冲区。 光照处理( l i g h t i n g ) 。该阶段接受归一化的设备坐标系的位置和归一化的 法向量的三角形，根据计算机图形的局部光照理论，和三角形的材质，独立 地计算出每个顶点的光照效果。多个光源的光照效果将被叠加计算。光源的 类型包括环境光，点光源，锥光源，允许计算高光区域和光源能量衰减。典 型的光源参数包括位置，亮度参数，衰减系数，和聚光灯。 扫描转换( r a s t e r i z a t i o n ) 。输入一个屏幕空间三角形的三个顶点，产生 三角形的内部采样一一片断( f r a g m e n t ) ，每一个采样为一个屏幕像素。每 个像素的属性一般包含颜色，深度和纹理坐标，这些数据是根据三个顶点的 属性采用双线性插值的方法生成。光照插值的方法可分为两种，g o u r a u d 和 p h o n g 。这个无纹理的片段将发送到纹理映射单元。当程序设置了不可见删除 属性，那么三角形法向量为负的面是不可见面将被删除。例如，o p e n g l 默认 浙江大学博：学位论文基于p c 集群崩【的并行图形绘制系统研究 正面为逆时针方向( c o u r t t e z c 1 0 c kw js e ) ，三个顶点构成顺时针方向( c l o c k w i s e ) 的三角形部可见，将被删除。 纹理映射( t e x t u r em a p p i n g ) 。基本的纹理操作足根据片断的纹理坐标将 一个纹理映射到一个透视变换后的三角形。般而言，纹理图像不能正好映 射到目标区域，最高细= 常层次的纹理图像可能比目标小，也有可能最低细节 层次的问题图像比目标区域大，因此需要进行纹理图像过滤操作以或的最接 近的纹理映射效果。典型的过滤器包括点采样，双线性插值和三线性插值。 点采样使用最接近的纹理元表示目标像素的纹理，双线性插值算法根据周围 的四个纹理元的权重计算目标像素的纹理数值。由于三角形投影到屏幕区域 大小变化很大，因此m i p 纹理映射是常用的方法。m i p 纹理映射使用多个纹 理层次细节表示纹理对象，每一个细节层次的纹理图像的宽度和高度是其低 一细节层次的两倍，从而形成多个预定义细节层次的纹理图像。通常一个像 素所对应的纹理元总是介于两个细节层次之间，利用两个细节层次的纹理元 可以得到三线性插值的像素纹理数值。 片段合成( f r a g m e n tc o m p o s i t i o n ) 。片段合成单元接受经过纹理映射的片 断，片断包括颜色，深度等属性，片段合成单元的职责是将这个片断和当前 的多个缓冲区合成，例如颜色缓冲区，深度缓冲区等。首先，片断的每个像 素的深度和当前缓冲区的像素的深度做比较，如果片断的像素的深度值小， 那么片断上的像素可见，应该被存储到深度缓冲区，否则它是被深度缓冲区 的像素遮挡而不可见，应该被抛弃。片断的像素颜色的a l p h a 分量代表改像 素的透明程度，1 o 表示不透明，0 则表示完全透明，0 0 1 0 之间的数值 表示半透明。片段合成单元根据片断的像素的a l p h a 分量和缓冲区的对应像 素做颜色混合，结果得到两者线性合成的颜色。模板操作( s t e n c i1b u f f e r ) 根据模板函数生成缓冲区，根据用户定义的模板函数决定像素的取舍。累积 缓冲区( a c c u m u l a t i o nb u f f e r ) 主要用来做超级子采样( s u p e r - s a m d l i n g ) 和运动模糊( m o t i o nb l u r ) 。 显示( d i s p l a y ) 。目前的显示设备主要为光栅显示器，采用逐行或隔行扫 描的方式，使用固定的刷新频率，每一帧的每一个像素都需要刷新和显示。 其刷新顺序从左上角开始扫描，到右下角扫描结束。般显示系统包含水平 扫描系统和垂直扫描同步控制系统。只有当每帧显示扫描结束后，图形流水 线才能将后台的缓冲区拷贝到前台缓冲区，供下一帧的图像显示使用。 上面的阶段构成了一个基本的顺序图形流水线，其中命令处理、几何变 换和光照处理属于几何处理过程；扫描转换、纹理映射、片段合成属于光栅 第1 章绪论 化过程。在本文以后的叙述中，图形处理流水线只用几何处理和光栅化两个 基本过程来描述，而不再详细指暖属于上述何种阶段。图形处理的流水线模 型是并行图形体系结构的设计基础。 1 1 3 并行多边形绘制 多边形绘制是计算机图形绘制方式之一，也是并行图形绘制的常用方式， 其他并行图形绘制方式还有劳行点绘制和并行体绘制等，本文采用并行多边 形绘制方式。 多边形绘制是用多个多边形来逼近物体的表面，并使用简单光照模型( 如 o o u r a u d 和p h o n g ) 的绘制方法。多边形绘制简洁、易于实现，尤其适合硬件 实现，且其真实感效果能满足大多数应用的需要，是使用最为广泛的绘制方 法。图形库o p e n o l 和d i r e c t 3 d 以及大部分的图形硬件都基于多边形绘制方 法构造。 在多边形绘制中，三角网格是目前最常用的物体外表面的表达形式。特 别是在处理性能要求较高的应用中，三角网格已取代了传统的c a d ( c o m p u t e r a i d e dd e s i g n ) 表面的表达形式( 如：n u r b s 表面) ，其中重要原因 4 6 有： 1 三角网格具有强大的表面表达能力，即：任何拓扑和任意形状的模 型外表面都能用三角网格进行表达，而且这种表达方式不需要满足 复杂的片内光滑条件； 2 。对三角面片的几何处理和绘制已得到高速图形硬件的支持： 和n u r b s 曲面片相比，三角面片有更简单的数学表达形式，从而使三角 网格模型中的大部分用来获取与n u r b s 相同的逼近程度。然而，光滑表面用 分片线性的三角网格来表示时，对三角形边氏减半可以减少4 倍的误差，这 意味着三角形的数量与逼近误差成反比。因此，根据表面曲率( 或形状复杂 度) 调整三角网格的顶点的密度可以更好地逼近模型的外表面。 多边形绘制过程遵从图卜1 经典图形处理流水线，它具有如下特点： 1 几何变换的输出为光栅化的输入，两者计算属性不同 6 5 ：几何变 换处理模型的物理坐标、浮点运算密集：光栅化处理模型的屏幕坐 标、整数运算( 主要为整数加法) 密集。几何变换和光栅化都由多 个计算步骤组成，经过图形学的充分研究，这些独立的计算步骤的 输入输出定义明确，算法成熟。这些特点使得多边形绘制非常适合 于模块化实现。 浙江大学博士学位论文：基于p c 集群机的并行图形绘制系统研究 2 多边形绘制的基本处理单元为三角面片，两个三角面片的计算大部 分可分离处理。除了“片段合成”步骤中，当它们的像素有重合时， 其中一个面片的部分像素的可见性需引用另一个面片的信息来判定 外，在此之前的其他步骤中，两个面片的计算不需相互引用，也没 有顺序的要求。数据弱相关的特点使得多边形绘制算法非常适合并 行处理。 多边形绘制功能模块化和数据弱相关性的特点满足并行计算理论中“近 似易并行”计算 1 1 0 的要求，多个图元可以乱序处理，有利于并行化绘制。 通常将多边形数据剖分成多个独立的数据流( d a t as t r e a m s ) ，同时将多条 绘制流水线并列，并行地处理这些独立的数据流，如图卜2 。这种方式的并 行效果不受绘制流水线级数的限制，只受制于处理器数目和通讯带宽。数据 并行方式有良好的可扩展性，能构建庞大的、包含上百个处理单元的绘制系 统 1 6 。 睁p 一一睁 p 睁一睁、 i 帧缓存 l 图卜2 数据流的并行 数据并行 绘 制 流 水 化 有三点理由使得并行多边形绘制技术成为基于p c 集群机的并行图形绘 制系统的主要研究方向： 1 多边形绘制算法内在的可并行性是多边形并行绘制技术的基础； 2 当前工业标准的主流图形库o p e n g l 和d i r e c t 3 d 都基于多边形绘制技 术构造； 3 目前应用于p c 的主流图形处理卡完全支持多边形绘制； 第1 章婧论 本文的基于p c 集群机的并行图形绘制系统也是以并行多边形绘制技术 为基础，后文中所述及“并行图形绘制”若无特别指出，均默认为“并行多 边形图形绘制”。 1 2 并行图形绘制系统分类 并行图形绘制系统种类很多，不同类型的并行图形绘制系统其运行机制 和功能侧重点各不相同，在不同的应用环境下性能差异很大，具有明显的个 体特征。目前常见的有以下三种分类方式： 1 2 1 按场景数据归属判断时机分类 并行图形绘制系统中，场景绘制由p c 集群机中担任绘制任务的p c 节点 完成，每个p c 节点上的图形处理卡都是一条完整的图形绘制流水线，包括几 何处理和光栅化两个基本过程，担任绘制任务的p c 节点称之为绘制服务器。 绘制时，场景数据需要按照一定的任务划分策略分配到不同的绘制服务器上， 这个数据划分和分配的过程称为归属判断( s o r t ) 。m o l n a r 6 9 等人根据归 属判断发生的方式和时机，将并行图形绘制系统归为三类：s o r t f i r s t ， s o r t m i d d l e ，s o r t l a s t ，女口图l 一3 所示。 s o r t f i r s t 类并行图形绘制系统的归属判断在几何处理之前进行，最终 显示屏幕的图像空间被划分为多个区域分配给不同的绘制服务器。绘制每一 帧前先根据场景几何数据在显示屏幕上的投影确认负责处理的绘制服务器， 然后将相应数据发送到此绘制服务器处理，绘制完成后将所有绘制服务器的 结果拼接成最终显示图像。s o r t f i r s t 的优点是各条流水线完整而独立，故 特别有利于构建集群式并行图形绘制系统。归属判断是此类并行图形绘制系 统的主要开销和瓶颈所在。典型的s o r t f i r s t 类并行图形绘制系统有 w i r e g l 7 ，9 ，4 1 、d i s p l a yw a u 5 9 等。 浙江大学博士学位论文：基于p c 集群机的并行图形绘制系统研究 0 r 嚣示孱j靠 0 二 1r 显示屏j嚣 g 几何处理r 光栅化 ( 1 ) s o r t f i r s t( 2 ) s o r t m i d d l e( 3 ) s o r t l a s t 图卜3 按照归属判断分类 s o r t m i d d l e 的归属判断发生在几何处理之后、光栅化之前，即在几何 处理阶段每个服务器处理整个场景数据的一部分，几何处理后的输出按照屏 幕分块送入相应流水线的光栅化处理阶段。s o r t m i d d l e 类并行图形绘制系 统要求得到绘制流水线几何处理后、光栅化之前的中间结果进行重分布，而 p c 一集群机所采用的商业图形卡一般将几何处理和光栅化功能集成在一起，很 难得到流水线的中间结果，这限制了s o r t m i d d l e 类系统在p c - 集群机上的 应用。但s o r t m i d d l e 在某些商业图形处理硬件上得到应用，如 i n f i n i t e r e a l i t y 7 0 、p g l 1 5 等。 而s o r t l a s t 类系统不对图像空间进行划分，只将场景数据等分为若干 子集，子集的戈分不受空间范围的限制，保证三角面片数量大致相等以保持 负载平衡即可，这使s o r t l a s t 的归属判断与s o r t f i r s t 和s o r t m i d d l e 不同。每个数据子集进入相应服务器的绘制流水线进行几何处理和光栅化后 得到一副全屏幕大小的图像，所有图像进行逐像素深度合成后得到最终的显 示结果。s o r t 一】a s t 最大的优点是简明，场景数据的不均匀分布引起的负载 失衡较小，但增加了一个像素合成的处理步骤。像素的传输和合成是 s o r t l a s t 并行图形绘制系统的主要开销和瓶颈所在。p i x e l f i o wl 2