虚拟现实引擎技术研究.doc

1、31淮南师范学院2009届本科毕业论文毕业论文题 目： 虚拟现实引擎技术研究 学生姓名： 张玉伟 学生学号： 059080143 系 别： 计算机与信息工程系 专 业： 计算机科学与技术 届 别： 2009届 指导教师： 杨星 目 录前言(3)1 概述(4)1.1 虚拟现实技术的概述(4)1.2 虚拟现实发展概况(7)1.3 各国虚拟现实技术的研究及应用情况(8)1.4 虚拟现实的技术的主要研究内容(9)1.5 虚拟现实技术的意义(9)2 虚拟现实引擎的结构及其关键技术(9)2.1 虚拟现实系统的组成(9)2.2 虚拟现实技术中引擎的构成(11)2.3 虚拟现实引擎中的几个关键技术(11)3

2、常用的可见性裁减算法(16)3.1 遮挡裁减算法的分类(16)3.2 物体空间的遮挡裁减算法(17)3.3 图像空间的遮挡裁减算法(21)4 可见性裁减的改进算法(24)4.1 组织场景(24)4.2 划分视点单元(24)4.3 计算视点单元的可见性保守集PVS(26)4.4 改进遮挡算法的评价(29)5 总结与展望(29)5.1 总结(29)5.2 展望(30)致谢(30)参考文献(31)虚拟现实引擎技术研究学生：张玉伟指导老师：杨星淮南师范学院计算机与信息工程系摘 要：虚拟现实技术又称灵境技术，它是二十世纪末才兴起的一门崭新的综合性信息技术。本文首先对虚拟现实（Virtual Realit

3、y）技术进行了概括性介绍，阐述了虚拟现实技术的基本概念、特征、发展、应用领域以及国内外的研究现状。虚拟现实中的引擎是虚拟现实技术的核心之一，文中阐述了虚拟现实引擎的体系结构，及其相关的技术，如碰撞检测、可见性裁减、LOD 技术和光照模型。本文对虚拟现实引擎的关键技术之一可见性裁减问题做了研究，并提出了一种改进的遮挡裁减算法，此改进算法是将Durand 提出的扩展投影作为保守可见性预处理的算法与Greene 等人提出层次遮挡图和层次深度图的算法相结合，将遮挡板的扩展投影生成层次遮挡图来判断被遮挡物是否可见，同时保持了扩展算法的基本特性。最后总结了本文的内容以及对本领域的展望。关键词：虚拟现实引擎

4、；可见性；扩展投影；层次遮挡图Engine technology of virtual reality researchStudent: Yu-Wei ZhangInstructor: Yang XingHuainan Normal College of Computer and Information Engineering Abstract：Virtual reality technology, also known as Virtual technology, it is the end of the twentieth century before the rise of a new

5、integrated information technology. This article first Virtual Reality (Virtual Reality) technology for the broad introduction of virtual reality technology on the basic concepts, characteristics, development, applications and research at home and abroad. Virtual reality technology virtual reality en

6、gine is the core of the text set out in the virtual reality engine architecture, and its related technologies, such as collision detection, visibility reduction, LOD technology and illumination model. In this paper, virtual reality engine of one of the key technologies - the reduction of visibility

7、of the research issues and to propose an improved block reduction algorithm, this improved algorithm is proposed to expand Durand projection can be seen as a conservative algorithm with preconditioning Greene and others raised the level of block-level depth map and a combination of graph algorithms

8、to block the expansion of the projector to generate board-level block diagram to determine whether objects can be seen to be blocked, while maintaining the basic characteristics of the expansion algorithm. The final summary of the contents of this article, as well as the prospects in this field. Key

9、 words: virtual reality engine; visibility; expansion of the projector; level block diagram前言VR技术具有超越现实的虚拟性。虚拟现实系统的核心设备仍然是计算机。虚拟现实是在计算机中构造出一个形象逼真的模型。人与该模型可以进行交互，并产生与真实世界中相同的反馈信息，使人们获得和真实世界中一样的感受。当人们需要构造当前不存在的环境（合理虚拟现实）、人类不可能达到的环境（夸张虚拟现实）或构造纯粹虚构的环境（虚幻虚拟现实）以取代需要耗资巨大的真实环境时，就可以利用虚拟现实技术。虚拟现实系统是相当逼真的三维视听、

