（计算机软件与理论专业论文）3d游戏引擎中场景绘制及光照渲染技术的研究与实现.pdf

摘要 3 d 游戏引擎包括几个方面：场景绘制、光照渲染、动画技术、 碰撞检测以及网络管理。其中，三维场景的绘制与光照的渲染是它的 核心与关键。另外，计算机游戏对游戏场景要求有较高的真实度与实 时性。其真实度要求全局光照效果的逼真渲染，实时性则要求对场景 进行快速绘制。如何提高游戏与用户的交互速度而又不影响场景的真 实效果，一直以来是一个研究热点。 针对这一现象而进行了研究与改进。首先，介绍了3 d 游戏引擎 的发展与加速绘制三维游戏场景及全局光照渲染的相关技术。然后， 研究了如何利用三角形网格为三维游戏场景中的几何体进行建模。通 过结合光学中的视域衰减模型，提出了一个基于视域衰减的l o d 地 形快速生成算法。最后，通过对全局光照模型的各个分枝地研究，并 结合预计算技术，提出了一个基于预计算静态场景的间接光照路径而 实现的全局光照明的动画算法。 通过研究与实现，对3 d 游戏引擎中的场景绘制及全局光照有了 深入的了解。基于视域衰减算法生成了三维l o d 地形三角形网格， 绘制帧频达到了实时的要求，并且具有相当的真实性。预计算静态场 景的全局光照而实现的动画算法，在加速游戏场景光照效果渲染上有 非常实用的价值和意义。 关键词三维建模，地形生成，非规则三角网格，实时绘制，预计算 a b s t r a c t av i d e og a m ei sag a m et h a ti n v o l v e si n t e r a c t i o nw i t ha u s e ri n t e r f a c e t og e n e r a t ev i s u a lf e e d b a c ko nav i d e od e v i c e t h ew o r dv i d e oi nv i d e o g a m et r a d i t i o n a l l yr e f e r r e dt oar a s t e rd i s p l a yd e v i c e i nt h el a s ty e a r st r i a n g l em e s h e sh a v eb e c o m ei n c r e a s i n g l yp o p u l a r a n da r en o w a d a y si n t e n s i v e l yu s e di nm a n yd i f f e r e n ta r e a so fc o m p u t e r g r a p h i c sa n dg e o m e t r yp r o c e s s i n g m o r e o v e r , t h ec o n s e q u e n tu s eo f t r i a n g l em e s h e sa ss u r f a c er e p r e s e n t a t i o na v o i d se r r o r p r o n ec o n v e r s i o n s ， b e s i d e sc l a s s i c a lg e o m e t r i cm o d e l i n g ，o t h e rm a j o ra r e a s f r e q u e n t l y e m p l o y i n gt r i a n g l em e s h e sa r ec o m p u t e rg a m e sa n dm o v i ep r o d u c t i o n t h i st h e s i sd i s c u s s e st h ew h o l eg e o m e t r yp r o c e s s i n gp i p e l i n eb a s e do n t r i a n g l em e s h e s r e n d e r i n gi st h ep r o c e s so fg e n e r a t i n ga l li m a g ef r o mam o d e l ，h a s u s e si na r c h i t e c t u r e ，c o m p u t e rg a m e ，s i m u l a t o r sa n dm o v i eo rt v s p e c i a l e f f e c t s ，e a c he m p l o y i n gad i f f e r e n tb a l a n c eo ff e a t u r e sa n dt e c h n i q u e s i n t h ec a s eo f3 d g r a p h i c s ，r e n d e r i n gm a yb e d o n e s l o w l y , a s i n p r e - r e n d e r i n g ，o r i n r e a l t i m e p r e r e n d e r i n g i sa c o m p u t a t i o n a l l y i n t e n s i v ep r o c e s st h a ti st y p i c a l l yu s e df o rm o v i ec r e a t i o n ，w h i l er e a l - t i m e r e n d e r i n gi so f t e nd o n ef o r3 dv i d e og a m e sw h i c hr e l yo nt h eu s eo f g r a p h i c sc a r d sw i t h3 dh a r d w a r ea c c e l e r a t o r so rb a s e ds o m ea c c e l e r a t e d a l g o r i t h m s o nt h ei n s i d e ，ar e n d e r e ri s ac a r e f u l l ye n g i n e e r e dp r o g r a m , b a s e do nas e l e c t i v em i x t u r eo fd i s c i p l i n e sr e l a t e dt o ：l i g h tp h y s i c s ，v i s u a l p e r c e p t i o n ，m a t h e m a t i c s ，a n ds o f t w a r ed e v e l o p m e n t m a n yr e n d e r i n ga l g o r i t h m sh a v eb e e nr e s e a r c h e d ，a n ds o f t w a r eu s e d f o rr e n d e r i n gm a ye m p l o yan u m b e ro fd i f f e r e n tt e c h n i q u e st oo b t a i na f i n a li m a g e i nt h i sp a p e r ，w er e s e a r c hs o m ek e yp r o b l e mo f3 dv i d e og a m e ， i n c l u d i n g ： s o m ea c c e l e r a t e dr e n d e r i n ga l g o r i t h m sw e r ep r e s e n t ，s u c ha sr e a l i s t i c i m a g e ，c u l l i n gt e c h n o l o g i e s t h et r i a n g l em e s h m o d e l i n gt e c h n i q u ew a sr e s e a r c h e d ，t h a nb eu s et o r e a l i z e3 dl o dt e r r a i nb a s e ds i g h tf i e l dd e c l i n et e c h n i q u e ，p r e s e n tan e w a l g o r i t h ma n dh a da ne f f i c i e n ti m p l e m e n t a t i o n ag l o b a li l l u m i n a t i o nm o d e lw a sp r o p o s e d b a s e do nt h i s ，an e w a l g o r i t h mw a sp r e s e n tf o r3 dg a m es c e n e sr e n d e r i n ga n dm a k eag o o d e x p e r i m e n t k e yw o r d s3 dm o d e l i n g ，t e r r a i nr e n d e r i n g ，t r i a n g u l a t e di r r e g u l a r n e t w o r k ，r e a l i s t i cr e n d e r i n g ，p r e - c o m p u t e d l l 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：奎幽至垄日期：= 三l 年上月上日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 中南大学硕士学位论文 第一章绪论 第一章绪论 计算机图形学是一个非常引人的研究领域。在艺术、娱乐及出版上，它广泛 应用于电影、电视节目、书籍以及杂志的制作中。计算机动画作为图形学的另一 分支，得到很多研究者的关注。三维计算机游戏( 简称3 d 游戏) 是凝聚了动画中 的关键技术，它要求极大的实时性，特别是在与用户的交互过程中，游戏要求的 响应速度是非常快的。要产生实时的3 d 游戏，游戏中物体运动规律地控制和绘 制都必须在短时间内完成，这对三维复杂场景的真实感绘制来说，采用传统的方 法无法达到这一要求，要达到实时效果，必须采用一些特殊的方法。目前有许多 人正致力于这方面的研究，除了算法的快慢外，3 d 游戏的实时响应时间还与许 多因素有关，如主机的c p u 速度，是否配有图形硬件加速卡以及场景空间的复 杂程度、生成单个游戏画面的大小、分辨率的高低、真实感程序等等。 网络游戏盛行的今天，三维游戏引擎成了它的灵魂与杠杆。没有一个好的游 戏引擎，很难开发出高效且具有吸引力的游戏。特别是随着三维游戏技术的不断 发展，对场景的大规模性、真实性等不断提出更新更高的要求。如今的游戏引擎 已经发展为一套由多个子系统共同构成的复杂系统，从建模、表示到绘制以及一 些光影特效，几乎涵盖了开发过程中的所有重要环节。有了这个处理游戏底层技 术平台，游戏开发人员就可以抛开一些烦琐的东西，而致力于使用这些引擎提供 的接口进行游戏开发，以此大大提高了游戏开发的效率。 1 1应用背景 国内的网络游戏萌芽于1 9 9 5 年以前。这一时期的单机版的游戏在国内已经 形成一定的气候，并向联机版游戏过渡；为网络游戏在国内得以快速发展在人才 和技术等方面做了储备。2 0 0 1 年至今正式进入了国内网络游戏的高速成长期。 网络游戏在发展期已经呈现出一定的赢利潜力和广阔的发展空间，因此，正在为 现金收入烦恼的网络公司不约而同地将目光投入到网络游戏，并且采取了实际的 行动。 2 0 0 5 年，国内游戏产业经历了由引进代理向自主创新转折的重要一年。在 这一年中，网络游戏产业继续保持了2 0 0 4 年的增长势头，用户达到2 6 3 4 万，比 2 0 0 4 年增长了3 0 1 ；网络游戏出版市场实际销售收入达到了3 7 7 亿元，比2 0 0 4 中南大学硕士学位论文 第一章绪论 年增长了5 2 6 。全国从事游戏自主研发的团队由2 0 0 4 年的7 3 家增长到2 0 0 5 年的1 2 0 多家，增长比例为3 7 ；开发的大中型网络游戏作品达到1 9 2 款，较之 2 0 0 4 年的1 0 9 款增加了8 3 款，增长幅度达7 6 。游戏研发从业人员数从2 0 0 4 年的4 0 0 0 多人，增长到1 2 6 0 0 人，增长幅度超过了2 0 0 。2 0 0 5 年国内民族原 创网络游戏的市场占有率已经达到6 0 以上。 2 0 0 6 年上半年国内互联网游戏市场规模达到3 2 7 5 亿元，前三家的市场份额 达到6 4 4 2 ，相较于2 0 0 5 年同期的5 1 有较大幅度的增长，市场集中度进一步 提升。同时网易的市场份额超过盛大，达到2 8 6 ，盛大的市场份额为2 0 9 ， 九城的市场份额为1 5 o ，腾讯的市场份额为1 0 o 。 据有关人士统计，国内的网络游戏玩家已经达到2 6 3 3 万人，但目前国内仅 有游戏技术人员几千人，这其中的缺口达到1 5 万人以上。然而网络游戏业务若 想表现良好并持续稳定增长，重要原因在于对研发的重视和投入【1 】。研发团队的 能力和经验，已经成了网络游戏方面重要的核心竞争力之一。 1 2 游戏引擎概述 简单地说，游戏引擎就是用于控制所有游戏功能的主程序，从计算碰撞、物 理系统和物体的相对位置，到接受玩家的输入，以及按照正确的音量输出声音等 等【2 1 。玩家所体验到的剧情、关卡、美工、音乐、操作等内容都是由游戏引擎所 直接控制的，它扮演着中场发动机的角色，把游戏中的所有元素捆绑在一起，在 后台指挥它们同步、有序地工作。 可见，游戏引擎并不是什么玄乎的东西，无论是2 d 游戏还是3 d 游戏，无 论是角色扮演游戏、即时策略游戏、冒险解谜游戏还是动作射击游戏，哪怕是一 个只有1 m 的小游戏，都有这样一段起控制作用的代码。经过不断地进化，如今 的游戏引擎已经发展为一套由多个子系统共同构成的复杂系统，从建模、动画到 光影、粒子特效，从物理系统、碰撞检测到文件管理、网络特性，还有专业的编 辑工具和插件，几乎涵盖了开发过程中的所有重要环节。有了这个处理游戏底层 技术的平台，游戏开发人员就可以不用花过多精力去处理系统架构、内存管理、 图像绘制等一些底层的技术，可以直接使用引擎提供的a p i 来进行游戏开发， 大大缩短游戏开发时间。 1 2 1 游戏引擎构成 总体来说，3 d 游戏引擎由以下一些关键部件构成： ( 1 ) 场景的光影效果，即场景中的光源对处于其中的人和物的影响方式。游 2 中南大学硕士学位论文第一章绪论 戏的光影效果完全是由引擎控制的，折射、反射等基本的光学原理以及动态光源、 彩色光源等高级效果都是通过引擎的不同编程技术实现【3 , 4 1 。 ( 2 ) 动画。动画主要是讲三维人体动画，大致可以分为两类：一是以传统计 算机动画技术特别是传统二维计算机动画技术为基础发展而来的模型动画；二是 随着近年来运动捕获系统普及而产生的基于运动捕获的动画制作技术【5 1 。 ( 3 ) 物理系统。引擎中物体的运动是遵循一定的物理规律的。例如，当场景 中一个角色跳起的时候，系统内定的重力将决定他能跳多高，也决定他下落的速 度有多快。其中，碰撞检测是物理系统的核心部分，它可以控测游戏中各物体的 物理边缘。 ( 4 ) 对三维场景的渲染。这是引擎最重要的部件之一，负责对三维场景进行 着色 6 1 。我们建立的模型相当于骨骼，而渲染则相当于为骨骼添加肌肉并把模型、 动画、光影、特效等所有效果实时计算出来并展示在屏幕上。 ( 5 ) 交互。处理来自键盘、鼠标、摇杆和其它外设的信号输入。如果支持联 网特性的话，网络代码也会集成在引擎中【7 1 。 1 2 2 国外发展状况 在国外，对3 d 游戏引擎的研究起步较早，而且是由射击游戏所驱动的。1 9 9 2 年，3 dr e a l m s 公司的德军司令部开创了第一人称射击游戏的先河，它在x 轴 和y 轴的基础上增加了z 轴，在由宽度和高度构成的平面上增加了一个向前向后 的纵深空间，给游戏玩家带来了巨大的冲击。同期，i ds o f t w a r e 公司推出了一款 非常成功的第一人称射击游戏毁灭战士( d o o m ) 。由于d o o m 引擎2 d + 3 d 技 术的有效结合，使得可以同时在屏幕上显示大量角色而不影响游戏的运行速度。 这一特点为游戏创造出了一种疯狂刺激的动作风格。 随着引擎技术的发展，引擎的商业化授权成为研究的方向与热门。d o o m 引 擎是第一个被用于授权的引擎。1 9 9 3 年底，r a v e n 公司采用改进后的d o o m 引 擎开发了一款名为投影者( s h a d o w c a s t e r ) 的游戏，这是游戏史上第一例成功 的嫁接手术。1 9 9 4 年r a v e n 公司采用d o o m 引擎开发异教徒( h e r e t i c ) ， 为引擎增加了飞行的特性，成为跳跃动作的前身。1 9 9 5 年r a v e n 公司采用 d o o m 引擎开发毁灭巫师( h e x e n ) ，加入了新的音效技术、脚本技术以及一 种类似集线器的关卡设计，使你可以在不同关卡之间自由移动。 r a v e n 公司与i ds o f t w a r e 公司之间的系列合作充分说明了引擎的授权 是使引擎研发与上层游戏开发最好的技术手段。 3 dr e a l m s 公司开发的b u i l d 引擎是一个重要的里程碑。它来源于毁灭公 爵( d u k en u d e m3 d ) 。在它的基础上曾先后诞生过1 4 款游戏，其中包括台湾艾 3 中南大学硕士学位论文 第一章绪论 生资讯开发的七侠五义，这是当时国内不多的几款3 d 射击游戏之一。不过 从总体来看，b u i l d 引擎并没有为3 d 引擎的发展带来任何质的变化，突破的任 务最终由i ds o f t w a r e 公司的雷神之锤( q u a k e ) 完成了。 之后，i ds o f t w a r e 公司推出的q u a k e ，采用了一套全新的引擎，可以更充 分地利用3 d 加速和o p e n g l 技术，在图像和网格方面与前作相比有了质的飞跃。 引擎技术对于游戏的作用不仅局限于画面，它还影响到游戏的整体风格。 1 9 9 8 年，两部划时代的作品同时出现在v a l v e 公司的半条命( h a l f - l i f e ) 和l o o k i n gg l a s s 工作室的神偷：暗黑计划( t h i e f ：t h ed a r kp r o j e c t ) 。它们对 后来的作品以及引擎技术的进化有着深远影响。 从本世纪开始，3 d 引擎朝着两个不同的方向分化：一是通过融入更多的叙 事成分和角色扮演成分以及加强游戏的人工智能来提高游戏的可玩性，二是朝着 纯粹的网络模式发展。这期间的作品有i ds o f t w a r e 公司的雷神之锤3 竞技场 ( q u a k ei ha r e n a ) ，它与e p i c 公司的虚幻竞技场( u n r e a lt o u r n a m e n t ) - - h 成为 引擎发展史上的一个转折点。 2 0 0 1 年后，又有许多优秀的3 d 射击游戏陆续发布，引擎技术在画面真实性 和内容真实性方面又有了新的突破。m a x f x 引擎是第一款支持辐射光影渲染 技术的引擎，物体有十分逼真的光影效果。g e o m o d 引擎也追求内容的真实， 它是第一款可任意改变几何体形状的3 d 引擎。 现在的3 d 引擎逐渐加入了人工智能，这极大地增加了游戏的真实性与趣味 性。 1 2 3 国内发展状况 在国内，3 d 游戏引擎的研究起步比较晚，基本还是基于国外一些开源引擎 在作进一步的研究与发展。随着2 0 0 0 年初，中国网络游戏市场的发展，国内3 d 引擎的研究开始迅速发展起来。 目前国内的大部分网络游戏都是代理韩国和欧美等国家的，如传奇、魔 兽世界以及天堂2 。一些具有软件强研发实力的公司开发的都是基于2 d 游 戏引擎上的网络游戏，如网易的大话西游、梦幻西游；金山的封神榜， 盛大的传奇世界等等。即使有一些公司开发了3 d 游戏引擎，但是这些引擎 渲染质量差，速度低。 造成这种现状的原因很多，除了上面提到的人才匮乏外，还有就是国内起步 比较晚、资料的短缺等。开发一个高效、结实的三维游戏引擎，解决一些其中的 关键技术，在国内已非常必要了。 4 中南大学硕士学位论文第一章绪论 1 3 研究工作 概括而言，主要研究工作有： ( 1 ) 研究当今的游戏场景绘制与全局光照技术，并进行深入的探讨。 ( 2 ) 研究三角形网格在地形生成上的应用。 ( 3 ) 研究室外地形快速生成技术。3 d 游戏引擎室外场景渲染的关键技术是 地形生成与地形渲染。地形技术有着非常广泛的应用，不论是实现3 d 游戏、计 算机模拟、地理信息系统还是实现航运或交通导航系统，地形技术都举足轻重。 如何高效地实现大规模地形绘制也是最为关键的问题。论文充分利用三角形网格 的便利性以及它的平面性来建模，并研究其建模步骤，对几何体表面如何细分也 将进行深入研究。研究视域衰减模型以及如何利用它来加速场景的快速绘制。 ( 4 ) 基于预计算可以加速真实感图形的显示。这在3 d 游戏场景绘制中是非 常重要的。我们总结了预计算技术，并在此基础上得出自己的全局光照明模型。 ( 5 ) 研究如何在静态场景下实现的场景的动画效果，并给出了自己的新的算 法以及实验步骤与结果。 中南大学硕士学位论文第二章场景加速绘制与全局光照相关技术 第二章场景加速绘制与全局光照相关技术 2 1 通用裁剪加速技术 裁剪的意思就是“从大量事物中进行删除”，在计算机图形学中，相对应的就 是裁剪技术( c u l l i n gt e c h n o l o g i e s ) 所要做的工作。“大量事物”是需要绘制的整个场 景，删除的是对最终图像没有贡献的场景部分，然后将剩余场景发送到绘制管线。 在交互式速率下绘制复杂场景的关键是如何有效的确定三维场景的可见部 分。如果场景中的局部多边形在视域之外则不需要进行绘制，可见性裁剪算法正 是基于这一原则减少输入到图形绘制管道的多边形数目，从而加速场景绘制。图 2 - 1 展示了常见的背面裁剪、遮挡裁剪及视锥体裁剪技术。背面裁剪将背向视点 的物体删除，这是一种非常简单的操作，每次只能删除一个多边形。视锥裁剪将 视锥之外的多边形删除，相对而言，这种操作稍微复杂一点。遮挡裁剪将被其它 物体遮挡的物体删除，这是一种最复杂的裁剪操作，因为它需要聚集一个或者多 个物体，同时还使用其他物体的位置信息。 视点 2 1 1 聚集背面裁剪 视锥体裁剪 图2 - 1 不同的裁剪技术 背面裁剪是最基本的可见性裁剪技术， 位置与方向，裁剪掉背向视方向的多边形， 6 具体方法是利用三维场景中模型的 以减少需要绘制的多边形数量。如果 中南大学硕士学位论文 第二章场景加速绘制与全局光照相关技术 在三维场景中有一个不透明的球体，则处于视线背面的、大约有一半的球体是 看不到的，那么在进行绘制时，就不必绘制看不到的部分。 判断需要裁剪的背面多边形，可以从多边形所在平面( 选择其中一个顶点是 最简单的方式) 上任何一个点到视点位置创建一个向量，然后计算这个向量与多 边形法线之间的点积，点积为负表明两个向量之间的夹角大于n 2 ，因此多边形 就没有朝向视点，应该裁剪掉。早期的典型的方法是层次表示法，如包围盒和八 叉树。此后，f u c h e s 提出了b s p 树方法，其主要思想是选取一个空间平面将物 体空间分割成两部分，将每一子空间内所含景物分别赋给该物体空间结构树的两 个子树，子树里的物体如果与视点处于平面同一侧，则这些物体将处于另一子树 里的物体之前，因而可能对它们形成遮挡然后递归地对己生成的两棵子树重复这 个操作，最终将生成一棵场景树【8 l 。从当前视点出发，遍历场景树，即可按严格 的从前往后或者从后往前顺序绘制场景。由于在树的各层次节点里，可以放置景 物的包围盒数据，因而可以形成场景的层次包围盒结构，这对光线跟踪算法和视 域裁剪算法中的加速求交很有利。但该方法由于以面为划分单元，因而会产生大 量新面片。 k u m a r 提出了一种快速简洁的背面裁剪算法，能精确地对物体空间的多边形 进行背面裁剪，并且所占用的存储空间仅为通用表面法向量的一半【9 】。该算法基 于多边形方向相似性和几何距离将输入模型划分成一个层次结构，视域空间也被 划分成与模型几何层次相对应的层次结构。在每一帧图像绘制中，通过将视点位 置和输入模型的几何层次划分相比较来实现背面多边形的裁剪。同时，该算法还 利用帧的相关性来加速背面裁剪。 2 1 2 层次视锥体裁剪 视锥体裁剪算法通常采用边界体层次结构或某一空间数据结构( 诸如 k d t r e e 树、八叉树或b s p 树) 来裁剪多边形。通过将视锥体与层次结构进行比 较，迅速将场景中位于视锥体之外的多边形裁剪掉【1 0 】。视锥体裁剪算法首先建 立一棵边界体树，然后遍历树结构用来测试视锥体是否与边界体相交。如果边界 体不与视锥体相交，则边界体的子树也位于视锥体之外，因此，停止遍历树结构。 由于所绘制场景中大部分多边形是静态的，因此，通过一种空间数据结构来实现 快速的视锥体裁剪，如八叉树结构【1 1 】、二叉树b s p 空间分割法。 s l a t e r 提出了一种视锥体可见性裁剪算法，充分考虑了帧的相关性【l2 1 。根据 物体所处位置，可将场景中的对象划分为三个集合：全部在视锥体之外、全部位 于视锥体之内，部分与视锥体边界相交。当视点在三维复杂场景中移动时，大部 分物体位于视锥体之外。根据帧的相关性可推知这三个集合改变缓慢。利用帧的 7 中南大学硕士学位论文第二章场景加速绘制与全局光照相关技术 相关性，s l a t e r 提出了一种快速将场景中的对象进行分类的方法。对位于视锥体 之外的对象，依据其距离视点的远近划分为一些子集，并按照对象的可见概率将 其划分为不同的集合。算法使用b s p 树结构来实现，在1 1 0 0 0 个多边形的场景 中，其绘制速度是层次边界包围盒裁剪算法的2 倍，并且在视点移动时，只有 1 4 帧多边形( 胁1 e p o l y g o n ) 传输到图形处理流水线。 a s s a r s s o n 提出了一种视锥体裁剪算法，通过收缩视锥体来判断物体上点的 与视锥体的几何关系，实现快速的对多边形进行裁剪【1 3 】。 2 1 3 遮挡裁剪 视锥体裁剪算法用来裁剪掉视锥体之外的对象，但是视锥体之内的对象并 非一直可见的，一些物体可能被场景中的其他对象遮挡或隐藏起来，因此，在 场景绘制前也没有必要将这些对象输送到绘制管道进行绘制。遮挡裁剪是比视锥 体裁剪更复杂的算法，用来确定视锥体之内哪些多边形被其他对象遮挡而不需要 绘制。算法中遮挡其他对象的物体称为遮挡体( o c c l u d e r s ) ，被遮挡的物体称为遮 挡对象( o c c l u d e e s ) ，如图2 2 所示。 视 被遮挡 图2 - 2 遮挡裁剪示意图 遮挡裁剪技术的关键是如何确定场景中的最佳候选遮挡体，最简单的方法是 将视锥体之内距离视点较近的对象作为遮挡体。c o o r g 与t e l l e r 建议在给定视点 下，对每一个可能的遮挡体计算所有可能被遮挡物体的区域，这些区域被遮挡体 的边界平面所划分，然后将遮挡对象同这些区域进行相交测试，如果对象的边界 完全位于这些区域内，则在该视点下这些对象是不可见的【1 4 1 川。 传统z 缓存算法有效地利用了图像空间相关性来加快可见性的判定，但它 未能同时有效利用物空间相关性。g r e e n e 提出用层次z 缓存进行可见性裁剪的 算法，它将场景中的景物组织成空间八叉树，并利用景物的空间连贯性来考察每 一个八叉树结点的可见性【1 6 1 7 】。若某个八叉树结点所对应立方体的六个表面相对 中南大学硕士学位论文第二章场景加速绘制与全局光照相关技术 当前的缓存器不可见，则该立方体内上任何景物均不可见，否则，需要进一步确 定该节点的子节点的可见性。若该节点为叶节点，则该可见节点的所有景物需逐 一绘制。为提高节点立方体关于z 缓存的可见性判断效率，层次z 缓存算法将 屏幕像素上的可见点按其深度值构成一棵四叉树，以便快速拒绝被遮挡节点。该 结构是一个分层结构，其中后一级z 缓存的分辨率是前一级z 缓存的四分之一， 其中每一z 缓存像素所存储的z 值是该像素在屏幕上所对应的正方区域中各屏 幕像素所含可见点的最大z 值。这样，利用层次z 缓存算法就可实现景物的八 叉树结点和当前屏幕像素可见点集合的快速区域重叠测试和深度比较，进而快速 地判定节点和面片的可见性。 层次z 缓存算法能高效地裁剪不可见景物。但该方法有以下缺点：只适合 于高遮挡率场景无法采用现有的硬件来更新层次z 缓存，当屏幕上存在极少像 素尚未被景物覆盖，程序不能快速终止由于八叉树管理的复杂性，对于动态场景 层次z 缓存算法不能提供实时性能。 张寒松等注意到了层次z 缓存算法的缺陷，提出了用层次遮挡图结构来进 行可见性裁剪，并对图形硬件和近似可见性裁剪提供支持。遮挡图是一帧二维图 像，其中每个像素记录了屏幕空间的一个方形区域的不透明度【1 8 , 1 9 】。若投影区域 被设置为不透明，则不透明度定义为其中不透明区域面积与整个方形区域面积之 比。这样，在绘制过程中，算法不断更新与层次z 缓存同分辨率的层次遮挡图。 若某一节点的不透明度大于给定的阈值，则说明该节点在屏幕上所对应的区域像 素已基本填满，无论剩下多少景物尚未绘制，程序将结束对该区域内屏幕像素的 绘制。剩余未填完的像素可简单地用背景或相邻像素颜色填上即可。 h u d s o n 提出了通过计算与遮挡体的阴影体相交测试来进行多边形裁剪，其 裁剪方法与视锥体裁剪基本一致。这是由于阴影体与视锥体相似，惟一不同的是 阴影体不存在远端的包围平面，并且可能有多于四个的边平面【2 0 1 。算法利用层 次数据结构进行视锥体裁剪、确定遮挡体，然后测试剩下的物体与遮挡体的相交 性。理想的遮挡体通过将其投影到视平面，计算遮挡物体边界包围体的内向角的 大小，选择角度越大的遮挡体，裁剪效果越好。 2 1 4 入口裁剪 对于建筑模型来说，有很多算法可以归结为入口裁剪( p o r t a lc u l l i n g ) 。在这 方面，最早的算法由a i r e y 提出【2 1 2 2 】，随后t e l l e r 和s e q u i n 2 3 2 4 1 以及t e l l e r 和 h a n r a h a n 2 5 1 构造了更有效、更复杂的算法。 入1 3 裁剪算法基本思想就是在室内场景中，建筑物墙面通常充当大的遮挡 物，通过每个入口进行视锥裁剪。当遍历入口的时候，就减小视锥，使得入口尽 9 中南大学硕士学位论文 第二章场景加速绘制与全局光照相关技术 可能紧密贴合。 入1 3 裁剪方法以某种方式对场景进行预处理，可以是自动形式，也可以是手 工形式。可以将场景分割为一系列单元；( c e l l s ) ，它们通常对应于建筑物中的房间或 者走廊；连接邻接房间的门和窗户称为入1 2 1 ( p o r t a l s ) 。单元中的每个物体和单元 的墙面可以存储在一个与单元关联的数据结构中，还可以将邻接单元和连接这些 单元的入口信息保存在一个邻接图中。t e l l e r 曾经给出了一些算法来对这种图进 行计算，别外一种经常使用的方法就是用手工方式来创建这个邻接图。 l u e b k e 和g e o r g e s 使用了一种简单的方法，只需要非常小的预处理【2 6 1 。其 中唯一需要的就是上面介绍的每个单元相关联的数据结构。用显示单元体集合方 法减少预处理的计算量。根据视点所在单元体定义一个二维边界体穿过整个场景 空间，绘制包含视点的单元体，将视点所在单元体的每个入口投影到屏幕空间， 计算其二维轴向边界体在屏幕空间的四边形区域。如果边界体四边形与相交则入 口是可见的，绘制包含入口的单元体。对于单元体，通过同样的入口视锥体迭代 处理方法，对其入口单元体的可见性进行判断。 2 2 真实感图形生成 真实感图形算法主要用于计算全局光照的分布、物体表面复杂的反射或透射 等光学特性以及它们之间的相互作用。其内容主要有全局光照算法、阴影生成技 术、物体模型表面几何细节和光学特性处理技术等。全局光照算法包括光线追踪 和辐射度两大类，表面细节处理方法包括各类纹理映射、双向反射特性模型等。 2 2 1 光线跟踪算法 光线跟踪算法是生成真实感图形的主要算法之一【z7 。由于该算法原理简单， 实现方便，且能生成各种逼真的视觉效果，因而在c a d 及图形学各领域得到了 广泛的应用。光线跟踪算法由原来用于消除场景中隐藏面的光线投射算法演变而 来。1 9 8 0 年，w h i t t e d 将光线投射算法扩展为递归算法，进而提出了一个与之相 匹配的整体光照明模型w h i t t e d 模型【2 8 】。从此以后光线跟踪算法得到了广泛的 注意和研究，成为8 0 年代图形学的一个研究热点。 在许多方面，光线跟踪是对局部光照模型绘制的一个逻辑推广。它是基于我 们先前的经验，即在所有从光源发出的光线中，对图像有贡献的只是那些进入虚 拟照相机的镜头且经过投影中心的光线。图2 3 显示的一个点光源与一些理想镜 面对象间相互作用的几种可能方式。进入照相机镜头的光线，有的是直接来自于 光源，有的来自于对象表面反射光线，这些光线可能经过多个对象表面的多次反 1 0 中南大学硕士学位论文第二章场景加速绘制与全局光照相关技术 射，有的来自经过一个或多个对象表面的折射。 实际上，整个过程是反的。如图2 - 4 ，光线从眼睛发出，透过像素中心后进 入场景。跟踪它的路径，看这条光线首行命中的对象是什么，命中点又在哪里( 因 为光线首先命中的表面是离眼睛最近的对象，更远的表面光线根本无法到达，所 以这个过程自动解决了隐藏面问题) 。如果对场景中的光源作了规定，使用一些 用在第一命中点处的明暗处理模型，如p h o n g 明暗处理模型，就可以计算出环境 光、漫反射光以及光的镜面反射分量。然后，所形成的颜色就会在像素上显示出 来。因为光线的路径通过整个场景，所以类似于明暗、反射和折射，可以有机地 将多种效果结合在一起，产生逼真的图像。 照相机 嬲疆 图2 3 光线跟踪的一个图图2 _ 4 逆向光线 光线跟踪可以用于可见性测试( 当一个三维场景映射至二维时) 与计算阴影， 但它真正的作用是用于计算镜面反射与折射。 基本的光线跟踪算法是非常简单且易于实现的，而且它能计算出用其它方法 会非常棘手的一些视觉现象。蒙特卡罗( m o n t ec a r l o ) 光线跟踪增加了远距离光 照效果如软阴影与环境消隐、光泽与漫反射、景深以及运动模糊等。 在标准的光线跟踪算法中，有两个隐含的假设：( 1 ) 光线是一根没有大小的 直线，亦即是数学意义上的直线；( 2 ) 景物表面是完全光滑的，光在表面的反射 遵循镜面反射和规则透射规律。由w h i t t e d 模型可知，景物表面上每一可见点处 的光亮度由以下三个部分组成： ( 1 )光源直接照射而引起的光亮度。 ( 2 )来自环境中其它物体的入射光在表面产生的镜面反射光亮度。 ( 3 )来自环境中其它物体的入射光在表面产生的规则透射光亮度。 由于从光源发出的光线有无穷多条，使得直接从光源出发对光线进行跟踪变 得非常困难。实际上，从光源发出的光线只有少数经由场景中景物表面之间的反 中南大学硕士学位论文第二章场景加速绘制与全局光照相关技术 射和透射后到达观察者的眼中。所以，算法从视点出发，通过图像平面上每一象 素中心向场景发出一条光线，若光线与场景中物体无交，则光线将射出画面，跟 踪结束。否则，光线与物体有交。它有三种可能： ( 1 ) 当前交点所在的景物表面为理想漫射面，跟踪结束。 ( 2 ) 当前所在的物体表面为理想镜面，光线沿其镜面反射方向继续跟踪。 ( 3 ) 当前交点所在物体表面为规则透射面，光线沿其规则透射方向继续跟踪。 其实现是一个递归过程。 虽然光线在物体间的反射和折射可以无限地进行下去，但在实际计算时不可 能做无休止的光线跟踪，因而需要给出光线跟踪的终判条件。一般来说，光线跟 踪的终判条件有以下两种： ( 1 ) 光线射出画面，即光线与场景中的物体没有交点；或者与光线相交的最 近物体表面为漫射面；或者当前跟踪层次已经超过用户设定的最大跟踪层数。 ( 2 ) 跟踪光线对显示象素光亮度的贡献小于预先给定的阈值。 为了跟踪光线，可以使用了一个方便的表示法来表示通过特定像素的光线。 如图2 5 ，先构造一个用于光线跟踪的照相机。 a 么 图2 - 5 构造用于光线跟踪的照相机 眼睛在点“眼睛”处，照相机的轴与向量厅、哥、元一致，近平面位于眼睛前 方距离处，帧缓冲就在这个近平面上。照相机的视角为p ，近平面视窗的纵横 l l ( 也p q 高宽比) 就a s p e c t 。因此，照相机在哥方向从一日延伸到h ，在厅方向从一形 延伸到w ，其中 h = n t a n ( o 2 )( 2 1 ) g o = h a s p e c t( 2 2 ) 因为通过视口变换，在近平面上的点和视口中的像素之间可以建立对应关 系。这同样利用了对应关系，只是不用显式视口变换。实际上最简单的方法就是， 1 2 中南大学硕士学位论文第二章场景加速绘制与全局光照相关技术 把视口看成贴到了近平面视窗上，于是眼睛就“透过”单个像素看场景。假设在视 口中有n c o l s xn r o w s 像素，考虑第，行、第c 列的那个像素，这里，从0 变到 n r o w s 一1 ，c 从0 变到n c o l s 一1 。我们称这个像素为，c 像素。则在近平面上，像 素的左下角位于( “。，v ，) 处，其中： 甜。= 一形+ 形羔，c = o ，1 ，n c o l s - 1 ( 2 - 3 ) 咋= 一h + 日， ，= o ，1 ，n r o w s - 1 ( 2 4 ) 它在3 d 中所处的位置也就是近平面上的实际点。为此，需确定从“眼睛( e y e ) ” 开始到像素左下角在厅、哥、元方向上分别经过多长距离。结果发现，必须沿一元 方向经过距离、沿厅方向经过距离玩、沿哥方向经过距离可。假设眼睛( 照相 机) 所处的位置为“e y e ”，于是得到3 d 点为， 0 馏一万+ “。历+ 咋哥 ( 2 5 ) 则光线跟踪算法的基本操作是：计算一条从眼睛开始的光线通过近平面上某 个像素后到达什么地方，具体来说，就是该光线命中哪些对象。假设这条光线在 t = 0 时位于“眼睛”处，在t = 1 时穿过像素的第r c 角。它的参数形式是 厂o ) = e y e ( 1 - t ) + ( e y e -+ “。厅+ v r 矿) f ( 2 6 ) 把光线的起始点和方向独立出来，表示成k t ) = 眼睛+ d i r , d 。则得到通过第 厂c 像素的光线表达式为 ，o ) = e y e + d i r ，： 蛾= 一厮川去- 1 ) 舢意- 1 ) 哥 q 7 我们把它命名为第f c 条光线。在这些光线中，每条光线都有一个重要的特 性：随着t 从0 开始增大，光线点会离眼睛越来越远。如果这条光线在它的路径 上碰到两个对象，比如在时刻乞和，那么离眼睛较近的那个对象将是在较d t 值 处被命中的对象。 绘制主要是为图像中的点确定颜色。当三维场景投影n - - 维图像时，我们就 会做这些事。光线跟踪是非常流行的绘制方法。基本的光线跟踪算法主要是对每 一个像素计算：为表面上的一点寻找最相近的颜色值。这取决于物体表面的可见 性，就像是有一条从眼睛射出的光线穿过场景中的物体一样，这种算法有时被叫 做光线投射( r a yc a s t i n g ) 。a p p e l 2 9 1 是最早利用计算机与光线跟踪来绘制图像的。 下面是基本的光线跟踪算法： f o r ( i n tr - - 0 ；r n r o w s ；h 斗) f o r ( i n tc = ：o ；c a a + f i b + y c( 3 - 1 4 ) 当参数从二维空间侬2 映射到三维空间侬3 ，为了使扭曲量最小化。一个自 然的想法就是用分段线性函数来参数化三角形曲面，且面片与曲面三角形要对 应。其中，在参数化过程中，坐标( 吩，u ) 与顶点( 薯，咒，z ，) 是相互关联的。 给定一个参数空间q 的坐标点( “，1 ，) ，它的参数x 由下式给出： x ( u ，y ) = 只+ 丑只+ 五丑 ( 3 1 5 ) 其中( f ，j ，k ) 表示参数空间中包含点( “，v ) 的三角形( 吩，) ，( u j , v ，) ， ( ，u ) 的下标。而三元组( a ，五，五) 则是那个由点( ”，v ) 组成的三角形的重心。 概括而言，对三角形曲面构造参数是一个查找的过程，在这个过程中，对二 元组( 嘶，) 找到其对应的顶点f 。而且，这样的坐标满足这样的条件：在参数空 间里曲面形成的图片是不允许相互交叉的。 一个三角形网格m 由几何元素与拓扑元素组成，拓扑元素可以由一个顶点 集与三角形面集合的联合面成的图形结构( 简单的联合体) 描述，其中 v = “，印)( 3 1 6 ) 其三角形面为 f =