（计算机应用技术专业论文）面向复杂三维场景实时绘制的高效纹理压缩技术.pdf

浙江大学硬士学位论文 摘要 在复杂三维场景的实时绘制中，实现优秀的光照效果是评判绘制质量的一 个重要标准。当今的高真实感光照通常使用全局光照模型，本文以光子映射算 法为倒阐述高真实感光照信息的预计算，并介绍预计算光照信息的存储到纹理 技术( r 朋d 盯t ot c x t u m 技术) ，通过该技术可明显改善复杂三维场景的实时绘 制效果。但该技术存在着纹理信息利用率较低的问题，预存储纹理的大量区域 是未被利用的黑暗区域。如何去除这些未被利用的黑暗区域，提高纹理信息的 利用率，减少内存与显存的负荷，是复杂三维场景实时绘制需要解决的问题。 传统的纹理压缩拼接方法主要有三种：第一种是降低纹理图片存储在硬盘 时的尺寸，以j p e g 2 0 0 0 为代表，其优点是能极大地减少硬盘存储空间的使用 量，其局限性则是无论算法如何对图片进行眶缩，图片在最终绘制载入内存和 显存时的尺寸并不会缩小；第二种是降低纹理图片在显存中展开所占用的空间， 以s 3 t c 及其后的若干改进算法( d x l r c 、a t i 3 d c 等) 为代表，其优点是节 省了显存的空间，而其局限性则是过于依赖硬件，如果本机的显卡不支持该技 术，就无法达到压缩的目的。而且对于光照信息预存储纹理的浪费部分也无能 为力；第三种是简单若干小幅纹理合并成大幅纹理，通过p h a r 0 s h o p 、3 d s m a x 等编辑工具能够实现合并功能，其优点是能减少显存换入换出纹理的次 数( 即。抖动次数”) ，提高绘制的效率，其局限性则是依然无法消除纹理本身 就存在的浪费部分，无法达到节省内存与显存资源的目的 为了弥补上述传统方法的不足，本文分析了纹理拼接压缩问题与经典的装 箱问题之间的相似性，然后研究比较了当前流行的几种装箱问题近似算法，最 后提出一种针对复杂三维场景光照信息纹理的拼接压缩方法，并详细阐述了该 方法的五个阶段的处理工作最后通过杭州全城景观数字化工程项目的其中三 个景观模型作为复杂三维场景测试数据，利用m 朋t a i 毗i y 渲染器的光子映射功 能进行全局光照预计算，并利用3 d sm a x 里的r 即d 盯t ot c x t i l r e 功能将光照 信息保存为新的纹理然后应用本文算法对纹理进行拼接压缩，并详细比较了 压缩前后的几项关键数据，显示了本文算法所取得的初步效果与尚待完善之处 关键词：真实感图形光子映射纹理压缩装箱问题 一i 一 浙江大学硕士学位论文a b q 埘 a b s t r a c t i i i r e a l t i m e 嘲d e r i n 舀i l l 啪i n a t i n ge 任b c t sav e f yi m p c l r t 锄tg t a l l 埘f o r j u d g i n gt h e 嘲l d e r i n gq u a l i 够1 b d a y sr c a n s t cc gt h n i q a l w a y su s 髂t l l eg l o b a i i l l u m i n a t i ( g i ) m e t i l o d 1 1 1 i sp a p e ri n 仃0 d u c e st l l ed c t a i l so fg im e t h o d ，彻d d 跚i 慨n 圮p b o 自明脚a p p i n ga 】g o r j t 量埘t dj m p l 锄曲n 砖g le 舵吨t h 舶i n t m d u 鲫 m er d 盯t ot e x t u m ( 哪t 。c h n i q u e ，t i l i st b n i q u ec a n 慨脚l e 咖t l l c 懈u n so fg li nm c 佗a l - t i m e 啪d e r i n g b u t i er 丌t c c l l i l i q h 硒ab i g d i s a d v 锄t a g e ：t h eb a k e dt e ) 【l u f e s u t i l i z a t o nr a t ba r et o ol o wt ow a s t cl a t so f s t o m g c 柚dm e m o i ys p a c e s h o wt oe l i m i n a t ct i l eu s e l e 豁d a r kr e g i o f t h ch a k e dt 甑t i l r 部 锄di m p r o v ct l l cu t i l 螂i 伽r a t i oo f t i i cs t o m g e 柚dm e m o r ys p a c e si so n eo f t i l ek c y p m b l c m so f 陀a l - t i m e 佗n 枷n gt ob e l v c d t a d i t i a lt e x t i i 坤c o m p r c 龉i o i l ，c o m b i n a t i o na f i l r m a j o fw a y s ：伽e s d u c i n gt l l c 矗l es 班so f t l 璩懒m 腓sb yu s i n gj p e ga l g 耐t h m ；i t 啪g r e a t l y 他d u t i l ed i s ks t o m g es p cu s a 萨i t si i m i t a t i o n sa 他t 1 1 em e m o r ys i z 嚣o ft i l e t c x t i l 心s a 佗n o tr e d u c e d ；卸o t l l 盯w a yi s 删u c i n gt t i et e x t u f c s s i z c s nt l i cv d m e m o r y ， 鲫c h 雏t h es 3 t c 卸dl i i ea t i 3 d ca l g o r i t h m t h ea d v 锄t a g ci st os a v cv i d m e m o i ys p e ，锄d 砥l i m i t 撕o n sa t 0 0d e p e n d 朋to nv i d h a r d w a 他c a r d ：i f y o u r v i d e oc a r dd o e 蚰t 鲫p p o r tt h a ta l g 嘶m 盹t i l 朋t h ec o m p m 船i o nw o n ，tw o 出a n d “ c 柚te l i m j n a t et l l cu s e l e 豁d a r k 陀g i 伽o f t h eb a k c dt e x t u 瞄e i t h 1 1 1 et l i r dw a yi s m e r g i n gt l l e 锄a l l 缸m r c si n t 0al a f g co n eb yu s i n gt h ep l i 咖s h o po r3 d s t c 锄佗d u c et i l e 把】曲r c 洲印p i n gb e 铆e e nm 锄o q 卸dv i d c om 伽o b u ts t i l lc 锄 n o tr c d u t l l et e x t u r es i z e t om a l 【eu pf o rt i l es h o n m i n g so f t r a d “i o n a lm 如o d s ，t l i i sp a p 盱锄a i y z 鹤t h e t e x t i i 他c o m p r 髂s i 伽p r o b l 啪sa n ds h o w si t sc 伽p a m b i l i t yb c “嘲mt l l cc l a s s i c a l b i n p k i n gp r o b l 啪s n 翎p a p e rc o m p a r c s v e m lp k i n ga l g o 删瑚f i n a l l y i t s h o w san e wm e t l l o do f t c x t l i r cc o m p r c s s i o f i c o m b i i l a t i o n t h cm e 廿i o d s6 v es 切唔e s w o u l db ed e s c r i b e d i nd 嘲i l 1 1 1 ep a p e ru s3p a n so f 雠h 柚g z h o ud i g i t a lc 时 m o d e lt ot e s tt l l ee f f 毫c to ft h cn e wm e t h o d a n ds h o w st l l ew h 0 1 et e s tr e s u l t sw i t l l 柚a l y 髓1 1 1 et e s t 懈u bs h o wt h a lt h en e wm e t l l o da c h i e v ca9 0 0 dp e 响舶a n c cb u t a l s oh a ss o m ef l a w st 0b e 默，l v e di nt h e 丘j t i 陀 k e y w o r d s ： r e a 伯c g 憎p h i c ， p h o t o n m a p p i n g ， t e x t u c o m p r e 鹤i o n ， 瑚n p a c “n g l l 浙江大学硕士学位论文图目录 图目录 图l - l 基于d i r t ) ( 1 0 的游戏c r y s i s 截图。 图l - 2 怪物史莱克3 剧照 图1 3 汉堡市三维模型 图2 1 建立光子图 图2 2 各色光源 图2 3 应用光照预计算绘制的小球 图2 - 4 将光照信息保存为纹理 图2 5 应用光照预计算绘制的高楼 图2 - 6 高楼光照信息纹理( 局部) 。1 3 1 3 图2 - 7 应用光照预计算绘制的武林广场场景 图2 - 8 武林广场光照信息纹理( 局部) 图3 1 棚- 3 d c 算法示意圈 1 6 1 7 1 7 1 7 图3 2 原图，图3 3 有效区域包围盒 图3 5 武林广场压缩前纹理、图3 6 武林广场压缩后纹理 1 8 1 8 2 l 2 2 3 6 图3 7 武林广场压缩前内存量、图3 8 武林广场压缩后内存量3 6 图3 9 钱江新城压缩前纹理、幽3 1 0 钱江新城压缩后纹理3 7 图3 1 l 钱江新城压缩前内存量、图3 1 2 钱江新城压缩后内存量3 7 图3 1 3 河坊街压缩前纹理、图3 1 4 河坊街压缩后纹理 图3 - 1 5 河坊街压缩前内存量、图3 1 6 河坊街压缩后内存量 图3 - 1 7 参与合并纹理数 图3 1 8 参与纹理大小( 外存) 图3 - 1 9 参与纹理大小( 内存) 图3 2 0 绘制内存使用 图3 2 l 压缩总用时 3 7 3 8 3 8 3 9 3 9 浙汀大学硕上学位论文 表目录 表目录 表3 1 一些著名的经典装箱问题近似算法。 表3 2 测试环境 表3 3 测试汇总 一v l 一 4 0 浙江大学硕士学位论文第l 章绪论 1 1 引言 第l 章绪论 三维虚拟现实仿真技术( v i r t u a lr l i t y ，简称v r ) 【1 l 是一项涉及计算机图 形学、人工智能、人机交互等学科的综合技术，其目的是用计算机来生成一个 逼真的三维世界给观众。随着计算机软硬件技术的飞速发展，用户对虚拟场景 的真实感程度也提出了越来越高的要求( 如图l 至3 所示) ，矛盾也随之而来： 真实感度越高的虚拟场景需要越复杂的光照模型、越海量的几何与纹理数据闭。 然而复杂的光照模型与海量的几何与纹理数据不仅创建极其复杂，而且对计算 机的运算速度与空间存储的需求也是惊人的如何令普通的主流p c 电脑也能 获得或接近高度真实感虚拟三维环境体验，是计算机图形学的热门研究课题。 本文通过对快速真实感全局光照预计算以及对存储光照预计算信息的纹理进行 高比率压缩这两方面的研究，提出缓解上述矛盾的一种方案尝试。 图l l 基于d i r t x l 0 的游戏c 盯s i s 截图，代表了当前实时三维虚拟的最高水平，但其 硬件要求大大超出了主流p c 水平f 3 】 浙江大学硕士学位论文 第l 章绪论 图l - 2 怪物史莱克3 剧照，反映了好莱坞电影级全局光照渲染的水平，每帧的渲染时 间都以小时计【4 】 图1 3 汉堡市三维模型【5 l ，集合了海量的几何与纹理数据 1 2 真实感图形学研究内容、发展现状及应用 真实感图形学是计算机图形学中的一个重要组成部分，它的基本要求就是 在计算机中生成三维场景的真实感图形( 或图象) 计算机辅助、多媒体教育、 虚拟现实系统、科学计算可视化、动画制作、电影特技模拟、计算机游戏等许 多方面，真实感图形学都发挥了霞要的作用。 对于场景中的物体、要得到它的真实感图形，就要对它进行透视投影，并消 除隐藏面，然后计算可见面的光照明暗效果。给定一个三维场景及其光照明条 件，如何确定它在屏幕上生成的真实感图象，即确定图象每一个象素的明暗、 一2 一 浙江大学硕上学位论文第l 章绪论 颜色，是真实感图形学需要解决的问题。 为了引入下文的快速真实感全局光照预计笄以及对该预计算结果进行高效 存储的技术，此处首先简单介绍几种主流的光照模型种类 1 2 1 光照模型种类 我们把在已知物体物理形态和光源性质的条件下，能够计算出场景的光照 明暗效果的数学模型称为光照明模型，这种模型可以用描述物体表而光强度的 物理公式推导出来早期的光照明模型都是基于经验的模型，只能反映光源直 接照射的情况，而一些比较精确的模型，通过模拟物体之间光的相互作用，可 以产生更好的真实感效果。 1 2 1 1 简单光照明模型 当光照射到物体表面时，光线可能被吸收、反射和透射。被物体吸收的部 分转化为热，反射、透射的光进入人的视觉系统，使我们能看见物体。为模拟 这一现象，我们建立一些数学模型来李辛代复杂的物理模型，这些模型就称为明 暗效应模型或者光照明模型。三维形体的罔形经过消隐后，再进行明暗效应的 处理，可以进一步提高图形的真实感。1 9 6 7 年，w y l i e 等人第一次在显示物体 时加进光照效果【6 】。w ”i e 认为：物体表而上一点的光强，与该点到光源的距离 成反比1 9 7 0 年，b o u l ( i l i g l l t 在c o m m ，a c m 上发表论文，提出第一个光反射模 型们，指出物体表而朝向足确定物体表面上一点光强的主要因素，用l 枷b e r t 漫反射定律计算物体表面上各多边形的光强，对光照射不到的地方，用环境光 代替1 9 7 1 年，g o u 啪d 在l e e et r 锄s c o m p m 哪上发表论文嘲，提出漫反射 模型加插值的思想。对多面体模型，用漫反射模型计算多边形顶点的光亮度， 再用增量法插值计算。1 9 7 5 年，p h o n g 在c o m m a c m 上发表论文嘲，提出图 形学中第一个有影响的光照明模型。p i i o n g 模型虽然只是一个经验模型，但是 其真实度已达到可以接受的程度。 p i l o n g 光照明模型有这样的一个表述：由物体表面上一点p 反射到视点的 光强i 为环境光的反射光强l e 、理想漫反射光强i d 、和镜面反射光i s 的总和 p l l o 鸣光照明模型是真实感图形学中提出的第一个有影响的光照明模型， 生成图象的真实度已经达到可以接受的程度；但是在实际的应用中，由于它是 一个经验模型，还具有以下的一些问题：用p h 伽g 模型显示出的物体象塑料， 一3 一 浙江大学顽上学付论文 第l 章绪论 没有质感；环境光是常量，没有考虑物体之问相互的反射光：镜面反射的颜色 是光源的颜色，与物体的材料无关：镜面反射的计算在入射角很大时会产生失 真等。 1 2 1 2 全局光照明模型 由于局部光照明模型假设环境反射分量为一常数，所以这种模型在原理上 就使生成的图形不太真实。为了使图形更加真实自然，则需要根据场景几何、 光照条件及表面特性把环境反射分量加入到光照模型中，以得到完整的光照明 模型。w h i t t e d 模型忡是一个整体光照明模型，它除了考虑光源在景物表诬的直 接照射而产生的光亮度外，还考虑了环境光在镜面反射方向和规则投射方向对 被照射点产生的光能贡献，但其他方向的环境光对被照射点的影响则仍用一常 数泛光项来模拟。 为了统一光照明模型的形式，文献恻从光度学的基本概念出发，建立起 光照明模型的理论基础，导出了统一的光照明模型，但这种模型仅具有理论的 价值，而在实际执行上却存在很大的困难。下一节将讨论几种具有实用价值的 全局光照明实现算法 1 2 2 真实感渲染的主要方法 1 2 2 1 扫描线算法 扫描线算法是基于局部光照明模型的简单的画面绘制算法，它主要在于隐 藏面的消隐，以确定屏幕像素和场景中的某个可见点对应 扫描线算法在真实感图形绘制算法上最早被开发，应用亦最广泛但由于 扫描线算法基础的局限性，所以这种算法也仅在速度上进行了不断的改进。扫 描线算法思想最早源于c a t n l u l l 提出的z 缓存器算法习，在此基础上形成的扫 描线z 缓存器算法m 1 和区间扫描线算法则在硬件加速中得到了充分的应用。 1 2 2 2 光线跟踪算法 光线跟踪算法是真实感图形学中的主要算法之一，该算法具有原理简单、 实现方便和能够生成各种逼真的视觉效果等突出的优点。在真实感图形学对光 线跟踪算法的研究中，早在1 9 6 8 年a p p i ca 研究隐藏面消除算法时，就给出 了光线跟踪算法的描述。1 9 7 9 年k a y 和g r n b e f g 的研究考虑了光的折射i 嗍。 1 9 8 0 年w h i 曲c d 提出了第一个整体光照w h i t c e d 模型1 1 1 ，并给出一般性光线跟 一4 一 浙江大学磺上学位论文 第l 章绪论 踪算法的范倒，综合考虑了光的反射、折射透射、阴影等。 在光线追踪过程中，相邻光线在光能传播过程中往往具有大致相同的路径， 因此h k b c f t 和h 锄r a l l 锄【18 1 通过光束追踪的方法来利用光线之间的连贯性，从 而有效地提高了光线追踪算法的效率 传统光线追踪由于假设光线是一根理想的直线，景物表面为理想镜面因 而所生成的图形不仅超现实而且具有尖锐的反射边界及阴影边界，同时点采样 的使用也导致了形状走样。在现实场景中，景物表面一般并不总完全光滑，其 镜而反射往往呈现模糊性质，为此，a m 锄t i d e s 【”1 提出圆锥跟踪算法来模拟表面 模糊反射和半影效果，并有效地克服了图形走样现象，但存在圆锥与景物求交 的困难 与圆锥光束追踪算法不同，其后发展的分布式光线跟踪算法不是采用几 何形状来表达一束光线，代之以在一立体角内分布式地随机跟踪一定数量的光 线。因而，该算法有效地克服了圆锥光线追踪的缺点，而且能生成诸如模糊镜 面反射、模糊折射、半影、景深及运动模糊等光照效果。 分布式光线追踪技术尽管极大地提高了所生成图形的真实感，但其仍和前 面的光线追踪算法一样，属于逆向跟踪，所以它无法模拟漫射表面上的整体光 照明效果。基于这种要求发展起来的双向光线跟踪算法最早由h c c k b c r t 和 h 锄a l l 锄提出，它们采用正向跟踪，从光源出发，利用光束追踪技术求解多边 形场景在光源镜面反射光的照射下引起的间接漫射分量，基于这种思想，a r v o 【2 1 1 采用照明图( ( i i l 啪i n a t i m a p ) 方法成功地计算了问接漫射分量，并首次模拟了 由规则投射引起的问接漫射分量，即所谓的焦散( c a u s t i c ) 现象。此后，光线追 踪结合p h o t o nm 卵技术或辐射度技术的算法的出现也拓展了光线追踪的未来 发展方向 1 2 2 - 3 辐射度算法 辐射度方法是继光线跟踪算法后，真实感图形绘制技术的一个重要进展。 尽管光线跟踪算法成功地模拟了景物表面间的镜面反射、规则透射及阴影等整 体光照效果，但由于光线跟踪算法的采样特性，和局部光照模型的不完善性， 该方法难于模拟景物表面之间的多重漫反射效果，因而不能反映色彩渗透现象。 1 9 8 4 年，美国c o m e l i 大学和日本广岛大学的学者分别将热辐射工程中的辐 一5 一 浙江大学硕士学位论文第1 章绪论 射度方法引入到计算机图形学中阱捌，用辐射度方法成功地模拟了理想漫反射 表面间的多重漫反射效果。经过十多年的发展，辐射度方法模拟的场景越来越 复杂，图形效果越来越真实。与前几章介绍的光照模型与绘制方法有所不同， 辐射度方法基于物理学的能量平衡原理，它采用数值求解技术来近似每一个景 物表面的辐射度分布。由于场景中，景物表面的辐射度分布与视点选取无关， 辐射度方法是一个视点独立( v i e wi n d e p d e n t ) 的算法，使之可广泛应用，丁虚拟 环境的漫游( w a l k t h r o u g l l ) 系统中。 标准辐射度方法假定场景中景物表面均为理想漫反射表面。为了克服这一 限制，许多研究者推广了辐射度方法，使之能处理包含镜面、投射面以及各种 纹理表面的复杂环境，从而较完善地发展了非漫射环境辐射度算法艏2 6 1 2 1 和 纹理表面辐射度算法l 嚣j 。这些算法模型较之w h i t b e d 模型更为完善，模拟的光 照明效果也更为真实。除此之外，辐射度算法还被推广到能处理含有介质( 如烟、 雾) 的场景中i 捌，从而扩展了可渲染的场景对象范围。 由于传统辐射度方法在算法效率上很低，特别对由成千上万个面片组成的 复杂场景，用传统辐射度方法求解简直不能被接受。针对这一局限性，m o n t e c 盯l o 辐射度算法应运而生，并在短短的几年中得到了迅速发展。 文献i ”1 首先将m o n t e c a r l o 技术引入全局光照以求得场景的整体光照分布。 p a t t 锄a i k 和m u d e 一3 4 提出粒子追踪算法，其基本思想是利用m o n t cc 甜i o 方法对 场景中的所有光子( p h o n o n s ) 进行收集，这种方法依赖场景的预剖分，但场景建 模人员在建模阶段并不知道场景面片的辐射度解，而且如果场景剖分不足将导 致场景的细节无法显示出来，如果剖分过细则在发射相同数量光子数情况下又 会出现采样不足的情况，使生成的图像产生严重噪波。 t o b i e 一”1 和b e k a c n l 3 q i ”1 将分层子分技术应用到了m t e c 砌。辐射度方法中 提出了分层m o n t ec 盯l 。辐射度方法( h m c r ) ，以削弱这种方法对场景初始剖分 的过分依赖。p o p e 阳随后对t o b h 提出的子分算法进行改进，提出多通道子分 和多阶子分的算法，以能对阴影边界和焦散边界进行更快地探测。文献旧使用 个称为最终收集处理( f i n a lg a r t h 盯i n g ) 的绘制步骤来提高最终生成的图像的 质盆，并将粒子体模型( 叫i c i p a t i n gm e d i a ) 放入分层m o n t cc a r i o 辐射度中求解， 将m o n t ec 甜l o 辐射度方法也扩展到一般环境场景。 一6 一 浙江大学硕士学位论文 第l 章绪论 1 2 2 4 光子映射算法 光子映像( p h 0 自m a p p i n g ) 算法于1 9 9 6 年由j e n n 叫所提出，算法的细节 将在第二章中详细讨论，此处不再重复叙述。 1 3 大规模三维场景的纹理需求及面临之问题 由于上述全局光照模型在大规模三维建筑场景绘制中还无法达到实时的效 率，因此如何充分恰当地利用全局光照的预计算信息提高大规模三维建筑场景 实时绘制的效果就成了急需解决的问题，将这些全局光照预计算信息存储在纹 理中是一个很好的解决方法。 纹理映射是解决场景真实感和实时性矛盾的重要途径之一。纹理可以在不 增加场景中几何对象模型复杂性的前提下得到逼真的表面细节，得到越来越广 泛的研究和应用然而纹理映射的广泛应用又提出了另一个方面的问题一如何 更有效地利用有限的硬件资源呢? 在有限的系统怡宽的前提下传输大量的纹理 数据到纹理缓存，不仅会造成系统数据传输瓶颈效应，而且还会占用大量宝贵 的纹理缓存a g p 总线技术虽然建立了一条缓存和主存之间的高速传输通路， 缓解了纹理缓存的不足但是a g p 总线和主存都是共享使用的资源，除了用于 传送纹理数据，a g p 总线还要用来传送几何数据，这使得数据处理速度将不可 避免有所损失，而且当需要装入大纹理甚至是超大纹理时，这样的总线也常常 难以满足要求基于这些考虑纹理压缩技术越来越成为这一领域的研究重点。 纹理压缩不仅可以提高纹理缓存的利用效率，使采用大纹理甚至超大纹理 成为可能，更能减轻系统数据传输的负担，有效地避免了由于纹理缓存交换带 来的系统性能下降，减少系统内存与显存的负担。 1 4 纹理压缩技术之优势 1 4 1 降低系统带宽需求 纹理压缩的明显优势就是可以把纹理贴图存储在更少的纹理缓存中，使得 超出纹理缓存而不得不放置于主存中的纹理数据大大减少，这样当纹理容量超 出缓冲区时，读取纹理贴图所需的带宽大大减少，从而带来a g p 总线性能的增 强。即使纹理缓存的容量在不断增加，纹理压缩技术的这一优势仍然是很明显 的。 浙江大学硕士学位论文 第l 章绪论 1 4 2 装载更多、更大、更高分辨率的纹理 如果纹理太小，物体的表面会显得模糊或呈马赛克状，而较大的纹理则可 以让物体表面表现出更多的细节。纹理压缩使得更多的纹理贴图可以同时使用， 使虚拟环境更加丰富多彩。而且纹理压缩节省的空间可以用来增加显示分辨率 或用作第三缓冲区。更高分辨率的显示可以使图像看起来更加平滑和细致，第 三缓冲区则可以大幅度提高图像显示性能，因为这样引擎可以更早开始处理数 据而不必等待下一次显示卡的垂直回扫周期。典型情况下，第三缓冲区可以提 高性能3 0 左右 1 4 3 整体性能与图像质量的平衡 采用纹理压缩，提高了系统的整体性能，就不得不牺牲一定的图像品质， 这两者不可能同时兼备。而若为了得到高品质的图像，就需要采用高分辨率纹 理，这样即使在纹理压缩后仍会占用很大的纹理缓存空间，系统的数据处理负 担仍然会很大。所以，纹理压缩技术不是解决实时真实感绘制的根本途径，它 只能在一定程度上缓解这对矛盾 1 5 论文的目的与意义 快速逼真地绘制出场景一直是真实感图形技术追求的目标，本论文就足在 这一要求下，对光线跟踪算法特别是最近几年发展起来的光子映射( p h o t o n m a p p i n g ) 方法展开研究，通过它们进行全局光照预计算，并将预计算信息存储 在纹理中，以用到复杂场景的实时绘制。 对于一定复杂度的虚拟环境，实时性和真实感仍是虚拟现实引擎的关键问 题所在。对于这两个密切相关的问题，传统的纹理映射技术取得了较好的平衡。 通过纹理映射，不仅可以降低对场景中景物模型复杂度的要求，而且还可以得 到真实细致的景物表面细节，获得满意的视觉效果。但是上述存储光照预计算 信息的纹理由于固有的原因，必然存在大量的纹理空间浪费，而纹理压缩技术 的解决和应用将使得在系统资源有限的情况下仍然可以大量地使用上述光照预 计算纹理，这无疑将有利于虚拟现实引单在满足一定逼真度的要求下实时性能 的进一步提高，也使得纹理映射技术的优势提高到一个新的高度。 通过上述两方面的改进，本文希望能令三维绘制的效率与质量达到更好的 一8 一 浙江大学磺士学位论文第l 章绪论 平衡，并在基于浙大c a d & c g 实验室研发的绘制引擎的基础上作出积极的尝 试 1 6 论文的主要内容与工作成果 论文的第二章主要介绍光线跟踪之改进方法咣予映射的原理、发展历 程，给出了一个初步的实现方案，并与基于传统光线跟踪的渲染器进行算法上 的对比分析通过这种全局光照预计算，将预计笄信息存储在纹理中以提高复 杂三维场景实时绘制的效率与质量，也引出下一章的纹理压缩算法内容。 论文的第三章主要介绍纹理压缩技术，尤其是面向存储全局光照预计算信 息纹理的压缩技术，它们的数学模型以及各种解决算法，并对算法的性能进行 详细分析，给出针对大规模三维场景纹理特征的具体压缩算法实现最后列出 对上述诸算法实现用例的具体测试环境、数据表格与结果，以及对数据的详细 分析。通过分析与对比说明笄法的优点与不足 论文的第四章给出了对已有工作的总结，并指出工作的不足之处与可改进 点，对后续阶段的继续完善进行展望 一9 一 浙江大学硕上学位论文 第2 章高真实感光照信息预计算与预存储 第2 章高真实感光照信息预计算与预存储 在复杂三维场景的实时绘制中，实现优秀的光照效果是评判绘制质量的一 个重要标准。在上一章介绍的众多光照模型中，简单的局部光照模型实现最方 便( o p e n g l 可直接支持) ，但效果难称真实，因此当今的高真实感光照通常 使用全局光照模型。光子映射算法是老式光线跟踪算法的一种改进算法，对于 间接光照、镜面反射与焦散等现象的模拟效果尤佳本章以光子映射算法为重 点阐述高真实感光照信息的预计算，并介绍预计算光照信息的存储到纹理技术 ( r 蛐d 盯t ot e x t i l r e ，俗称烘焙技术) ，通过该技术可明显改善复杂三维场景的 实时绘制效果。 2 1 光子映射算法的提出 光子映射法是由j e n s 提出，这是一个二阶段式( m o - p a s s ) 的算法。 w ，耐嗍| o 】亦曾提出类似做法，将照度信息储存在物体表面上。光子映射法 可视为双向路径追踪( b i d i r 鳅i o n a lp a t i i 慨i n g ) 的储藏方式，它亦能够提供一种 以密度估计为基础的照度估计的新方法光子映像法是以点来产生、储存、和 计算照度的一个算法，而光子图( p h o t o nm a p ) 则是用来处理这些点信息的数据结 构整个算法纪录了光能流入的通量，即每个光子代表一定量的光能通量，这 方法虽较简单但也较不精确，它可提供大量有用的信息，且适合各种场景环境。 其演算过程包含两个阶段，其中，第一阶段是利用光子追踪技术，透过光源点 经过整个场景来产生点信息，进而建立光子图数据结构。而第二阶段则是利用 第一阶段所建立的光子图数据结构所提供的信息，进行整个场景显像动作。 2 2 光子映射相比光线跟踪之优势 光子映射继承了双向路径追踪法( b i - d i r e c t i o n a lp a i l 一订a c i n g ) 及蒙地卡罗光 子追踪法，既保留原有的优点，且在相同的时间内对于复杂的场景可以有效率 地产生高质最影像，并免除了高频率的噪声。它可解决辐射法无法处理的镜面 反射及焦散现象，以及减少光迹追踪法中光线航行的时间和内存的耗费。事实 上，光子映射法的基本理论是打出一个带有能蹙的粒子即所谓光子( p h o t o n ) ，追 一1 0 一 浙江大学磺上学位论文第2 章高真实感光照信息预计算与预存储 踪此光子的行进路线，并纪录其在场景中每一次碰撞到物体的各项信息，如入 射角、反射角、碰撞坐标等照度估计是整个光子映像算法中最耗费时间的一 部分，且照度估计的效果受限于打入整个场景中的光子总数。事实上，光子映 射法使用无限光子时，理论上可完全模拟自然场景中任何光照现象，然而使用 越多光子数在时间上及内存上的花费会随着光子数的增加而增加。 光子映射方法已被证明是进行全局光照计算的有效的工具，丽且已经成为 计算机图形学领域实现全局光照的主流方法。而光子图这种与场景复杂度无关 的空间数据结构的应用，使得光子映射对渲染包括参与介质的场景有得天独厚 的优势 2 3 光子映射算法的实现 2 3 1 场景数据组织 要实现快速全局光照计算，必须对场景数据进行有效组织，以加快求交运 算的效率如果简单遍历场景中所有面片，其计算复杂度将为o ( n ) ，当n 达 到数百万甚至更高时显然无法接受。包围盒技术1 就是一种加速遍历场景树的 手段，通过包围盒迅速剔除无关的物体对象。然而当物体对象数也高达数千甚 至更多时，包围盒算法的效率仍然不能令人满意。 基于空间的连贯性，考虑到场景中的各景物在景物空间中有固定的方位， 可将景物空间剖分成网格与层次包围盒技术不同，空问剖分技术用一系列空 间网格来标识物体在空间中的方位景物空间首先被剖分成一系列互不重叠的 予空间，这些子空间以一定方式被组织成层次结构，其叶节点记录了它所包含 的景物愿片表。子空间的大小则依赖于景物在空间的分布以及空间剖分的方式。 另外，由于子空间在空间排列的有序性，因而在很大程度上避免了对不可见景 物交点的求交运算及交点问的捧序。空间剖分算法应该尽量满足： 一、计算复杂性与场景复杂性的关联度相对较小； 二、每次求交计算时间近似为常数，与起点和方向无关； 三、无需用户提供场景的层次描述； 四、能处理各种几何物体 浙汀大学顿上学竹论文第2 章高真实感光照信息预计算与预存储 比较有代表性的空间剖分算法有3 d d d a 算法1 2 】、b s p 树算法、空间八叉 树算法、k d 树算法等，在上述各类空间剖分算法中，由于四叉树一般只适 用于地形的空间组织，而且四叉树默认情况下有一个统一的分布方向，如地形 的水平分布，所以对于用于通用场景的空间结构不易采取，而对于八叉树由于 动态更新需要消耗大量的时间，所以本文采用k d 树作为空间剖分算法。 k d 树是平衡二叉查找树的一种推广众所周知，平衡二叉查找树在一维 数据( 即数据的待比较关键字只有一个) 中具有良好的查找性能与方便的动态 维护性。然而当数据足多维的时候( 即数据的待比较关键字多于一个，如三维 坐标点集) ，平衡二义查找树将失去效力，必须进行推广：对于k 维数据，在平 衡二叉树的深度为l 的节点，依据第一关键字进行划分；在深度为2 处则依据 第二关键字进行划分在深度为n 处依据第( nm o dk ) 关键字进行划分。这 种树就是k d i m e n s i o 舱i t 佗c ，简称k d 树 在复杂三维场景数据中，由于节点在空间分布并不是均匀的，所以如果按 照均匀的方式进行节点划分的话，将很容易导致k d 树的不平衡度( 左右子树 深度差) 过大，导致查找的效率严重降低。因此通过代价函数： l e f r r h v 0 i u m e + l e f r r 慨o 巧协n u m + r i 曲t t i 雠v o l u m e r 培h l 胁e o b j e c i s n 啪 计算剖分平面，然后分别在x ，y ，z 轴分别计算出每个轴向上的代价函数最 小的剖分平面。 可以证明，构造k - d 树的时间复杂度是o ( n l o 鲫) ，空间复杂度是o ( n ) ，在 d 维的n 个节点的k d 树中查找k 个节点的时间复杂度是0 ( n 。”+ k ) m 。 2 3 2 建立光子图 下一阶段的标是将预设数量的光子从光源点射入整个场景中，并且追踪每 一个光子的路径，用来建立光子图： 一1 2 一 浙江大学顶上学位论文 第2 章高真实感光照信息预计算与预存储 图2 - l 建立光子图 光子是由场景中的光源所产生出来的，因此，光子的放射状态完全根据备 色光源放射分布函数( r a d i a n td i s t r i b u t i o nf i i n c t i o n ) 所决定 f 7 f 孓 ( a ) ( b )( c ) 图2 - 2 各色光源 当光子击中物件，光子有可能被反射，折射或者吸收，但不管如何皆决定 于对象材质参数的设定，并用俄罗斯轮盘法( r u s s i 柚r o u l e n e ) 决定。假设光子击 中漫射表面( d i 筋辩鲫r f a c e ) 则此光子将会被储存于全域光子图( g l o b a ip h o 自 m a p ) 中，储存的信息包括：光子碰撞的坐标，光子颜色，光子能量等等。如此 重复地将光子射入3 d 虚拟场景中，直到达到目标光子数为止，即完成光子映 射法第一阶段我们知道焦散在传统蒙地卡罗路径追踪法是很难实现的，但光 子映射法可以很有效率地达到，主要原因是光子映射法特别使用焦散光子图 ( c 卸s t i c sp h o t m 印) 独立表示散焦信息。显像焦散现象必须是高质量的，因此 必须要有足够的光子数使得模糊不清和人工化降低到可接受的范围。 一1 3 一 渐江大学硕士学位论文 第2 章高真实感光照信息预计算4 预存储 本阶段算法的伪代码如下： p r o ce m “p h o t o n ( n ) f o r i = o t o n 选择一个点x 0 ； d o 随机选择一个方向d ( 根据概率分布函数) ； ) w h i l e ( s q r t ( d x d x + d y + d y + d z 。d z ) 1 ) 创建一个具有能量( a ) 的光子o ； p h o t o n ( x 0 ，d o ，n ) ； ) p r o ct r a c e p h o o 明( x o ，d o ，q ) i f ( a 穿过介质) 选取一个步长s ； x m = x o + d 0 a s ； w h i l e ( i s i n m e d i a ( x ) ) 计算x 。处的消光系数k t ( x ) ，且透射率t = e + 戤q ； i f ( m n d o m ( o ，1 ) t ) ，则光子与介质相交产生事件，则有 在体光子图中x 。处插入光子o ； 计算x 。点处的散射辐照度o ( x 。) ； i f ( 砌d o m ( 0 ，1 ) ) 一1 4 一 浙江大学硕士学位论文第2 章高真实感光照信息预计算与预存储 2 绘制 光子映射法最后成像是使用分布式光线跟踪程序，完成图上的每一像素 ( p i x c l ) 的亮度足经由一些数量光子的样本估计平均计算而得，并根据观察者视 点透过完成图平面上某一像素进入场景到达第一相交平山，进行估计作业。 光子图已经充分表达场景中很多相关信息，每一个光子皆具有光源的一小 部分能量，当该光子到达场景中某一区域，代表这一区域直接或间接地接收到 从光源来的些许能量然而，只根据单一光子不能代表某区域究竟接收到多少 光源能量，所以必须利用光子密度间接估计此区域的能量。 厶动言歹( w 瓦，动掣 此公式意味着估计x 点的亮度是藉由不断地扩大以x 为圆心的球体，直到 球体内包含了n 个光子纪录，此处的a 为将球体投影到x 点所属的平面所 获得的圆面积，亦可表示为a = ，。整个公式即可改写为： 厶( 五动z 专耄歹瓦，动锄( 五瓦) 本阶段算法的伪代码如下： p r o c r a d i 锄c e e s t i m g i e ( x ，d ，n ) 检索与x 最近的光子的集合c ； 计算以x 为中心包围c 中所有光子的最小球的半径r ： l i ( x ，d ) = o ； f o r ( c t 中所有的光子q ) l i ( x ，d ) = l i ( x ，d ) + p ( x ，d n ，d ) m ( q ) ； l i ( x ，d ) = l ( x ，d ) + 4 靠一o ( x ) 3 ； l ( x ，d ) = l 。( x ，d ) + l 。( x ，d ) k 。( x ) ； p r o c r e i l d e r ( x l ，d ) i f ( i s i n m e d i a ( x 。) ) 浙江大学硕上学伊论文 第2 章高真实感光照信息预计算与预存储 e i s e x 1 1 = ) i + d as ； 计算x i 点处的消光系数k i ( x ) ，则有t “) = c k “i 日； l = r a d i 柚c e e s t i m a t e 伍，d ，n ) ( k ) + 黜n d c 峨1 ，d ) r e t u m l ： 2 4 光照信息预存储技术 上述光子映射算法在大规模三维场景绘制中，以当今的硬件水平尚无法达 到实时的水平，然而由于复杂建筑场景绘制中具有光源与破照射物体一般保持 静止的特点，因此可以考虑对全局光照信息进行预计算，并设法将预计算结果 保存起来供实时绘制使用。在大规模三维场景的制作过程中，经常要用到 r d e r t o t e x t i i m ( 俗称烘焙映射) 的方法。就是一种把光照信息保存成纹理的 方式，而后把这个烘焙后的纹理再贴回到场景中去的技术。这样的话光照信息 变成了纹理不需要c p u 再盖费时的计算了，只要计算普通的纹理映射就可以 了，所以速度极快。由于在烘焙前需要对场景进行渲染，所以纹理烘焙技术对 于静帧效果图来讲意义不大，这种技术主要应用于游戏和建筑漫游动画里匝， 这种技术实现了我们把费时的光能传递计算应用到实时绘制中去的实用性。而 且也能省去讨厌的光能传递时抖动的麻烦。如下图所示： 图2 3 应用光照预计算绘制的小球 一1 6 一 浙江大学碰士学位论文 第2 章高真实感光照信息预计算与预存储 图2 4 将光照信息保存为纹理 图2 - 5 应用光照预计算绘制的高楼 图2 - 6 高楼光照信息纹理( 局部) 一1 7 一 浙江大学硕士学位论文第2 章高真实感光照信息预计算与预存储 图2 - 7 应用光照预计算绘制的武林广场场景 图2 8 武林广场光照信息纹理