10、触摸和感觉的虚拟空间环境，虚拟三维可以随需要而变换，交替更迭1。用户不再是被动性的观看，而是融合在其中，交互性的体验和感受虚拟现实世界中广泛的三维多媒体内容。作为一门具有多媒体交互共享模式的新兴技术，虚拟现实技术以其独特的优势，在各个领域的应用越来越广。当人们需要构造当前不存在的环境和人类不可能到达的环境或构造虚拟环境以代替耗资巨大的现实环境时，虚拟现实技术是必不可少的。目前，虚拟现实已被推广到不同领域中，得到广泛应用。1 概述1.1 虚拟现实技术的概述虚拟现实技术（Virtual Reality, 简称VR）是近年来计算机网络世界的热点之一。Virtual reality 概念从美国人加龙兰

11、里尔(Jaron Lanier)在20 世纪80 年代初正式提出，并于90 年代以来兴起的一种新型计算机综合信息技术2。虚拟现实是利用计算机和人机交换的一种方式。虚拟现实技术是目前计算机界比较热门的一项技术。它是用计算机模拟的三维环境对现场真实环境进行仿真，用户可以走进这个环境，可以控制浏览方向，并操纵场景中的对象进行人机交互。虚拟现实技术的发展，不仅从根本上改变人们的工作方式和生活方式，将劳逸真正结合起来，使人们在享受环境中工作，而且虚拟现实技术与美术、音乐等文化艺术的结合，使人们在工作过程中得到享受；随着计算机技术的发展，在PC机上实现虚拟现实技术已成为可能。1.1.1 虚拟现实技术概念虚

12、拟现实技术（virtual reality,简称VR）又称虚拟环境，虚拟现实技术(VR) 是一种模拟人在自然环境中的视觉、听觉、触觉等行为的高度逼真的人机交互技术，是利用人类感知能力和操作能力的新方法。在VR虚拟现实中，人们利用头盔显示器、图形眼镜、数据服、立体声耳机、数据手套及脚踏板等多维输入输出设备通过传感器装置与计算机生成的三维虚拟环境交互作用,可获得视觉、听觉、触觉等多种感知反馈,并按照自己的意愿去实时地改变虚拟环境。1.1.2 虚拟现实技术的原理与特征虚拟现实技术起源于可视化化，是多媒体技术的延伸，反映了人机关系的演化过程，是一种多维信息的人机界面它在计算机中构造出一种具有三维世界效

13、果的模拟环境（如飞机驾驶舱、操作现场等）同时还可以通过各种传感设备，使用户“投入”到该环境中，实现用户与该环境进行直接交换操作，并产生与现实世界中相同的反馈信息，使人们得到与在现实世界中同样的感受2。虚拟现实系统实际上是一种先进的人机接口。它是利用计算机以及专用硬件和软件去仿真各种现实环境，通过计算机和信息技术构造虚拟自然环境，将用户和计算机结合成一个整体。用户置身于模仿真实世界而创建的三维电子环境中，通过各种技术模拟直接进入到虚拟环境中去接受和影响环境中的各种感觉刺激，与虚拟现实的人及物进行思想和行为的交流。用户可以利用人类本能的方式与计算机交流，人的语言、眼神、手势都可以为计算机所识别，而

14、人则可以用听觉、视觉、触觉来感受计算机信息，如同现实环境中人与人交流一样的感受和交互对话，达到与计算机进行直观、自然的交互。构造VR系统的目的和所需的技术如图1.1所示：VR技术的根本目的是：不仅能够杂多维信息空间仿真建模，而且能够帮助人们获取知识和形成新的概念。图1.1 构造VR系统的目的和所需的技术虚拟现实技术具有以下三个重要特征2：(1) 交互性（Interaction）：是指用户对模拟环境内物体的可操作程度和从环境中得到反馈的自然程度（包括实时性）。(2) 沉浸感（Immersion）：它是指用户感到作为主角存在于模拟环境中的真实程度。沉浸感被认为是VR 系统的性能尺度，导致“沉浸感”

