（计算机应用技术专业论文）一种大型场景表示方法及其加速绘制技术的研究与应用.pdf

一种大型场景的寰示方法及其加速绘制技术的研究与应用摘要 摘要 随着虚拟现实技术和可视化技术的实用化，虚拟场景中需要建造大量逼真、复杂 的三维模型，因而该三维场景的规模也就很大。用传统的方法建造大型场景、组织和 存储大型场景的三维模型数据以及在大型场景中进行实时交互漫游，都变得非常地 困难。因此，开发大型场景漫游系统时都需要解决两个关键问题：如何表示大型场景 以及如何实现大型场景的实时交互漫游。目前还没有较好的方法来解决这两个难题。 本文对大型场景的表示方法和加速绘制技术作了一定的研究。 首先在研究三维模型的转化方法的基础上，本文提出了一种基于导出插件 的m b y a 多边形模型移植方法，即先开发m a y a 导出插件，再利用插件从m a y a 软件内部 提取模型数据，最后根据实际需求组织存储这些模型数据。相比较从现有图形文件格 式提取数据的模型移植方法而言，用这种移植方法构造数据模型可以从m a y a 软件巾 获取模型的更多信息并且组织信息的方法也更加灵活。有了这种模型移植的新方法， 用户先根据m 3 d 的数据采集模型开发一个m a y a - 导$ 插件，就可以把m a y a e p $ 作的多 边形模型转化为个m 3 d 数据模型了。 第二，在研究大型场景的特性及数据组织存储结构的基础上，本文设计了一种规 范、优化且有空间数据结构的m 3 d 数据模型。在开发大型场景漫游系统时利用这种 数据模型构造数据引擎。既有助于提高复杂模型的建造质量和建造效率，又有助于实 现实时渲染精细场景的目标。 第三，在研究地平线特性以及视觉特性的基础上，本文提出了一种基于局部纲分 地平线的遮挡裁减算法( p o d h o c ) 。该算法设计了一种局部细分地平线。可以积累 物体细节产生的遮挡信息并且又设计了一种基于时间空间以及光照度的白遁应贡 献园子口。口既可以用来平衡局部细分地平线时的精度和构造速度之间的矛盾，实现 高效的遮挡裁减：义可以用来为场景中的每个物体选择适当的l o d ，进一步加快场 景的绘制速度。 最后。利用v c 6 0 和o p e n g l l 2 实现了一个大型场景漫游系统原型。这个漫游 系统的数据引擎部分是基于m 3 d 数据模型构造的，且系统的图像引犟部分也应用了 p o d h o c + l o d 加速绘制算法。 关键词；大型场景漫游，m a y a 多边形模型移植方法，m 3 d 数据模型，局部细分地平 线 作者：王敏 指导教师：吕强 a b s & r a n t a r e d s e f a a r s c t h r a e n n d d e a r p i p n g i i t c a e t c h i o n n i q o u f er f e 。p r r e l a s e r n g t e a t s c i o a n i e i l e s t c h e o n e d ar e s e a r c ha n da p p l i c a t i o no fr e p r e s e n t a t i o n m e t h o da n df a s tr e n d e r i n gt e c h n i q u ef o r l a r g e s c a l es c e n e a b s t r a c t w i t ht h ea p p l i c a t i o no fv i r t u a lr e a l i t ya n dv i s u a l i z a t i o n i ti sv e r yn e c e s s a r yt o b u i l dt h o u s a n d so fc o m p t i c a t e da n dr e a l3 dm o d e li nav i r t u a ls c e n ew h i c hc o n t a i n s u n e x p e c t e d l yl a r g e3 ds c e n e i ti sv e r yd i f f i c u l tf o ral a 。g e - s c a l ec o m p l e xs c e n et o b u i l dt h e3 dm o d e l ，m a n a g et h ed a t ao ft h e3 dm o d e la n dr e a l t i m ei n t e r a c ta n d w a l k t h r o u g hi nt h es c e n e t h e r e f o r e ，t w op i v o t a lp r o b l e m sm u s tb es o l v e di nt h e d e v e l o p i n gp r o c e s so fal a r g e - s c a l es c e n e sw a l k - t h r o u g hs y s t e m ：h o wt or e p r e s e n ta l a r g e - s c a l es c e n e ，a n dh o wt or e a l i z er e a l t i m ei n t e r a c t i n ga n dw a l k - t h r o u g hi nal a r g e - s c a l es c e n e a n dt h e r ei sn og o o dm e t h o dt os o l v i n gt h et w op r o b l e m sa tp r e s e n t t h i s p a p e ra d d r e s s e st h er e p r e s e n t a t i o n sa n df a s tr e n d e r i n gt e c h n i q u e sf o rl a r g e - s c a l es c e n e f u r t h e r b a s e do nt h er e s e a r c ho fc o n v e c t i n gm e t h o do f3 dm o d e l ，t h i sp a p e rp r o p o s e s an e wt r a n s p l a n t i n gm e t h o do fp o l y g o nm o d e lm a d eb ym a y a ：d e v e l o p i n gam a y a e x p o r t e rp l u g - i n ，t h e ne x t r a c t i n gt h ed a t ao fs o m e3 dm o d e l sf r o mm a y ae n v i r o n m e n t s e c o n d l y , a n do r g a n i z i n ga n ds a v i n gt h e s ed a t aa c c o r d i n gt or e a l t i m er e q u i r e m e n t c o n s e q u e n t l y , t h i sp a p e rd e s i g n sam 3 dd a t am o d e lw i t hs t a n d a r d i z e d ，o p t i m i z e d a n dp o s s e s s e ds p a t i a ld a t as t r u c t u r e s b e i n ga p p l i e dt ot h el a r g e3 dv i r t u a ls c e n ed e - v e l o p m e n t ，t h i sd a t am o d e lc o n d u c e sn o to n l yt of a s tb u i l d i n gt h o u s a n d so fc o m p l i c a t e d a n dr e a l3 dm o d e l si na3 ds c e n ew a l k - t h r o u g hs y s t e m ，b u ta l s ot or e a l t i m er e n d e r i n g f i n e3 dm o d e l s b a s e do nt h er e s e a z c ho ft h eh o r i z o n t a la n dt h ev i s u a lc h a r a c t e r i s t i c s ，t h i sp a p e r p r o p o s e sas e l l a d a p t i v ec o n t r i b u t i o ni n d e x 口b a s e do nt i m e ，s p a c ea n di l l u m i n a n c e ， a sar e s u l to ft a k i n ga d v a n t a g eo fp ，t h i sp a p e ri m p l e m e n t so c c l u s i o nc u l l i n gb a s e d p a r t - o f - d e t a i lh o r i z o n ( p o d h o c ) a l g o r i t h mi no r d e rt os p e e du pt h er e n d e r i n go f l a r g e - s c a l e3 ds c e n ew i t ht h es u p p o r to fm 3 dm o d e l f i n a l l y , b a s e do nm 3 dd a t am o d e la n dp o d h o c + l o df a s tr e n d e r i n ga l g o r i t h m al a r g e - s c a l es c e n ew a l k t h r o u g hs y s t e mp r o t o t y p eh a sb e e nr e a l i z e du s i n gv c 6 0a n d o p e n g l l 2 k e y w o r d s ：w a l k - t h r o u g hf o rl a r g e s c a l e3 ds c e n e ，t r a n s p l a n t i n gm e t h o do fm w a p o l y g o nm o d e l ，m 3 dd a t am o d e l ，p a r t - o f - d e t a i lh o r i z o n ( p o d h ) l j - ar e s r c ha n da p p l i c a t i o no f r e p r e s e n t a t i o nm e t h o d 竺! ! 些垦竺! ! ! g ! 竺塑! ! ! ! ! ! ! ! 竺坚笠竺! ! ! 竺些 垒! ! 壁壁 w r i t t e nb yw a n gm i n s u p e r v i s e db yl vq i a n g 一种大型场景的表示方法及其加速绘制技术的研究与应用 表格 表格 3 1 三种数据模型的平均文件大小比较 3 2 三种数据模型的平均文件大小比较 3 3 三大殿场景的三种数据模型文件大小的比较 4 9 4 9 5 0 4 1 四种加速绘制算法的比较实验：a f r 、m f r 分别表示平均、最小帧速6 8 1 1 1 2 1 3 1 4 2 1 2 2 2 3 3 1 3 2 3 3 3 4 3 5 4 1 4 2 4 3 4 4 4 5 4 6 4 7 插图 常见的包围盒类型 轴对称b s p ( 左图) 及多边形对称b s p ( 右图) 四叉树的构造( 左图) 及松散四叉树( 右图) 本文主要工作的关系图 传统的m a y a 多边形模型移植方法( 左) 和基于导出插件的新方法( 右) 与m a y a 导出插件主要相关的1 5 个类 一般的数据采集模型( 左) 和m 3 d 数据采集模型( 右) 规范处理后的m 3 d 数据模型 m 3 d 索引关系图 有空间数据结构的m 3 d 数据模型 顶点条带5 个顶点绘制3 个三角形( 左) 和顶点表9 个顶点绘制3 个三角 形( 右) 移植到虚拟测试环境中的模型( 左) 和原m a y a i = f , 的模型( 右) 的比较： 两幅图像都保存为j p e g 文件( 分辨率为6 4 0 + 4 8 0 、压缩质量为8 ) ，文件 大小依次为7 4 8 k 和7 5 1 k 视角的定义 检查视觉敏锐度的兰道环 物体偏离中央视野的角度和敏锐度因子的关系图 运动视觉图例 融合区域( 左) 和v i e t h - m u l l e r 相同视点几何示意图( 右) 左图：亮度与兰道环视觉敏锐度的关系( 纵轴是兰道环表示的人眼分 辨率，横轴是以n i t 为单位的亮度) 右图：归一化后亮度与视觉敏锐度 的关系 用三个垂直棱柱来代替一个简单房屋的遮挡指数。在这种情况下使用 的是长方形( 右图所示的为其他一些垂直棱柱的图例) 4 8 新算法的四叉树结构( 左) 和空洞的填充面组( 右) 5 0 5 4 5 5 5 7 5 7 5 8 5 9 6 2 6 3 0 0 0 如 n n 般 骢“ 盯 4 9 二叉树表示地平线( 棋盘格区域是空洞的物体的遮挡作用区域) 4 1 0w 产生的遮挡作用分解成两区域( 左) 和w 的遮挡因子必须分段添 加( 右，黑色实线是添加后的地平线) 4 1 1 由精细至粗糙的分层佛头模型序列 4 1 2 利用两种不同的l o d 选择方法得到的图像比较 4 1 3p o d h o c 算法的地平线构造和裁减效果 4 1 4p o d h o c 算法的试验结果 5 1 大型场景漫游系统的结构图， 5 2 漫游系统原形的类结构图 5 3 任意角度漫游效果图 5 4 a a b b 碰撞检测效果图 以 弱卵盯鼹 孔花”馋 y ：9 5 7 1 5 2 苏州大学学位论文独创性声明及使用授权声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本入在导师的指导下，独立进行研究工作所 取得的成果。除文中已经注明引用的内容外，本论文不含其他个人或集体已经发 表或撰写过的研究成果，也不含为获得苏州大学或其它教育机构的学位证书而使 用过的材料。对本文的研究作出重要贡献的个人和集体，均已在文中以明确方式 标明。本人承担本声明的法律责任。 研究生签名： i 敏日期：2 鲤! 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论文合作部、 中国社科院文献信息情报中心有权保留本人所送交学位论文的复印件和电子文 档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质 论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以 公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权苏州大 学学位办办理。 研究生签名： 导师签名： 期：趣：芏 期：0 嘘： 一种火型场景的表示方法及其加速绘制技术的研究与应用 第一章绪论 1 1 课题研究背景 第一章绪论 虚拟现实技术( v i r t u a lr e a l i t y ) ，又称灵境技术，是在综合计算机图形技术、多 媒体技术、传感器技术、显示技术以及仿真技术等多种学科的基础上发展起来的新学 科。它以机器设备模拟的方式为用户创造一个实时反映实体对象变化并与用户相互 作用的三维世界，在视、听、触摸等感知行为的逼真体验中，可以使用户感觉到自己 置身于“真实”环境中或者探索虚拟对象在所处环境中的作用及变化规律 1 1 。虚拟现 实技术把人和机器的力量以一种直观而自然的方式加以统一，这种革命性的变化无 疑将极大地提高人们的工作效率。 三维表现技术是计算机图形学发展的结果，这些三维表现技术让我们能够用计 算机制作的三维模型再现现实世界中的物体或者直观地描述某些复杂信息，这种技 术就是可视化( v i s u a l i z a t i o n ) 技术。可视化不仅仅是通过计算机图形显示来表达数 据，本质上是人们建立某种事物在脑海中的意象，是人们对复杂信息( 例如，城市分 布信息、自然规律、科学试验结果等) 认知和交流的过程，通过这个过程可以帮助人 们获取该抽象信息的相关知识，认识其中包含的规律。当前可视化技术的研究侧重于 研究复杂三维体的可视化，大规模试验数据的可视化和空间变化过程的可视化。 将虚拟现实技术和可视化技术结合起来可以赋予人们一种仿真的、三维的并且 具有与三维虚拟环境实时交互的能力，这样人们可以在三维图形世界中用以前不可 想象的手段来获取信息、分析信息、发挥自己创造性的思维。可视化技术为从抽象数 据生成虚拟空间模型提供了可能，而虚拟现实技术提供了先进的图形显示方式和多 样的用户交互途径为可视化技术研究提供了理想的技术平台。特别是虚拟现实技术 提供的多种交互手段，为被可视化的抽象数据提供了有效的数据分析方法。 近年来，随着“数字城市”建设掀起的热潮，虚拟现实技术和可视化技术被广泛 地应用在城市规划、建筑设计、景观展示、学校教育等领域。三维场景漫游系统就是 可视化技术与虚拟现实技术相结合的产物。它能够让设计者利用计算机重现某个大 型数据场景，然后在生成的三维虚拟世界中对模型代表的具体信息进行操作。这样不 仅为设计者提供了直观地分析抽象数据的手段。还可以帮助设计者更好地发挥自己 创造性的思维。例如，在城市规划设计或者小区规划设计的初期，单纯的平面设计图 及沙盘模型无法以直观的方式来表达设计师的设计意图，而3 d 效果图又只是一幅静 态的图像。当前流行的用m a y a 等三维工具制作的动画又有着必须按照固定路径漫游 的局限性。如果利用计算机可视化技术和虚拟现实技术开发一个虚拟城市( 或小区) 第一章绪论一种大型场景的表示方法及其加速绘制技术的研究与应用 三维场景漫游系统那么就可以实现虚拟模型和设计者之间的实时交互了。设计者通 过鼠标、键盘等输入工具就可以在虚拟场景中进行任意漫游、为虚拟场景的某些部分 提供详细的文字说明以及录制任意路径的动画进行播放等操作。有了这些与虚拟场 景的实时交互操作，设计者可以以直观的方式表达自己的设计意图，大大地提高了工 作效率。 当前构造虚拟环境的主流方法是几何建模技术( 这种方法建造的三维虚拟场景 可以非常好地还原真实场景的三维空间信息，从而能够实现用户任意视角的漫游。然 而，基于图像的建造虚拟场景的方法就不能实现任意视角地漫游) ，而且几何建模中 用得最多就是多边形建模技术( 主要因为图形硬件提供的大多数加速技术部是针对 多边形的) f 2 1 。随着虚拟现实技术和可视化技术的实用化，虚拟场景中需要建造大量 逼真、复杂的三维模型，因而该三维场景的规模也就很大。用传统的方法建造大型场 景、组织和存储大型场景的三维模型数据以及与大型场景进行实时交互漫游都变得 非常地困难。比如，波音7 7 7 的三维模型包括1 3 2 5 0 0 个零件和3 0 0 万个以上的扣件，大 概有5 亿个三角形面片【3 】。如果以2 0 帧秒的速度来绘制这样的三维模型，那么图形卡 就需要每秒钟绘制1 0 0 亿个三角形面片。用传统方法实现这样的大型场景的三维漫游 系统会遇到以下两个问题： 1 这样复杂的虚拟场景如何表示? 为了理解场景并与场景中的物体交互作用，必须将场景的三维模型数据进 行有效的表示。三维场景表示包含三维模型建造和场景数据的组织存在这 两个基本阀题。 三维模型是虚拟场景的重要组成部分。建造三维模型是构造三维场最漫游 系统的重要组成部分。目前建造三维模型可以利用编程方式建立虚拟场景 三维数字高程模型( d e m 模型) ，但是用这种方法只能建造细节要求不高 的三维场景，严重地影响了虚拟场景的真实性( 特别在虚拟景观场景以及 城市细节规划中，对建筑的细节要求相当高) ，不能获得很好的仿真效果。 此外，还可以利用o p e n g l 、d i r e c t x 等图形开发程序库提供的基本绘图语 句绘制三维模型，但是由于这种绘制方式太不直观，也极难建造复杂的三 维模型。 如果场景模型复杂度变大，那么场景的三维模型数据煎也相应增加，数据 的组织和存储问题变得越来越突出。因此，大型场景模型的三维模型数据 组织和存储的效率是影响三维场景漫游系统效率的重要囚素， 2 如何实时绘制这样的复杂三维场景? 一种火型场景的袭示方法及其加速绘制技术的研究与应用 第章绪论 为了实现三维漫游系统的实时交互功能，图形卡必须每秒钟处理加0 亿个三角 形面片。这样计算量已经远远超过了目前最好的图形硬件的计算能力【4 】。 只有解决好上述两个问题，才能把虚拟现实技术和可视化技术应用到当前社会 建设的更多方面，推动社会经济的发展。本文正是试图通过研究大型场景的建模方 法、场景数据的组织存储结构以及加速绘制技术，找到躬决上面两个问题的途径。 1 2 相关研究 1 2 1虚拟场景建模技术 目前，构造虚拟场景的方法主要是多边形建模技术，而实现场景中多边形建模的 手段分为直接应用编程方式和间接应用编程方式两大类。直接应用编程方式就是利 用三维图形绘制语言直接绘制三维模型的方法。例如，利用o p e n g l 的基本绘图语句 绘制三维模型等。间接地应用编程方式就是先通过第三方工具采集到绘制兰维模型 所需要的数据，再剥用三维图形绘制语言读取这些数据，自动绘制三维模型的方法。 例如，绘制三维高程模型、摸型移植等。 当前主流的图形开发库有o p e n g l 和d i r e c t x 两种。o p e n g l 是- - 个工业标准的 三维计算机图形软件接口，工! 眦设计上常用于绘制三维立体模型等。它是开放 的。适用于多种硬件平台及操作系统。由于o p e n g l 是与硬件无关的软件接口，使 得o p e n g l 的应用程序有较好的移植性。d i r e e t x 是微软开发的面向w i n d o w s 操作系 统的三维计算机图形软件接口，其图形开发的功能也一样强大。然而利用这两种图形 开发库的绘图语句都不能在计算机中直接绘制复杂的三维模型。 数字高程模型( d i g i t a le l e v a t i o nm o d e l ) 简称d e m 。它用一组有序数值阵列形 式表示地面商程的一种实体地面模型。是数字地形模型( d i s t a lt e r r a i nm o d e l ，简 称d t m ) 的一个分支 5 卜数字地形模型是描述包括高程在内的各种地貌因子，如坡 度、坡向、坡度变化率等因子在内的线性和非线性组合的空间分布，其中数字高程模 型是零阶单纯的单项数字地貌模型，其他如坡度、坡向及坡度变化率等地貌特性可在 数字j 岛程模型的基础上派生。通过三维数字高程模型只能建造精度要求不高的地形 场景模型、三维城市模型等。 以上两种都是非可视化建模方法，而模型移植对于虚拟场景米说是一种非常直 观且可操作性强的建模方法。它先利用3 d s m a x 等模型制作软件制作三维模型，再通 过编程将这个三维模型移植到当前虚拟系统的开发环境中。模型移植充分利用了三 维建模软件的优点( 对于专业的三维建模软件来说，大量复杂的三维模型的建立将没 有太大的困难) ，所以这种方法是建造大型场景模型的有效途径 q n 。目前，大量的 三维模型尤其是较为复杂的场景模型，一般都是采用3 d s m a x 、m a y a 等软件建造的。 3 第一章绪论一种大型场景的衰示方法及其加速绘制技术的研究与应用 但是，由于3 d s m a x 等文件都是数据结构复杂的二进制或a s c i i 文件对其文件赢接 进行转化将会十分困难；而采用文件格式相对简单的o b j 和v r m l 作中介转化三维 模型，将大大提高模型移植效率。但是，这些现成的数据模型包含的信息有限，都会 缺少一些重要的模型信息( 如，缺少包围盒信息、模型变换中心信息、程序贴图信息 等) ，可能导致部分虚拟场景的模型失真( 如，模型丢失了凹凸贴图信息或贴图旋转 信息等) 或在数据引擎的预处理阶段增加不必要的编程工作量( 如，需要重新计算每 个物体的a a b b 包围盒或重新计算r a m p 贴图等) 。而且。这些现成数据模型的数据组 织方式不够合理规范，也间接地降低了模型移植效率。因此，这种基于图形文件的多 边形模型移植方法并不能完全满足实际应用需求。 1 2 2 空间数据结构 大型场景中三维模型数据的组织存储一般分为两部分：第一，利用某个数据结 构( 如，数组、树、索引结构等) 存储三维模型的基本信息( 顶点、面等) ；第二，用一 个空间数据结构存储场景的分割信息( 例如，在研究加速绘制技术时往往要涉及这些 空间分割信息) 。只有这两部分都能高效地实现并有效地结合在一起，才能提高三维 场景漫游系统的效率。 所谓空间数据结构是将几何体组织在n 维空间中的数据结构，一般是只使用二维 和三维的数据结构。这种数据结构可以加快几何实体之间是否重叠的判断速度，主要 用于裁减算法、相交测试、光线跟踪以及碰撞检测等操作。空间数据结构的类型主要 有：包围体层次( b v h ) 、b s p 树、k - d 树、四叉树以及八叉树等【8 】。 包围体( b o u n d i n gv o l u m e ) 是包围体层次的主要构成元素，它广泛应用于 光线跟踪，可见性测试，碰撞检测等方面。包围体主要包括包围球( b o u n d i n g s p h e r e ) ，包围棱柱( b o u n d i n gc y l i n d e r ) ，包围盒o b b ( o r i e n t e db o u n d i n gb o x ) ，包 围盒a a b b ( a x i s a l i g n e db o u n d i n gb o x ) 以及更复杂的k d o p 。 包围a a b b 又可以称为轴对齐包围盒，它的1 2 条边都与世界坐标系中的x ，y ，z 轴 对齐( 如图1 1 所示) 。 ， 由于包围盒a a b b 的几何概念简单( 只需两点即可定义) ，因此在复杂模型进行 测试前对其相应的包围盒进行先行测试，可以大大提到测试效率。 b s p 树( b i n a r ys p a c ep a r t i t i o n i n gt r e e ) 算法，又称二叉空间分隔树算法。它 是f u c h s 等人 9 】首先提出来的，作为对s c h u m a c k e r 分隔树【4 】的的一个简单自然的扩 充。b s p 树算法主要依赖于这样的一个事实。即多边形可以根据它的法线定义“正 面”和“背面”。一颗b s p 树表示空间的一个递归细分。按照分隔空间方式，b s p 树主 要有轴对称b s p ( 如图1 ，2 左所示) 和多边形对称b s p ( 如图1 2 右所示) 两种形式。 4 一种大型场景的表示方法及其加速绘制技术的研究与应用第一章绪论 ( a ) a a b b ( b ) 包围球 ( 。) o b b 图1 1 ：常见的包围盒类型 蹿ifi o i 哦 眵q 愈 i 州国画稳 图1 2 ：轴对称b s p ( 左图) 及多边形对称b s p ( 右图) 四叉树可以在场景的坐标平面上( 例如，x y 平面、x z 平面) 通过将整个场景包 含在一个最小的轴对齐长方形中来构造，这个构造过程性质上是一个递归形式，直到 满足某个条件( 如递归到达最大层次、长方形中包含的图元小于某个阀值) 为止。如 果递归过程终h 那么这个算法将这些图元绑定在这个长方形上，然后终j i = ：递归。 松散四叉树1 0 1 的基本思想和普通四叉树一样，但是每个长方形的大小选择可以 比较空松。如果一个普通长方形的边长为l ，那么构造松散四又树所用的长方形的边 长可刖k l 代替( k 1 ) ，如图1 3 所示。 1 2 3大规模场景加速绘制技术介绍 一直以米，对计算机绘制技术的研究一直围绕着绘制速度和真实感这二个方面 展开。图像的真实感愈高，需要的计算量和计算时间就愈多，其绘制的速度也将降 低。相反，如果减少计算时间，则图像的绘制结果的真实感亦将相应地降低。随着计 算机硬件技术的发展，目前主流专业图形处理卡的多边形处理能力已经达到每秒钟 百万量级甚至千万量级。然而，场景规模也在不断扩大，单纯依赖于硬件加速的快速 绘制技术，并不能满足实际应用对绘制速度的要求。理论上说，场景的复杂性是无限 的，而任何硬件的单位时间内的处理能力总是有限的。所以不难得到一个结论，那 就是需要软件加速绘制技术。目前大规模场景利用软件加速绘制的途径主要有层次 5 第一章绪论- i 十大型场景的表示方法及其加速绘制技术的研究与应用 平 牛 图1 3 ：四叉树的构造( 左图) 及松散四又树( 右图) 细节和可见性判断【1 1 1 。 1 2 3 1可见性判断 可见判断主要包括消隐算法和不可见面裁减算法。消隐( h s r ) f h i d d e ns u r f a c e r e m o v a l ) 算法是精确的可见性判断算法。这类算法需判断三维场景中每个多边 形面是否可见，其算法复杂度至少为0 ( n ) ，无法应用大规模场景中。不可见面裁 减( v i s i b i l i t yc u l l i n g ) 算法是快速判断不可见性的算法。这类算法先尽可能地裁减掉 那些定不可见的多边形面，得到一个潜在可见集p v s ( p o t e n t i a l l yv i s i b l es e t ) 。再 对这个包含了全部或绝大部分的可见多边形面和一些不可见多边面的潜在可见集进 行精确的可见性判断算法。 目前在可见性判断的研究领域热点集中在如何快速判断潜在可见性和不可见 性两个方面。不可见面裁减算法主要包括如下三方面： 1 背面裁减( b a c k f a c ec u l l i n g ) 背面裁减判断不可见性的依据是：如果一个多边形面的法线方向背离视点 观察方向，则该面必不可见。 聚集背面裁减算法用来判断一组多边形面是否都为背面，需要引入法向锥 的概念 1 2 】。 6 一种大型场景的表示方法及其加速绘制技术的研究与应用 第一章绪论 2 视锥裁减( v i e w f r u s t u mc u l l i n g ) 视锥裁减判断不可见性的依据是：如果一个多边形面位于视见约束体之 外则该多边形面必不可见。 层次视锥裁减算法是利用空间数据结构来层次性地表示三维场景中的组成 元素。采用多边形面组的包围盒作为替代物进行可见性评估。这样一次可 以判断一组多边形面是否在视锥约束体外面f 1 3 】o 3 遮挡裁减( o c c l u s i o nc u l l i n g ) 遮挡裁减判断不可见性的依据是：如果一个绘制元素被其它不透明多边形 面( 或物体) 所遮挡，则该多边形面必不可见。 a i r e y 1 4 最$ 提出了基于视点区域的c e l l - a n d p o r t a l 可见性评估技术。该 方法只适用于建筑物的室内场景，并且需要大量的内存存储可见性信 息。l u e b k e 1 5 等人在a i r e y 的基于区域的遮挡裁减算法的基础上提出了一 个改进算法，新算法大大降低了预处理时的消耗。 s c h a u f l e r 1 6 等人提出了轴遮挡裁减的方法，这个算法是最早的一个基于 视单元遮挡裁减算法。该算法基于单元并使用一些小技巧进行遮挡物的融 合。 g r e e n e 等人【l7 】提出了层次z b u f f e r ( h z b ) 算法，它是一种扩展的z b u f f e r 消隐算法。这个算法利用了两种层次结构：物体空间的八叉树和 图像空间的z p y r a m i d 。由于z - b u f f e r 在硬件上还没有实现，因此在许多情 况下并不适合实时绘制。z h a n g 的博士论文f 1 8 1 对一种层次遮挡图( h o m ) 算法进行详细介绍。这个算法将可见性测试分成覆盖测试和深度测试两个 部分。先利用深度缓冲器进行深度测试，再利用h o m 进行覆盖测试。该算 法是可以通过改变覆盖测试 r 的阔值，可以改变该方法的近似性一一也就 是以牺牲正确性，来换取效率的提高。 w o n k a 和s c h m a l s t i e g 1 9 首先提出了一种基于地平线的遮挡裁减算法，其 主要算法部分是由硬件实现的。这种算法将场景中遮挡物体连同地平面作 为一个高度场看待，然后通过一条地平线不断累积这些高度场所对应的遮 挡因予，从而可以达到遮挡裁减的目的。该算法应用在建筑物为主的场景 漫游系统中可以得到很好的加速效果，但是需要很长时间的预处理和很大 的额外空间。d o w n s 等人【2 0 】在上述w o n k a 等人的算法基础上提出了遮挡地 平线算法。这个算法利用几何计算的方法在不需要很多预处理和额外空问 的条件下实现了地平线遮挡测试，应用在建筑物为生的场景漫游系统中同 7 第一章绪论一种大型场景的表示方法及其加速绘制技术的研究与应用 样可以得到很好的加速效果。但是。该算法必须单独处理所有悬浮或者有 空洞的物体( 如，桥梁) 。b r a n d o n 等人 2 1 $ 1 j g j d o w n s s j 现遮挡 地平线的算法结合地形的特点，提出了一种裁减地形场景中不可见面的新 算法，应用在地形场景漫游中不可见面的裁减方面获得了很好的效果。李 胜等人 2 q 在b r a n d o n 的遮挡地平线算法基础上，改进了地形场景中地平线 的构造方法，实现了一种面向地形场景的高效遮挡裁减算法，并利用新的 遮挡裁减算法结合o u t o b c o r e 数据调度、多线程等技术实现了超大型地形 场景的高性能漫游。 1 2 3 2l o d 数据 层次细节( l o d ) 的基本思想是距离当前观察视点越远的物体，其在成像平面上 的投影面积越小。这样对远处的物体在绘制阶段可以用一种简单形式来表现它。层次 细节算法包含两个主要部分：简化算法和l o d 选取方法。 简化算法是用来生成不同细节的模型表示。对于大多数简化算法来说，形式上是 求解一个最小复杂度的全局最优化问题。l u e b k e 等人f 2 3 1 将多边形简化算法分为静态 简化方法、动态简化方法和依赖于视点的简化方法f 8 1 。静态简化方法的思想是在场景 绘制之前生成离散的细节模型，然后再对这些模型进行绘制。动态简化方法可以给 出l o d 模型的连续图谱，而不是一些离散模型，所以这种方法也称为连续细节层次 算法。依赖于视点的技术是指模型中细节层次是变化的，地形绘制就是这样的一个例 予，在视线的领接区域需要详细的表示，而在较远的地方需要比较低的细节层次。 一个物体有了不同的细节层次后，选择该物体的一个用于绘制的细节层次的方 法，就是l o d 选择方法。选取l o d 常用的两种方法是基于距离的l o d 选取方法和基 于投影面积的l o d 选取方法。f u n k h o u s e r 2 4 等人还提出使用物体的重要程度( 例如， 墙而要比墙上的挂钟重要) 、运动以及焦点等来决定l o d 。 此外，o h s h i m a 等人【2 5 】提出了两种确定视觉敏锐度的不同公式并且根据当前帧 速来自适应地选择l o d ，但是这两种决定视觉敏锐度的公式都没有考虑亮度视觉；纪 庆革等人【2 6 】又在此基础增加了一个亮度因子并演变出三种决定视觉敏锐度的方法， 但是估计亮度因子的经验公式并不合理。 1 3 本文的主要工作 本文工作源于“江苏省计算机信息处理技术重点实验室开放谍题一- - 3 d 场景漫 游系统”。围绕该课题对大规场景的可视化建模方法和加速绘制技术进行了相关的研 究，具体所做的工作集中在如下三个方而： 8 一种大型场景的褒示方法及其加述绘制技术的研究与应用 第一章绪论 针对非可视方法建造复杂模型困难以及现成数据模型( 如，v r m l 模型、o b j 模 型等) 信息量不足的缺陷，本文梳理出了一种基于m a y a 导出插件的多边形模型 移植方法，即开发者先利用m a y a 软件建造一个三维场景；再根据漫游系统开发 项目的实际需要直接从m a y a 软件内部采集这个三维场景的各类模型数据( 例 如，顶点坐标、面法线、a a b b 包围盒、组信息等) ：最后按照自定义的图形文 件格式来组织存储这些模型数据。这种模型移植的新方法既能够辅助虚拟场景 漫游系统高效地建造复杂模型，从而提高了建模的效率并缩短了漫游系统的开 发周期；又能够根据实际需要从m a y a 中采集到多边形模型的任意数据并能够自 由组织存储这些数据。按照这种新方法的思路，本文根据m 3 d 的组织结构，开 发了一个导出m 3 d 文件的插件。有了这个插件就能把m a y a 中制作的多边形模 型转化为一个标准的m 3 d 数据模型。 针对大型场景的信息量庞大以及现成数据模型的数据组织形式不够合理规范的 问题，本文创造性地提出了了一种规范、优化且有空闻数据结构的m 3 d 数据模 型，并基于m 3 d 构造了一个面向大型场景漫游的高效数据引擎。 针对大型场景的实时绘制问题，本文利用视觉心理学的研究成果，给出了一个 亮度视觉敏锐度因子k 的一个计算公式；设计了一种当前画面的自适应贡献因 子口；改进t o h s h i m a 等人的l o d 算法；提出了基于局部细分地平线的遮挡裁减 算法( p o d h o c ) ，并结合了改进后的l o d 算法形成了一种p o d h o c + l o d 的 加速绘制算法。 1 4 本文结构 第章介绍了虚拟现实技术和可视化技术的应用背景和当前应用发展面临的问 题，并从实际问题着手具体分析问题，提出了解决问题的基本途径。同时总结了目前 文献中所提出的相关技术路线。 第二章先总结了一些研究m a y a g g 部信息和组织结构的辅助工具和1 5 个与m a y a 导 出插件的主要相关类；接着介绍了利用这些辅助工具找到的与分离提取m a y a 多边形 模型数据主要相关函数；最后介绍了导出插件的设计与开发方法。 第三章先介绍了m 3 d 数据模型以及它的规范化处理、优化处理以及空间分隔处 理；再利用m 3 d 设计了一个数据引擎：最后分析了这种基于m 3 d 的数据引擎构造方 法的优点。 第四章先提出了局部细分地平线的定义；再介绍了人类视觉敏锐度的四种影 响因子，并根据视觉心理学中的研究成果给山了一个亮度视觉敏锐度因子k 4 的计 算公式：接着又提出了当前画丽的自适应贡献因子卢的定义，并改进了o h s h i m a 等 9 第一章绪论 一种大型场景的表示方法及其加速绘制技术的研究与应用 图1 4 ：本文主要工作的关系图 人的l o d 算法【2 5 】：最后介绍了基于局部细分地平线的遮挡裁减( p o d h o c ) 算法 和p o d h o c + l o d 加速绘制算法的设计和实现方法，并利用实验分别说明了新遮挡 算法、新选择模型l o d 的方法以及两者结合产生的杂交加速算法对加速场景漫游的 实际作用。 第五章介绍了大型场景漫游系统的设计与开发方法。 最后章，总结本论文的工作，并提出进一步研究的方向。 1 0 一种大型场景的表示方法及其加速绘制技术的研究与应用第二章萋干导 珏插件的m b y a 多边形模型移植方法 第二章基于导出插件的m a y a 多边形模型移植方法 大型场景漫游系统都需要一个高效的三维漫游引擎作支撑，而三维漫游引擎的 性能主要受到数据引擎和图像引擎两部分性能的影响。数据引擎和图像引擎两部分 的性能越高，三维漫游引擎的性能越高；反之，三维漫游引擎的性能越低。 本文将要介绍一种基于m 3 d 构造高效数据引擎的新方法。这种新方法首先利 用m a y a 软件建造大型场景的多边形模型，再利用模型移植方法将多边形模型转化为 一种模型信息丰富、规范、优化且空间数据结构的m 3 d 数据模型，最后在这个数据模 型的基础上构造数据引擎，这样就可以将m a y a 5 b 建造的三维模型移植到三维场景漫 游系统中了。但是，传统的m a y a 多边形模型移植方法( 即利用现成图形格式作中介的 多边形模型转化方法，如图2 1 左所示) 中使用的数据模型包含的信息有限。因此，这 种方法不能把m a y a 软件中的多边形模型转化成m 3 d 数据模型。 罔2 1 ：传统的m a y a 参：边形模型移植方法( 左) 和基于导出插件的新方法( 右) 本章先介绍