当前位置： >>
虚拟现实 中的 碰撞检测技术 word文档格式
碰撞检测技术的研究摘要实时精确的碰撞检测对于提高虚拟环境的真实性、增强虚拟环境的沉 浸感有着至关重要的作用。 该文对碰撞检测相关技术进行了深入的研究,主要包括以下几个方面的 内容： 首先介绍了虚拟现实技术的发展及现状、碰撞检测的研究现状；然后简 单介绍了碰撞检测一些基础理论知识，着重介绍常用的碰撞检测算法。紧 接着，简单介绍了 OpenGL 编程的基础知识和面向对象编程的特点。在碰 撞检测算法的应用中，运用 OBB 包围盒层次树的碰撞检测算法，提出了一 种一般多面体间碰撞检测的可行性方案，并用软件对该方案进行实现，同 时指出该方案的优缺点。最后,对全文进行了总结,并指出今后的研究方向。关键词： 关键词：虚拟现实碰撞检测包围盒层次树 OBBSTUDY AND IMPLEMENTATION ON COLLISION DETECTION TECNOLOGY OF VIRTUAL REALITYAbstractReal-time and accurate collision detection is very important to improve reality and enhance illusion of immersion for virtual environment. This paper studies the technique of collision detection deeply.It contains the following parts: Firstly,this paper reviews recent research on collision detection field.Then it introduces some basic knowledge and emphasizes on introduce of collision detection algorithm.Next,it introduces OpenGL and Oriented-object language program character.In collision detection implementation chapter,a scheme of collision detection between general polyhedron is presented by using bounding hierarchy volume algorithm.The method is implemented by vc6.0.And it analyses advantage and disadvantage of the method.Finally,the conclusion is drawn and the work of future research is presented.KEY WORDS: virtual reality collision detection bounding hierarchy volume OBB目第一章录................................................................ ......................................... 绪 论 ......................................................................... 11.1 虚拟现实技术发展及现状 ............................................................ 1 1.1.1 虚拟现实的特点 ............................................................... 1 1.1.2 国内外虚拟现实技术的研究状况.................................................. 2 1.2 碰撞检测的研究现状 ................................................................ 3 1.2.1 意义及特点 .................................................................... 3 1.2.2 碰撞检测的研究现状 ............................................................ 4 1.3 论文的工作和组织结构 .............................................................. 6 ................................................................ ................................... 第二章 碰撞检测理论 ................................................................... 8[3]2.1 碰撞的定义...................................................................... 8[2]2.2 碰撞检测的模型类别 ................................................................ 8 2.3 碰撞检测的场景特征 ............................................................... 9 2.4 碰撞检测技术的基本原理 ............................................................ 9 ................................................................ .................................. 第三章 碰撞检测算法 .................................................................. 11 3.1 空间剖分法 ....................................................................... 11 3.2 包围盒层次树法 ................................................................... 12 3.2.1 包围盒形状的设计准则 ......................................................... 13 3.2.2 包围盒类型 ................................................................... 13 3.3 基于特征的距离计算增量算法 ....................................................... 16 3.3.1 基本概念 ..................................................................... 16 3.3.2 Lin-Canny 算法概述 ........................................................... 19 3.3.3 适应性准则 ................................................................... 20 ................................................................ .................................. 第四章 编程基础理论 .................................................................. 25 4.1 OPENGL 编程基础 ................................................................... 25 4.1.1 OpenGL 基本特点 .............................................................. 25 4.1.2 OpenGL 实现 .................................................................. 27 4.1.3 OpenGL 图形绘制 .............................................................. 28 4.1.4 OpenGL 光照处理 .............................................................. 29 4.1.5 OpenGL 纹理映射 .............................................................. 30 4.1.6 深度测试 ..................................................................... 32 4.2 面向对象的编程 ................................................................... 32 4.3 OPENGL 编程环境的设置 ............................................................. 33 ............................................................ 第五章 碰撞检测算法的应用 ............................................................ 35 5. 1 物体建模 ........................................................................ 35 5. 2 场景绘制 ........................................................................ 38 5.3 碰撞检测算法的应用 ............................................................... 41 5.3. 1 基础理论 ................................................................... 41 5.3.2 碰撞检测的实现过程 .......................................................... 43 5.3.4 用户交互 ..................................................................... 505.4 本程序的优缺点 ................................................................... 52 第六章 总结与展望 .................................................................... 54 .................................................................... ................................ 主要参考文献 ...................................................................... 55 ..................................................................................................................................................................................第一章绪 论1.1 虚拟现实技术发展及现状1.1.1 虚拟现实的特点自 20 世纪 90 年代初以来，虚拟现实技术一直是信息领域研究、开发和应用的热点 方向之一。虚拟现实（Virtual Reality）,也称为“人工现实”或“临境”技术，是多媒体发展 的更高境界，虚拟现实以更加高级的集成化和交互性，给用户以更加逼真的体验，可广 泛应用在模拟训练、科学可视化等领域，将是今后十分活跃的技术课题。 虚拟现实就是用计算机技术生成一个逼真的，集听、视、触及嗅觉为一体的感觉世 界，用户以人的自然技能与虚拟现实交互考察，包含三层意思：[1] 1) 虚拟实体是用计算机来生成的一个逼真的实体，“逼真”就是要达到三维视觉，甚 至其他三维感觉。 2) 用户可以通过人的自然技能（如头和眼的转动、手势等其他身体动作）与环境交互。 3) 虚拟现实往往要借助于一些三维传感设备来完成交互动作，如头盔立体显示、数据 手套、数据服装、三维鼠标等。 虚拟现实是一种高度集成技术，是计算机、机器人、人工智能以及心理学等发展的 联合结晶，因此取决于三维实时图像显示、三维定位跟踪传感技术、人工智能技术、高 速并行计算机技术及人的行为学等领域的研究进展。 因此虚拟现实技术的研究和实现难 度很高， 美国著名图形学专家 J.Foley 讲过： “虚拟现实是人机接口设计中最后一个堡垒， 也是最有意义的领域。” 虚拟现实的基本特征可以概括为三个“I”,即 Immersion-Interaction-Imagination(沉浸交互-构思)。它强调了人在信息处理过程中的主导作用，使信息处理从以计算机为中心 转到以人为中心。 虚拟现实这一概念起源于 Ivan Sutherland 在 1965 年发表的一篇题为“The Ultimate Display”的报告。在该报告中提出利用计算机系统构造一个具有视觉、听觉和感觉真实 感的世界。1968 年，Ivan Sutherland 开发了第一个可以跟踪头部运动的头盔显示器-1（head-Mounted Display,简称 HMD） HMD 根据用户在虚拟世界的位置来显示相应的内 。 容，当用户移动或转动头部时，通过 HMD 所看到的虚拟世界也随之发生改变。后来， 许多人在这方面进行了大量研究，并取得了一些进展。1.1.2 国内外虚拟现实技术的研究状况在虚拟现实领域，国内外专家和学者已经做出了许多研究工作。 国外研究状况： 1）美国的研究状况 美国是虚拟现实技术的发源地。其水平基本上就代表国际发展的水平。目前美国在 该领域的基础研究主要集中在感知、用户界面、后台软件和硬件四个方面。 2）日本的研究状况 在当前实用虚拟现实技术的研究与开发中,日本是居于领先位置的国家之一， 主要致 力于建立大规模虚拟现实知识库的研究。 另外在虚拟现实的游戏方面的研究也做了很多 工作。 NEC 公司计算机和通信分部中的系统研究实验室开发了一种虚拟现实系统， 它能让 操作者都使用“代用手”去处理三维 CAD 中的形体模型，该系统通过 VPL 公司的数据手 套把对模型的处理与操作者手的运动联系起来。 东京大学的广濑研究室重点研究虚拟现实的可视化问题。 为了克服当前显示和交互 作用技术的局限性，他们正在开发一种虚拟全息系统。 富士通实验室有限公司正在研究的一个项目是虚拟生物与虚拟现实环境的相互作 用。他们还在研究虚拟现实中的手势识别，已经开发了一套神经网络姿势识别系统，该 系统可以识别姿势，也可以识别表示词的信号语言。 3）英国的研究与开发 在 VR 开发的某些方面，特别是在分布并行处理、辅助设备 （包括触觉反馈）设 计和应用研究方面，英国在欧洲是领先的。 国内研究状况： 和一些发达国家相比，我国虚拟现实技术还有一定的差距，但是一些国内大学都也 做出很多研究。 1) 北京航空航天大学首先进行了一些基础知识方面的研究，并着重研究了虚拟环-2境中物体物理特性的表示与处理；在虚拟现实中的视觉接口方面开发出了部分硬件，并 提出了有关算法及实现方法等。 2) 浙江大学 CAD&CG 国家重点实验室开发出了一套桌面型虚拟建筑环境实时漫游系 统。另外，他们还研制出了在虚拟环境中一种新的快速漫游算法和一种递进网格的快速 生成算法。 3) 哈尔滨工业大学计算机系已成功地虚拟出了人的高级行为中特定人脸图像的合成， 表情的合成和唇动的合成等技术问题，并正在研究人说话时头势和手势动作等。 4) 清华大学对虚拟现实的临场感的方面进行了研究，他们还针对室内环境水平特征丰 富的特点，提出借助图像变换，使立体视觉图像中对应水平特征呈现形状一致性，以利 于实现特征匹配，并获取物体三维结构的新颖算法。 5) 西安交通大学对虚拟现实中的关键技术，立体显示技术进行了研究。他们在借鉴人 类视觉特性的基础上提出了一种基于 JPEG 标准压缩编码新方案，并获得了较高的压缩 比、信噪比以及解压速度。1.2 碰撞检测的研究现状1.2.1 意义及特点目前，虚拟现实真实性的研究大量集中在视觉、听觉和触觉等几个方面。例如采用 几何建模方法来表示虚拟环境中的实体，然后使用纹理映射、消隐和光照计算等方法生 成逼真的环境。虚拟现实只有逼真的外观是不够的，还需要有逼真的状态变化，例如， 实体位置、方向和形状等状态变化规律与真实世界中相同或相似，即虚拟现实中的实体 需要具有运动逼真性。碰撞检测和响应是虚拟现实中的一项重要技术，是其基本特性之 一“沉浸感”的重要保证。 碰撞检测的两个重要约束条件是实时性和精确性[2]。就实时性而言，针对虚拟环境 中的视觉显示要求，碰撞检测的速度至少要达到 24Hz;而针对虚拟环境中的触觉显示要 求， 碰撞检测的速度至少要达到 300Hz 才能维持触觉交互系统的稳定性， 要达到 1000Hz 才能获得平滑的效果。精确性取决于具体的应用，比如对于环境漫游系统，一般只要近 似模拟碰撞检测情况，此时，若两个物体实际没有发生碰撞但其距离比较近（如在某一 阈值内） ，就可以将其当作是发生了碰撞，并粗略计算碰撞位置。而对于虚拟手术仿真、-3虚拟装配等应用，就要精确地检测碰撞的发生和计算碰撞发生的位置。1.2.2 碰撞检测的研究现状[3]碰撞检测最早被广泛用于生产中的自动操作和处理，即虚拟组装和拆卸。近年来， 碰撞检测和响应的研究在虚拟现实中扮演了越来越重要的角色， 特别是用碰撞检测和响 应来模拟现实生活中的接触、抓、移动和打击等情况。下面我们将对于碰撞检测的研究 状况进行简单介绍。 对于碰撞检测和响应的研究主要集中在对实体间精确碰撞检测算法和碰撞响应的处 理。目前已经形成了一些比较成熟的算法。虚拟现实中检测两个实体之间是否发生了碰 撞，实际上就是检测这两个实体所占的几何空间是否相交，常用的方法有离散方法和连 续方法。离散方法（Discrete Methods）也称为静态方法（Static Methods）,是指当检测 时间（Ts,Te）内是否发生碰撞，则仅在 Ts&Ts+t1&Ts+t2&……&Ts+tk&Te 一系列离散的时 间点上进行碰撞检测。Moore,M.和 Wilhelms,J.提出了两种基于实体模型点、边和面几何 关系的碰撞检测方法。一种方法直接计算两个实体顶点、边和面之间的关系，另一种方 法是使用点积来判断一个点是否进入另一个实体内部。M.K.Ponamgi,D.Manocha,Ming C.Lin 等人提出了一种基于 Voronoi 区域的碰撞检测方法。 这种方法利用虚拟环境中实体 运动的一致性， 即实体运动状态的变化在 dt 时间内是有限的， 大大减少了检测两个凸多 面体是否碰撞的时间，取得了实时碰撞检测的突破性进展。连续方法（Continuum Methods）也称为动态方法（Dynamic Methods）,是指检测当前实体从当前状态运动到下 一状态所滑过的四维空间与其它实体同时滑过的四维空间是否发生重叠。T.Duff 的区间 分析（Interval Analysis）方法就是一种连续碰撞检测方法。由于连续方法比较复杂，计 算量比较大，所以绝大多数虚拟现实系统采用离散的碰撞检测方法。 当检测到虚拟环境中发生碰撞时， 需要根据碰撞情况修改发生碰撞实体的运动表示， 即修改实体的运动方程，确定实体的损坏和形变，实现碰撞对实体的影响，这就是碰撞 响应。在虚拟现实研究初期，对碰撞响应的要求比较简单。例如，在虚拟漫游系统碰撞 检测只是当检测到碰撞时禁止该方向的运动。现在对碰撞响应的研究越来越多。目前对 碰撞响应的研究主要有两个方向，一类是研究针对虚拟实体物理特性的碰撞响应，即碰 撞对实体的运动行为和本身特性的影响。例如美国联邦铁路部（FRA）对防撞性评估系 统的研究，主要分为三步：第一步是对单节机动有轨车辆碰撞物理特性的定义；第二步-4是机动有轨车辆碰撞动力学模型的建立；第三步是计算碰撞结果，评估两铁路系统的防 撞性。另一类着重于研究碰撞响应的图形效果，即碰撞后实体损伤的图形表示和一些烟 火等特殊效果。在 STOW97 的联合演练中，已经完成了炮弹爆炸后所产生的弹坑，道 路、桥梁及建筑物不同程度的损坏，车辙和一些明显痕迹的图形效果。 关于平面碰撞检测问题的研究主要有 3 个方面，包括可碰撞、可移动区域和最初碰 撞部位的检测。近 10 几年来，许多专家学者对平面碰撞问题进行了深入的研究，并取 得一些很好的结果，提出了许多算法。Tetsuya，Toshiaki 和 Mario 等人提出了一种称为 空间占有的方法，即物体在目标空间移动，当试图占有相同的球体时来检测它们的碰撞[21]。这种算法基于这样一条原理：没有任何物体和其他物体占有同一个球体，也不需要 特殊的计算来检测碰撞。 并且， 在它们的方法中， 每个物体连同它们所占有的球体在 3D 空间中都被赋予一个名字，因而其他物体知道它们和哪个物体发生碰撞。Chin 及 Wang 研究了两个多边形的相交和最小距离问题。 利用可视边链和凸的顶点相对于其内部点的 单调性，提出了判别凸 n-边形和一个简单非凸 m-边形的相交问题的最优算法[22]，并且 研究了当两个多边形相交时一个多边形是否被另一个多边形完全包含的问题， 其时间复 杂度都为 O(m+n)。David Baraff 研究了平面内多个凸多边形的碰撞问题，并采用将凹多 边形分解为凸多边形的方法来求解碰撞问题，其实质还是凸多边形的碰撞问题[23]。 关于三维空间碰撞问题的研究一般有可碰撞和碰撞规避两方面。所谓可碰撞问题就 是物体 A 和 B 在空间沿给定轨迹移动时是否发生碰撞。可移动区域就是物体 A 沿给定 的规律运动，而不与物体 B 发生碰撞的所有可能运动的区域。最初碰撞点的检测就是当 物体 A 以给定的运动规律运动，并将与物体 B 发生碰撞时，检测它们在最初发生碰撞 时的接触部位。碰撞规避就是两个或多个物体的无碰撞运动。从对平面碰撞检测问题的 研究中，可得到有力和巧妙的技巧。而对于空间（≥3D）的情形，则潜藏着难以克服的 困难，这也许是平面碰撞问题已得到很深入的研究，并提出了很多种最优算法，而对于 空间问题尚少有高效算法的一个原因吧。 很多学科都对研究和模拟三维物体的干涉问题感兴趣。物体的干涉是两个或多个物 体的体积占有相同的空间。通常，物体的干涉有两大类，即静态干涉和动态碰撞检测。 动态碰撞检测就是沿特定轨迹移动的物体的干涉检测。 动态碰撞检测算法又可分为两大 类：①判断移动的物体之间是否发生碰撞亦即可碰撞问题；②检测到碰撞的存在并采取 措施进行规避， 也就是碰撞规避问题。 静态干涉检测算法根据所用实体表示模型的不同， 在这方面， Ganter 现有实体干涉检验算法大致可分成两类。 一类算法主要基于 B-rep 模型。-5提出空间分割技术[24]。另一类算法是以层次模型为基础的，如八叉树干涉检验算法和层 次 Sphere 检验算法[25[26][27]。动态碰撞检测可应用两类技术，第 1 类技术是一种基于在给定轨迹上反复利用静态干涉检测被称为“单步检测”的方法，第 2 类技术是基于产生称 之为“扫描实体”的物体。对于这两类技术的研究许多研究者都提出自己的算法 aruyama 提出了一种递归空间分割算法和一种一般的面对面相交算法。然而，Boyse 提出了第 1 种可用的单步检测系统[28] Ganter 及 Isarankura 发展了单步检测方法， 提出了一种空间分 割技术的方法。Hahn 采用层次包围盒技术来加速多面体场景的碰撞检测。Moore 与 Wilhelems 根据 Cyrus-Beck 裁剪算法提出了一种凸多面体碰撞检测算法，即通过检测多 面体顶点是否相互包含来判定它们是否发生碰撞。对于具有 n 个凸多面体、每个多面体 有 m 个顶点的问题，此算法的时间复杂度为 O(n2m2)；对于凹多面体则分解为多个凸多 面体来处理。Ganter 和 Isara nkura 提出了一种空间分割的方法，即将给定物体所占有的 空间划分成一系列子空间，将碰撞测试限定在两物体的重叠子空间中进行，并且在重叠 子空间里的元素都按最大、最小来排序，从而进一步减少了测试时间。最坏情况下的处 理时间为 O(*N2/2)，*N 是重叠区域的单元面的总个数。1.3 论文的工作和组织结构碰撞检测是虚拟现实中的关键技术，能够增强虚拟环境的真实感和用户的沉浸感， 并在计算机动画、物理仿真、计算几何、机器人学、CAD/CAM 等领域有广泛的应用。 因此对碰撞检测技术的研究具有十分重要的意义。 本论文的整体框架如下： 第一章， 简要介绍了虚拟现实技术的发展及现状， 然后主要介绍了研究碰撞检测技 术的意义，最后介绍了碰撞检测技术在国内外研究发展与现状。 第二章， 介绍碰撞检测的一些基本理论。 为了进一步深入研究碰撞检测技术， 首先 第三章， 有必要了解一些相关基础理论。 在本章中主要介绍了碰撞的定义、 碰撞检 测的模型类别、碰撞检测的场景特征及其碰撞检测技术的基本原理。 第四章， 着重介绍了常用的一些碰撞检测算法。 分别介绍了空间剖分法、 包围盒层 次树法、基于特征的距离计算增量算法等算法原理和优缺点。 第五章， 介绍了 OpenGL 编程基础和面向对象编程。 主要针对即将用到一些知识进 行简介。主要介绍了 OpenGL 基本特点、OpenGL 实现、OpenGL 图形绘-6制、OpenGL 光照模型、OpenGL 纹理贴图等知识和介绍了面向对象编程 的特点、OpenGL 编程环境设置。 第六章， 介绍碰撞检测算法的应用。采用 OBB 包围盒层次树算法实现一个碰撞检 测场景。 本章中简要介绍了场景实现步骤， 并用流程图清晰展示了碰撞检 测的实现过程。然后分析本实例程序实现的优缺点。 第七章， 总结了本论文的主要工作内容，并提出了下一步工作的目标。-7第二章 碰撞检测理论2.1 碰撞的定义[3]在现实世界中，碰撞是一种常见的动力学现象。其特点是整个过程时间短暂，一般 在 10-2 秒以内，并在碰撞实体之间产生相当大的冲击力，使实体发生形变，并在一定程 度上改变实体的运动状态。 在虚拟现实系统中一般通过检测两个实体所占的几何空间是 否相交来判断是否发生碰撞。在现实世界中，每个实体都占有一定几何空间，而且不可 能出现两个实体相互穿透的现象。 当虚拟现实系统中两个实体所占有的几何空间试图相 互穿透时，系统就认为这两个实体发生了碰撞。 如果有四维空间来描述运动实体， 前三维是通常意义上的三维空间， 第四维是时间， 那末一个实体就可以用四维空间中的点集来描述，即：{( x, t ) | x ∈ L(t )( S )}其中：S 是构成实体的三维空间点集，L(t)是确定实体 t 时刻空间位置的函数。通过 L(t)(S)可以给出三维空间点集中每个点 t 时刻的位置。假设用四维空间中的点集 S1*和 S2 *来描述两个实体 S1 和 S2 以及它们的运动，则碰撞检测可以描述为在某时刻某两个 实体所占空间位置的关系，即： 对于 ( x, t ) ,有 ( x, t ) ∈ S1*和 ( x, t ) ∈ S2*，当且仅当 S1* ∩ S2* ≠ ? 时，发生碰 撞。2.2 碰撞检测的模型类别虚拟环境中的物体所用的模型大体分为面模型和体模型两大类。面模型用物体的边 界来表示物体，而不包括物体内部信息。体模型采用体元来表示物体，可描述物体的内 部信息。 体模型所耗存储量大， 计算量也大。 而面模型的研究和应用比体模型的成熟多。 由于凸多面体有很好的性质，因而可以获得较高效率的基于凸多面体的碰撞检测算法。 对于一般的体，由于处理相对比较复杂，往往采用将一般的体分解成几个凸多面体再进 行逐个碰撞检测。 所以碰撞检测的研究工作大多是基于面模型的， 少数是基于体模型的。 面模型又可进一步分为很多种，如多面体模型、CSG、隐式曲面、参数化曲面等。-8其中，最常用的一种是多面体模型，特别是三角形模型。多面体模型是一种简洁，通用 的表示方法，几乎应用于表示任何形状的物体，而且便于操作，易于实现硬件加速。 多面体模型又有多种形式，碰撞检测算法也可能对模型的形式有要求，如很多算法 要求输入模型是实体，即可表示成闭合曲面，其中，不少算法利用物体的凸性来加速， 因而进一步要求输入模型是凸多面体，对非凸多面体则做特殊处理；另一些算法对输入 模型则不做特殊处理要求，输入模型被表示成一组无拓扑约束的三角片，这类算法通用 性比较好。本论文输入模型便是一组无拓扑约束的三角片。2.3 碰撞检测的场景特征[2]场景可按物体的运动状态分为静态部分和动态部分，静态部分间的碰撞检测可离线 计算，而动态部分如果事先能知道物体的运动轨迹，其碰撞检测可离线计算。但是虚拟 环境是一个实时交互系统，物体的运动轨迹一般是未知的，故碰撞检测要实时地进行。 在虚拟环境中有些物体是静态的，有些物体是动态的，动态物体越多，碰撞发生的概率 越大，其碰撞检测的复杂程度越高。 场景中的运动物体还可分为刚体和柔体，刚体物体在运动中不改变物体形状，其运 动形式局限于平移和旋转； 柔体物体在运动中会改变物体的形状， 其运动形式除了平移、 旋转还有变形，如心脏的跳动。故柔体物体的碰撞检测比刚体要复杂得多。在本论文中 我们只针对刚体物体进行碰撞检测。2.4 碰撞检测技术的基本原理如果两个安全封闭的多面体发生相互碰撞时，其中一个多面体至少会有一个面与另 一个多面体的至少一个面发生相交。若能在碰撞发生时，立刻检测到相交，然后将两个 物体的位置稍做调整，可消除碰撞现象。如下是碰撞检测基本算法描述： 设在一虚拟环境中要仿真 n 个物体：A1,A2……,An,其对物体的仿真过程是逐帧计算的， 从 T0 到 T1 按时间步长 dT 进行计算。 //在虚拟环境中调用碰撞检测过程[2] Simulation() { …-9for (T=T0 to T1,步长为 dT) do { 获得用户的输入； 更新 A1,A2…,An 各物体的行为； if (collisionDetect(T,{A1,A2…,An}找到了碰撞) then 计算碰撞反应； 绘制 n 个物体 A1,A2…,An } } //碰撞检测过程，Tprev 为全局变量，初值为（T0-dT）,dt 为碰撞检测的步长， collisionDetect（Tcurr, {A1,A2…,An}） { for (t=Tprev to Tcurr,步长为 dt) do { for ({A1,A2…,An}中每个物体 Ai) do 移动 Ai 到其在时间 t 的位置; for({A1,A2…,An}中每个物体 Ai) do for({Ai+1,…An}中每个物体 Oj) do if (Oi 与 Oj 相交) then 报告在时间 t 发生了碰撞； } Tprev = Tcurr； } 以上是碰撞检测思想的一种最基本的方法，在实际应用过程中可以根据需要对该方 法进一步改进，以得到更高效的碰撞检测算法。-10第三章 碰撞检测算法由于碰撞检测的重要应用，人们对它进行了广泛而深入的研究，算法种类也很多。 在很多时候，对碰撞检测实时性要求很强，需要碰撞检测的几何模型集合中模型复杂且 很多，在这种情况下，一般是针对虚拟场景的特点、几何模型的几何与运动等特点设计 可高效应用于该虚拟场景的算法，如有些算法适用于凸多面体几何模型、有些适用于可 运动模型少的虚拟场景。然而还没有能够满足所有情况的通用碰撞检测算法。3.1 空间剖分法空间剖分法通常将空间剖分成均匀的单元，每个物体对应一个或多个单元中，只有 当物体处于同一单元空间中才可能相交，这时应该对该单元空间进行精确的碰撞检测。 采用空间剖分思想[19]的算法一般用树的方式逐步分割空间，可以进一步加速碰撞检测。 常用的空间剖分方法是 BSP[4]、八叉树[5]（如图 3-1） 、均匀网格[6]、3-d 树[7]。八叉树用 树的结构表示空间的分解情况，根是整个空间，将每个父结点空间用三个分别与坐标轴 垂直的分割面分成大小相等的八份，每一份作为它的一个子结点，分割不断进行直到与 子结点相交的三角形数目小于一个阈值或者与子结点相交的三角形属于同一模型， 该子 结点成为一个叶结点；如果来自两个模型的三角形与同一个叶结点相交，那末需要对这 两个模型进行碰撞检测。BSP 树与八叉树相似，但是二叉树。3-d 树是一种特殊的 BSPs 树，用来分割空间的分割面都是与某一个坐标轴垂直的。一般，空间剖分算法在每次碰 撞检测时都需要确定每个模型占有的空间单元，如果场景中不可动的模型很多，可以预 先划分好空间单元并计算出每个模型占有的空间单元，当有模型运动时，只要重新计算 运动模型占有的空间单元就可以。 所以空间剖分算法比较适合用于稀疏的环境中分布比 较均匀的几何对象间的碰撞检测，如图 3-2。-11图 3-1八叉树图 3-2空间剖分法在场景中的应用3.2 包围盒层次树法另一种常用方法是包围盒， 包围盒方法被广泛应用于对光线跟踪和求交运算的加速。 其基本思路是用体积略大而几何特性简单的包围盒将复杂的几何形体围住， 当对两个物 体做碰撞检测时，首先检测包围盒是否相交，若不相交，则两个物体不相交。反之，需 要进一步对两个物体进行精确检测，此方法可以快速排除不相交的物体，加速了算法。 与一个物体相对应的层次树的结点是空间上包围该物体一部分几何结构的几何近似体： 层次树的根结点是包围了整个物体， 每个父结点包围的几何结构是它所有子结点包围的 几何结构之和；结点从上到下逐渐逼近它包围的几何结构。判断两个模型是否相交时，-12首先判断两个层次树的根结点是否相交；如果两个父结点相交，那末将它们的子结点分 别进行相交判断；如果最后有相交的叶结点对，判断每对叶结点包围的几何结构是否相 交，如果有相交的几何结构对，则模型相交，反之不相交。[8] 比较典型的包围盒类型有包围球 （spheres） 、 沿坐标轴的包围盒 AABB （axis alignedbounding box）[9]、方向包围盒 OBB(oriented bounding box)等。层次包围盒法则应用于 复杂环境中的碰撞检测。3.2.1 包围盒形状的设计准则选择哪种形状的包围盒通常取决于应用领域及其蕴含的不同约束条件。例如在光线 跟踪算法中，包围盒应能紧密包围物体，同时又便于高效地对一条光线和包围盒做求交 测试。对于碰撞检测算法，可借助一个耗费函数来分析T = NvxCv + NpxCp + NuxCu [2]其中：T 是碰撞检测的总耗费；Nv 是参与重叠测试的包围盒的对数， Cv 是一对包围盒做重叠测试的耗费；Np 是参与求交测试的几何元的对数， Cp 是一对几何元做求交测试的耗费；Nu是物体运动后包围盒层次需要修改的结点个数， Cu 是修改一个结点的耗费； 根据 T 这一耗费函数，可以推测理想的包围盒应满足如下要求： 在各层次上紧凑地逼近输入模型及其子部分，以减少 Nv 、 Np ； 支持快速为一对包围盒做重叠测试，以减少 Cv ； 当物体旋转或平移时，支持对其包围盒层次中结点的快速修改，以减少 Cu3.2.2 包围盒类型从上节知道选择不同类型的包围盒直接影响到碰撞检测算法的效率。本节将详细介 绍一些常用的包围盒类型[20]，并分析各自的优缺点。 1）沿坐标轴的包围盒 AABB（axis aligned bounding boxes） AABB 在碰撞检测的研究历史中使用最悠久，一个 AABB 被定义为包含该对象且边 平行于坐标轴的最小正六面体。 如图 3-3 所示， 基于 AABB 碰撞检测系统的有 I-collide[10]、-13SOLID[11]等。 AABB 间的相交测试比较简单，两个 AABB 相交当且仅当在三个坐标轴投影区间均重 叠。但是 AABB 紧密性比较差，尤其是对于沿斜对角线放置的瘦长物体，用 AABB 将 留下很大边角空隙，从而导致大量冗余的包围盒相交测试。这样的话，减少 Cv 、 Cu ， 同时可能增加 Np 。图 3-3AABB 包围盒2）包围球（spheres） 包围球类似 AABB,是一种简单性好紧凑性差的一类包围盒，包围球被定义为 包含该对象的最小球体。如图 3-4 所示图 3-4包围球包围盒包围球间的相交测试也相对比较简单。对于两个包围球(ｃ1,ｒ1)和(ｃ2,ｒ2),如果球 心距离小于半径之和,即|ｃ1-ｃ2| ＜（ｒ1+ｒ2）,则两包围球相交,可进一步简化为判断 (ｃ1-ｃ2)?(ｃ1-ｃ2) ＜(ｒ1+ｒ2)2。故包围球间的相交测试需要 4 次加减运算、4 次乘法 运算和 1 次比较运算。 包围球的紧密性在所有包围盒类型中是比较差的,它除了对在三个坐标轴上分布的 比较均匀的几何体外,几乎都会留下很大的空隙,通常需要花费大量的预处理时间以构造 一个好的层次结构逼近对象,这在 Hubbard 的工作中得到验证。相对于 AABB 而言,在大 多数情况下包围球无论是紧密性还是简单性都有所不如,因此,它是使用得比较少的一种 包围盒。当对象发生旋转运动时,包围球不需要做任何更新,这是包围球比较优秀的一个-14特性,当几何对象进行频繁的旋转运动时,采用包围球可能得到较好的结果。当对象发生 变形时,很难从子结点的包围球合成父结点的包围球,只能重新计算。 3）方向包围盒 OBB(oriented bounding box) OBB 是 Gottschalk 在 1996 年实现的 RAPID 系统中首先使用的[13],当时该系统声称是 最快的碰撞检测系统,曾一度作为评价碰撞检测算法的标准。一个给定对象的 OBB 被定 义为包含该对象且相对于坐标轴方向任意的最小的正六面体。OBB 最大特点是它的方 向的任意性,这使得它可以根据被包围对象的形状特点尽可能紧密地包围对象(如图 3-5), 但同时也使得它的相交测试变得复杂。图 3-5OBB 方向包围盒OBB 的计算相对复杂一些,其关键是寻找最佳方向,并确定在该方向上包围对象的 包围盒的最小尺寸。OBB 间的相交测试基于分离轴理论。若两个 OBB 在一条轴线上(不 一定是坐标轴)上的投影不重叠,则这条轴称为分离轴。若一对 OBB 间存在一条分离轴, 则可以判定这两个 OBB 不相交。对任何两个不相交的凸三维多面体,其分离轴要么与任 一多面体的某一个面垂直,要么同时垂直于每个多面体的某一条边。因此,对一对 OBB, 只需测试 15 条可能是分离轴的轴(每个 OBB 的 3 个面方向再加上每个 OBB 的 3 个边方 面的两两组合),只要找到一条这样的分离轴,就可以判定这两个 OBB 是不相交的,如果这 15 条轴都不能将这两个 OBB 分离,则它们是相交的。两个 OBB 的相交测试最多需要 15 次比较运算、60 次加减运算、81 次乘法运算和 24 次绝对值运算。尽管 OBB 间相交测 试的代价比较大,但它的紧密性是最好的,可以成倍地减少参与相交测试的包围盒的数目 和基本几何元素的数目,在大多数情况下其总体性能要优于 AABB 和包围球。此外,当几 何对象发生旋转运动后,只要对 OBB 的基底进行同样的旋转即可。 因此,对于刚体间的碰 撞检测, OBB 不失为一种较好的选择,但迄今为止,还没有一种有效的方法解决对象变形 后 OBB 树的更新问题,而重新计算每个结点的 OBB 的代价又太大,故而 OBB 不适用于软-15体对象环境中的碰撞检测。 OBB 算法采用任意方向的包围盒作为物体及子部分的包围盒，组成 OBB 树。该算 法的主要特点是采用了一个“分离轴”方法来检测两个包围盒是否相交，此方法大大加速 了包围盒测试过程，从而从整体上加速了算法。此外，该算法力图使包围盒与物体很紧 凑，以提高包围盒的检测命中效率。 为一个物体创建 OBB 树的过程可分为两部分： 1)为表示该物体的多边形集合计算一个 OBB 包围盒 首先将所有多于三条边的多边形分割成三角片，即把物体表面三角化。然后采用一 阶和二阶方法对构成物体的所有三角形的所有三角片的顶点进行统计，分别求得均值 U、协方差矩阵 C。设第 i 个三角片的顶点是 pi,qi,ri,则有?=1 n i ∑ p + qi + r i 3n i = 0 1 n ?i ?i ?i ?i ?i ?i ∑ p j pk + q j qk + rj rk 3n i = 0?C jk =1 ≤ j, k ≤ 3? ?其中 n 是三角片个数， pi = p i - ? ， q i = q i - ? ， r i = r i - ? C 是一个对称矩阵，而对称矩阵的特征根是正交的。将 C 的 3 个特征根归一化，作为一 个基。沿基的每个轴向，找到轴向的极点顶点，根据各轴向上的这些极点顶点来规定 OBB 的大小，将基的轴向作为 OBB 的方向，使 OBB 包围各轴向上的极点顶点。因此 3 个特征向量中有两个分别表示最大和最小的方差方向， 这样构造出来包围盒与物体比较 紧凑。 2)将 OBB 组成树状结构 创建包围盒层次结构的方法通常有两种：自底向上和自顶向下。自底向上方法首先 为组成物体的每个多边形分别计算包围盒，然后将它们逐渐合并成更大的包围盒，直到 构成一棵树；自顶向下方法首先为整个物体计算包围盒，然后递归地对物体进行剖分， 直到所有叶结点不可再分。3.3 基于特征的距离计算增量算法 基于特征的距离计算增量算法 距离计算增量算3.3.1 基本概念在实体和几何建模中，主要有两种表达方案：边界表达模型（B-rep）和构造实体几-16何模型（CSG） 。 边界表达：通过描述实体的表面来表达实体，这样我们关于物体内、外部的全部信 息。这样表达提供了两类信息： （1）几何信息―用来描述面、边、顶点的参数； （2）拓 扑信息―顶点、边、面的邻近和连接关系。 构造实体几何模型：它用一个体素的布尔运算表达式来表达实体。CSG 操作运算包 括旋转、平移、正规化并、正规化差和正规化交。CSG 的标准体素是球、圆柱、圆锥、 平行六面体、三角棱柱及圆环。为了产生一个体素，需要指定这些体素的尺寸（比如长 方体的高、 宽和长） 每个物体都有与之相关联的局部坐标系。 。 通过基本 CSG 操作运算， 相对整体世界坐标系放置各物体，就可以表达物体的空间位置。Voronoi 图[14]Voronoi 图在求解点集或其他几何对象与距离有关问题都起着很重要的作用。图 3-6设 p1 、 p2 是平面上两点，L 是线段p1 p2 的垂直平分线，L 将平面分成两部分 LL 、LR ，位于 LL 内的点 pl 具有特性：d( pl , p1 )&d( pl , p2 ),其中 d( pl , p1 )表示 pl 与 p1 之间的欧几里德距离，i=1,2。这意味着，位于 LL 内的点与平面其他点更接近点 p1 ，也就是说，LL 内的点是比平面上其他点更接近于 p1 点的轨迹，即为 V( p1 ),如图图 3-6 示。如果用H( p1 , p2 )表示半平面 LL ，而 LR = H( p2 , p1 )，则有 V( p1 )=H( p1 , p2 )，V( p2 )=H( p2 , p1 )。 给定平面上 n 个点的点集 S,S= {P1 , P2 ..., Pn } 。定义 V( p1 )= I H ( P1 , P1 ) ，即表示比其他i ≠1点更接近 p1 点的轨迹是 n-1 个半平面的交，它是一个不多于 n-1 条边的凸多边形域，称 为关联于 p1 的 Voronoi 多边形[33]。图 3-7 中表示关联于 p1 的 Voronoi 多边形，它是一个-17四边形，n=6.图 3-7 ，V(p1 )对于 S 中的每个点都可以做一个 Voronoi 多边形， 这样的 n 个 Voronoi 多边形组成的 图称为 Voronoi 图，记为 Vor(S),如图 3-8 所示图 3-8 Voronoi 图与其对偶图该图中的顶点和边分别称为 Voronoi 顶点和 Voronoi 边。Vor(S)的边是 S 某点对的垂 直平分线上的一条线段或者半直线，从而为该点对所在的两个多边形域所共有。 Voronoi 图扩展到高维特特征称为普遍 Voronoi 图，即一个特征的最近点集。一般来 说，普遍 Voronoi 图具有两次边界。但是对于凸物体，它的普遍 Voronoi 图具有平面边 界。 特征：指多面体的一个顶点，边或面。 特征对的距离：指两个特征上最近的两点距离。最近特征对两个凸多面体间的最近特征对指包含最近点的一对特征。设多面体 A 和 B 表示 R3 中的两个凸集。假设 A 和 B 是封闭和有边界的，则物体间的距离定义为最短欧氏距离d AB-18d AB =若 p ∈ A , p ∈ B ，使得p∈ A , p∈ Binfp-q d AB = PA ? PB则 PA 和 PB 为 A 和 B 间的最近点。特征的 Voronoi 区域：多面体 A 上的一个特征 f 的 Voronoi 区域由距特征 f 最近的空间 点组成，即若设 p 为该区域内任一点，则 p 点距特征 f 的距离比 p 点距 A 上其他特征的 距离都小，即特征 f 是多面体 A 上距 p 点最近的特征。3.3.2 Lin-Canny 算法概述Lin-Canny 算法是一种基于特征（点、线、面）的增量算法。Ming C.Lin 引入了最近 特征对的概念， 通过构造 Voronoi 图， 利用凸性建立了用于验证最近特征的局部适用准 则来确定最近特征对，然后计算两个最近特征间的距离以判断两个凸多面体是否相交。 该算法利用了运动的空间及时间的连贯性， 假定新的最近特征对是上一时刻最近特征对 邻近的特征，因而下一时刻最近特征对的确认不再需要全局搜索。如图 3-9 所示，图 3-9 Voronoi 图V 面 1 和顶点 Vb 分别为物体 A、B 上的候选特征，先测试看点 b 是否在面 1 的Cp C V Voronoi 域 （单元 1） 由于 Vb 在约束面 里， 外， 故下一步测试 b 是否在 p 指向的邻近域（单元 2）中，如此测试下去直到两特征都分别位于对方的 Voronoi 域中， 这样的特征对即为最近特征对。一般情况下，物体在相邻两时刻位移不大，故相邻两时 刻的最近特征对相隔也不会很远，最近特征对的更新花费时间很少，从而使得该算法具 有实时性。-193.3.3 适应性准则测试一个点是否在某特征的 Voronoi 域，称为“适用性测试”。下面介绍三种直观的 几何适应性测试。 1）点-顶点适应性准则 如下图 2 所示，若被检测特征是多面体的一个顶点 V,其 Voronoi 区域是由几个约束面围 成，这几个约束面分别垂直于与 V 点相接的边，算法检测 P 点是否落在该区域内。若 P 点落在该区域外，则 P 点至少突破了某一个约束面，因而该约束面对应的多面体上的边 是距 P 点更近的特征 fB`,将之代替特征 V,与 fA 构成新的特征对，在递归地调用算法判 断 fA 与 fB`是否最近特征对。图 3-10 点-顶点适应性准则2）点-边适应性准则 如下图 3 所示，若被检测特征是多面体的一条边 E,其 Voronoi 区域是由 4 个约束面 围成。设 E 的两个顶点分别为 H e 和 Te ，有两个约束面垂直于 E 并分别经过 H e 和 Te ，另 两个约束面包含 E 并分别垂直于与 E 相接的两个面。算法检测 P 点是否落在该区域内。 若 P 点落在该区域外，则 P 点至少突破了某一个约束面，因而该约束面对应的多面体上 的边或顶点是距 P 点更近的特征 fB`,将之替代特征 E,与 fA 构成新的特征对，在递归地-20调用算法判断 fA 与 fB`是否最近特征对。图 3-11 点-边适应性准则3）点-面适应性准则 如下图 4 所示， 若被检测特征是多面体的一条边 F, 其 Voronoi 区域是由 F 和 F 的棱 柱约束面围成，这些约束面分别包含 F 的各边并垂直于 F。算法检测 P 点是否落在该区 域内，分两步。首先，检测 P 点是否在棱柱约束面围成的区域内，若是，则说明包含 P 点的特征 fA 与特征 F 是最近特征对。否则 P 点至少突破了某一约束面，因而该约束面 对应的物体 B 上的边是距 P 点更近的特征 fB`，将之代替特征 F,与 fA 构成新的特征队， 在递归地调用算法判断 fA 与 fB`是否最近特征对。 然后在检测 P 点是否在 F 面上， 以确 定 P 点不在物体 B 之内。若 P 点是在 F 面上，则 P 点在物体 B 之内。则说明至少有一 个物体 B 上的特征距 fA 更近，或者说明物体 A 和 B 可能发生碰撞。-21图 3-12点-面适应性准则当然适应性准则测试还有很多情况，如面-面，面-边，边-边情况，但是由于这 3 种 情况比较复杂，在此不作论述。主要以上述 3 种情况为主。 算法的伪代码如下： closetFeatureInit (poly1,poly2) { feat1=poly1 上的任一点； feat2=poly2 上的任一点； 调用 closetFeature（poly1,poly2,feat1,feat2）返回最近特征队； } closetFeature（poly1,poly2,feat1,feat2） { dist=-1; do { 根据 feat1，feat2 的类型分为: case&V,V&:dist=v_v(poly1,poly2,feat1,feat2); case&V,E&:dist=v_e(poly1,poly2,feat1,feat2); case&V,F&:dist=v_f(poly1,poly2,feat1,feat2);-22}while(dist=-1) } //点-点 v_v(poly1,poly2,v1,v 2) { if(v1 不在 v2 的 Voronoi 区内) { 将 v2 更新为相邻边； return -1; } if(v2 不在 v1 的 Voronoi 区内) { 将 v1 更新为相邻边； return -1; } return v1 与 v2 的距离； } //点-边 v_e(poly1,poly2,v,e) { if(v 不在 e 的 Voronoi 区内) { 将 e 更新为相邻顶点或面； return -1; } 计算 e 上距 v 最近点 if(u 不在 v 的 Voronoi 区内) { 将 v 更新为相邻边； return -1;-23} return v 与 e 的距离； } //点-面 v_f(poly1,poly2,v,f) { if(v 不在 f 的 Voronoi 区内) { 将 f 更新为相邻边； return -1; } 计算 f 上距 v 最近点 if(u 不在 v 的 Voronoi 区内) { 将 v 更新为相邻边； return -1; } return v 与 u 的距离； }-24第四章 编程基础理论第五章碰撞检测算法的应用是在 Visual C++6.0 环境下利用 OpenGL 库得以实现。 因此，本章将简要介绍 OpenGL 编程和面向对象编程的基础知识。4.1 OpenGL 编程基础4.1.1 OpenGL 基本特点随着计算机技术的不断发展， OpenGL 已被认为是高性能图形和交互式视景处理的 标准。目前包括 IBM 公司、SUN 公司、HP 公司、Microsoft 公司和 SGI 公司在内的几 家在计算机市场占领导地位的大公司都采用了 OpenGL 图形标准。 OpenGL 三维图形加速卡和微机图形工作站的推出，人们可以在微机上实现三维图 形的应用， CAD 设计、 如 仿真模拟、 三维游戏等， 从而更有机会、 更方便地使用 OpenGL 及其应用软件来建立自己的三维图形世界。OpenGL 具有以下特点[15]： 1）工业标准 OARB(OpenGL Architecture Review Board)联合会领导 OpenGL 技术规范发展， 使其 得到广泛的支持，成为业界唯一真正开发的、跨平台的图形标准。 2）可靠度高 OpenGL 与硬件独立，只要硬件支持 OpenGL API 标准就行，也就是 OpenGL 应用 可以运行在支持 OpenGL API 标准的任何硬件上。 3）可扩展性 OpenGL 是低级的图形 API,它具有充分的可扩展性。 4）可伸缩性 基于 OpenGL API 的图形应用程序可以运行在许多系统上， 包括各种用户电子设备、 工作站以及超级计算机。 5）容易使用-25OpenGL 的核心图形函数功能强大，带有很多可选参数，可以利用已有的格式数据 进行三维物体建模，大大提高效率。 OpenGL 提供了以下基本操作： 1）绘制物体 OpenGL 提供了丰富的基本图元绘制命令，利用简单的点、线、面绘制真实世界中 任何真实的物体。 2）变换任何复杂的物体都是经过基本图元一系列变换得到。OpenGL 提供了一系列基本变 换，如取景变换、模型变换、投影变换、视口变换。 3）光照处理为了使场景得到真实感效果，必须进行光照处理，OpenGL 正好提供此功能。 4）着色 OpenGL 提供了两种物体着色模式，一种是 RGBA 颜色模式，另一种是颜色索引模 式。 5）反走样 在 OpenGL 绘制出来的图形中，由于是位图，图像的边缘处会出现锯齿形状，称为 走样。为了消除该现象，OpenGL 提供了反走样技术。 6）纹理映射在计算机图形学中，把包含颜色、alpa 值和亮度等数据的矩形数组称为纹理。而纹 理映射是将纹理贴在所绘制的三维模型表面，使三维图形显得更生动。 7）动画 OpenGL 提供了双缓存区技术来实现动画绘制。-264.1.2 OpenGL 实现整个 OpenGL 的基本工作流程如下图所示：图 4-1 OpenGL 工作流程图其中几何顶点数据包括模型的顶点集、 线集和多边形集， 这些数据经过流程图的上部， 包括运算器、逐个顶点操作等；图像数据包括象素集、影像集、位图集等，图像象素数 据的处理方式与几何顶点数据的处理方式是不同的，但它们都经过光栅化、逐个片元 （Fragment）处理直至把最后的光栅数据写入帧缓冲器。在 OpenGL 中的所有数据包括 几何顶点数据和象素数据都可以被存储在显示列表中或者立即可以得到处理。 OpenGL 要求把所有的几何图形单元都用顶点来描述。这样运算器和逐个顶点计算 操作都可以针对每个顶点进行计算和操作，然后进行光栅化形成图形碎片；对于象素数 据，象素操作结果被存储在纹理组装用的内存中，再象几何顶点操作一样光栅化形成图 形片元。整个流程操作的最后，图形片元都要进行一系列的逐个片元操作，这样最后的象素 值 BZ 送入帧缓冲器实现图形的显示。 根据这个流程可以归纳出在 OpenGL 中进行主要的图形操作直至在计算机屏幕上渲 染绘制出三维图形景观的基本步骤： 1）根据基本图形单元建立景物模型，并且对所建立的模型进行数学描述（OpenGL 中把：点、线、多边形、图像和位图都作为基本图形单元）。 2）把景物模型放在三维空间中的合适的位置，并且设置视点（viewpoint）以观察所 感兴趣的景观。 3）计算模型中所有物体的色彩，其中的色彩根据应用要求来确定，同时确定光照条-27件、纹理粘贴方式等。 4） 把景物模型的数学描述及其色彩信息转换至计算机屏幕上的象素， 这个过程也就 是光栅化（rasterization）。 在这些步骤的执行过程中， OpenGL 可能执行其他的一些操作， 例如自动消隐处理等。 另外，景物光栅化之后被送入帧缓冲器之前还可以根据需要对象素数据进行操作。4.1.3 OpenGL 图形绘制在 OpenGL 中，所有的几何物体都是由若干个有序的顶点集合来描述。例如： glVertex2s(3,8);//整数定义的二维坐标 glVertex4f(1,2,….4);//浮点数定义的齐次坐标 在 OpenGL 中，同一个几何图元的所有被定义的顶点一起放在 glBegin()和 glEnd()函 数之间，同时定义这些定点之间的关系。例如： glBegin(GL_POLYGON);//绘制一个多边形 glVertex2s(0,0); glVertex2s(0,12); glVertex2s(12,16); glVertex2s(16,8); glVertex2s(8,0); glEnd(); 另外 glBegin()和 glEnd()之间可以指定顶点的颜色、法向、纹理坐标等信息。例如： glCallList();//执行显示列表 glColor*();//设置当前颜色-28glEdgeFlag*();//控制边界绘制 glMaterial*();//设置材质 glNormal*();//设置法向坐标 glTexCoord*();//纹理坐标4.1.4 OpenGL 光照处理 光照处理当光照射到一个物体表面上时，会出现三种情形。首先，光可以通过物体表面向空 间反射，产生反射光。其次，对于透明体，光可以穿透该物体并从另一端射出，产生透 射光。最后，部分光将被物体表面吸收而转换成热。在上述三部分光中，仅仅是透射光 和反射光能够进入人眼产生视觉效果。 这里介绍的简单光照模型只考虑被照明物体表面 的反射光影响，假定物体表面光滑不透明且由理想材料构成，环境假设为由白光照明。 就光源而言，一般来说，反射光可以分成三个分量，即环境反射、漫反射和镜面反 射。 环境反射分量假定入射光均匀地从周围环境入射至景物表面并等量地向各个方向反 射出去，通常物体表面还会受到从周围环境来的反射光（如来自地面、天空、墙壁等的 反射光）的照射，这些光常统称为环境光（Ambient Light） ；漫反射分量表示特定光源 在景物表面的反射光中那些向空间各方向均匀反射出去的光，这些光常称为漫射光 （Diffuse Light） ；镜面反射光为朝一定方向的反射光，如一个点光源照射一个金属球时 会在球面上形成一块特别亮的区域，呈现所谓“高光（Highlight）”，它是光源在金属球 面上产生的镜面反射光（Specular Light） 。对于较光滑物体，其镜面反射光的高光区域 小而亮；相反，粗糙表面的镜面反射光呈发散状态，其高光区域大而不亮。 至于光源的位置，在现实生活中，光密度是随着光源的距离的增加而减少；而在图 形学中则按照一定的衰减来反映这种位置的变化。 另外，不同的材质有不同的环境、散射和反射颜色，它们决定了材质的环境、散射 和镜面反射颜色。材质的环境反射颜色与进入光源的环境反射分量结合，它的散射反射 则与光源的散射分量结合，镜面反射则是与光源镜面反射分量结合在一起。反射和散射 定义了材质的颜色，并且二者在典型的情况下是相同的或者是相似。镜面反射颜色通常 是白色或灰色，因此镜面反射的高度端就是光源镜面反射颜色的密度。比如当一束白光 照到一个会闪光的红色塑料球上时，我们会看到这样的效果：大部分球体看上去是红色-29的，但高度处则是白色。 OpenGL 提供了较为丰富的手段实现光照处理，以产生逼真的图形效果。OpenGL 光 照模型考虑光源和物体材质属性两个方面的因素，同时光照效果又细分为环境光、漫射 光和镜面反射光等方面的效果。概括来说，对物体对象光照处理的基本步骤如下： （1）定义物体各顶点的法向矢量，借助这些法线可以确定物体与光源的相对方向。 OpenGL 由此可计算出每个顶点接受来自光照的光强度。 （2）创建、放置、打开光源。OpenGL 提供 glLightv 函数用于定义光源，并允许同时最 多 8 个光源。可以在空间任意点布置光源，既可以安排离场景较近，也可以是无穷远； 光束的形状也可以控制。不过，每引入一个光源，都会给 OpenGL 带来大量计算工作， 最终会影响绘图的性能，因而光源的使用需要慎重。 （3）选择光照模型。OpenGL 提供了 glLightModel 函数用于完成这一工作。 （4）定义场景中物体的材质属性。物体的材质属性决定了物体反光的性质。 OpenGL 中光照处理中一些常用的函数： void glLight {if}[v](GLenum light,GLenum pname,TYPE param); 参数 light 是光源的标识，例如 GL_LIGHT0,GL_LIGHT1,……,GL_LIGHT7 pname 代表需设置的属性。 启动和取消光照的函数如下: glEnable(GL_LIGHTING);//启用光源 glDisable(GL_LIGHTING);//取消光源 如果在环境中定义光源，则需要为每个光源指定打开或关闭。 glEnable(GL_LIGHT0);//打开光源 glDisable(GL_LIGHT0);//关闭光源4.1.5 OpenGL 纹理映射 纹理映射现实世界中的物体表面很少是光滑和单调的，往往具有各种纹理，通过颜色色彩或 明暗的变化体现出来的表面细节，这类纹理称为颜色纹理。在计算机图形学中是采用纹 理映射的方法给计算机生成的物体图像加上纹理。 生成颜色纹理的一般方法是在一平面 区域上预先定义纹理图案，然后建立物体表面的点与纹理空间的点之间的对应。当物体-30表面的可见点确定以后，用纹理空间的对应点的值乘以亮度值，就可以将纹理图案附到 物体表面，即生成纹理。 使用纹理绘制的一般步骤为： 1．定义纹理 定义纹理是指设定纹理图像。在一般情况下，纹理图像为一单独图像。有一维纹理 图像、二维纹理图像。1D 纹理是只有宽度、没有高度的图像仅仅是简单的像素宽或高； 2D 纹理是多于一个像素宽和高的图像，通常从 WINDOWS BMP 文件的加载。在在 OpenGL 中一个简单的函数定义 1D 纹理： glTexImage1D， 一个简单的函数定义 2D 纹理： glTexImage2D 函数定义如下： Void glTextImage1D(GLenum target,Glint level,Glint components,GLsizei width,Glint border,GLenum format,GLenum type,const GLvoid *pixels) [17] Target 参数指定应该定义哪一个纹理，这一参数必须为 GL_TEXTURE_1D；level 参数指出纹理图像的详细级别，并且通常为 0；components 参数指定每一个像素颜色值 的数字。对于颜色索引纹理，component 参数必须为 1、3 和 4 分别用于 RGB 和 RGBA 纹理图像；Width 和 border 指定纹理图像的尺寸；format 参数指出颜色值的类型。 要在 OpenGL 中定义 2D 纹理图像，可以调用 glTexImage2D,它除了含有参数 height 之外，其他参数与 glTextImage1D 相同，如下所示： Void glTextImage1D(GLenum target,Glint level,Glint components,GLsizei width, GLsizei height, Glint border,GLenum format,GLenum type,const GLvoid *pixels) 与 glTexImage1D 一样，参数 width 和 height 必须为 2 的幂数。 2．定义纹理映射方法 定义纹理映射方法是指设定纹理图像映射到目标区以获得最终 RGBA 值的方式。 OpenGL 提供了三种纹理映射方法： 一种是简单地把纹理的颜色作为最终的颜色来使用； 另一种方法是使用纹理来调节目标区的颜色，以获得最终颜色；最后一种是使用纹理颜 色与目标区颜色相融合。定义纹理映射方法的 OpenGL 函数为 glTexParameter,glTexEnv 等。 3．启动纹理绘制 要进行纹理绘制， 首先必须启动纹理绘制。 GL_TEXTURE_1D 和 GL_TEXTURE_2D 用 作参数调用 glEnable()函数可以分别启动一维纹理和二维纹理。用同样的参数调用函数-31glDisable 则禁止一维纹理或二维纹理。 4．用纹理坐标和几何坐标绘制目标区 在纹理被粘贴之前，需要指明纹理和目标区的对齐方式，即在指定绘制物体的同时指 定纹理坐标和几何坐标。对于二维纹理图，纹理坐标在两个方向上的取值范围都是 0.0~1.0。若目标区只绘制一份纹理图案，可分配纹理坐标（0，0）、 （1，0）、 （1，1）、 （0，1）到目标区的四个角上。指定纹理坐标的 OpenGL 函数为 glTexCoord。4.1.6 深度测试 深度测试深度缓存保存每个象素的深度值。每个值都代表了像素与观察者之间的距离，并按 比例去填满当前的近处/远处剪贴空间。在 windows 下，OpenGL 的软件实现都支持 16 位和 32 位深度值。深度通常用视点到物体的距离来度量，这样带有较大深度值的象素 就会被带有较小深度值的象素替代。深度缓存也称为 z-buffer，因为在实际应用中，x,、 y 常用来度量屏幕上水平与垂直距离，而 z 常被用来度量眼睛到屏幕的垂直距离。 深度缓冲区经常用来执行隐藏面的删除。隐藏表面的删除是在现实世界中自然发生 的过程。当一个实体（不透明）对象放置在另一个对象前的时候，前面那个对象就会遮 住后面对象的一部分或者全部。 在 OpenGL 中通过使用 glEnable 来执行一些隐藏表面的删除操作或者深度缓冲区的 其他一些应用来进行深度测试[17]。 glDisable(GL_DEPTH_TEST); 一旦完成绘图工作，就应该使用 glDisable 来禁止深度测试 glEnable(GL_DEPTH_TEST);4.2 面向对象的编程使用 VC++开发 windows 环境下 OpenGL 应用程序， 采用面向对象的程序设计方法， 便于维护管理三维数据，使开发出来的源代码具有很好的可调试性、可维护性以及可重 用性。 1）面向对象技术 面向对象技术是目前流行的系统设计开发技术，它包括面向对象分析和面向对象设 计，面向对象设计是一种围绕真实世界的概念来组织模型的程序设计方法，采用对象来-32描述问题空间的实体，一般认为对象是包含现实世界物体特征的抽象实体，反映了系统 为之保存信息和(或)与它交互的能力。 类是具有相同操作功能和相同的数据格式(属性)的对象的集合。从外部看，类型的 行为可以用新定义的操作加以规定，类为对象集合的抽象规定了对象的公共属性和方 法，对象就是类的一个实例。消息是向某对象请求服务的一种表达方式，对象内有方法 和数据，外部的用户或对象对该对象提出的服务请求称为向该对象发送消息。合作是指 两个对象之间共同承担责任和分工。 面向对象的编程方法具有以下四个基本特征： 抽象、 继承、封装、多态。 2）面向对象设计用于三维图形处理的优势 三维图形处理的一个显著特点就是处理的数据量特别大，而他们的共性很大程度都 相同.如果处理不好的话， 会造成设计代码的重复与不便维护管理。 面向对象程序设计用 类(class)来表示具有相同属性的所有对象的逻辑原型，是对象设计的规则。同一类的对 象具有相同的性质和方法，每一个具体的对象都是类的一个实体，创建对象就是把类实 例化。从而很轻松的维护管理此类的数据，提高代码的可重用性，避免了代码的重复。 三维图形处理的目的就是模拟真实世界形成模型，进行设计优化。而面向对象的基本思 想就是尽量对客观世界的直观化反映，所见即所得，它与图形处理的要求相符，同时符 合程序设计者的思维方式，以便程序设计者集中精力进行三维图形处理的数据结构设 计。 三维图形处理的理论在不断的发展改变。对于程序设计者来说，某种功能的实现随着 它的发展会不断的优化和改变，如果能够通过只是改变某一部分程序而能实现它，且不 影响其他部分的功能的实现，就会大大提高程序设计的可修改性。而面向对象的封装性 (Encapsulation)将数据和处理数据的方法组合在类中。类只向外界公布其具有 public 属 性的数据和代码，并构成类与外界的接口，程序的其他部分只能访问类的接口，只要保 持类的接口不变，改变类的内部结构、工作方式和实现就不会对整个程序产生附加的影 响，因此，改变类内部实现方式能够达到优化的目的。4.3 OpenGL 编程环境的设置OpenGL 编程环境的设置： 1) 从 OpenGL 开发库中获得 3 个文件：glut32.dll、glut32.lib、glut.h；-332) 将 glut.h 文件拷贝到 VC 的\Include\GL 目录中； 3) 将 glut32.lib 文件拷贝到 VC 的\lib 目录中； 4) 将 glut32.dll 文件拷贝到操作系统对应的目录中； 5) 添加 OpenGL 库。 打开 Visual C++6.0， 选择“工程”菜单， 在下拉菜单下选择“设置”， 出现“project setting” 界面， 然后选择“link”选项， 最后在“对象/库模块”中添加“opengl32.lib、 glu32.lib、 glaux.lib” 三个库文件，最后单击“确定”按钮，这样 OpenGL 库文件添加完毕。图 4-2 添加 OpenGL 库-34碰撞检测算法的 算法的应用 第五章 碰撞检测算法的应用鉴于上文对各种碰撞检测算法的分析与研究，在此将采用 OBB 包围盒层次树来实[18]现一个虚拟场景中多面体之间碰撞检测的过程。虚拟场景是描述一个多面体从空中做自由落体运动，碰到地面上的物体发生碰撞摔 成碎片的过程。本实例涉及到技术有物体建模、场景绘制和碰撞检测。下面将详细介绍 这三种技术。5. 1 物体建模 物体建模虚拟场景中物体是：多面体、圆柱体易拉罐、立方体箱子，地板。 虚拟环境中物体所用的模型有体模型和面模型。体模型采用体元表示物体，可描述 物体的内部信息，但所耗存储量大。一般情况下采用面模型表示物体，尤以三角形模型 为最优。因此，采用若干个三角形面片构造出现实生活中常见的物体：多面体、圆柱体 和立方体。因此，本实例虚拟场景中物体形状的选择具有代表性和典型性。 虚拟场景的建模是采用读取外部.mod 文件实现的。每个物体的.mod 文件均包括了 每个三角面片的三个顶点在空间位置的坐标， 以及每个物体划分的三角面片的个数等等 信息。对于.mod 文件的形成，用 fwrite 函数来实现，详细的文件格式有 object 结构体给 出。 在碰撞检测，以及物体三维显示中，场景中各物体的绘制均是采用读取.mod 模型文 件来建立的。首先读取一个 config.txt 文件，在该文件中设置了场景的对象树目、各对 象的名称和对象的初始位置。实验中 config.txt 各参数值如图 5-1 所示：-35场景中对象划分个 数 场景的对象名称 block plate_base plate_sarm0 plate_sarm1 plate_sarm2 plate_sarm3 plate_sarm4 plate_sarm5 plate_sarm6 plate_sarm7 plate_larm0 plate_larm1 plate_larm2 plate_larm3 plate_larm4 plate_larm5 plate_larm6 plate_larm7 plate_vstaple can20场景对象初始 x 坐标 场景对象初始 y 坐标 场景对象初始 z 坐标 5.8 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 7.3 -11.0 15.0 15.0 15.0 15.0 15.0 15.0 15.0 15.0 15.0 15.0 15.0 15.0 15.0 15.0 15.0 15.0 15.0 0.0 -5.5图 5-1 实验中 config.txt 数据0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0读取 config.txt 文件中参数值的实现代码如下： if((file=fopen(&config.txt&,&r&))==NULL) { printf(&Can't open config.txt\n&); exit(-1);-36} fscanf(file,&%d %f&,&STEP,&GRAVITY); fscanf(file,&%d&,&NUM); for(x=0;x#x++) // 读出对象的名称和对象的初始位置 // 读出对象的数量fscanf(file,&%s %f %f %f&,&filename[x][0],&offset[x].x, &offset[x].y,&offset[x].z); fclose(file); 然后根据读取的每个对象名称，可以获得该对象所在的文件名，通过这些文件名读 取外部.mod 文件可以继续将各个对象的各种参数读出来。如顶点数目、面的数目、摩擦 系数、纹理参数等。 本程序中采用面模型来实现三维物体的建模，考虑到物体建模的复杂度，采用了最 常用的多面体建模，具体的来说，输入模型是一组无拓扑约束的三角面片。其中对物体 三维空间的划分，是靠自己来定义的，包括了物体用多少三角面片来表达，每个三角面 片的顶点在空间的坐标等等， 这些信息都存在.mod 文件中。 三维物体的建模是通过调用 OpenGL 库函数 glVertex3f（）在三维空间中绘制三角形面片来实现。物体分的越细，三 角面片就越小，真实感就越强。缺点就是，增加了碰撞检测算法的复杂度，不利于实时 性的监测，同时生成三维实体所耗费的时间增加。 为了能够逼真的看到物体的建模过程，在程序中用两种方法来实现，一种是线框模 式绘制；一种是颜色实体绘制。在线框模式下如图 5-2 中可以清楚地看到若干个点绘制 三角形片的框架。图 5-2 线框模式绘制在虚拟场景中地板是静止、规则、简单的物体，因此对于地板的建模我们只需要调-37用 OpenGL 库函数即可。 场景中地板的绘制代码如下： // 绘制地板 glColor4f(.2,.4,.2,1.0); glNormal3f(0.0,1.0,0.0); glBegin(GL_TRIANGLES); glTexCoord2f(0.0,1.0); glVertex3f(-20.0,-15.4,20.0); glTexCoord2f(1.0,1.0); glVertex3f(20.0,-15.4,20.0); glTexCoord2f(0.0,0.0); glVertex3f(-20.0,-15.4,-20.0); glTexCoord2f(1.0,0.0); glVertex3f(20.0,-15.4,-20.0); glTexCoord2f(0.0,0.0); glVertex3f(-20.0,-15.4,-20.0); glTexCoord2f(1.0,1.0); glVertex3f(20.0,-15.4,20.0); glEnd();5. 2 场景绘制为了虚拟场景到达更加逼真的效果，需要对虚拟场景进行各种处理，比如，添加光 照、纹理等。 OpenGL 可以根据光照条件创造出和真实世界非常接近的图形来，有三种类型的光 照：环境光、散射光和镜面光。 环境光不来自任何特殊方向，它有光源，但是被周围的房间或场景多次反射后以至 于变得没有方向。被环境光照射的物体表面各个方向都均等受光。 散射光来自某个方向，被物体表面均匀地反射。即使光是被均匀反射回去的，它直 射的物体表面比从某个角度照射过来时要亮。 比较典型的散射光源是荧光照明设备或中 午时入射侧窗的太阳光束。 镜面光和散射光一样有方向性，但被强烈地反射到另一特定的方向。高亮度的镜面 光往往能在被照射的物体表面上产生称之为亮斑的亮点。 本实例中光源定义代码如下： // 光源定义 GLfloat light_diffuse[] = {1.0, 1.0, 1.0, 1.0};-38GLfloat light_position[] = {10.0, 10.0, 30.0, 1.0}; 在绘制多面体、圆柱体易拉罐和立方体箱子时，使用 glNormal3f（）函数即法线矢量定 义了物体表面在 3D 空间的方向，尤其是相对光源的方向。在定义虚拟场景中物体时， 同时也定义其法线矢量。 在本实例中多个顶点共用一个法线矢量。虚拟场景的物体建模是三角形描述表面， 其法线的计算是为每一个三角形面计算法线矢量，然后对相邻面的法线取平均，相邻多 边形的公用顶点使用平均法线。在本场景中立方体箱子本身就是一个多边形，就不用求 平均法线。在对象的面的数据结构 struct face 中，有 p 、 p2 、 p3 顶点，则法线矢量为1objects[i].faces[x].nor.x= objects[i].faces[x].nor.y=( p1 x - p 2 x ) × ( p 2 x - p 3 x )(p1y- p2 y ) ×(p2z2y- p3 y )objects[i].faces[x].nor.z= ( p1 z - p 2 z )× (p- p3 z )最后再对 x,y,z 方向的法线矢量单位化。 例如： glNormal3f(objects[i].faces[x].nor.x,objects[i].faces[x].nor.y,objects[i].faces[x].nor.z); glNormal3f(0.0,1.0,0.0); // 使用光照 glLightfv(GL_LIGHT0, GL_SPECULAR, light_diffuse); glLightfv(GL_LIGHT0, GL_POSITION, light_position); 场景中增加了光照实现了高度的真实感，然而仍然感觉场景比较单调没有生机。在 此我们可以利用一幅图像，比如真实表面的照片或细节，然后将这幅图像应用到多边形 面上，这幅图像称为纹理。 本实例中纹理参数是通过读取外部 TGA 文件获得。部分代码如下 //启动纹理 glEnable(GL_TEXTURE_2D); //纹理映射 glTexEnvf(GL_TEXTURE_ENV, GL_TEXTURE_ENV_MODE, GL_DECAL); glTexParameteri(GL_TEXTURE_2D,GL_TEXTURE_WRAP_S, GL_REPEAT); glTexParameteri(GL_TEXTURE_2D,GL_TEXTURE_WRAP_T, GL_REPEAT);-39glTexParameteri(GL_TEXTURE_2D,GL_TEXTURE_MAG_FILTER,GL_LINEAR; //定义纹理图像 glTexImage2D(GL_TEXTURE_2D,0,GL_RGBA,64,64,0,GL_RGBA,GL_UNSIGNED_BY TE, objects[i].texmap); glBindTexture(GL_TEXTURE_2D, texName); //设置纹理坐标 glTexCoord2f((*objects[i].texfaces[x].p1).x,(*objects[i].texfaces[x].p1).y); //关闭纹理 glDisable(GL_TEXTURE_2D); 为了更好绘制碰撞检测的全过程，可以采用多种模式显示场景，包括线框模式、颜 色实体模式和纹理实体模式，首先是场景的初始化操作，包括创建和使用、应用使用深 度测试和投影矩阵。 在 OpenGL 中允许通过使用 glEnable 来执行一些隐藏面的删除操作或深度缓冲区的其他 一些应用来进行场景深度测试 代码如下： // 使用深度测试glEnable(GL_DEPTH_TEST); 又如： void glMatrixMode(GLenum mode) 这个函数用于确定将使用哪个矩阵堆栈（GL_MODELVIEW、GL_PROJECTION 或 GL_TEXTURE）,参数 mode 标识出将哪个矩阵堆栈用于接下来的矩阵操作，参数可为 GL_MODELVIEW、GL_PROJECTION 或 GL_TEXTURE 中任何值。 （用于在场景中移动对象） ； GL_MODELVIEW 表示矩阵操作将作用于模型视图矩阵堆栈 GL_PROJECTION 表示矩阵操作将作用于投影矩阵堆栈（用于定义修剪空间） ； GL_TEXTURE 表示矩阵操作将作用于纹理矩阵堆栈（处理纹理坐标） ； 在本程序中所使用的是投影矩阵和模型视图矩阵。即： glMatrixMode(GL_PROJECTION)；//用于将创建的模型转换成屏幕上的最终图像 glMatrixMode(GL_MODELVIEW);//用来场景中物体的模型变换，如平移、旋转-405.3 碰撞检测算法的应用 碰撞检测算法的应用5.3. 1 基础理论本场景中碰撞检测认为是弹性碰撞，整个程序的实现涉及到许多弹性碰撞理论。下 面有必要介绍一下弹性碰撞的理论。 如果两个物体在碰撞前后内部状态不发生改变， 则这种碰撞称为弹性碰撞或弹性散 射。弹性碰撞的特点是：动量守恒、角动量守恒和机械能守恒。 发生弹性形变的物体， 由于要恢复原状而对跟它接触的物体产生的相互作用力叫弹 力。弹力是形变物体内部产生的反抗力。弹力产生的条件：物体发生弹性形变和物体之 间必须直接接触。弹力遵循胡克定律即在弹性限度内，弹簧弹力的大小 f 和弹簧伸长或 缩短的长度 x 成正比，即：f=-kx。式中 k 是比例常数，叫做劲度系数，国际单位制中 k 的单位是：牛顿／米。劲度系数与弹簧的材料、粗细、长短等有关，不同弹簧的劲度系 数一般是不同的。x 称为形变量，单位是米。负号表示力的方向与形变方向相反。 弹性碰撞要讨论的两个问题：(1)不考虑两个物体相互作用的细节，只根据守恒定律 的要求， 找出碰撞前后物体运动所必须满足的条件． 这类问题称为碰撞的运动学问题． (2) 如果相互作用是已知的，则由碰撞前的物体状态可唯一的确定碰撞后的物体状态，或反 之，由碰撞后的物体状态，倒过来推算出两个物体间的相互作用 题称为碰撞的动力学问题． 在本程序中主要涉及的是碰撞的动力学问题即碰撞响应问题， 即当实体发生碰撞时 所受力对其运动的影响。 动力学的基本定律是牛顿所建立的三条运动定律。 第一运动定律：任何实体都保持静止或匀速直线运动状态，直到其它实体的作用力 迫使它改变这种状态为止； 第一定律指明任一实体在未受外力的情况下，将保持原有的运动状态；在第一定律 的基础上。 第二定律： 实体受到外力作用时， 实体获得的加速度的大小与合外力的大小成正比， 并与实体的质量成反比，加速度的方向与合外力的方向相同； 第二定律对实体机械运动的规律作了定量的陈述，引入力和质量两个物理量，即 f=m?a；-41函数形式．这类问第三定律：当实体 A 以 f1 作用在实体 B 上时，实体 B 也必定以力 f2 作用在实体 A 上，f1 和 f2 在同一直线上，大小相等而且方向相反 第三定律说明了实体间的作用力具有相互作用的本质:力是成对出现的， 作用力和反 作用力同时存在，同时消失。→另一表示实体运动状态的物理量是动量 P,即实体质量与实体速度的乘积， p =m×v；→→→ →根据动量定理：实体所外力的冲量等于实体的动量的增量，即 I = p2 - p1 其中 p1 表示 初动量，P2 表示末动量。 动量定理在冲击和碰撞等问题中特别有用。两个实体在碰撞的瞬间，相互作用的力 称为冲力，如下图 5-3，其中 f 表示冲力的大小，t 表示时间。冲力的作用时间极短，而 在最值上的变化极大，所以很难度量每一瞬间的冲力。如果知道碰撞前后动量，根据动 量定理就可以计算实体所受的冲量；如果知道时间的话，那末就可以得到这段时间内冲 力的平均大小。另一方面，可根据冲量的大小计算动量的变化量，从而得到碰撞后实体 的速度。 在本章碰撞检测实现中， 利用以上理论计算场景中物体碰撞前后的动力学状态变化 的。ft图 5-3碰撞过程冲力示意图-425.3.2 碰撞检测的实现过程本虚拟场景碰撞检测的实现过程是采用 OBB 包围盒层次树法。前提准备工作如下： 1）树的度数选择 在构造树层次时，一般趋向于将树的高度最小化，使得从根到叶的搜索路径最短。 通常情况下，树的度数越大，即其内部结点的子结点个数越多，则树的高度越小，这样 虽然搜索路径较短，但是花费时间比较多；如果树的度数越小，在每个内部结点上所花 费的工作比较小，但树的高度比较大。因此，树的度数选择是一定要考虑花费时间和树 的高度两个方面。 比较好的选择是二叉树，原因一是二叉树的计算最简单最快速，原因二是理论分析 结果说明，二叉树比其他多叉树更好。理论证明如下： 设有一个带 n 个叶结点的多叉树，其内部结点的度数为 δ ≥ 2 ，则从根到叶搜索的 耗费与 f (δ ) = δ logδ n 成正比。通过对 f (δ ) 微积分，可以求得当 δ =2 时， f (δ ) 的值 达到最小。 因此，在本实例中树的度数选择为 2 2）构造树方法的选择 从一输入几何元集合 S 上构造一个树可采用两种方法：自顶向下和自底向上。在本 实例中采用自顶向下方法是从一个逼近 S 的结点开始， 利用整个集合的性质递归地划分 结点，直至到达叶结点。 3）分割规则 每个结点 v 都对应于输入几何元集合 S 的一个子集 Sv,以及 Sv 的一个相应的包围盒 b(Sv),构造树的过程中， 每一步的目标是将集合 S 的子集 Sv 划分到当前结点 v 的子结点 上，使得某种表达其子结点尺寸的函数值达最小。 综合各方面的考虑，OBB 包围盒层次树碰撞检测算法整体框架可如下所示图 5-4：-43预处理阶 段输入物 体模 型进行物体表面 分解得到一系 列三角面 片建构节点为层 次二叉树计算顶层包围 盒和子结点包 围盒碰撞检测 阶段判 断并 返 回 检测 结 果在层次树的节 点对之间进行 碰撞检测遍历物体对的 层次二叉 树快速找到可能 发生碰撞的物 体对图 5-4OBB 包围盒层次树碰撞检测算法整体框架OBB 包围盒层次树碰撞检测实现的具体步骤如下： 首先， 碰撞初始化。 为场景中每个物体计算顶层 OBB 包围盒和 OBB 子结点包围盒。 计算包围盒的各顶点沿 x、 和 z 坐标轴投影得到沿每个坐标轴上最大最小值相对应的 6 y 个顶点。 OBB 包围盒的创建方法参照如第 3.2.2 节中“为表示物体的多边形集合计算一个 OBB 包围盒”中所介绍的，创建 OBB 包围盒流程如图 5-5 所示。读取 物体 三角 片的顶点 求顶 点的 均值 和协方差矩阵 协方差的3个 特征 根归 一化 作为一个基OBB包 围 盒 构造完毕基的 轴向 作为OBB的方向沿基 的每 个轴 向， 找到 轴向 极点 顶点 ，规 定OBB大小图 5-5 OBB 包围盒的创建流程然后，开始碰撞检测，先顶层包围盒间的一维空间排序法进行碰撞检测，如果两个 顶层包围盒发生碰撞，在继续对子结点包围盒利用一维空间排序法进行精确碰撞检测。 如果不发生碰撞，则继续进行检测下一对顶层包围盒是否碰撞，直到找到发生碰撞的两 个顶层包围盒为止。 一维空间排序法将物体的包围盒分别投影到 x,y,z 坐标轴上，成为一些一维区段。显-44然，两个包围盒有重叠的充要条件是它们在三个轴上的投影区段都有重叠。为此，可创 建三个列表，分别对应于三个坐标轴。每个列表记录了其对应坐标轴上的投影区段的端 点。通过对这些列表分别排序，可以找出有重叠的区段。通常，这类排序运算时间开销 为 O(nlogn)；n 是物体的个数。这里，可通过保存前一帧的列表排序结果来减少运算时 间，当前只需修改运动物体的区段端点。若帧间物体运动很小，则列表已比较接近排序 状态，可在 O(n)时间内完成重新排序。 最后，进行碰撞后的处理。根据运动学的相关原理，实时地对碰撞后包围盒的更新、 获取各面速度、各个三角面片定点的位置。以此来完成空间各个物体的重画以及实时显 示，达到比较真实的反应碰撞效果。 要实时更新碰撞后包围盒，先计算每个物体包围盒的每个顶点的沿每个坐标轴的初 始最大最小值相对应的 6 个顶点，称为最值定点。当物体移动时，各帧的时间间隔足够 小，各帧之间运动的物体变化不大，在每一帧进行如下的重新计算。 1）分别检查物体的 6 个原值顶点，将它与其相邻顶点相比较，如果它仍保持原有的极 值性（最大或最小） ，则无需更改； 2）否则将原最值顶点替换成比之更大（或更小）的相邻顶点，此过程重复指到找到当 前的最值顶点。 //子结点包围盒计算，在 x,y,z 轴方向的最大最小值 objects[i].max.x=(objects[i].max.x&objects[i].points[x].x)?objects[i].points[x].x:objects[i].ma x.x objects[i].max.y=(objects[i].max.y&objects[i].points[x].y)?objects[i].points[x].y:objects[i].ma x.y; objects[i].max.z=(objects[i].max.z&objects[i].points[x].z)?objects[i].points[x].z:objects[i].ma x.z; objects[i].min.x=(objects[i].min.x&objects[i].points[x].x)?objects[i].points[x].x:objects[i].min. objects[i].min.y=(objects[i].min.y&objects[i].points[x].y)?objects[i].points[x].y:objects[i].min. objects[i].min.z=(objects[i].min.z&objects[i].points[x].z)?objects[i].points[x].z:objects[i].min. 场景碰撞检测程序实现的流程图如图 5-6，图 5-7。-45主程序流程说明：物体对象的初始化函数完成了物体对象信息的提取，其中包括 了.tga 图像格式 RGBA 图像数据的提取，重力加速度的初始值，各个物体模块的在空间 所在的位置，以及每个物体所分割的面数，边界盒的线数，是否有纹理等等，这些数据 的取得，均靠读取文件得到。OpenGL 场景的初始化工作包括了纹理的取名，纹理的绑 定，纹理参数的设置，设置光照参数，以及使用深度测试等等。注册键盘响应函数只给 出了函数的接口，接口的实现在程序中有描述。注册 OpenGL 绘图函数同样也只是给出 了函数的接口，这个接口函数是程序的主要部分，它主要完成了碰撞检测算法的实现、 如何检测到碰撞以及碰撞后物体的重画，场景的显示以及碰撞后各个物体的重画等等， 该函数由系统来调用，它相当于一个定时函数，每个隔一定时间，自动调用一次。-46进入GLUT 环境初始化定义窗口位置定义窗口大小初始化显示模式设置窗口标题注册键盘响应函数注册 OpenGL 绘图函数注册一函数接口使其一 直在后台运行物体对象的初始化OpenGL 场景的初始化调用 GLUT 消息循环函数返回图 5-6碰撞检测应用主程序流程图-47进入注册 OpenGL 绘 图函数碰撞计算， 取到每个物体 以及物体的每个三角面得到每个面的相对位置、 速度以及弹性力计算每个物体每个面的 OBB 包围盒，并在 x,y,z 的 投影得到每个 OBB 包围盒顶 点所对应在 x,y,z 轴上最 大值、最小值对每一个物体粗略以及 精确碰撞检测开始Y同一物体？N-48物体间发生碰 撞吗？ NYN 子结点包围 盒发生碰撞？Y 精确检测：采用子结点 OBB 包围盒检测N 各面的包围 盒碰撞吗？ Y计算面的平均速度, 得到每个面新的坐标现场重画，包括各个 面以及背景的绘制返回图 5-7 碰撞检测应用接口函数流程图-49说明：该碰撞检测算法采用的是 OBB 动态包围盒，它根据各个三角面片，在空间 的位置，来构造包围盒的大小。其中包围盒采用了一维空间排序方法，它将包围盒投影 到 x,y,z 坐标轴上，当两个包围盒在三个轴上都重叠的时候，才认为此包围盒有重叠， 本程序采用了包围盒层次树算法来检测物体的碰撞，顶层包围盒以单个物体为单位，只 有物体与物体发生碰撞，才进一步考虑物体内每个三角面片子结点包围盒的碰撞情况， 用此可以粗略进行碰撞的检测。要进行精确检测，必须检测物体的每个三角面片是否发 生了包围盒重叠的情况，如果有，说明发生了碰撞；反之，没有发生碰撞。如果发生了 碰撞，必须伴有碰撞响应，必须考虑物体的速度、摩擦系数、地心引力。不论是否检测 到碰撞， 都要计算每个物体的速度， 摩擦情况的分析等等， 以此来进行整个场景的重画， 包括了各个物体各个面的重画，地面场景的重画。因为整个碰撞检测函数的调用由系统 自动完成，为了进一步增加检测的精度，可以采用外层 for 循环来控制扫描的次数，这 样做的代价是牺牲了 CPU 的资源。好处是可以使实时性进一步的增强。对于实时性能 要求较高的场合，是必须的。5.3.4 用户交互为了使用者和场景达到互动性，本实例通过键盘来实现用户交互。按 1 和 3 键可以 向左和向右旋转场景，从不同角度观看碰撞检测的全过程；按下 5、8、4、6 键可以移 动桌面上的立方体盒子改变碰撞发生的位置。按 r 键可以使场景复位。t 和 d 键分别是 纹理显示和线框显示的开关，按下 ESC 键退出程序。 以上简要介绍了整个场景的实现步骤，在 VC6.0 环境下编程，经多次调试成功，最 终的实现。 碰撞检测实现场景如下图 5-8、图 5-9 所示-50图 5-8碰撞检测初始场景图 5-9碰撞后的场景-515.4 本程序的优缺点 程序的优缺点本程序采用了 OBB 包围盒层次树算法来实现三维物体的空间碰撞检测。 所做的工作如下：1）物体的建模：对三维物体的空间表述，与反映物体的逼真度密切联系在一起的。物 体的逼真度越高，物体的空间表示就越复杂，则物体的剖分越细。对于程序本身所造成 的影响具体表现在：CPU 资源消耗增大，对硬件的要求增高，实时检测性能越差，不能 正确的反映空间物体碰撞的真实效果，产生失真。所以，逼真度与算法的复杂度是矛盾 的，只能在它们中间找个平衡点以求得两方面的折中。本程序在兼顾两者的基础上，对 物体进行了不同个数的三角面片划分，在满足实时性的同时，最大限度的满足了人眼对 视觉的需求。其中对于三角面片的划分，每个三角面片顶点在空间的分布信息存在 mod 文件中，靠读这些文件来进行物体的初始化。 2）实时性选择：OpenGL 自动调用碰撞检测函数，它每隔一段时间片，来执行函数。如 果不能满足碰撞检测的精度，可以增加循环步长来提高碰撞检测的精度。 ，在程序中通 过 for(step=0;step&count_step++)循环函数实现比较精确的碰撞检测， 。 3）碰撞检测算法的实现，算法采用了 OBB 包围盒层次树来实现碰撞的检测。具体的来 说，即采用 OBB 底层包围盒算法进行粗略的碰撞检测，用来检测是不是每个物体之间 发生了碰撞，如果物体间有碰撞发生，在采用 OBB 子结点包围盒进行精确的碰撞检测, 即对物体中的每个最小单元三角面片进行检测，如果发生了碰撞，就认为两个物体发生 了碰撞，如果三角面片取的足够多，就可以做到精确的检测。 4）碰撞的响应，为了真实的反映客观世界，程序中对碰撞后