15、的原因是用户对计算机环境中的虚拟物体产生了类似于对现实物体的存在意识或幻觉。(3) 构想性（Imagination）：是指用户通过对虚拟环境中物体的操纵与观察加深对事物的认识和理解，提高感性与理性认识，从而启发新的构思。VR 系统中虚拟环境设计不仅可以来自真实世界，也可来自人的想象世界。特别是将现实生活中出现的复杂、危险环境，用虚拟技术显现出来，使用户得到亲历与锻炼机会，从而提高认识问题、解决问题的能力。1.1.3 虚拟现实系统的分类和构成虚拟现实系统按其功能高低大体分为4类4：（1）桌面虚拟现实系统,也称窗口中的VR。它主要在台式计算机上实现,所以成本低,功能也最简单,主要用于CAD、CAM

16、、建筑设计、桌面游戏等领域。（2）沉浸虚拟现实系统,如各种用途的体验器,使人有身临其境的感觉,各种培训、演示以及高级游戏等均可用这种系统。（3）分布式虚拟现实系统,它在因特网环境下,充分利用分布于各地的资源,协同开发各种虚拟现实的利用。它通常是沉浸虚拟现实系统的发展,也就是把分布于不同地方的沉浸虚拟现实系统,通过因特网连接起来,共同实现某种用途。美国大型军用交互仿真系统NPSNET以及因特网上多人游戏MUD便是这类系统。（4）增强现实或混合现实系统。它是把真实环境和VR虚拟现实环境结合起来的一种系统,既可减少构成复杂真实环境的开销,又可对实际物体进行操作,真正达到了亦真亦幻的境界,是今后的发展

17、方向之一。1.1.4 虚拟现实技术主要应用领域虚拟现实使参与者处于一个具有身临其境的感觉、具有完善交互作用能力的、能帮助和启发构思的信息环境，通过与所处环境的交互作用，利用人本身对接触事物的感知和认知能力，以全方位的方式获取各式各样表现形式的信息5。因此，虚拟现实技术的应用前景是很广阔的。目前，虚拟现实的主要应用领域主要涉及到以下几个方面：(1) 军事、航天、航空军事、航天和航空部门一直十分重视VR 技术，并且投入了巨额资金，用于人员培训、产品设计测试和战略规划等方面，典型成果如SIMNET 虚拟战场、虚拟毒刺导弹训练器、波音飞机虚拟设计系统和宇航员太空训练系统等。(2) 娱乐、艺术虚拟音乐、

18、虚拟博物馆、虚拟画廊、虚拟演员、虚拟电影、虚拟游戏等都是当时随时可听到的虚拟现实成果，该方面的应用是目前VR 技术应用最多的领域之一。(3) 教育培训利用虚拟现实技术进行虚拟实验可以避免某些真实实验或操作不当可能带来的各种危险；也可以突破时间、空间的界限同时还能有效地利用教学资源。(4) 房地产开发项目房地产开发仿真系统和虚拟样板房系统以虚拟现实技术平台为基础，以同样的工作模式将房地产楼盘建筑外观，景观绿化，各款户型的最终设计结果，通过计算机图纸绘制成精确的三维数字模型，导入虚拟程序，模拟建成后的真实效果（即楼盘的虚拟环境和虚拟样板房）。(5) 医疗主要应用包括解剖学和病理学教学、外科手术训练

19、、复杂外科手术的规划、手术期间的信息支持、遥控手术等；(6) 通信VR 技术与通信技术相结合，可以为不在同一地理位置或不能同时到场的人们建立一个协同工作的环境。在这个虚拟环境下，人们可以共同讨论、交流、指挥和决策。(7) 商业“体验广告”、股票及金融数据可视化、虚拟商场购物、商场装饰的VR 设计等方面是目前VR 在商业中应用最多的地方。1.2 虚拟现实发展概况虚拟现实技术与多媒体、网络技术并称为三大前景最好的计算机技术。自1962年，美国发明了实感全景仿真机的开始，90年代初期，技术不断完善，进入到实际的应用阶段7。2000年后，整合正在发展的XML、JAVA、流技术等先进技术，应用包括更强大

20、、更高效的3D技术能力、渲染力量和传输速度，以及对数据流强有力的控制等多种多样的交互式技术，虚拟现实技术进入了一个崭新的发展时代：以三个I即 Immersion沉浸感，Interaction交互性，Imagination思维构想性，作为虚拟现实技术最本质的特点，并融合了其它先进技术，在国际互联网发展迅速的今天，具有广泛的应用前景，虚拟现实技术越来越受到各个行业和大众的关注。1.3 各国虚拟现实技术的研究及应用情况（1）美国 美国作为VR技术的发源地，其研究水平基本上就代表国际VR发展的水平。目前美国在该领域的基础研究主要集中在感知、用户界面、后台软件和硬件四个方面。美国宇航局（NASA）的Am

