（计算机应用技术专业论文）terrainvdr：基于outofcore的交互式地形并行绘制框架.pdf

a b s t r a c t v i s u “i z a t i o no f t e n a i ni sp l a y i n gak c yr o l ei nm a n y 印p l i c a t i o n s ，s u c ha sn i g h ts i m u l a t i o n s ， 3 dg 锄e s ，g e o g r a p h i ci n f o 皿a 廿o ns y s t e m ，e t c w i mt 1 1 er 印i dd e v e l o p m e n to f 恤r e m o t es e n s e 锄ds a t e l l i t et e c h n o i o g y ，p e o p l ee x p e c tt oi n v e s t i g a t eo rv i e w1 a r g et e r r a i nr e g i o n sw i t hf l n e r p r e c i s i o n 汕o w e v e lt h ei n t e r a c t i v ev i s l l a i i z a l i o no f1 鹕et e r r a i nd a t a s e ti sr e a l i yag r e a tc h a i l e n g e t ou s i n t h i sp a p e w ep r o p o s e 拍i n t e r a c t i v ep a r a l l e lr e n d e r i n gs y s t e mf o ro u t - 0 f - c o r et e r r a i n d a t a s e t t h e s y s t e mi si i i l p l e m e n t e di np cc l u s t e r a i l da d o p tr “nm o d eb a s e ds o n f i r s t a r c h i t e c t u r e t h er e n d e r i n gr e s u 垴a r ep r o j e c t e do nal a r g ed i s p l a yw a l l t h es y s t e mi n c l u d e sa c o r l 仃o lc l i e n t 肌df i f t e e nr e n d e r i n gs e r v e r s ，w h i c ha r ec o n n e c t e db yh i g hs p e e de m e m e t t h e r e t a i nm o d em e a n st l l a tw es t o r eac o p y0 f t h ew h 0 1 e 把a i nd a 忸i ne a c hr e n d e r i n gs e r v e lw h i c h a v o i d st l l e 丘弓q u e n c yo ft r a n s m o no fd a t a 洫t 1 1 en e 撕o r k t h es o n 壤r s ta r c b j t c c t i l r ci sc o n v e m e m f o rt a s kp a n n i o nb e t 、v e 曲r e n d e r i n gs e e lt h ec o 咖1c h 髓ti sr e s p o n s i b l ef o rt l l ec o n 订o l 舭d s y n c h r o n i z a t i o nb e t 、v e e nt h e ”n d e r i l l gs e n ，e r s b e s i d e s ，b o t hg e o m 曲叮c a l i b r a t i o na f l dc o l o r c a l i b r 砒i o na r ep e r f o n e di nt h em u l t i - s c r e e n 廿l ed i s p i a ya i l dg e n e r a t et r 吡1 ys e 蜘l e s sd i s p l a yw i t h h i g hd y n a m i cr a n g e w ep r e s e n tan o v e lv i e w - d e p e n d e n ti n t e r a c t et e r r a i l lr e n d e 血ga l g o r i t h m i no r d e rt oe x p l o i t 协ec a p a b i l i t yo f c 咄n t 饼u ，t 量l et e r r a i l lg e o m e n yd a t ai so 唱姐i z e da sq u a d 廿e ，锄de a c hn o d eo f m eq u a d t r c ei sa 仃i 蚰g l em e s h ，w i l i c hi sc o n s 帆c t e da l l do p t 弧i z e do 昏l i n ew i t l ll l i 曲q u a h t y s i m p l i f i c a t l o na n d 订i s 廿i p p i n ga l g o m f l i n s e a c hn o d ec 蚰b ed r a w0 u tu s i n gas i n 出e c a l l _ e ) c p l o i 吐n gt 1 1 e 妇n ec o h e r e n c e ，w ec o n s 劬c tm et e x t u r ed a 乜a sq u a d t r e e ，柚di n t e g 嘶e dw h g e o m e h yq u a d 打c e ，w h i c hl l a i l d l et l l ep r o b l e mo fl a 唱et e x t u r ei nr e a l 一廿m e i n 陀n d e r i n gt i m e ，协e c h o o s i n go fl o di s 捌v e nb ys c r e e ns p a c ee r r o lt ok e e pt l l ec o n t i n u 时o f t e m i ns u r f k em e s l l ， t l l e s k i n t e c h n i q u ei su s 酣t 0a v o i dt _ 甜a 氐锄dg e o m o r p h 堍i su s e dt or e m o v e 恤v h u a l 删缸tw h e ns w i t c h _ m gb 咖e e nd i 位r e n tr e s o l u t i o n so 儿o dd a 诅f u n h e 瑚o r e ，也ec o m p l e x 时 0 f t l e 崩1 d e r i n gs c e n ei sg r e a l l yr e d u c e db yv i e w f 如s t i l mc u l l i n g n l ed e l a yc a u s e db y 血c ae x c h 锄g eb e t w e e l lm a i nm e m o r ya n ds e c o n d a 叮s t o r a g ei st h e 眦i e n e c k so fr e a l - t i m er e n d e r i n g砌一o f 二c o f et e m md a t a s e t 肼i c i e n ta u f - c o r ed 缸a i i t c m j n v d r ：基于o u t _ 0 c o r c 的交互式地形并行绘制框架 殷萍 1 1 引言 第一章绪论 1 9 9 8 年1 月3 1 日，时任的美国副总统戈尔在加利福尼亚科学中心发表了题为“数字地 球：展望2 1 世纪我们这颗行星”的演讲，率先提出了“数字地球”( d 瑭i 诅le a n h ) 的概念。 戈尔在他的文章里面指出“我们需要一个数字地球，即一种可以嵌入海量空间数据的、 多分辨率的和三维的地球的表示，可以在其上添加许多与我们所处的星球有关的数据”。通 常认为数字地球主要由三部分构成： ( 1 ) 不同分辨率尺度下的地球三维可视化的浏览界面 ( 2 ) 网格化的空间信息世界，为用户提供公用信息和商业信息。 ( 3 ) 多源信息的集成和显示机制，就是融合和利用现有的多源信息，并将其嵌入数 字地球的框架，进行“三维的描述”和智能化的网络虚拟分析。 在信息爆炸的今天，“数字地球”能帮助人们还浩瀚的信息海洋中快速的定位和查找信 息无疑将对经济发展和社会进步发挥重大作用。 基于数字地球的参考模型，很多国家和地区的研究机构和商业组织都开发了应用原 型。g 0 0 9 1 e 公司的提供的g 0 0 9 1 em a p 服务凭借d i g i 诅l g l o b e 和e a m l s a t 卫星提供的图 片可以为人们提供精确的地理信息。人们可以将将世界每个角落放大或缩小，诸如台湾 军方视为最高机密的花莲佳山基地等空军机场、总统府：北京中南海或天安门的情况， 都可透过这项卫星图片一览无遗，见图卜1 1 。g o o g l e e a r t l l 采用的3 d 地图定位技术能 够利用g o o g l em a p 上的最新卫星图片使用户在3 d 地图上搜索特定区域，放大缩小虚 拟图片，然后形成行车指南。杭州e 都市是全球首个网上仿真城市( 见图1 】2 ) ，可以 给市民提供城市电子地图、生话咨询、电子政务、同城电子商务、虚拟社区等服务。 3 r 碱l 蝻- v d 基于o u 0 c o 他的交互式地形并行绘制框架 般萍 图l - l - 1 ：9 0 0 9 l e m a p 提供的卫星图片。 图1 ，1 - 2 ：杭州e 都市提供的杭州黄龙体育中心定位图。 地形，定义为在二维平面上的高度连续函数【b e 唱1 9 9 5 】，通常用均匀采样的高度场来表 示地形表明，许多标准的文件格式都采用正规网格来表示，在图形学中一般用三角形网格来 表示地形并进行绘制。如果地形用正规网格表示，最精细的地形三角形网格是对最精细采样 点的矩形区域用对角线分割，形成两个三角形，则地形的三角形个数随地形尺寸成四倍增长， 地形三角形数目与地形尺寸的比例关系如图1 1 3 所示。此外为了加强绘制的真实感，通常 采用纹理映射技术。 4 1 n a i n - v d r ：基于0 u t - 碓c o r c 的交互式地形并行绘制框架 殷萍 图1 - 】- 3 ：三角形与地形尺寸的关系 遥感技术，卫星技术的发展，使的获得高分辨的数字几何数据以及影像纹理数据成为可 能，但随之也产生了很多的问题，无论在存储上还是绘制上都给我们带来新的挑战，例如 5 0 0 k r n 5 0 0 k m 的地形以1 0 m 的分辨率进行采样，将会有2 5 千兆的数据点，如果以1 m 的分辨 率进行采样，那么会有2 5 0 g 的数据点，如果每个数据用4 b y t e s 那么地形数据将达到1 i b 的容 量。而三角形的数目也达到5 0 0 g 个。 随着计算机的发展，计算机的硬件得到了长足的进步，目前主流p c 图形显卡的多边形 处理能力已经达到每秒上亿个，如g e f o r c e7 8 0 0 。对于海量的地形高程数据，更逼真，更精 细的场景显示需求，使的场景的规模不断扩大，单纯依赖硬件加速的快速绘制技术，并不能 满足实际应用对绘制速度的要求。面对这一难题，常见的解决方案是构建采用高速总线和专 用图形硬件的并行图形绘制系统，利用多个处理嚣和多条图形流水线进行并行化的计算和绘 制，然后将多条通道的绘制结果进行合成得到最终的结果。此类系统的典型代表为i n f m i 钯 r e a l i t ye n g 协e 【m o d 订y m l 9 9 7 ，该系统采用高速系统总线实现多条图形流水线之间的几何数 据分配和多通道绘制结果的拼图输出；几何数据分配策略主要采用r o u n d 莉b m 策略。但是此 类高端并行机昂贵冉匀价格严重的阻碍了其推广和普及。如今，p c 硬件不断完善，低端图形 卡发展突破摩尔定律，几乎每6 个月，其性能提高一倍。【s h i 2 0 0 4 中指出p c 集群的优势包括： ( 1 ) 高性价比，p c 集群的价格是同等处理能力专业机价格的十分之一甚或几十分之一。( 2 ) 扩展性好，理论上p c 集群的计算能力随节点数增加而线性增加，增删节点都很方便。( 3 ) 使用灵活，可以做任何计算机处理，不仅仅局限于图形处理。( 4 ) 升级方便可随时采用当 前最先进的配件进行升级。因此，国内外关于高性能图形绘制的研究逐渐转向了利用高速网 络互联的p c 集群系统来代替传统的图形工作站，利用分布式并行绘制来代替单处理器绘制， 以实现对大规模数据的实时绘制。 t b m i n v d r ：基于0 u t - 0 c o r c 的交互式地形并行绘制框架 殷萍 第二章研究背景综述 2 1 并行绘制研究综述 2 1 1 研究背景 计算机图形学是计算机科学的一个重要的分支，图形学的目的是利用计算机的计算能 力，生成具有真实感或非真实感的图像。今天，图形学的应用已经渗透到科学研究、工程设 计、影视制作、广告艺术、教育培训等各个方面，计算机图形学已经成为人类日程生活不可 或缺的一部分。各种应用程序，如沉浸式虚拟现实，科学计算可视化等，不断从真实感和绘 制速率两方面向图形系统的绘制能力提出挑战。 目前计算机硬件性能已经得到很大的提高，尤其是计算机图形硬件技术得到了很大的发 展，出现了g p u ( g r a p h i c s p r o c e s s i n g u 血) 。p c 图形( 如照片、视频和游戏等) 需要大量 的处理能力，在g p u 出现以前c p u 必须执行所有的系统处理和图形处理任务，因此结果降 低了系统的性能。g p u 的出现，可以卸载c p u 的图形处理负荷，从而让c p u 有更多的资 源用于执行更重要的系统处理任务。目前p c 的性能已经远远超过了早期昂贵的专用图形工 作站，而且低端图形显卡的性能几乎每6 个月就翻倍，发展速度突破了m 0 0 r 定律。尽管 如此，在一些应用领域，如大数据集的科学计算可视化，高分辨率超大屏幕显示，】g 以上 数量级三角形的巨型几何场景交互式绘制，大纹理数据量的绘制等，仍是孤立的图形处理系 统难以应付的。这些孤立的图形系统的性能在一下些方面受到限制 b a r t z l l 9 9 9 】 d a v i s 2 0 0 0 】： 1 产生几何数据的能力( c o m p u t e 1 i m 溉d ) 2 图形计算能力( 妒a p h i c s - l i m i t e d ) 3 几何指令发射能力( i n i e 也c e 1 i l i l i t e d ) 4 显示分辨率( r e s o l 埘o n 1 i m i t e d ) 在这种情况下，并行绘制技术应运而生，通过将笔形计算理论和方法引入图形处理领域 为以上闻题提供了解决的方法。 1 0 t c f r 曲1 v d r ：基于0 u 伽f - c o r c 的交互式地形并行绘制框架 殷萍 圈元归主要开镑瓶颈问题适合的经典系统 燧判定蜜现方 式 金翔像深度 像素数据图像的话输与深图形处 残x e 疆。讯l 合成的传输和度合成速度限制理硬件， p a 糟n e l ( s o f t _ i a g t ) 图像合成了系统性能大型机 m e s a ，s q 商 翦分布拼接几何变预变换负载不平衡导致王作站 w i r 合成换之前系统性能锐减集群d i 则印w 墟 ( s o 小l j r 吐) 中分布拼接几何变g 与r 之负载不平衡，数图彤处抽五n i t e r e a l i t 合成化之后，阀的数据据传鞴嚣以处淫鹫嫒件 y p g l 缸) 水矗d d i e )光栅纯 传输 器数的几何级数 之前增长 图2 1 - 1 ：s o n 一髓 ，s o r t - m i d d l e ，s o n l a s t 的分析比较。 2 1 3 立即模式v s 保留模式 按几何场景数据的存储位置，可以将分布式并行绘制技术分为立即模式与保留模式 s 1 1 i 2 0 0 3 】。单机情况下，无论立即模式还是保留模式，应用程序、绘制器和模型数据都在同 一个进程空间里，相互之间的数据传递通过计算机系统总线进行，数据保存在客户端还是绘 制器端并无性能上的本质差异。而在分布式并行绘制环境下，应用程序和绘制器分布在两个 进程里，彼此通过网络连接。由于网络通讯的速度比总线速度低3 6 个数量级，大量数据 通过网络将引起很长的延迟。如何缓解网络通讯对系统整体性能的影响成为并行绘制系统设 计的主要问题，这使得立即模式并行绘制系统和保留模式并行绘制系统在实现上有着巨大的 差异。 立即模式并行绘制中，每绘制一帧，客户端必须向服务器端传送几何数据，绘制服 务器绘制完成后，丢弃所有几何数据，当绘制下一帧时，客户端必须重传所有几何数据，由 此造成了立即模式对高速网络的依赖。当几何数据不断增加时，这一传送步骤将成为瓶颈， 限制整体的绘制速度，w _ 玎e g l 与c j l r o m i u r n 即是此类系统的典型代表。立即模式并行绘制 系统最大的优点是结构流畅，兼容性强。它的基本工作方式是“传输指令一远端执行”，对 应用程序没有特殊的要求，一般的o p e n g l 图形程序二进制代码，可直接在上述系统上执行。 良好的兼容性使得这些立即模式系统得到了广泛的应用和认同。但是，立即模式并行绘制的 t c r r 由v d r 基于o u t o b c o f e 的交互式地形并行绘制框架 般萍 体系结构也存在这着天然的缺陷：每绘制一帧，都要通过阿络传输大量的几何指令，这给网 络造成了很大的负担，网络带宽是立即模式体系结构最严重的瓶颈。且从图形应用的特性来 说，这种数据传输不是必要的。 保留模式并行绘制系统在体系结构上的特点是：绘制计算分布到多台服务嚣执行，模型 数据分布存储在绘制服务嚣端，每绘制一板，只需传输必蘩的控制命令，不需要所有模型数 据通过网络。最终图像拼接输出。或集中起来由输出节点输出。相比立即模式并行绘制，保 留模式的并行绘制体系结构有明显的优势：网络流量可以大大减小，并可充分利用绘制服务 器的数据存储能力和内存资源，在归属判断操作上，保留模式并行绘制体系结构也有着独特 的优势。m s p r 是一个保留模式的分布式并行图形绘制系统【c h a o l l 2 0 0 3 】。系统在任务分布 上采用s o 九行r s t 结构。m s p r 提出一套类似o p e n g l 的接口，保持比较好的兼容性，一般 o p e n g l 图形程序只需做稍微修改就可以支持分布式并行绘制和大屏拼接显示。 2 2 地形实时绘制算法研究综述 2 2 1 实时连续层次细节( c l o d ) 算法 实时连续层次细节算法根据给定的世界坐标误差或者屏幕误差通过c p u 运算来构建连 续多分辨率层次三角形网格，在不影响画面视觉效果的条件下，通过逐次简化景物的表明细 节来减少场景豹几何负责栏，从而提高绘制算法的效率。在原始模式数据中没育显示的细节 层次存在，在绘制过程中由绘制算法自动地生成对应于当前视点的细节层次。在连续的层次 细节模型中，主要有两类，类是不规则网格( t h a n g u l a t e di r r e g i l l a r n e 似o r k s ，t i n s ) ，另一 类是规则网格( 趾g u s q l l a r eg r i d ，骼g ) 【l i s h e n 啦0 0 4 1 。r g s 的多分辨率层次表示又称为 ，而t i n s 的多分辨率网格又称为h r i n 。 | x 图2 2 1 ：( a ) r g s 1 昔m i n v d r ：基于o u f - c o r e 的交互式地形并行绘制框架 殷萍 t i n s 的地形模型表示方法是一种约束少的自由度高的地形表面三角形化方法，这类表 示方法包括了递进网格算法的扩展一视点相关的递进网格动态地形算法 h o p p e l 9 9 7 】， m u l t i t i j a n g u l a t i o n 方法 p u p p 0 1 9 9 6 】，h y p e n r i a n 叫甜o n 算法【c i 印o n i l 9 9 7 】et i n s 类型的方 法可以在可变间距上对地形高程顶点进行采样构建三角形网格，可以以任意层次细节精度来 近似表示地形表明，采用不规则三角网格构建的地形模型可以弹性的增加或者一处动态的地 形顶点，或者依照不同方式的几何连接进行三角化，可以适当的调整地形模型的拓扑构架， 因此，往往可以用较少的量的三角形数目表示出较为理想的地形全貌或局部特征。但是另一 方面，t i n s 需要消耗更多的内存以及更加复杂的多分辨率数据结构，尤其t i n s 层次结构的 生成方面更是需要大量的计算开销。 r s g 类方法简化得到的地形模型从二维平面上看，顶点与顶点连接的方式和几何模型 的三角形组成方法具有一定的规律性。( 1 ) 几何模型的顶点都会出现在格栅点( g r i dp o i n t s ) 上：( 2 ) 由顶点连接而成的三角形都是以等腰直角的形势出现。这些特点使的r s g 比t i n s 在多层次细节模型的构建过程中具有较快速以及较简洁的数据结构。成功的规则三角形结构 类型的方法包括约束四叉树三角化方法【p 匈a r o l a l 9 9 8 】，最长边对分算法【i j n d m o m 2 0 0 2 】，三 角形二叉树算法 d u c h a i n e a u l 9 9 7 】，层次直角三角形( 玎) w i a i 2 0 0 1 】等多种多样的算 法。这些算法的主要思想是通过自顶向下的细化或者自低向上的简化手段构建规则的层次多 分辨率几何表示。细化方法是从一个等腰直角三角形开始，不断的执行最长边的对分递归操 作得到所需要层次细节模型，蔼蔼化方法则剐好耜反。对手一个给定的规则网格构成的精细 的三角形网格，等腰直角三角形通过进行有选择的合并操作形成粗糙层次上的模型。无论是 对分还是合并操作，r s g 方法可以确保细化以及简化之间的顶点依赖关系以一种隐含的方 式表现出来，这种关系为一棵简单的四叉树或者二叉树。但是由于r s g 的各层次顶点之间 的依赖关系，使的地形模型存在很多冗余的三角形，因此使的表达相同分辨率的场景，使用 r s g 类型方法比n n s 类型方法需要使用更多的三角形数目。但是由于r s g 方法提供地形 顶点选取较简单的算法和节省大量的存储空间，并且可以更弹性的、直接地变更和调整地形 数据、以及快速地三角形条带化，所以c l o d 算法中，r s g 方法比t i n s 方法有更大的实用 性。下面列出c l o d 算法的几个典型代表 a l j n d s 锄m 在1 9 9 6 年首次提出c l o d 算法 l i n d s 仃o m l 9 9 6 】。该算法提出了屏幕误差的概 念和计算方法，在一定的误差范围内，对地形数据首先做了一个基于块的粗略简化，然 后对确定了分辨率的块做基于点的精细简化，最大量的减少每一帧需要绘制的三角形面 片数，自底向上实时生成连续细节层次，在连续细节层次生成过程中使用顶点依赖型关 1 4 t e m 曲一) r ：基于o u i 罅c o f c 的交互式地形并行绘制框架 殷萍 系消除裂缝，见图2 _ 2 2 ，在高端平台上实现了地形的实时连续细节层次绘制。该算法 采用了四叉树的数据结构。该算法不支持几何平滑过渡会有一定跳跃现象。l i n d s 廿o m 方法采用自低向上从最精细模型开始简化的模式会消耗大量的c p u 计算时间，并且其 顶点依赖关系进行显示的保存也需要大量的存储开始。这些缺点使的l i n d s 订o m 方法很 难应用到大规模的地形场景中。 因圈纛 图2 2 - 2 ：顶点依赖关系图。最后一个图为完整的顶点依赖关系图。 日约束四叉树( r e s 蜘c t e dq u a d 订e e ) 是删a r 0 1 a 在l i n d s t r o m 算法的基础上的延伸 ( p 匈a m l a l 9 9 8 】。他使用四叉树陈列结构支持大规模场景数据的载入。与l i n d 5 n 口m 一样， 他们都小心甚至更加严格地保持不同层次节点之间地连续性约束。他提出了自顶向下地 层次细节模型建立方法。该方法需要地存储量少。只需要记录顶点地高度值和顶点所在 区域地误差值，而且不需要显示建立各个顶点之间地依赖关系。此外论文使用p e a l l o 曲 线历遍树来生成个长三角形带，但是该方法会产生许多退化地三角形。 c r o a m 算法是r s g 类型方法的另一个典型代表【d e c h a i n e a u l 9 9 7 。该算法明确使用三角 形对的概念，采用二叉树的数据结构，通过对三角形对的合并和细分对网格进行简化和 细分。r o a m 算法使用两个优先队列( 分裂优先队列和合并优先队列) 来驱动三角形对 的分裂和台并。队列中三角形按单调的权值进行排序，从而保证在若干步简化和细分之 后得到一个最优的三角形网格。在队列中三角形数目不是非常大的情况下，每次视点变 化后只需要对合并和分裂队列中很少的三角形进行操作，从而很好的利用了帧与帧之间 的连贯性。r o a m 算法中在消除裂缝方面通过对三角形进行一系列强制剖分来保证最终 产生的三角形网格的一致性，见图2 _ 2 3 。2 0 0 0 年b i o w 等对r o a m 做了重要的改进 【b 1 0 w 2 0 0 0 】。b 1 0 w 抛弃了r o a m 中根据视点计算误差的方法，改为根据误差函数对每 个顶点预先计算一个包围圈球，当视点进入包围球的范围内，就加入该顶点，否则就不 加入，而各个顶点包围球之闻有树状关系。 t 婀a i n - v d r ：基于0 u t o f c o r c 的交互式地形并行绘制框架 殷萍 弋 ， 。 j 。 图2 1 2 3 ：三角形强制剖分过程。 2 2 2c l o dv s 图形硬件 c l o d 算法对于减少实时绘制的多边形数量非常有效。对于离视点远的区域和平坦的区 域，c l o d 算法能够简化多边形网格，同时对于离视点近的区域和非平坦的地区，c l o d 算 法能够通过增加三角彤数量来保持地形的细节。因此c l o d 算法在2 0 世纪9 0 年代为地形实时 绘制的主流算法，在游戏上有着很广泛的应用。 c l o d 算法提出的背景是图形硬件处理三角形性能差，需要通过c p u 运算来简化三角形 网格，减少需要绘制的三角形数目，从而降低图形硬件的负担。随着计算机图形硬件的发展， 出现了g p u ，图形硬件处理三角形能力有了很大的提高。目前n v i d i a 公司的g e f o r c e7 系列 的显卡能够每秒绘制1 + g 的三角形。图形硬件的发展致使绘制流水线的瓶颈发生改变。c l o d 算法通过对每个进行三角形剖分和合并的揉作来实时构建网格的操作很大程度的依赖于 c p u 操作，而不能有效的利用目前g p u 处理三角形的性能，造成c p u 与g p u 之间的负载不平 衡。 j o h nr a t c 船座限a t c i i 舷0 0 2 】中给出一些非常有参考性的建议： ( 1 ) 除了要尽量避免过多的纹理状态变换外，我们可要考虑进行避免过多的v e 他xb u r 的 改变。我们的目标是通过给图形硬件发送尽可能多的数据来实现尽可能多的并行性。通过将 几何数据存蘸 ef x 5 9 5 0 显卡 网卡i n t e lp r o1 0 0 0 m t 双口网卡+ 主板集成一口千兆网卡 交换机 e n t t e m i n v d r 薏于0 m o f 芝o r e 的交互式地形并行绘制框架 殷萍 ( 4 ) 将几何数据组织为索引的三角形条带。将三角形数目少的几个小组存放到一个共同的 v 尉忱xb u f f b r 。 ( 5 ) 尽可能使用v e r t e xs h a d e r s 。 这些对我们如何高效的利用现代g p u 提出一些非常重要地、有实用价值地建议。c l o d 算法 仍然在理论上有很高的参考价值，但是由于不能很好的利用现代g p u 处理三角形的性能，2 1 世纪初提出的地形实时绘制的l ( ) d 算法都是基于批数据的l o d 算法。 2 2 3 分块多分辨率l o d 算法 由于现代g p u 性能的发展，地形实时绘制的瓶颈主要位于图形硬件与系统内存之阉的 图形数据传输。为了获得最大的性能，图形数据应该以索引的三角形条带方法组织，并根据 需求传送到图形卡。传统c l o d 算法以单个三角形为最小处理单元的处理方法不再实用， 而是采用数据块为最小处理单元的l o d 算法【d e b o e r 2 0 0 0 】。每个数据块可以在预处理阶段 进行优化，组织为适合g p u 处理的模式。在绘制的时候，可以用一条绘制函数将一个数据 块绘制出来。此外用索引的组织方式，可以避免多次传输顶点数据。 b d a m 是c i g l l o l l i 提出的基于块的动态构建网格的地形实时绘制算法【c i 红0 n i 2 0 0 3 a 】。 b d a m 中纹理数据组织为四叉树，几何数据组织为基于三角形块的二叉树。每个三角形块 是一个在预处理的阶段进行优化的1 1 n s ，并存储为三角形条带。在实时绘制时根据视点对 纹理数据和几何数据进行选取构建地形三角形阿格，并进行视域剔除。b d a m 算法在预处 理和实时绘制阶段对数据进行o u 卜o o r e 管理。 c i g l l o n i 对b d a m 算法进行改进，提 x t e n 砒) r ：基于o u t 0 f c o f c 的交互式地形并行绘制框架 殷萍 一点尤显突出。 以上两个因素促使海量数据的外存( o u i - o f o r e ) 处理技术成为当今国际图形学界的热 点研究方向之一。海量三维模型的外存处理技术必须满足下列两个条件： ( 1 ) 必须尽量少而高效地使用内存等高速缓存，所需的内存必须与输入模型规模弱相关。 不能像传统的内存处理技术那样，所需的内存规模与输入模型规模成线性关系。所以又称为 具有高效使用内存性( m e m o r ye 衔c i e n t ) 或缓存连贯性( c 驸1 ec o h e r e n t ) 的技术。 ( 2 ) 必须充分考虑不同的存储介质之间由于速度的差异造成的数据传输上的瓶颈问题，比 如高速的内存和相对低速的外存之间，高速的c p u 缓存和相对低速的内存之间；必须优化 对相对低速的介质的访问，保证访问的线性、顺序性和继承性，以减少数据输入输出上的瓶 颈 x 1 撕面n v d r 基于0 u 细c o r e 的交互式地蟛蓑行绘制框椠 瑚菲 禧鼍不是孺凳磊磊 蘩鋈暮萋融拥餐护鳓防斧鎏酗鬟n 羚雾嚣程睚基萄蓍丽鬟蔼蔼害罗量引 至薹堪臻羹墨葡；i 艘| 髓l 裘i ! 喜；l l | 王蠹囊i ；f 靠”解“踺鲥萎孳d 美筘鞘影薹器墓丽瓣= 奏社薹帮卤融璃瓣彰砻肌闹刖参祁至璧蔼毫醵钳到冀鬟据隘预；取霸耘氆珍爨番室冁f j ：j 刊 孺萋誊蟊融窆堂攀皤骚驰m 据服务器的外存中。当绘制服务器请求数据时，如果数据 存放在外存中，数据服务器需要将数据先从外存读取到内存中，再通过网络传输给绘制节点。 因此这会给系统带来很大的时间延迟。个解决的方法，采用多台数据服务器，将地形数据 全部都存放在数据服务器的硬盘中。此时，数据延迟只包括网络传输的时间。图3 3 2 就是 这种体系。但是这种体系结构因为要把所有的数据存放在数据服务器的硬盘中，因此对地形 数据的大小有一定的限制。 3 4 网络通信 投影图像 图33 - 3 ：t e r r a i n v i ) r 体系结构框架图2 。 网络通信在我们的t e m l i n _ r 并行绘制体系中是非常重要的一块。绘制节点与控制节 点之间必须建立快速、可靠、稳定的网络连接。我们采用面向连接的、可靠的t c m p 协议。 系统中用户与控制节点进行交互，发送控制指令给绘制节点。 2 6 x t c m i n - v d r ：基于o u t o c o r c 的交互式地形并行绘制框架殷萍 将预取交给个单独的线程来完成。 _由g p u 承担尽可能多的工作 c p u 已经成为外存交互式绘制系统中的主要瓶颈，一个行之有效的解决方案是将c p u 所承担的计算任务尽可能地交有计算能力日益强大且已经具有灵活的编程能力的g p u 分 担，尽量平衡c p u 和g p u 的负担。呻o i l 2 0 0 4 】利用显卡来完成保守的遮挡剔除计算。 【b o l 琴e a t 2 0 0 5 】利用显卡来完成几何过渡( g e o m o r p h i n g ) ，消除了基于多分辨率结构的绘制中 常见的跳跃现象以及保证不同块之间光滑过渡，同时并没有增加c p u 的负担。 2 1 r r r a i n v d r ：基于0 u f - c o r c 的交互式地形并行绘制框架 殷萍 图3 2 1 ：图形p c 集群机( 4 机柜，3 2 节点) 在显示系统方面，我们采用背投模式，建立一个由3 2 台l c d 投影仪拼接显示的超高分 辨率的屏幕显示系统。图3 2 2 为我们的5 3 投影仪摆放阵列。图3 2 3 为几何和色彩校正 前的显示结果。图3 2 - 2 和图3 2 3 中我们只显示了1 5 个投影仪的摆放和投影结果，但是实 际上，我们每个投影区域准备了两个投影仪，分别插入不同偏振片，用作透视投影。 图3 2 2 ：5 3 投影仪摆放阵列。 t 缸a i 卅v d r ：基于o u t - o f c o r c 的交互式地形并行绘制框架 殷萍 图3 _ 2 3 ：5 3 投影仪矩阵的未矫正时的显示结果。 3 3 体系结构概要 图3 - 3 1 中是t e m i n ) r 的系统结构框架图，它包括用高速以太网互联的控伟0 端( 控 制节点) 和绘制服务器( 绘制节点) 。每个绘制服务器跟一个l c d 投影仪相连，并将绘制结 果投影到大屏幕上。图中为了方便演示只显示了4 个绘制服务器的输出投影图像在实际实 现中我们使用1 5 台绘制服务器和1 5 个投影仪。 t e r r a i n - v d r 系统采用s o r t f i r s t 的并行体系主要有两个原因： ( 1 ) ：系统运行在p c 集群上，每个p c 节点使用商业的图形显卡，商业图形卡一般将 几何处理和光栅化功能集成在一起，很难得到流水线的中间结果。s o n - f i r s t 的并行体系可以 使的每条绘制流水线完整而独立，特别适合构建p c 集群式并行绘制系统。 ( 2 ) s o n f i 戚并行系统有利于我们对绘制节点进行任务划分。图元归属判断在几何处 理之前进行，s o n _ n r s t 并行体系将最终的显示屏幕划分为多个区域分配给绘制节点，绘制完 成后将所有的绘制节点的绘制结果拼接成最终的显示图像。在t e m i n - v d r 中，将显示屏幕 划分为1 5 个区域，每个绘制节点负责绘制其中一个区域。 2 4 t e 仃a i n v d r ：基于o u t o c o r c 的交互式地形并行绘制框架 殷萍 系统启动时，通过控制节点对系统进行配置，并将配置参数发送给绘制节点。配置包括 对绘制节点进行任务划分以及对每个绘制节点绘制结果的几何矫正和色彩矫正的信息。系统 运行以后，用户通过控制节点改变视点，来对地形场景进行浏览。绘制每一帧，绘制节点必 须从控制节点得到用户的视点参数，绘制当前视点参数下地形数据。 具体实现时，控制端使用多线程实现机制。一个主线程与用户进行交互，为每一个同绘 制节点的连接建立一个辅助线程。绘制节点也使用多线程机制，一个主线程负责场景绘制， 一个线程进行网络连接，还有一个线程进行0 u t - o f _ c o r e 数据管理。 t e r r a i n - v d r 并行绘制系统中还有个必须解决的问题就是同步问题。1 5 台绘制服务器 之间进行同步，才能得到一个统一的超大屏幕投影显示。同步的实现有两种选择： ( 1 ) 用c p u 时钟的同步方法。控制端发送启动时钟的命令，每个绘制服务器开始启动时钟， 通过时钟定时调用o n t i m e r ( ) 函数进行同步。这种方法的优点时启动以后，控制节点和绘 制节点之间不需要进行同步指令传输。但是缺点是，每个绘制服务器独立进行时钟计时，在 绘制一段时候后，由于误差累计，同步效果不好。 ( 2 ) 控制节点控制的同步策略。绘制节点绘制完一帧后，并不马上交换缓存，而是向控制 节点发送通知绘制完毕的消息。控制节点收到所有绘制节点的消息后，通知每个绘制节点可 以交换缓存。绘制节点收到来自控制节点的消息后，交换缓存。t e n a i n _ v d r 中采用这种同 步策略。 3 5 多屏幕拼接矫正 在多屏拼接显示系统中，一个十分关键和必须解决的问题是几何校正，即校正每台投影 仪的投影位置和角度以保证拼接显示结果为一个在边缘上无缝的，在逻辑上单一的显示设 备。在图3 5 1 左图是几何校正前2 x 2 投影仪矩阵的投影图像，由于投影仪本身的梯形失 真，每台投影仪很难呈现规则的矩形显示区域。此外相邻投影仪之间由于重叠显示造成高亮 区域。图3 4 右图为我们希望看到的投影屏幕显示结果。 t e r r a i n - v d r ：基于0 u t d b c o r c 的交互式地形并行绘制框架 殷萍 图3 5 1 左图为几何校正前结果，右图为校正后结果 我们提出一种基于多矩阵的几何校正算法。首先用高分辨率的数码相机捕获一系列特征 点。由于数码相机分辨率小于投影屏幕的分辨率，我们采用5 个象素的特征球。接着，我们 用特征球来计算每个投影仪投影图像在整个显示屏幕上的有效区域。这里我们还是以2 2 拼接显示为例，在图3 - 5 2 中，绿色，黄色，蓝色和红色的细线表示的区域分别为每个投影 仪的投影区域，紫色的线表示每个投影仪的有效区域。堆后，我们用映射矩阵来计算得到有 效区域在帧缓存中的有效位置。 图3 5 2 ：用特征球计算有效区域。 我们在5 3 投影系统上实现了 c h a o l l 2 0 0 5 】的单矩阵映射算法，但是结果并不理想。 由于相机镜头的扭曲，使得最终计算的显示有效区域的四条边的向中心收缩。这造成相邻的 两个有效区域之闻有明显的裂缝。我们提出的多矩阵算法有效的解决了这个阔题。我们把有 效区域分成多个小的区域，每个区域都计算出相应的映射矩阵。通过多个矩阵来提高映射精 度，如图3 - 5 3 所示。理论上，划分的区域越小，映射精度越高，但是实际上，经过我们测 试采用1 6 1 6 区域划分已经可以得到很好的效果。 2 r t c 肌i n v d r ：基于o 【l 卜o f c o r c 的交互式地形并行绘制框架 殷萍 燃 i “ 、-i 。： 十降件件 u 图3 5 3 ( a ) ：将有效区域划分为更小的区域，( b ) ：有效区域在帧缓存中的有效位置 在上面的多矩阵几何校正算法中，相邻的两个投影有效区域是不重叠的，这种校正算法 我们称为无缝拼接算法，见图3 5 4 。在无缝拼接算法中，相邻的两个显示区域之间有条 较暗的细线。这是自于有效区域在顿缓存中映射区域的边界为斜线，而显卡固有的抗锯齿算 法会在帧缓存中产生多于一个象素宽度的效果。在拼接显示时，抗锯齿算法产生的象素会相 互交迭，从而出现暗的细线。 图3 5 - 4 ：无缝拼接算法的效果图 我们解决细线的方法是让相邻的有效区域相互交迭。这会在交叠区域产生亮带，见图 3 - 5 - 5 ( a ) ；然后我们在帧缓存中对交迭的区域进行颜色校正，降低亮度，见图3 - 5 5 ( b ) 这 种校正算法我们称为交迭拼接算法。在我们的系统中。帧缓存的映射和颜色校正都用g p u 来实现，因此对我们实时绘制系统的性能影响很小。 t c n 锄n v d r ：基于o u t o f c o 陀的交互式地形并行绘制框架 殷萍 图3 - 5 5 ( a ) ：交迭校正中，交迭区域出现亮带 图3 5 5 ( b ) 交迭校正中，对亮带进行颜色校正后效果 3 0 t h t i i i - v d r ：基于o u t o b c o r c 的交互式地形并行绘制框架 殷萍 3 6 试验结果和分析 我们在p c 集群系统上实现了t e r f 如- v d r 基于o u t o f o r e 的交互式并行绘制系统。系 统采用s o n 币r s t 的并行绘制体系，将投影屏幕划分为1 5 个区域，每个区域由台绘制服务 器负责。系统采用保留模式，每个服务器的硬盘上都存储一份完整的地形数据。实时绘制时， 服务器根据任务划分，从硬盘调度所需的数据进行绘制。 我们给出了地形p u g e t 、i s l a n d 、k a u a i 三个地形的多屏幕拼接的超高分辨率绘制效果图。 从绘制效果图中可以看出，系统实现较好的几何矫正，但是色彩矫正还存在一定的问题，不