（计算机应用技术专业论文）虚拟校园的碰撞检测研究.pdf

硕士学位论文 m a s t e r st h e s i s 摘要 虚拟现实技术近年来在计算机仿真研究领域十分活跃。为保证虚拟现实的真 实性，参与者不仅要能从视觉上如实地看到虚拟现实中的虚拟对象以及它们的表 现，而且要能身临其境地与其发生各种交互。在虚拟校园系统漫游过程中，虚拟 场景漫游的动态物体与静态物体之间或者动态物体与动态物体之间的交互基础 就是碰撞检测。快速高效的碰撞检测对于增强虚拟场景的沉浸感和真实感至关重 要。 本文以虚拟华中师范大学校园系统为实例，开发了基于沁a 平台的部分 可交互虚拟三维浏览环境，在虚拟校园的漫游过程中对碰撞检测进行了研究和 探讨。首先介绍了计算机图形学中几种主流的模型，及其相关的碰撞检测算法， 层次包围盒是目前应用最广泛的一类碰撞检测算法，常见的包围盒有包围球 ( s p h e r c ) 、沿坐标轴的轴向包围盒( a a b b ) 、方向包围盒( o b b ) 、离散方向多 面体( k - d o p ) ，本文分别对它们进行了讨论和比较；然后对粒子系统及其相关 的碰撞检测进行了分析，以虚拟华中师范大学图书馆前的喷泉为例，实现了一 定的喷泉飞溅效果。最后，漫游系统采用了基于几何建模的方法实现了部分华 中师范大学校园的漫游，针对本漫游系统的具体特点，采用了手动漫游和自动 漫游相结合的方法。 基于! g a 平台，对华中师范大学虚拟校园系统进行了开发和研究，在虚 拟校园的漫游过程中，实现了与地形和建筑物的碰撞检测，使虚拟场景具有一 定的沉浸感和真实感。 关键词：虚拟校园，粒子系统，碰撞检测，漫游 i i ir e c e n ty e a r s ，、r i n u a lr e a l i t yt c c h 肿l o g yi sw i d e l yu s e di nt h ca r c a0 fc o m p u t e r e m u l a t i o ns t u d y 抽g i te n a b l c s 璐c r st ov i e w 卸de x p e r i c ct h ev i r t u a le v 沛枷e n t 置r e dy d u r i n gt l l ep r o c e s so fv i n l l a lc a i i l p u s 砌k 啪u g l l ，c 0 1 l j s i 咖d e t e c t i o ni st h e v i t a li i i t c r a c t i o nb a s cb c 柳nd y a m i c0 _ b j e c t 锄ds t a t i c0 _ b j e c t 叫砌o n g 也ed y i i a m i c o b j 鳅s m s of a s ta i l dh j 曲c 丘i c i e n tc o m s i d e t 硎o np l a y s 粗i m p o n a 咀tm l ci l i s t r c n g m e n i l l g i l l 珊e r s i o a n dr e a l i t ys 髓o fv i n i l a ls c e n e b 鹋c d0 nm ec a | p u so fh u a z h 蛐gn 帆a lu n j v e r s 姆醛av i n l l a ls p a c e ， d c v c l 叩v i n u a lt h r e c _ d i m e n s i o n a lb r a w s cc n v i r o 啪c n tb 鹤e d0 n g ap l a t f o m 1 1 l ec o l l i s i d e t e c t i o d l l r i n gv i n u a lw a l l 【t h m u g hp r i ) a 瑚i sd i s c i l 辅e dj nt l l i sp a p e l 碰m r c h i c a lb a u n d i n gi sam o s tw i d e l y 吣c da l g 耐t h mo fc o m s i 油d c t e c t i o n t 1 l c 锄m b o u n d i n gb o xc o m 呻s c so fs p h c 他，a a b b ( a x i s a l i 伊c db o u n d i l l g b o x e s ) ，o b b ( o t i e n t c db 0 岫d i n gb o x ) k d o pp i s c r e t c 伽c n t a t i o np 0 1 y t o p c s ) 1 1 l ea l g o r j t h m so ft h o s eb 咖n d j n gb o x a b o v ea r ca l 蛐s e d 如t h i sp a p e r 砌【i i i g t h e f 0 眦t a i n i n 丘蛐to f l i b 呻o f h u a z h 咖g 珊a l u 血i i y 站c x 锄p l c ， i t 柚a l y s e sp a n i c ks y s t e l n 锄dr e l a t c dc o l l i s i o nd e t e c t i i nt l l i sp a p e r ，a l l d i m p l e m e n tr e a l - t i m es p l a s he 纸d s oc o 蛹d c r j n gc o u i s i 咖d c t e c l i m c t h o d 缸d s 哪cs p e d a lr e q u i 瑚n e n t s ，t h cb o u n d i l l gb o xa l g o r i t l l n lo fc o n i s i o nd e 把c t j o n d e s 州b e di nt h i sp a p 既i sc h o s c nt o 印p l yt ot l l cv i n u a ic a l l l p u sw “k t i i r o u g h d e v e l o p i n gv i n u a lc a r 叩u ss y s t e mo f 壬| h a 烈1 0 n gn o 皿a lu n i v c r s i t yb a s e do n 抡ap l a t f o r i n ，也ec o l l i s i o nd e t c c t i o n b 幽咒e nc u r r e n tt e f r a i n 趾de x i s t 崦b u i l d i n g i sw e l i a c h i c v e dd u r i n gt h ew 电o l cv i n i l a lw a l k t h r o u 曲p r o c e s s a n di 1w c l l s t r e n g t l l e n si m m e r s i o na n dr e a l i t ys e n s eo fv i n u a ls c e n e k e y w o r d s ：r t u a lc a m p u s ，p a n i c l es y s t c m ，c o l l i s i o nd e t e c t i o n ， v i r t u a lw a l k t h r o u 曲 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名：何窄艳 日期：扣g 年6 月1 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 作者签名：f 矸木j 节 日期：抄6 年g 月 日 导师签名： 日期：励伊月，日 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程”，同意将本人的 学位论文提交“c a l i s 高校学位论文全文数据库”中全文发布，并可按“章程”中的 规定享受相关权益。回壶论塞埕交蜃溢盾；旦圭生；旦= 生；旦三生筮查。 作者签名：开术主萼 日期：“年阳 日 导师 日期 日 1 1 虚拟校园 第l 章概述 数字化、信息化是当今国内外高科技发展的潮流和趋势。随着对地观测、互 联网、虚拟现实等技术的发展以及国家信息技术基础设施的建设，数字地球、数 字城市和数字大学等概念逐渐被一些学者提出并付诸实施。大学作为高新科学技 术研究和开发、利用的前沿阵地，理当成为数字化、信息化研究、开发、利用的 重要承担者，进行实施建设数字化校园工程。作为数字城市建设的一个层面，数字 校园的建设也必将推动数字城市的建设，为整个城市的信息数字化打下良好的根 基。 虚拟校园作为数字化校园工程的一个重要组成部分，也是学校信息化建设的 重要内容，它为校园规划、管理提供了最直观的表现形式虚拟校园系统目前并 无公认的定义，一般认为，它是在计算机环境中，虚拟再现真实校园的景观，用 户可以进入虚拟的校园中进行有一定自由度的游览，进行一定的人机交互是虚 拟现实技术在校园数字化进程中的具体应用。采用三维成像、虚拟现实技术的虚 拟校园漫游系统，则是将学校风光和学校地图有机结合起来，既可以为学校树立 良好的形象，提高校园的知名度，宣传校园文化，让来访者足不出户就可浏览校 园风光和有关介绍信息，体验身临其境的感受；还可以作为校园规划的辅助工具， 提高校园管理的现代化水平。 本文对虚拟华中师范大学漫游系统的碰撞检测和粒子系统的碰撞检测进行 了一定的研究和探讨，为以后该系统能更好更完善的研究发展作了前期铺垫， 具有一定的实践意义。 1 2 国内外研究现状 ( 1 ) 国外的研究现状 自从1 9 9 3 年美国政府制定国家信息基础设施( a t i o n a li n f o 咖a t i o n i n 劬s t m c i u r e 简称n u ) 的行动纲领以来，大大推动i n t e m e t 在美国尤其是大学校 园的应用与发展。近年来，i n t e m e t 逐渐改变着美国大学校园的传统工作、学习、 管理和生活方式，成为大学教师、研究生、本科生和行政管理人员在教学、科 研、学习、管理和日常生活中必不可少的工具，并开始成为衡量一所大学教学、 科研与管理水平高低的重要标志之一。目前，美国大学校园的信息化建设己经 涉及图书馆网络、学校管理工作、教学活动、科研活动、学生日常生活的各个 方面，并且已经取得举世瞩目的成绩。美国大学“虚拟校园”的大门已经向世界 敞开。 1 9 9 9 年1 0 月，瑞士联邦两院正式通过了瑞士大学2 0 0 0 2 0 0 3 年发展计划。 在2 0 0 0 2 0 0 3 年期间，瑞士联邦政府以特别财政补贴方式为州立大学拨款3 0 0 0 万元瑞郎，以鼓励在高等教育领域进行信息化建设，建立“瑞士虚拟校园”。瑞 士的两所联邦高工和7 所高等职业学院也将参加实施“瑞士虚拟校园计划”。瑞 士大学联席会议委托弗里堡大学的新技术与教学中心建立了国家高等教育和新 信息技术网n w n 】| re d u t e c h c h ) 。 日本电信与京都大学、s t 蛐f o r d 大学合作致力开发网上虚拟京都，发布城 市信息，为社会提供服务。德国的r t o c l c s t i l t t g a n 大学建立了模拟系统，对 一些城市的基础设施提供相关的查询、分析和显示功能。 ( 2 ) 国内的研究现状 j 匕京大学正在建设的数字校园工程一“数字北大”，利用北大青鸟公司的g i s 软件- 一g ou n i o n 作为w c bg i s 服务器，并提供三个客户端插件，实现了北大 校园及周边环境的地图显示，基本信息浏览、查询及路径分析等功能。用户将 通过浏览器可以方便地找到北大周边的大专院校、湖泊、旅游区及其它重要地 物，并能获取这些对象的简要信息；可以快速地查到北大周边的重要路段和通往 某地的最佳路径等交通信息：可以浏览校园的全景和局部，还可以根据校园的一 个建筑查询到所有坐落在该建筑中的院系或行政机构，链接到各个院系的主页。 “数字北大”从g i s 角度规划了数字校园工程。成都理工大学也提出基于g i s 的 数字化校园工程“数字成都理工大学”。其中规划的主要内容包括收集、提 取、更新成都理工大学基础地理信息数据库( 4 d 产品) ，实现成都理工大学校区 的三维可视化漫游、检索和动态管理。建立和发布g i s 网站，建成成都理工大 学校园g i s 、校园m i s 、校园以综合服务体系。 港理工大学、香港中文大学研究的类似系统实现了虚拟校园的部分功能， 2 如香港理工大学的校园信息系统是一个较为成功的集虚拟现实技术、因特网和 电子地图为一体的虚拟校园系统：人们可以浏览虚拟校园环境，利用虚拟图书馆 查找和阅读期刊及书籍，通过访问虚拟实验室来使用计算机设备，通过虚拟教 室进行网上学习，而这一切都能让用户有身临其境感。 国内其它许多大学也都正在努力进行自己的虚拟校园建设。上海市科委代 表和芬兰拉赫蒂墟c l 代表经过交流和协商，特提出建议共同创建“中国 芬兰虚拟校园t c l es c h o o l ”，尝试在中国上海与芬兰拉赫蒂之间建立一个网上虚 拟校园，给两国的学生创造一个网上交流、沟通的场所。网上提供了用f 1 a s h 和v r m l 程序设计的虚拟科技创新博物馆、虚拟教学环境、虚拟图书馆等供学 生浏览。 1 3 论文的主要研究内容 本文以虚拟华中师范大学校园系统为实例，开发了基于g a 平台的部分 可交互虚拟三维浏览环境，在虚拟校园的漫游过程中对其碰撞检测进行了进一 步的研究和探讨主要内容如下。 碰撞检测的主要算法：碰撞检测问题是一个非常复杂的问题，涉及的领域 和技术都非常广，碰撞检测算法依赖于模型的表示等。首先介绍了计算机图形 学中几种主流的模型，及其相关的碰撞检测算法# 层次包围盒是目前应用最广 泛的一类碰撞检测算法，常见的包围盒有包围球( s p h e r e ) 、沿坐标轴的轴向包围 盒b ) 、方向包围盒( o b b ) 、离散方向多面体( k _ d o p ) 等，分别对其进行了 讨论，并对它们的优缺点进行了比较。 粒子系统与碰撞检测；对水流运动的粒子系统及其相关的碰撞检测进行了 分析。以虚拟华中师范大学图书馆前的喷泉为例，提出了利用o p e n g l 编程和 c r e a t o r 的动画技术相结合的方法来绘制喷泉粒子系统，并得到了较好的视觉 效果。 虚拟校园的漫游系统与碰撞检测及其实现：本文的华中师范大学校园漫游 系统采用了基于几何建模的方法。当整个模型完成后，就可以导入到v e g a 中进 行实时漫游的应用开发，针对本漫游系统的具体特点，采用了手动漫游和自动 漫游相结合的方法。为了增强虚拟场景的沉浸感和真实感，本文实现了与地形 和建筑物的碰撞检测。 3 第2 章系统分析及虚拟校园体系结构 2 1 碰撞检测的需求分析 虚拟现实技术的主要目标之一是允许用户以尽可能自然的方式与虚拟世界 直接交互。用户希望虚拟现实系统中的虚拟物体给人的感觉是真实的存在。为保 证虚拟现实的真实性，参与者不仅要能从视觉上如实地看到虚拟现实中的虚拟对 象以及它们的表现，而且要能身临其境地与其发生各种交互。碰撞检测是虚拟现 实中动态物体与静态物体之间或动态物体与动态物体之间的交互基础。若要实现 自然、精确的人机交互，就必须解决碰撞等问题。 在虚拟校园系统漫游过程中，虚拟场景漫游的动态物体与静态物体之间或者 动态物体与动态物体之间的交互基础就是碰撞检测。虚拟场景的三维建模是创建 v r 系统的基础，其中碰撞检测是构造虚拟漫游系统不可缺少的一个重要部分： 其一要根据地面、天空边界对摄像机高度进行检测，避免在交互式漫游过程中发 生钻入地下或穿出大气层的现象；其二是要根据建筑物模型轮廓进行检测，防止 穿墙而过的现象。此时为保持环境的真实性，需要及时检测到这些碰撞，并计算相 应的碰撞反映，更新绘制结果。快速高效的碰撞检测对于增强虚拟场景的沉浸感 和真实感至关重要。 2 2 虚拟校园系统的硬软件结构 虚拟三维校园的仿真对硬件系统有较高的要求，本系统采用的硬件环境 为：大显示器、超大硬盘、大内存、多c p u 、高速缓存、高效图形加速卡、 立体眼镜、三维鼠标和数码相机。 软件环境如下： ( 1 ) 图像处理软件p h o t o s h o p6 o 数据预处理软件，拍摄的实景照片或实体中某些局部表面经过p h o t o s h o p 工 具编辑处理后作为纹理赋给实体表面，使模型更具有逼真感。注意要把纹理照片 大小调整为2 的幂次，这样在v e g a 中才能显示。 4 硕士荦住论文 m a s t e r st h e s i s ( 2 ) 三维建模软件m u l t i g m u n i g e n 是m l l l t i g e n 公司出品的三维仿真建模软件，它提供创建和编辑数 据库文件可视化环境，其对3 d 场景的描述几乎己成为交互式3 d 的工业标准。 m u l t i g e 定义了一种数据格式，称为o p e n h i 9 1 l t 。数据库采用树状层次结 构进行组织，它支持许多场景仿真中的概念：如光源、纹理映射、层次细节 ( l 胛e l o f d e t a i l ) ，3 d 声音、自由度、动画序列、模型实例化等。 ( 3 ) l 狎_ ) ( 图形用户界面f 5 l l y n x 是用来设定和预览v c g a 应用程序的图形式用户界面，它可以在不涉 及源代码的前提下改变应用程序的性能。此外，l - 砌x 的开放性使用户可根据自 己的特殊需求赋予其新的功能。 ( 4 ) 大型实时仿真软件v e d 4 l v e g a 美国m u m g c n - p a r a d i 鲁m 公司用于虚拟现实、实时视景仿真、声音仿 真以及其它可视化领域的世界领先级应用软件工具。它支持快速复杂的视觉仿 真程序，能为用户提供一种处理复杂仿真事件的便捷手段。 v c g a 是在s g ip e r 吣皿e r 软件的基础上发展起来的，为p c r f o 蛐e 增加了许 多重要特性。它将易用的工具和高级仿真功能巧妙地结合起来，使用户以简单 的操作迅速地创建、编辑和运行复杂的仿真程序。v e g a 可以迅速创建各种实时 交互的3 d 环境，以满足不同行业的需求。 5 患怒。 2 3 虚拟校园体系结构 图2 1 系统总体框架结构图 根据分析，虚拟校园的总体框架结构图如上图所示。 虚拟校园系统的开发可以简单地归为以下几个阶段：首先进行数据的采集参 照设计图纸、总规划平面图，拍摄虚拟校园场景、建筑结构照片等；然后借助于 3 d sm a 】【和c 陀a t o r 建模工具来构建立体式校园模型；再将建好的模型导入l v l l x ，进 行漫游的初始化参数设置，将设置好的场景生成a d 破件；最后，读入设置好的a d f 文件，进行v e g a 驱动程序的设计。 硕士学住论文 m a s t b r st h e s i s 第3 章碰撞检测算法 3 1 一般的模型表示和碰撞检测算法 3 1 1 碰撞检测的概念 简单地讲，碰撞检测( c o m s i d c t c c n ) 就是检测虚拟场景中不同对象之间 是否发生了碰撞。从几何上讲，碰撞检测表现为两个多面体的求交问题；按对象 所处的空间可分为二维平面碰撞检测和三维空间碰撞检测。平面碰撞检测相对简 单一些，已经有较为成熟的检测算法，而三维空间碰撞检测则要复杂得多。在虚拟 现实系统中，主要是如何解决碰撞检测的实时性和精确性的矛盾。准确的碰撞检 测对于增强虚拟场景的真实感和沉浸感起着至关重要的作用。而碰撞问题包括碰 撞检测和碰撞响应两部分。碰撞检测的目标是发现碰撞并报告；碰撞响应是在碰 撞发生后，根据碰撞点和其它参数促使发生碰撞的对象做出正确的动作，以反应 真实的动态效果。碰撞响应涉及到力学反馈、运动物理学等领域的知识。 下面对虚拟环境中的碰撞检测问题简化描述如下：碰撞检测系统的输入模 型为一个静态的环境对象和一个动态的活动对象的几何模型，它们均为基本几 何元素的集合。其中环境对象可以包括刚体对象，也可以包括软体对象，它们 的位置和方向不会发生变化，但软体对象可能在外力的作用下发生变形。活动 对象可以在虚拟环境中自由运动，方向和大小完全取决于仿真过程或者用户控 制的输入设备，无法用关于时间的运动方程来表示，只能得到某一时间采样点 相对于前一时间采样点或一固定参照物的运动信息( 旋转角度和平移量) 。其任 务是确定在某一时刻两个几何模型是否发生干涉，即它们的交集是否不为空， 若不为空，则判断发生了碰撞，确定碰撞点或参与碰撞的基本几何元素。 3 1 2 一般的模型表示1 1 】 碰撞检测问题是一个非常复杂的问题，涉及的领域和技术都非常广，碰撞 检测算法的涉及依赖于模型的表示法、需要查询的类型和虚拟环境等。 几何模型的表示法从目前的研究来看，可分为面模型和体模型两类。面模 型用面片来表现对象的表面，其基本几何元素多为三角形；体模型用体素来描述 7 对象的结构，其基本几何元素多为四面体。面模型相对简单一些，而且绘制技 术成熟，处理方便，但难以进行整体形式上的体操作( 如拉伸、压缩等) ，多用 于刚体对象的几何建模。体模型拥有对象的内部信息，可以很好地表达模型在 外力作用下的体特征( 变形、分裂等) ，但计算的时间和空间复杂度也相应增加， 一般用于软体对象的几何建模。 下面就一般的模型表示先介绍如下。 ( 1 ) 多边形模型 在计算机图形的建模中，多边形模型是最常用的模型，它的表示方法很简 单。最一般的多边形模型的类是“多边形群”，它是多边形的集合，但是不包括 这些多边形之间的连接信息，并且没有可用的拓扑结构信息。如果多边形形成 一个封闭的多面体，那么该模型有明确的内部和外部定义，即它是严格意义上 的多面体，一些几何学算法就依赖于这种结构。如果这个封闭的多面体是凸的， 那么该附加的结构特点也能在碰撞检测算法中得到利用。 ( 2 ) c s g 模型 c s g ( c 加s t m c t i v es o 瑚g 姗e n mc s g ) 模型形成的对角，利用简单的几何 体，如长方体、球体、柱体、圆锥和圆环面，通过将它们与固定的理论操作( 如 接台、交集和调整差别等_ ) 丰日结合，形成复杂的对象模型。c s g 模型表示法的作 用在于，它使能建造形状的直觉设计过程用剪切( 交集和调整差别) 和连接( 结合) 简单的几何形体来形成更复杂的对象模型。这种模型表示法使碰撞检测更加容 易，但使用c s g 模型的困难是某些操作，例如边缘圆滑和平面连接难以用对 c s g 模型的操作进行描述此外，对描述和碰撞检测有用的精确的边界或平面 表示法，也很难从c s g 模型表示法的计算中得出。 ( 3 ) 隐式面 隐式面是由隐式函数定义的一系列的面。用从空间到实际数字的映射定义， ，：r 3 一r ，并且隐式面位于f 伍，y ，z ) = o 内。这样函数清楚地定义了哪些点在 模型的内部，f ，y ，z ) o 。 如果该函数是在x ，y 和z 上的多项式，那么成为代数的，它包含代数表面、 更高次的函数和回旋面，隐式面又常常作为初始化在c s g 系统中使用。 代数表面的一种特殊情况是二次曲面，它是在x ，y 和z 上的二次多项式。 它能表示统一结构内部的平面，圆锥面、球面和柱面，这些都广泛应用于各种 8 应用，并且己经开发出许多专门的算法进行二次曲面问的交集计算。 ( 4 ) 参数面 参数面是从平面到空间的些子集映射：，：见一r ，。不同于隐式面，参数 面不是通常的封闭的物体，因此它不表示完整的模型，而是面边界的描述。 与隐式面相比较，参数面更容易多边形化和实现，被称为非均匀有理b 样 条曲线 o n u n i f o 珊r a t i o n a lb s p l i n e ，n u r b s ) 的特殊类在计算机辅助设计中 很流行。n u r b s 有一些很好的属性，使它们更容易操作。它们还可以用贝塞尔 曲线( b e z i e f ) 后缀表示。合理的参数面( 如n u r b s 和b 睨j c r ) 是一种代数表面的 适当子集。 3 1 3 一般表示的碰撞检测 碰撞检测算法中有不少是专门面向某种具体表示模型而设计的，包括面向 c s g 表示模型的碰撞检测算法、面向参数曲面的碰撞检测算法和面向体表示模 型的碰撞检测算法等。 ( 1 ) 面向c s g 表示模型的碰撞检测算法 c s g ( c 0 璐m l c t i v cs 0 l i dg e o n l e t 啪表示模型用一些基本体素如长方体、球、 柱体、锥体和圆环等，通过集合运算如并、交、差等操作来组合形成物体。c s g 表示的优点之是它使得物体形状的建构更直观，即可以通过剪切( 交、差) 和 粘贴( 并) 简单形状物体来形成更复杂的物体。 z c i l i e 一3 0 1 提出了一种面向c s g 表示模型的碰撞检测算法。他将算法分为三 个部分。第一部分求出c s g 树的每个节点的包围体用于快速确定可能的相交部 分；第二部分别对所有c s g 树表示的物体创建类似八叉树的层次结构，采用这 种结构找到同时包含两物体体素的子空间：在最后一部分，检测子空间中基本体 素之间的相交关系。 s u 等【3 l j 在算法预处理阶段首先将c s g 表示模型转化为边界表示模型 ( b r e p ) ，然后混合两种表示，把每个c s g 的基本体素与对应b r c p 的面片关联起 来。此外，还对c s g 树中的非叶子节点建构相应包围体，并在相交检测时采用 自适应的包围体选择策略以快速确定潜在相交区域，从而提高算法效率。该算 法结合了包围体技术的快速性和基于多边形表示相交检测的精确性来提高碰撞 检测算法效率。与s u 算法相类似的还有p o u t r a i n 等【3 2 1 提出的一种混合边界表示 9 和c s g 表示的碰撞检测算法。算法利用了包括c s g 在内的多种表示方法，将 包围体、层次细分和空间剖分等技术融合起来实现实时碰撞检测。 面向参数曲面的碰撞检测算法 1 1 】r n b u l l 等【3 3 】提出了一种面向n u b r s 表示凸体的碰撞检测算法，该算法 借助“支持映射”c s u p p o r tm a p p 抽g ) 来求出两凸体之间的距离。“支持映射”通过给 定的支持函数( s u p p o nf i i i l c t i o n ) 和方向，获取两个凸体之间的最小距离，同时返 回两物体距离最近的两个顶点，如图3 1 所示。利用这种思想1 、l m b u u 提高了 n u b r s 曲面表示物体间的碰撞检测速度。 图3 1 支持映射示例 ( 3 ) 面向体表示模型的碰撞检测算法 体表示模型用简单体索来描述物体对象的结构，其基本儿何构件一般为立 方体或四面体。与面模型不同，体模型一般用于软体对象的几何建模，它拥有 对象的内部信息，能表达模型在外力作用下的变化特征( 变形、分裂等) ，但其 计算时间和空间复杂度也相应增加。 因为体表示模型可以表示物体内部的相关数据，面向体表示模型的碰撞检 测算法通常用于虚拟手术。体表示的简单性也使其可用于对碰撞检测算法速度 要求极高的应用，如面向触觉反馈的碰撞检测计算。触觉反馈中由于人对触觉 的敏感度，系统对碰撞检测的计算要求非常高，通常要求刷新频率达1 0 0 0 h z 。 对于如此高的计算速度要求，除结合具体场景的特点来加速算法外，往往会考 l o 虑以牺牲精度为代价来提商碰撞检测的速度。 3 2 层次包围盒的碰撞检测算法 层次包围盒是利用体积略大而形状简单的包围盒把复杂的集合对象包裹起 来，进行碰撞检测首先进行包围盒之间的相交测试；如果包围盒相交，再进行 几何对象之间精确的碰撞检测。它是目前应用最为广泛的一种碰撞检测算法。 ( a ) 包围球 a a b b 包围盒( c ) o b b 包围盒 ( d ) 6 - d o p 包围 图3 2 包围体二维示意图 常见的包围盒有包围球( s p h e 碥) 、沿坐标轴的轴向包围盒( a a b b ) 、方向 包围盒( o b b ) 、离散方向多面体( k - d o p ) 等。如图3 。2 所示，下面分别进行讨 论，并对它们的优缺点进行比较。 ( 1 ) 沿坐标轴的轴向包围盒( a a j 3 b ) 轴对齐包围盒也称作矩形盒，通常简写为a a b b ( a x i sa l i 弘e db 0 u n d j n g b o x ) ，它是一个表面法向与基轴方向一致的长方体。图3 3 是包含一个带有符 号的三维a a b b 示意，可以用两个定点a m “和a 。“来表示，其中 口ys 口严，v f 而y ，z ) 。如图3 3 是一个带符号的三维a a b b 示意。 z a m m x 图3 3 一个具有定点a “和a “而且轴为标准基准的三维a a b b 包围盒 a a b b 层次包围盒树，是利用a a j 3 b 构建的层次结构二叉树。母b 的建 构比较简单，相互之间的求交也很快捷，但由于包围物体不够紧密，有时会增 加许多不必要的检测，反而影响算法效率。 一般的a 柚b 树由于包围较松散，会产生较多的节点，导致层次二又树的 节点过多的冗余，从而影响虬蛆b 树的碰撞检测效率。为此，b e r g e ni 州提出了 一种有效的改进算法。该算法采用分离轴定理( s c p 甜g i ca x i s1 m e o r 啪) 加快 a a b b 包围盒之间的相交检测，同时又利用a a b b 局部坐标轴不发生变化的特 性加速a 蛆b 树之间的碰撞检测。他的算法与g o t 眦h a l k 等【3 5 j 提出的采用o b b 树的碰撞检测算法相比，计算性能上相差不大。由于a a b b 树原本就具有建构 简单快速，内存开销少的特点，能较好地适应可变形物体实时更新层次树的需 要，因此b e r g e n 又把他的算法用于进行可变形物体之间的相交检测。 l s s o n 等p 6 】针对可变形物体的碰撞检测问题提出了一种有效建构、更新层 次包围盒树的方法。他通过多种启发式搜索策略构建结构良好的a a b b 层次树， 并在碰撞检测阶段结合了自顶向下和自底向上的两种层次树更新策略来保证层 次包围体树的快速更新，有效加快了变形物体之间碰撞检测的速度。 ( 2 ) 包围球法( s p h e r e ) 对象的包围球p 7 j p 8 】1 3 明( s p h e r e ) 被定义为包含该对象的最小的球体，包围球可 表示： r = f 阢_ ) ；力i 似+ 陟叫。+ 陪叫。 r ，则粒子继续运动；否则进行求交计算。( 如图4 5 所示) p ，z 1p n 图4 5 粒子与障碍物碰撞 m 图4 6 粒子碰撞反弹的几何关系 点m 的求解公式如下： f fi 尸( 1 一f ) + ，h + f f i m s l - r 设k ，n ，l 分别为船、历、面的单位向量( 如图4 6 ) 。因为 足。2 ( 上) 一工 则可求出膨点的位置、运动方向和速度。m 点的速度为： 一啡 a 是粒子碰撞后速度的衰减系数，咋是p 点到达m 点并与其发生碰撞之前的速 度。 3 粒子的消亡 粒子系统中，粒子的生存周期以帧为单位。在粒子的运动过程中，其生存 期不断地缩减，当其生存期减至零时，该粒子即消亡。显然，在水粒子系统中， 当粒子碰到水面或其a l p h a 值减小到零时粒子自动消亡。 4 2 4 粒子的绘制 一旦确定了某一帧所有粒子的位置，即开始绘制过程。 绘制粒子的方法有多种：( 1 ) 用3 d m a ) ( 绘制；( 2 ) 用o p e n g l 编程实现；( 3 ) 用v e g a 编 程实现，l 蛐( 中的很多特效如爆炸、烟、火焰等功能是用粒子系统实现的。 粒子具有一定的生命周期，且数量大( 一个复杂的爆炸场景至少需要几万个，一 个简单的喷泉场景也需要几千个) 使算法的计算量大，很费时，还不能满足实施绘制 的要求，而要在c r e a t o r 中绘制粒子系统还是有困难的。因此提出了基于粒子系统和 c r e a l o r 中动画技术相结合的方法：先利用由o p e n g l 开发的粒子系统软件绘制喷水的 喷泉；然后将其喷水效果图导入c r e a t o r 中，利用动画的技术，进行绘制，可以得到 较好的视觉效果( 如图4 7 所示) ，从而大大提高了模糊景物的绘制速度。 图4 7 喷泉图 项士学位论文 m a s t e r st h e s i s 第5 章实时漫游与碰撞检测 5 1 漫游系统的设计过程 5 1 1 虚拟校园漫游系统的设计 目前国内外研究的虚拟场景漫游在实现方法上可分为两种，主要按照虚拟 场景的构造方法来区分。一种是传统的基于几何建模的虚拟漫游技术，另一种 是新兴的基于实景图像的虚拟漫游技术。本文所实现的华中师范大学校园漫游 系统采用了基于几何建模的方法。 图5 1 系统实现流程与组成框图 系统实施大体可以简化为两大步骤，首先完成三维场景建模，然后对场景 进行实时漫游，在漫游的过程中需要进行一定的碰撞检铡。系统实现流程与组 成框图见图5 1 。 5 1 2实时仿真软件v cg a 【蛤”】 基于底层的三维图形库0 p 锄g l ，有许多高层的三维视景开发环境。当前 支持实时三维处理的软件很多，在这里重点介绍当前国内使用较多的三个软 件：s g l 公司的i r i sp e r f o 咖m u l t i g e n - p a r a d i g m 公司的v e g a ，c g 2 公司的 v i r e e 。 ( 1 ) 珏u sp c r f o n n e r 0 p 锄g l a _ p i 最初是使用在第一代的即时图形模式中的，即它提取组成图形 的基本元素三角形，然后按照程序员的指令对其上色。它能够快速而有效地生 成单个图形元素，或者生成一幅新的场景。但是，第一代的图形a p i 不能有效 的把本帧画面的图形信息传给另一帧画面。场景图形出现在s g i 第二代的3 d 图形a p i 中，它包括u s o p e n h v 蛆t o r 和瓜i sp c r f o 咖e 巧瓜i s p e r f o n n e r 是s g i 公司开发的一个可扩展的高性能实时三维视景开发软件包。它基于g l 为开发 实时图形应用程序提供了一组与标准c 或c + + 绑定的程序接口( a p ik 可运行 于所有s g i 图形计算机系统之上，并通过一个使用灵活的三维图形工具集提供 高性能渲染能力。i r i sp e 血皿髓软件包主库包括：仿真可视化应用开发库 ( 【j b p f ) ，可提供全面的视觉仿真能力，控制多进程数据库遍历和渲染；高性能渲 染库( u b p r ) ，可提供最佳的运行环境实现优化后的渲染，状态控制和其他面向 实时图形的基本功能。珉i sp c r f 0 】e r 还提供一组数据库载入器。 但是需要指出的是p e r f o 皿e r 是用编程来实现的，没有良好的用户可视化编 程界面。因此，p e r f o 瑚e r 开发交互仿真程序，对用户编程能力要求高，开发周 期也相应延长。同时，取i sp e 哟珊c f 最开始只能在s g i 工作站上运行，近年来 虽然出现了i j 肌x 版本的p e 由珊c r ，但并不十分完善，而且目前还没有基于 n t 的p e 疵哪n e r 版本出现，这些都限制了瓜i sp c r f o 肌e r 的推广。 ( 2 ) v e g a v c g a 是m u l t i g e n p a r a d i g m 公司最主要的工业软件环境，用于实时视觉模 拟、虚拟现实和普通视觉应用。m u l t i g e n - p a r a d i g m 还提供和v e g a 紧密结合的 特殊应用模块，这些模块使v c g a 很容易满足特殊模拟要求，例如，航海、红外 线、雷达、高级照明系统、动画人物、大面积地形数据库管理、o 也数据输入、 d i s 等等。 v e g a 具有良好的可视化编程环境，便于程序员和非程序员使用。它使用一 种点击式的图形环境l 扣x ，可以快速、容易、显著地改变应用性能、视频通道、 多c p u 分配、视点、观察者、特殊效果、系统配置、模型、数据库及其他，而 不用编写源代码。此外，l 扣x 的开放性使用户可以根据自己的特殊需求赋予其 新的功能。 v e g a 还包括完整的c 语言应和程序接口，为软件人员提供最大程度的软件 和灵活性。v c g a 还支持多种数据库输入，允许多种数据格式综合显示。v e g a 及相关模块支持u n 】d ( 和n t 平台。用v c g a 写的应用可以兼容跨平台使用。 v c g a 最大的优点是：它为非程序员实现一个视景仿真系统提供了捷径，同 时，它支持n t 平台，使高档微机的用户可以拥有自己所感兴趣的视景仿真系 统成为可能。 ( 3 ) r e e y r h c 是一个基于o p e n g l 面向对象的和便携平台的图形图像开发软件包 ( s d k ) 。s d k 包括大量的c + + 类和压缩抽象o p c n g l 数据库、数组类型及操作 方法。在商业和政府领域，b c 长期以来被用于开发高质量的可视化和仿真应 用，可把符合工业标准的3 d 图形模型引入慨程度并对其进行实时的控制， 从而产生生动的可视内容，可通过各种方式( 如显示器、头盔显示仪等) 观看。 v t i 的强大的视景生成功能可以和u sp e 咖咖盯相媲美，同时它也可以 用在普通的微机上，因此，对于开发高帧速率和实时响应的三维图像应用来说， v i r c c 是一个成本低廉的最佳选择其缺点是没有良好的可视化编程界面，对 于非专业程序员而言不易掌握。 通过对以上三种软件的技术比较，结合实验室现有条件，选用v c g a 作为三 维视景开发软件。 5 1 3 场景的实时漫游 当整个模型完成后，就可以导入到v e g a 中进行实时漫游的应用开发。v c g a 是一种用于实时仿真与虚拟现实应用的高性能软件环境和开发平台，由l y n x 图 形化用户接口和v c g a 库组成。利用v c g a 类函数，在l 弘x 中建立漫游所必需的 对象包括场景、窗口、通道、运动方式、观察者、碰撞方式等，定义对象的初始 化参数以及建立对象之间的相互联系。 作为高性能的t 开发平台，v e g a 提供了两种系统设计模式：一是使用v e g a 的l y n x 图形用户界面配置系统；二是运用v e g a 提供的a p i 函数( c 语言) 进行程序 开发。针对本漫游系统的具体特点，决定综合便种模式进行系统的开发基于v e 黔 的t 系统运行流程如图5 2 所示。 图s 2 基于v c g a 系统的运行流程 ( 1 ) 可视化编程方式 l y n ) ( 是定义和预览v c g a 应用的图形用户界面，用来定义和编辑a d f 文件，一 个a d f 文件包含v c g a 应用初始化及运行所需要的信息，大幅度减少了源代码的编 写 可视化编程方式的基本方法是：启动v c g a ，在l y n x 图形界面的左边的工具 箱中选择设置工具，在右边的窗口中进行相应的参数设置主要步骤如下： 第一步：选择o b j 耐( 对象 按钮，设定虚拟场景中要加入的地形、建筑物、 运动目标等三维模型文件。 第二步：选择s c c n e ( 场景) 按钮，设定虚拟场景中要显示的全部目标。 第三步：选择o b s c r v e r s ( 观察者) 按钮。设定在虚拟场景中进行观察的方式。 以下是几种不同的放置观察者的方式： 手动( m 曲u a l ) 允许用户指定观察者固定的位置和方向。如果不通过a p l 改变其位置，则观察者的位置和方向在整个应用程序中保持不变。 运动模型( m o t i o nm 0 d d ) 允许用户从运动模型事件表中选择一个运动 模型。 随动式系链( t c t h c r - f “1 0 w ) 使观察者跟随场景运动体的后面。 旋转式系链( t c t h c 卜s p i n ) 使观察者在场景运动体当前位置周围的一个圆 形轨迹上运动。 固定式系链( ，r c t h c r - f i x e d ) 允许用户通过一组固定的偏移量把观察者放 置到一个场景运动体身上。 路径导航器口a t i ln a l v i g a t o r ) 允许用户从路径导航器事件的类表选择一 个路径导航器。 第四步：选择m o t i o nm 0 d e l s ( 运动方式) 按钮，设定观察者在虚拟场景中的运 动方式，如：驱动、飞行等方式。 下面是一些运动类型： ( 1 ) 旋转：当移动鼠标向左时，模型在它的原点沿顺时针旋转；当移动鼠标向 右时，模型在它的原点沿逆时针旋转；当按鼠标中键时，可使物体或视点朝操作 者移动或背离。 ( 2 ) 驱动：通过控制它的最大速度、加速因子、减速因子，实现视点或运动 对象的运动。当输入设备为三键鼠标时，向右移动鼠标，视点或运动对象向右 转向；向左移动鼠标，视点或运动对象向左转向；当按鼠标右键，实现视点或运动 对象的加速动作；当按鼠标左键，实现视点或运动对象的减速动作：当按鼠标中 键，实现视点或运动对象的刹车动作： ( 3 ) 模拟无惯性的飞行运动，即无动力驱动的飞