21、es实验室研究主要集中在一下方面：将数据手套工程化，使其成为可用性较高的产品；在约翰逊空间中心完成空间站操作的实时仿真；大量运用了面向座舱的飞行模拟技术；对哈勃太空望远镜的仿真9。现在正致力于一个叫“虚拟行星探索”（vPE）的试验计划。现在NASA已经建立了航空、卫星维护VR训练系统，空间站VR训练系统，并且已经建立了可供全国使用的VR教育系统。华盛顿大学华盛顿技术中心的人机界面技术实验室（lilt lab），将VR研究引入了教育设计娱乐和制造领域。（2）英国在VR开发的某些方面，特别是在分布式并行处理、辅助设备（包括触觉反馈）设计和应用方面，在英国是领先的，尤其是在欧洲8。（3）日本日本主要

22、致力于建立大规模VR知识库的研究，在虚拟现实的游戏方面的研究处于领先地位。京都的先进电子通信研究所（ATR）正在开发一套系统，它能用图像处理来识别手势和面部表情，并把它们作为系统输入。日本奈良尖端技术研究生院大学教授千原国宏领导的研究小组于2004年开发了一种嗅觉模拟器，只要把虚拟空间里的水果拉到鼻尖上一闻，装置就会在鼻尖处放出水果的香味，这是虚拟现实技术在嗅觉研究领域的一项突破10。（4）中国中国VR技术研究起步较晚，与国外发达国家还有一定的差距，但现在已引起国家有关部门和科学家的高度重视，并根据我国的国情，制定了开展VR技术的研究计划。九五规划、国家自然科学基金委、国家高技术研究发证计划等

23、都把VR列入了研究项目11。国内一些重点院校，已积极投入到了这一领域的研究工作。清华大学计算机科学和技术系、西安交通大学信息工程研究所、北方工业大学CAD 研究中心、西北工业大学CAD/CAM 研究中心、上海交通大学图像处理模式识别研究所，长沙国防科技大学计算机研究所、安徽大学电子工程与科学系等单位也进行了一些研究工作和尝试。1.4 虚拟现实的技术的主要研究内容（1）人与场景的融合技术，人与场景的融合主要体现沉浸与交互特征。（2）物体对象的仿真技术，物体对象的仿真技术主要演剧几何仿真、物理仿真和行为仿真。（3）三维地形建模技术，可视化的GIS系统以及GPS军事分布式虚拟环境的重要研究内容，在建

24、筑规划、水利工程中地理信息系统与三维数字地形是一个十分重要的研究内容12。（4） 图形图像的实时生成与合成技术，实时显示的刷新频率大于15帧/秒，复杂的场景显示由于计算量巨大，必须采用层次信息模型与逐步求精技术。双屏显示的同步问题也是立体显示的一个关键。1.5 虚拟现实技术的意义虚拟现实（VR）技术是近年来出现的高新技术。VR是一项综合集成技术，涉及计算机图形学、人机交互技术、传感技术、人工智能等领域，它用计算机生成逼真的三维视觉、听觉、嗅觉等感觉，使人作为参与者通过适当的装置，自然的对虚拟世界进行体验和交互作用。在虚拟现实中强调了人的主导作用，虚拟现实技术不仅实现了从“计算机为主体”到“人为

25、主体”的转变，而且实现了“适计算机化的单维信息空间”到“适人化的多维信息空间”的转变17。过去的人机界面（人同计算机的交流）要求人去适应计算机，而使用虚拟现实技术后，人可以不必意识到自己在同计算机打交道，而可以像在日常环境中处理事情一样同计算机交流。这就把人从操作计算机的复杂工作中解放出来。在信息技术日益复杂、用途日益广泛的今天，这对充分发挥信息技术的潜力具有重大的意义。2 虚拟现实引擎的结构及其关键技术本部分主要介绍了虚拟现实系统的组成以及通用结构，并详细介绍其核心部件-虚拟现实引擎，阐述虚拟现实引擎的四个关键技术：可见性裁减、LOD 技术，碰撞检测及光照模型3。2.1 虚拟现实系统的组成V

26、R是一个十分复杂的系统，涉及的技术包括图形图像处理、语音处理与音响、模式识别、人工智能、智能接口、传感器、实时分布系统、数据库、并行处理、系统建模与仿真、系统集成及跟踪定位等。VR的技术组成如图2.1所示19。从图中可以看出，典型的虚拟现实系统的基本组成包括2：（1） 效果产生器：完成人于虚拟环境交互的硬件接口装置；（2） 实景仿真器：系统的核心部分，由计算机软件系统、软件开发工具等组成；（3） 应用系统:面向具体问题的软件部分，描述仿真的具体内容；（4） 几何构造系统：提供描述仿真对象的物理特性的信息。 2.1 VR系统组成虚拟现实（VR）系统简化后的通用体系结构，如图2.2 所示3。主要是

27、由虚拟现实引擎（VR Engine）和输出/输入处理子系统有机的结合起来，形成一个较为完整的VR 系统。VR引擎实质上是一个包括虚拟世界数据库的高性能计算机系统。该数据库包含了虚拟环境对象的描述及对象的运动、行为及碰撞作用等性质的描述。图2.2 VR系统通用体系结构输入/输出（I/O）处理子系统可以分为：(1) 网络通信模块 ：主要为引擎提供网络通信、数据传输以及控制等功能。(2) 输入/输出模块：主要就是负责接收键盘、鼠标和操纵杆等输入设备的控制命令，以及打印、导入/导出数据等输入/输出功能的管理。(3) 辅助工具模块：主要是为引擎提供一些辅助功能。(4) 音乐音效模块：主要是完成引擎的声音

28、和音效处理，这里的声音主要指的是双声道立体声。2.2 虚拟现实技术中引擎的构成虚拟现实(VR)引擎是虚拟现实系统中最为关键的部件之一13。虚拟现实引擎可以有下模块构成，如图2.3所示：(1) 对象处理：是引擎最基本的组织方式。引擎对世界的构造是以对象为基础的。(2) 摄像机：该模块完成场景的显示。它按照人类的正常视觉对场景进行处理，裁减掉视域外的内容然后把裁减后场景投影到屏幕空间。(3) 场景构造：该模块从世界数据库中提取相应的场景数据，并构造场景。世界数据库中包含场景的必要信息和数据。(4) 场景渲染：这是引擎中最重要的子模块之一。负责实现基本图元的绘制、光线处理和纹理处理等。三维引擎的好坏

29、，在很大程度上取决于图形渲染模块的质量。(5) 事件处理：事件就是对象状态的变化。事件的含义一般由程序来定义，程序根据触发事件的不同，把不同的消息发送到与该事件相关的模块进行处理。(6) 碰撞检测：碰撞检测是三维图形引擎中不可缺少的重要组成部分。在实现该模块时，最重要的就是要在一定精度的前提下尽量地提高碰撞检测的速度。碰撞检测不应该过分地影响图形渲染的速度和质量。图2.3虚拟现实引擎的结构2.3 虚拟现实引擎中的几个关键技术2.3.1 可见性裁减技术 可见性判断，即从某个视点决定哪些面可见，从任何视点看，都会存在一些对象遮挡着其他一些对象，而且当你移动头部的时候，对象遮挡的部分就会发生变化，同

30、时会有新的部分进入视野。可见性裁减是也计算机图形学的基本问题，也是图形绘制管线提高图形显示帧率的关键技术之一，也是虚拟现实引擎中的一个关键技术。我们不能将场景与几何模型简单地送入渲染管道，我们需要加速算法。而在游戏中使用的场景更特殊，它的面片几乎全是具有纹理的，所以渲染多边形的代价成倍提高。为加速绘制场景，可以使用裁减技术，目的是找到从视点处可以看到并需要进一步处理的所有物体。可见性裁减大致分为三种：视截体裁减、背面裁减和遮挡裁减，如图2.4所示。视截体和背面裁减是最常用的。视截体裁减是丢弃场景中位于视截体之外的部分，避免绘制和裁减过程作无谓的处理，通常的做法是将空间上连贯的图元组成对象，采用

31、层次包围盒来排除不可见对象；背面裁减就是避免绘制物体上那些背向观察者的面。判断多边形面是否为背面，可由观察点与面法向量的点积来判断，因为背面的法向量总是在背离观察点的方向上；遮挡裁减一般基于可见性预计算，比较复杂，对于简单的场景来说可能并不需要进行遮挡裁减，但是对于大规模密集的场景来说遮挡裁减是必不可少的。图 2.4 三种类型的裁减2.3.2 LOD 技术LOD 也就是层次细节（Level of Detail）的简称，目前比较常用的在减少计算机开销的同时保证良好的视觉效果的方法2。应用该技术的对象具有不同精细程度的多层模型，在实景仿真过程中，具体使用哪个层次模型表示物体由视点与物体之间的距离决

32、定，视点与物体之间的距离越近，使用的模型就越越精细，多边形数量就越多。当视点远离该物体时，就不再需要表现过多的物体细节，其基本原理是如果所产生的图像只占屏幕很少的一些像素则没必要渲染太多多边形，这样每当视点足够远的时候，我们就使用对象的哦一个低细节版本，所得渲染图像之间差别很小，可以忽略不计，这样，就可以在将当前需要绘制的多边形数量控制在一个范围内的同时，尽可能的表现出感兴趣的物体细节，提高绘制效果。使用LOD时，一般根据视点与用户设定的模型几何中心的距离来设置相关函数的具体数值，从而确定每个层次模型的可见距离范围在仿真过程中，不断计算视点与模型之间的距离，根据这个距离落在某一层次模型对应的范

33、围内确定使用该层次的模型来表示物体。由于只是简单的定义了一系列的数值来控制模型各个层次之间的切换，所以会产生在当前视点下看不到的物体也用其模型中最细致的一个层次来表示，从从而导致计算性能下降的问题。如图2.5所示，其中A、B、C分别为场景中的物体，为当前的视角，B虽然位于视点的后方，但由于距离视点较近，所以仍使用0层的LOD对它进行描述。图2.5 LOD层次与视角的关系在大规模场景的绘制中，使用层次细节可以有效的提高场景绘制的速度。产生细节层次的根本任务是简化输入模型的几何描述而同时尽可能好地保持其外观。尽管在原则上细节层次的产生是针对由任意类型的几何图元组成的复合模型，但是在实际中几乎都是使

34、用多边形模型。多边形表面的简化主要有几下几类方法3。(1)面元聚合：其基本思想是将相邻的几乎共面的所有面元合并成大的面元簇。消去其中的内点，留下边界，然后对此边界化简，最后在由新的边界所确定的域上进行三角剖分，从而获得对这一簇面元的简化。(2)顶点聚合：其方法的思想是将输入模型的顶点坐标量化成整数，这相当于在几何上建立了一个方格坐标，而将所有落在一个方格内的顶点合并为一个代表该方格的顶点。被完整地包含在一个方格中的所有三角形和边也都被合并为一个点，从而简略掉这些三角形和相应的边。(3)边收缩：此方法的思路是将一条边的两个端点沿着该边收拢成为一个顶点，因而消去这条边以及与它相关连的两个三角形。(

35、4)顶点对收缩：该方法是比边收缩更为一般化的简化操作，它允许收拢合并任意一对顶点，不管它们是否在同一条边上。2.3.3 碰撞检测技术无论是PC游戏，还是移动应用，碰撞检测始终是程序开发的难点，甚至可以用碰撞检测作为衡量游戏引擎是否完善的标准。碰撞检测问题是三维图形引擎中不可缺少的重要组成部分18。精确的碰撞检测对提高虚拟环境的真实性、增强虚拟环境的沉浸感有着至关重要的作用，而虚拟环境自身的复杂性和实时性对碰撞检测提出了更高的要求。碰撞检测系统的输入模型是构成几何对象的基本几何元素（通常是三角形）的集合，其任务是确定在某一时刻两个模型是否发生干涉，即它们的交集是否不为空，如发生碰撞，还需确定碰撞

36、部位（参与碰撞的基本几何元素）。最原始最简单的碰撞检测算法就是对两个输入模型中的所有基本几何元素进行两两相交测试，当模型的复杂度增高时，这种O（n2）次的相交测试显然是无法容忍的。因此减少基本几何元素两两相交测试的数目，提高算法速度，以保证虚拟环境的实时交互性是碰撞检测问题的核心18。两个几何元素间的碰撞检测算法大致可分为两类9：空间分解法和层次包围盒方法。空间分解发的基本思想是将整个虚拟空间划分成相等体积的小的单元格，只对占据了同一单元格或相邻单元格的几何对象进行相交测试。比较典型的例子有k-d 树、八叉树、BSP 树、四面体网和规则网格等，采用层次划分方法进行空间分解，如八叉树，BSP 树

37、等，可以进一步提高算法的速度。层次包围盒的核心思想是用体积略大而几何特性简单的包围盒来近似描述复杂的几何对象，从而只需对包围盒重叠的对象进行进一步的相交检测。此外通过构造树状层次结构可以越来越逼近对象的几何模型，直到几乎完全获得对象的几何特性。比较典型的包围盒类型有沿坐标轴的包围盒AABB（axis-aligned bounding boxes）、包围球（spheres）、方向包围盒OBB(oriented bounding box)等19。这两类算法都是使用了层次结构模型，其目标都是尽可能地减少需要进行相交测试的几何对象的数目。空间分解法通常适用于稀疏的环境中分布比较均匀的几何对象间的碰撞检

38、测，层次包围盒方法则应用得更为广泛，适用复杂环境中的碰撞检测。2.3.4 光照模型技术真实的表现光照，可以提高大规模场景的渲染质量。光照模型是计算机图形学中生成真实感图形的基础，当光照射到一个物体表面上时，会出现三种情况，首先，光可以通过物体表面向空间反射产生反射光；其次，对于透明体，光可以穿透该物体并从另一端射出，产生投射光；最后，部分光将被物体表面吸收而转换成热。在上述三部分光中，仅仅是透射光和反射光能够进入人眼产生视觉效果。为模拟这一现象，我们建立一些数学模型来代替复杂的物理模型。这些模型就称为明暗效应或者光照模型14。物体所表现的颜色与光源有密切的关系2。光照模型的作用就是计算物体可见

39、表面上每个点的颜色与光源的关系，因此它是决定图形真实感的一项重要内容。物体表面发出的光是极其复杂的，它既与环境中光源的数目、形状、位置、光谱组成以及光强分布有关，也与物体本身的反射特性和物体表面的朝向有关，甚至还与人眼对光线的生理和心理视觉因素有关。把这一切都通过计算机精确的计算出来是不现实的，我们只能用尽可能精确的数学模型光照模型来模拟光和物的相互作用，从而近似地计算物体可见表面每一点的亮度和颜色。在三维图形绘制中，需要根据光照模型计算每一个像素上可见的景物表面投向观察者的光亮度。在对三维模型的渲染中，光照模型主要有Lambert漫射、Phong光照模型和Blinn模型等。Phong光照模型

40、是比较常用的，Phong模型虽然只是一个经验模型，但是其真实度已达到可以接受的程度。它首次使光源和视点的位置可以任意选定。Phong模型表达式如下：I=IaKa+IiKd(NL)/(r+k)+IiKs(NH)n/(r+k)其中：IaKa为环境光参数；Ii为入射光强；Kd为物体表面的镜面反射系数；N为物体表面的法向；L为从物体表面指向光源的向量；r为光源到物体表面的距离；H为视线与L的平分向量。目前，图形芯片的发展速度非常快，图形硬件通常也叫做图形加速器，图形加速器其实就是一个独立于中央处理器CPU的特殊设计的硬件，其目的是专门用来加速实现图形算法。以前，图形中的不少运算都是在CPU中计算的，如

41、光照Lighting计算需要在CPU 中进行。这样做加重了CPU的负担。而且因为图形计算大部分是浮点计算，而CPU 是一个通用的处理器，其浮点运算能力并不高，所以使用CPU做图形计算效率很低。为了提高图形的绘制速度并解放CPU，可以采用图形硬件进行光照计算。这样做不仅可以提高图形处理的实时性而且可以提高图形绘制的真实性。3 常用的可见性裁减算法常用的可见性裁减有背面裁减、视截体裁减和遮挡裁减20。其中背面和视截体裁减是很常用的。这两种裁减不必考虑场景及场景对象的类型，可以对场景采用通用的裁减算法进行可见性处理，而且现在有专门的图形硬件用于背面裁减。而遮挡裁减就比较复杂，一些遮挡裁减算法占用内存

42、大，有些算法的处理时间较长，而其他算法则仅针对某些特定的物体类型。我们为某个特定的应用背景选择算法时，应该考虑场景复杂度、待显示物体的类型、显示设备及最终画面是静态还是动态等因素。3.1 遮挡裁减算法的分类根据处理场景时是直接对物体进行处理还是对投影进行处理，可将可见性判断算法大致分为两类：物体空间和图像空间。物体空间算法是定义、描述物体的世界坐标系中的实现的，将场景中的各物体和物体的各个组成部件相互进行比较，从而判断出那些是可见的。它以场景中的物体为处理单元，可描述如下：for（场景中的每一个物体）将其与场景中的其他物体比较，确定其表面的可见部分；显示该物体表面的可见部分；物体空间算法具有很

43、高的精度，通常与机器的精度相同，因而物体空间算法在对精度要求较高的工程应用方面特别有用。图像空间算法是在观看物体的屏幕坐标系下实现的，它以窗口内的每个像素为处理单元，在投影平面上逐点判断各像素所对应的可见面。可描述如下： for（窗口内的每一个像素）确定与此像素对应的距离视点最近的物体，以该物体表面的颜色来显示像素；图像空间算法的计算仅局限于屏幕的分辨率，比如1024768，这通常是很粗糙的。物体空间算法和图像空间算法一个显著区别在于算法所需要的计算量不同。理论上讲，物体空间算法的计算量少于图像空间算法的计算量。3.2 物体空间的遮挡裁减算法物体空间遮挡中的对象可以仅仅被个别遮挡版遮挡，它使得

44、该方法只对包含有大量凸多边形的场景作用。3.2.1 画家算法本算法过程与画家创作一幅油画的过程类似，因此而得名。画家画油画时，先画背景，然后画中间景物，最后才画近景。画家通过这种顺序构造画面，从而解决隐藏面或可见性问题4。用计算机绘制图形，也可以建立类似的深度顺序，按照图形中各单元到视点的距离确定一个深度优先级表，从而使图形中任意两个元素在深度上均不重叠。算法执行时，先从表中离视点最远的图形元素开始，依次将每个元素写入帧缓冲器。表中离视点较近的元素覆盖帧缓冲器中原有的内容，于是隐藏面自然消除，最后得到物体的图形，实际上是物体可见部分的图形。画家算法也可称为表优先算法，开始，观察方向经变换后与Z

45、轴负向重合，以变换后平面多边形顶点的最大Z值Zmax作为排序关键码建立初步的深度优先级表。算法处理每一个平面时，动态地计算和产生一个新的深度优先级表。表中第一个平面多边形是具有最大Z值得多边形，即到位于Z轴负向无穷远出视点的距离最远的平面多边形，记为P0，表中第二个平面多边形记为Q0，检查表上每个平面多边形与P的关系21。（1）若P的最近定点离视点的距离Zmax（P）比Q的最远定点离视点的距离Zmax(Q)还远，即Zmax（Q）Zmax(P),则P 不仅可能部分遮挡Q，而且还可能部分遮挡表上任何具有Zmax（Q）Zmin（P）的平面多边形Q，所以这样的平面多边形的集合记为Q，如果P不能遮挡Q

46、中的任何多边形的任何部分，即对下面所有检测问题的回答是肯定的，那么P写入帧缓冲器。 对 Q 中 每一Q，第一步，检测P和Q的包围盒是否在X方向分离。第二步，检测P和Q的包围盒是否在y方向分离。第三步，检测P是否全部位于Q所在的平面的背离视点的一侧。第四步，渐次Q是否全部位于P所在的平面的靠近视点的一侧。若经过上面（1）与（2）的检测，P不能写入帧缓冲器，则P可能遮挡Q。交换P和Q在表中的位置，对重新排列的表重复进行上述检测。若Q的位置需再次交换，则表明存在交叉覆盖情形，这时，可将P沿Q所在的平面分割成两个以上部分。从表中删去原多边形P而将P的这两个以上部分排序置入表内，对新表重复上述检测。采用这一步骤可防止算法陷入无限循环。3.2.2 二叉空间分割树（BSP ）算法早期的遮挡裁减算法是采用BSP(Binary Space-Partitioning)树算法。这种算法是一种辨别物体可见性的有效算法16。该算法类似于画家算法，将表面由后往前地在屏幕上绘出，该算法特别适用于场景中物体位置固定不变、仅视点移动的情况。处理可见面确定问题的BSP树算法有两部分：首先是从场景多边形集合出发构造出树，然后假设一个视点，对树进行遍历以便得到所需要的从后向前的顺序。利用BSP 树来判断表面的可见性，其主要操作是在每次分割空间时，判别