（计算机软件与理论专业论文）vrgis城域仿真平台的场景组织与优化.pdf

v r gls 城域仿真平台的场景组织与优化 摘要 目前，面向城市区域仿真逐渐成为一个研究热点，随着计算机图形学和虚 拟现实技术的发展，人们对于虚拟仿真环境的实时性、沉浸感提出了越来越高的 要求，希望以更自然的方式来观察效果更逼真、范围更广的虚拟场景。从理论上 讲，城域景观场景的复杂性是无限的，而任何硬件单位时间内的处理能力总是有 限的。在城域景观仿真系统中，需要处理的数据量庞大、模型数目多，并且可见 性判定和碰撞检测时的效率较低。因此，场景模型不同的组织和管理方式直接影 响到系统的性能。 本文参与设计并实现了一个面向城市区域级的大场景、多精度等级的 v r g i s ( v m u a lr e a l i t yg e o g r a p h i c a li n f o r m a t i o ns y s t e m ) 虚拟现实仿真平台。 v r g i s 是一个基于o p e n g l 开发的三维图形引擎，支持由多数据源的海量数据 构建的三维场景的稳定快速导航，采用组件式开发技术使v r 与g i s 两大功能模 块实现无缝集成，具备多种自然现象的模拟仿真功能，具有真实感强、交互性强 和仿真效果佳等优点。v r g i s 平台已通过国家软件评测中心的质量认证。 本文在研究现有各种虚拟场景组织及优化方式的基础上，引入了层次包围盒 ( h b b h i e r a r c h i c a lb o u n d i n gb o x ) 的方法来组织和管理v r g i s 平台中的场景 模型，使用i - i b b 结构来对场景结构进行优化组织，并基于此结构实现了v r g i s 仿真平台中可见性剔除、l o d 、碰撞检测等功能。本文为v r g i s 平台设计的最 核心部分，其中，使用人工智能的视锥体裁剪方式以及基于h b b 结构的城域景 观大块场景l o d 的实现为本文的主要创新点。 关键字：城域仿真平台，场景组织，层次包围盒，可见性剔除，层次细节， 碰撞检测 t h e m a n a g e m e n ta n do r g a n i z a t i o no f v i r t u a ls c e n e s 加唿g i sp l a t f o r m a b s t r a c t 1 1 硷c i t y r e g i o ns c a l es i m u l a t i o ni sb e c o m i n gah o tt o p i ci nr e c e n ty e a r s w i t ht h e d e v e l o p m e n to fc o m p u t e rg r a p h i c sa n dv i r t u a lr e a l i t yt e c h n o l o g y , m o r ea n dm o r e e f f o r t sa l em a d ef o rt h ea c h i e v e m e n to far e a l - t i m e ，i m m e r s e dv i r t u a ls i m u l a t i o n e n v i r o n m e n t i ti sh o p e dt h a tt h ev i r t u a ls c e n ew i t hb e t t e rr e a l i t ya n dw i d e rr a n g ec a l l b eo b s e r v e di nam o r en a t u r a lw a y a c t u a l l y , t h ec o m p l e x i t yo ft h ec i t y r e g i o ns c a l e s c e n e si si n f m i t ew h i l et h eh a n d l i n gc a p a c i t yo fa n yh a r d w a r ei nu n i tt i m ei sl i m i t e d i nt h ec i t y r e g i o ns c a l es i m u l a t i o ns y s t e m , l o t so fd a t aa n dv i r t u a lm o d e l sn e e dt ob e p r o c e s s e da n dt h ev i s i b l ec u l l i n ga n dc o l l i s i o nd e t e c t i o na r el e s se f f i c i e n t t h e r e f o r e ， d i f f e r e n to r g a n i z i n ga n dm a n a g i n ga p p r o a c h e so ft h ev i r t u a ls c e n em o d e l sd i r e c t l y a f f e c tt h ep e r f o r m a n c eo ft h es y s t e m t h i st h e s i sp a r t i c i p a t e di nt h ed e s i g na n da c h i e v e m e n to fac i t y r e g i o ns i m u l a t i o n p l a t f o r mv r g i s ( v m u a lr e a l i t yg e o g r a p h i c a li n f o r m a t i o ns y s t e m ) v r g i sp l a t f o r m i sa3 dg r a p he n g i n eb a s e do no p e n g l ，w h i c hs u p p o r t ss t a b l ea n dr e a lt i m e n a v i g a t i o no f3 ds c e n e sc o n s t r u c t e db yh u g ev o l u m ed a t e c o mt e c h n o l o g yi s a p p l i e df o rt h es e a m l e s si n t e g r a t i o no fv ra n dg i s v r g i sp l a t f o r ma l s op r o v i d e s v a r i o u sn a t u r a lp h e n o m e n o ns i m u l a t i o n s ，w i t ht h ea d v a n t a g es u c ha sr e a l i t ya n d i n t e r a c t i o n v r g i sh a sp a s s e dt h eq 砌i t ye v a l u a t i o no fn a t i o n a ls o t t w a r et e s t i n g c e n t e r b a s e do nt h er e s e a r c ho ft h ev i r t u a ls c e n eo r g a n i z a t i o n sa n da l g o r i t h m si n e x i s t e n c e , t h i st h e s i si n t r o d u c e sah b b ( h i e r a r c h i c a lb o u n d i n gb o x ) a p p r o a c ht o o r g a n i z ea n dm a n a g em o d e ls c e n e s ，a n du s e st h eh b b s t r u c t u r et oo p t i m i z et h es c 圮n e s t r u c t u r e i na d d i t i o n , b a s e do nt h eh b b $ t a u c t u r e ，v i s i b i l i t yc u l l i n g ，l o da n d c o l l i s i o nd e t e c t i o ni nv r g i ss i m u l a t i o np l a t f o r mi sa c h i e v e d t h i st h e s i si st h eg o r e o fv i r t u a ls c e n e so r g a n i z a t i o na n dm a n a g e m e n ti nv r g i s t h e r ea r et w op r i m a r y i n n o v a t i o n s ，w h i c ha r et h ef r u s t u mc u l l i n gi na na r t i f i c i a li n t e l l i g e n c ea p p r o a c ha n d l o da c h i e v e m e n ti nc i t y r e g i o ns c e n e sb a s e do nh b bs t r u c t u r e k e y w o r d s ：v r g i s ，s c e n eo r g a n i z a t i o n , h b b ，v i s i b i l i t yc u l l i n g ，l e d ， c o l l i s i o nd e t e c t i o n 独创声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含未获得( 洼! 翅遗直基他 置墨挂剔直明的：奎拦亘窒2 或其他教育机构的学位或证书使用过的材料。与我一同 工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位做作糍：弘辩吼2 呐8 年r 月拥 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，有权保留并向国 家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权学校 可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。同时授权中国科学技术信息研究所将本学位论 文收录到中国学位论文全文数据库，并通过网络向社会公众提供信息服务。( 保密 的学位论文在解密后适用本授权书) 学位做作撇：橡 辩日期：撕r 月详日 导师签字： 签字日期：) o 嚼年s 月冰日 v r g l s 城域仿真平台的场景组织与优化 第一章绪论 1 1 虚拟现实技术与虚拟仿真平台 虚拟现实是一种可以创建和体验虚拟世界的计算机系统，它利用计算机技术 生成一个逼真的，具有视觉、听觉、触觉等多种感知的虚拟环境。同时，虚拟现 实技术也是一种先进的数字化人机接口技术：用户通过使用各种交互设备，与虚 拟环境中的实体进行相互作用，使之产生身临其境的感觉，实现交互式视景仿真 与信息交流。 虚拟现实技术自诞生以来，即在数字仿真、城市规划、地理信息系统、石油 工业、计算机辅助制图、军事、航空航天、医药生物、游戏娱乐业等领域中发挥 着巨大的经济、军事和社会效益。它与计算机网络、多媒体并称为2 l 世纪最具 应用前景的三大技术。 虚拟仿真平台是虚拟现实在计算机上的表现形式。我们利用虚拟仿真平台的 实物虚化、虚物实化和高性能计算处理等技术来实现对现实的虚拟。这其中，实 物虚化是现实世界空间向多维信息化空间的一种映射，主要包括基本模型构建、 空间跟踪、声音定位、视觉跟踪和视点感应等关键技术，这些技术使真实感虚拟 世界的生成、虚拟环境对用户操作的检测和操作数据的获取成为可能。虚物实化 是指确保用户从虚拟环境中获取同真实环境中一样或相似的视觉、听觉和触觉等 感官认知的关键技术。高性能计算处理技术主要包括数据转换和数据预处理技 术，实时、逼真图形图像生成与显示技术，多种声音合成与声音空间化技术，多 维信息数据融合、数据压缩以及数据库的技术。 1 2v r g i s 仿真平台简介 本课题的总体目标是研究开发出一套面向城市区域级大场景、多精度等级 虚拟现实应用的软件开发平台。将强大的g i s 功能、海量数据库引擎、自动路 径规划、海浪特效等无缝融入其中。 v r g i s ( x r t m u dr e a l i t yg e o g r a p h i c a li n f o r m a t i o ns y s t e m ) 是地理信息系统与 虚拟现实技术相结合的产物，是目前地理信息系统和虚拟现实技术研究的热点和 前沿方向之一。它既具有传统g i s 系统所具有的空间数据的存储、处理、查询和 分析等功能，又兼备了v r 技术所提供的浸入式实时交互功能。但是，v r 与g i s 的融合不是两者的简单连接，而是从空间模型分析到空间数据库的结构直至三维 t g i s 城域仿真平台的场景组织与优化 数据的可视化，包含两者数据、模型、功能的一体化设计。 v r g i s 的主要创新在于。v r g i s 平台的底层一体化架构；面向对象的节点 数据管理，数据存储方面采用深度优先存储，并建立高效的空间数据m 索引技 术：面向三维对象的矢量模型匹配技术，便于优化三维显示引擎，提高虚拟地理 环境系统的实时绘制效率：有自主的3 d sm a x 场景导出插件及自定义的文件读取 机制等。 v r g i s 使用了最新的o p e n g l 的扩展机制顶点数组( v b o ，v e r t e xb u f f e r o b j e c t ) 来渲染场景模型，把数据加载到图形处理器的高性能的显存里，突破了 渲染速度和计算速度的瓶颈，大大减少了渲染时间，提升了系统效率。 根据项目发展规划，该项目研发成功后，将要服务于城市规划建设、宣传推 介、公共设施、商业中心规划项目、城市形象宣传、企业招商推介等项目。高端 用户还可以应用该软件工具提供的组件和插件，开发适合特定需要的虚拟现实和 三维地理信息系统。 1 3 研究工作的背景与意义 随着计算机图形学和虚拟现实技术的发展，人们对于虚拟仿真环境的实时 性、沉浸感提出了越来越高的要求，希望以更自然的方式来观察效果更逼真、范 围更广的虚拟场景。当前许多3 d g i s 系统中可视化已经有了很好的表现力，画 面甚是精致。然而可视化所涉及的区域范围却很小，多数是针对某一有限区域来 进行的。目前，对于更大范围的城域仿真还无法做到实时的可视化，其中重要的 原因是数据量过大，对于城域景观场景，从理论上说，其数据量和复杂性是无限 的，我们称之为大规模三维场景海量数据的实时绘制问题。大规模三维场景所涉 及的数据量己经远远超出了计算机的运算能力，我们不可能把内存中的数据全部 绘制，而只能根据场景绘制的需要生成动态的可见集，并在可见集内进行查询和 碰撞检测等操作。 因此这需要设计合理高效的场景模型数据组织结构，对场景模型进行快速高 效的检索，对数据调度过程进行控制和优化。并基于此组织结构进行高效的可见 性剔除，l o d 应用以及碰撞检测，最终达到减少所需绘制的场景数据、加快绘 制速度的目的。 目前国内外很多学者都致力于这些问题的研究，也提出了一些解决方案，但 是，这些方案还不能满足v r g i s 仿真平台实际应用的需要。因此，针对v r g i s 平台，我们提出了自主的场景模型组织与管理的方式。 2 v r g i s 城域仿真平台的场景组织与优化 1 4 本论文主要工作 基于“v r g i s 城域仿真平台开发项目，本论文做了以下几个方面的工作： 1 ) v r g i s 虚拟场景数据的组织 阐述了三维空间中基于四叉树索引结构的层次包围盒( 册b h i e r a r c h i c a l b o u n d i n gb o x ) 的构造方式，并用此结构来组织与管理v r g i s 平台中的虚拟 场景数据； 2 ) v r g i s 平台中可见性剔除的实现 对虚拟仿真平台中的可见性剔除做了深入研究，并基于h b b 结构，实现 了v r g i s 平台中背面剔除、视锥体裁剪以及遮挡剔除，保证了平台的性能： 3 ) v r g i s 平台中l o d 实现 基于h b b 结构，实现了平台的l o d 功能，优化了场景模型的结构； 4 ) v r g i s 平台中碰撞检测的实现 - 实现了基于h b b 结构的碰撞检测，以及发生碰撞后视点移动时产生的滑 动，保证了平台的运行效率。 3 v r g i s 城域仿真平台的场景组织与优化 第二章三维虚拟场景数据组织 2 1 常见三维空间数据组织方式 2 1 1 三维空间数据结构 空间数据结构是指空间数据在计算机内的组织形式。它是一种适合于计算机 存贮、管理和处理空间数据的逻辑结构，是空间中地理实体排列和相互关系的一 种抽象描述。 所谓三维空间数据结构是将虚拟场景中的几何体组织在三维空间中的数据 结构。利用这种数据结构来组织和管理虚拟场景，可以减少几何实体之间相交性 判断的次数、加快判断的速度。其主要应用于裁剪算法、光线跟踪以及碰撞检测 等操作。 大型场景中三维模型数据的组织存储一般分为两部分：1 ) 利用某个数据结 构，如数组、树、索引结构等，存储三维模型的基本信息( 顶点、面等) ；2 ) 用 一个空间数据结构存储场景的分割信息，例如，在研究加速绘制技术时往往要涉 及这些空间分割信息。只有这两部分都能高效地实现并有效地结合在一起，才能 提高三维场景漫游系统的效率【1 1 。 目前常见的空间数据结构类型主要有：h b b 、b s p 树、k 树、r 树、四叉 树以及八叉树等。 2 1 2 包围盒 包围盒技术是在1 9 7 6 年由c l a r k 提出的1 2 1 ，基本思想是用一个简单的几何形 体( 即包围盒) 将虚拟场景中复杂的几何物体围住，通过构造树状层次结构可以 逐渐逼近真实的物体。 包围盒是h b b 的主要构成元素，它广泛应用于光线跟踪、可见性测试、碰 撞检测等方面。比较常见的包围盒有5 种：沿坐标轴的包围盒a a b b ( a x i s a l i g n e d b o u n d i n gb o x e s ) 、包围球( s p h e r e s ) 、沿任意方向包围盒o b b ( o r i e n t e db o u n d i n g b o x e s ) 、以及更复杂的离散方向多面体k - d o p s ( d i s c e r e t eo r i e n t a t i o np o l y t o p y ) 和凸包( c o n v e xh u l l ) 。 4 v r g i s 城域仿真平台的场景组织与优化 ( a ) 包围球( b ) a a b b 包围盒( c ) o a b 包围盒( d ) k - - d o p $ ( e ) 凸包 图2 - 1 常见包围盒类型 对于包围盒一般有两个评定标准：1 ) 紧凑性。包围盒的紧凑性决定了包围 体逼近物体的程度，包围盒应尽可能逼近所包围的模型，减少冗余空间；2 ) 简 单性。包围盒要比被包围的几何对象简单。简单性不仅表现为几何形状简单，易 于计算，还包括相交测试算法快速简单。 各种包围盒的优缺点比较如下： 包围球是一种最简单的包围体，它易于计算，非常易于做重叠测试和节点修 改，但缺点是与物体的逼近程度较差。 一 a a b b 又可以称为轴对齐包围盒，被定义为包含该对象且各边平行于坐标轴 的最小的六面体，它的1 2 条边都与世界坐标系中的x ，y ，z 轴平行( 如图2 i 所示) 。由于a a b b 的几何概念简单，但紧密性差，它的计算也就相应比较简单， 只需分别计算组成对象的图元集合中各个元素顶点的x 坐标、y 坐标和z 坐标 的最小值和最大值( 1 x ，l v ，l z 和u x ，u y ，y z ) 。 a a b b 间的重叠测试也比较简单，两个a a b b 重叠当且仅当它们在三个坐 标轴上的投影区间均重叠时，两个a a b b 重叠。即：分别先找出两个包围盒各 自的八个顶点中，三维坐标值同时拥有最大值及最小值的两个顶点，将坐标值最 大的点与另一个包围盒坐标值最小的点作比较，如果有某一轴的坐标值使得一个 包围盒坐标值最大点，小于另一包围盒坐标值最小点，则此两个包围盒是分开的， 假使六种测试结果都不分开，则可得知两包围盒重叠。a a b b 间的重叠测试最多 只需要六次比较运算。根据两个a a b b 相交当且仅当它们在三个坐标轴上的投 影区间均相交这一特性，我们可以将三维求交问题转化为一维求交问题1 3 j 。 o b b 是一个任意方向的长方体包围体，与前二者相比，它可提供非常紧凑 的逼近效果，但o b b 的计算相对复杂，其关键是寻找最佳方向，并确定在该方 向上包围对象的包围盒的最小尺寸。o b b 间相交测试的代价比较大。 v r g i s 城域仿真平台的场景组织与优化 k - d o p s 则是一个凸多面体，它的面由一些半空间所确定，这些半空间的外 法向是从k 个固定的方向中选取的。与包围球和轴向包围盒相比，离散方向多面 体对物体的逼近程度相对较好，与方向包围盒和凸包相比，它的重叠测试和节点 修改耗费相对较低。使用k - d o p s 同样存在着计算相对复杂的问题。 凸包是一种极端情况，它提供了物体最紧凑的凸包围盒，但它的重叠测试和 节点修改的耗费都相当高【4 】。 一般来说，以上几种包围体( 包围盒) 的紧凑程度依次增大，但其计算复杂 度也相应地越来越高( 图2 1 ) 。 2 1 3 空间分割法 空间分割法将空间按照某些规则分割成均匀的单元，然后将空间中每个实体 对应到一个或多个单元中，这一方法很适用于实体在空间中均匀分布的稀疏环 境。但对于更为一般的环境，则很难选择一个最优的剖分尺寸，若选择不当，会 导致空间耗费大，计算效率低。常用的空间剖分法有规则网格、k d 树、k d b 树、 b s p 树、四叉树、八叉树和r 树系列等( 图2 2 ) 。 规则格网空间索引的思路简单，容易理解和实现，其基本思想是将研究区域 用横竖线划分为大小相等或不等的网格，记录每一个网格所包含的地理对象。 k d 树( k 维搜索二叉树) 是将二叉树推广到多维数据的一种主存数据结构， 它是一个k 维空间中的二叉树。在每个内部节点中，用一个k - 1 维的超平面( 如 二维空间中的线) 将节点所表示的k 维空间分成两部分，这些超平面在k 个可 能的方向上交替出现，而且在每一个超平面中至少包括一个点数据。 b s pc b m a r ys p a c ep a r t i t i o n ) 树采用二叉空间分割，其基本思想是：任何平 面都可以将空间分割成两个互不相交的半空间，所有位于这个平面一侧的点定义 了一个半空间，位于另一侧的点定义了另一个半空间。此外，如果在任何半空间 中有一个平面，它会进一步将此半空间分割为更小的两个子空间。可以使用多边 形列表将这一过程进行下去，当子空间中仅存在单个平面时，即可构造出一个描 述三维实体对象层次结构的二叉树( b s p 树) 。在这个树中，一个进行分割的多 边形被存储在树的节点，所有位于子空间中的多边形都在相应的子树上。这一规 则也适用于树中的每一个节点。构造b s p 树的关键是如何在三维空间中快速确 定分割平面，以使生成的b s p 树尽量趋于平衡【4 j 。 。 四叉树( q u a d t r e e ) 是一种有效描述场景模型数据的数据结构，它的分层树 结构将指定的三维空间区域按水平面的四个象限分成四个空间( 图2 2 ) 。将水平 面均匀划分成四个象限且在树上的每个非叶子节点处存储四个数据元素。每个元 6 婚l s 城域仿真平台的场景组织与优化 素称为体元，以该象限为水平面的自下而上的柱面体三维空间称为体素。在三维 空间中，如果一个体素是空的，则该体元的类型用“n u l l 表示，非空的体素 就以该体素中心为原点再一次均匀的划分成四个象限，这样就可以把三维空间中 的所有模型节点归属到四叉树的相应叶子节点上。为了防止由于模型节点过多造 成四叉树划分过深的情况的发生，我们需要在四叉树的层次上做一些限制。 四叉树算法的特点是数据结构简单，集合运算容易，形体上各元素已按空间 位置排成了一定的顺序，便于找到其所在的空间位置。当然分割的深度越大，查 找节点的速度越快，但是分割深度的增加会直接导致四叉树节点的指数级增加， 而四叉树的构建是在场景载入的同时进行的，树节点的增加会直接影响到场景读 取的速度。所以在使用四叉树算法时需要规定一个分割深度，达到该深度的四叉 树节点就直接定义为叶子节点不再进行分割，以此来有效地控制节点的数量，使 场景读取时间保持在用户能够接受的合理长度1 5 j 。 八叉树是对二维g i s 中四叉树索引进行扩展的，是一种三维空间数据结构， 其基本思想是将三维区域划分成三维栅格，每一个小正方体( 称为一个体元) 有 一个或多个属性数据。属性相同的区域用大块表示，而复杂区域则用小块表示， 以一大块分为a d , 块进行规则划分。建立八叉树索引的难点一是空间分割时应遵 循一定的原则，这可通过规定一个阈值k ( 表示空间对象的个数) 来解决，即只 有当区域中空间对象的个数多于k 个时，该区域才需要进一步划分；二是分辨率 问题( 即空间分割时允许达到的最小予区是多大) ，这可以通过规定一个不再需 要分割的体元大小来解决。 r 树是近年应用最广泛的空间索引方法之一，可扩展为支持更高维的数据 集。r 树采用最小约束矩形来递归分解索引空间，其存储效率相对较高。但r 树的区域之间经常产生重叠( 这种重叠通常会随数据量或空间维数的增加而剧 增) ，因此区域搜索可能需要沿多条路径进行，从而降低了搜索效率。在3 d g i s 中，通常需采用启发式算法来降低三维r 树节点的空白区域、各分支的重叠区 域以及外包范围的体积，从而减少各分支的重叠区域，提高节点利用率，改进r 树的性能。如可采用球形或规则多面体作为三维空间对象的外包围，从而避免使 用正六面体作为外包围分解三维空间所造成的大量重叠区域和空白区域。国内外 学者对r 树提出了许多不同的扩展，包括r + 树、r 。树等。r + 树虽然避免了区域 的重叠，但它可能需要在不同的节点中存储同一个区域的标识，从而降低其存储 效率。r 树则尽量减小节点间的重叠面积，它对上溢节点进行删除，并强制重新 插入该节点中的所有对象 4 1 。 7 v r g i s 城域仿真平台的场景组织与优化 ( a ) 规则网络( b ) 四叉树八叉树( c ) k d 树( d ) b s p 树( e ) r 树 图2 - 2 常见的空间分割法 2 1 4 层次包围盒 在虚拟场景中，我们可以预先把整个场景的几何体根据空间位置划分成很多 的几何子部分，这些子部分又递归划分出更多的子部分，将物体及子部分以一种 数据结构组合在一起。比如树形结构，树的根节点代表全部的物体，每个子节点 为物体的一部分，一层一层细化，直到叶节点为单个几何体甚至到几何体的基本 单元( 三角面片) ，与此同时，我们为每层节点建立相应的包围盒。这种表示物 体及建立物体包围盒的方法就是h b b 。 因此，h b b 可以说是一种简单的树结构( 图2 3 ) ，它用一些特定的方法对 空间实体对象进行分割，最终将树的每一个节点保存为所在层次的包围盒信息， 叶子节点则存储基本对象。h b b 技术的基本思想是通过构造包围盒的树状层次 结构来逼近对象的几何模型，直到几乎完全获得对象的几何特性，从而只需对包 围盒重叠的部分进行进一步的相交测试。与一个物体相对应的层次结构的节点是 空间上包围该物体一部分几何对象的几何近似体( 包围盒) ：层次结构的根节点 包围了整个物体，每个父节点包围的几何对象是它的所有子节点包围的几何对象 之和，节点从上到下逐渐逼近它包围的几何对象。 8 v r g i s 城域仿真平台的场景组织与优化 介俞介介 图2 - 3 层次包围盒树结构 h b b 的基本算法包括包围盒的计算、分割和相交判断等。在选择合适的h b b 在组织和管理场景时要综合考虑包围盒的构造与以上各种算法的复杂性。 另外，将包围盒与空间分割结合，用层次包围盒表示三维实体的边界层次， 然后建立三维空间索引，如四叉树索引或b s p 索引，可以加速三维空间检索， 这种混合索引技术现在已广泛应用于三维场景实时绘制，包括可见性判断、碰撞 检测、光线追踪和辐射度计算等。 2 1 - 5 常见三维空间数据组织方式的比较 每一种空间索引方式都有其优越性、使用范围和适用对象。实际开发中具体 选取哪种组织方式作为数据的组织方式，要根据实际情况和应用需要来确定。目 前，多数g i s 软件采用多种组织方式并存、取长补短的策略。表2 1 是在对各种 类型三维空间数据组织研究的基础上归纳出来的不同组织方式的性能对照表，对 实际应用具有参考意义。 v r g i s 城域仿真平台的场景组织与优化 表2 1 常见三维空间数据组织方式的比较 组织方式适合对象划分方法优点缺点 数据冗余，变长纪录， 规则网格空间对象网络等分查询高效，算法简单 难以维护 支持数据量少，更 k d 树点对象按点二分存储效率低，查询高效 新困难 可以控制切割面以及分割 b s p 树空间对象按点二分树的深度，分割更有效，树 算法较复杂。动态维护性 的检索较快 较差，需预先生成 划分简单直观，与空间对象 可能会存在冗余信息，对 四叉树空间对象空间四分的分布相对应，计算相对简跨在交界处的模型管理 单不便，高空飞行时没优势 p 划分简单直观，与空间对象可能会存在冗余信息，对 八叉树空间对象 空间八分的分布相对应优于四叉树，跨在交界处的模型管理 计算较四叉树复杂不便 矩形不规算法复杂，动态维护性较 l 湔变种空间对象区域重叠改善，效率改善 则多边形 差 层次 空间对象 根据场景 能够迅速检索到最小包围 盒的相应模型信息，有成熟算法复杂 包围盒模型特性 算法支持 2 1 6 现有仿真平台数据的组织方式 1 ) v r m a p v r m a p 是北京灵图软件技术有限公司开发的三维地理信息系统平台软件， 可以在三维地理信息系统与虚拟现实领域提供从底层引擎到专业应用的全面解 决方案，它具有海量数据处理能力、高级仿真效果、跨平台通信、数据库驱动、 二次开发支持等关键技术。 v r m a p 通过基于结点的属性绑定、分层管理技术和r 树技术管理空间数据 和属性数据【引。它将数据按照空间关系划分成多个块，每个块由多个结点构成。 在v r m a p 中任何场景对象均可以描述成为结点，包括地形、摄像机、灯光、媒 体、控制器、触发器、粒子系统等等均为结点对象。任何结点对象均可以成为另 一个结点的子结点。父子结点之间的关系通常为空间关系上的绑定关系。基于结 点的空间描述模型使得在描述真实空间时变得简单和易于理解，同时很好的解决 了空间场景与数据库的绑定问题。 2 ) s ie n g i n e ， 。 s ie n g i n e 是基于d i r e c t 9 和n e t 体系结构的用于p c 机实时图形应用和游戏 1 0 v r g i s 城域仿真平台的场景组织与优化 的开发平台。该平台包括两个主要部分。一是实时图形应用的开发制作系统，二 是支持实时图形运行的虚拟机。s ie n g i n e 是一个具有革命性的平台，它的创新 体现在绘图上是优异的场景简化和渲染管理体系结构、对新渲染算法的充分支持 以及可自扩展渲染算法的体系结构。 s ie n g i n e 利用八叉树来管理一个区域内的场景物体，通过八叉空间划分树 来帮助场景裁减以提高裁减算法的效率。同时将采用硬件支持的闭合测试来剔除 大部分被遮挡的场景物体。硬件支持的闭合测试是：用物体层次包围球和包围盒 来代替物体，进行尝试性渲染，如果尝试性渲染过程中没有影响z 缓存的数据 就说明物体被已经绘制的物体所遮挡的可以剔除掉，否则就绘制物体本身。通过 八叉树的空间排序性我们可以按距离判断视点远近和物体大小，先绘制近处的大 物体，然后在绘制后续物体前先用物体的包围盒进行上述的遮挡测试，如果测试 通过就绘制物体，否则就忽略掉物体的绘制。由于包围盒的面片数量比较少，所 以能够很大的剔除掉被遮挡物体的绘制，而增加的测试代价可以忽略不计。 2 2v r g i s 场景的组织与管理 三维场景组织与管理主要负责组织和管理场景中的所有物体以及决定物体 的渲染顺序。实用、高效的场景组织方式是v r g i s 设计与开发需要解决的关键 技术之一，场景的组织方式直接决定了平台的性能，高效的组织方式也是快速地 查询场景数据的基础。目前，国内外学者提出了多种三维空间索引方法，但还没 有一种方法明显优于其他方法。 v r g i s 城域景观仿真平台是一套基于o p e n g l ，面向城市区域级大场景、 多精度等级虚拟现实应用的软件平台，它具有大规模的场景组织和渲染能力。 v r g i s 平台中需要对场景中大量散列在地形上的模型进行组织和管理，本文针 对平台需要，选用了a a b b 包围盒来生成基于四叉树索引h b b 结构。a a b b 包 围盒占用储存空间较小，相交测试速度较快，在模型相对规范的城域仿真中也不 太会有太多冗余，具体有较强的适用性。场景中的数据以i - i b b 树的方式来组织， 提高平台可见性判断、碰撞检测和数据存取的效率。 场景组织方式是v r g i s 平台设计的最核心部分，虚拟场景模型包括建筑模 型、摄相机、动光、特效、动画等各种城市景观数据。v r g i s 采用树桩管理场 景中的各种元素，所有的东西都挂在h b b 树上，不在h b b 树上的东西不会被 渲染。v r g i s ：v g q u a d t r e e s c e n e m a n a g e r 就是h b b 树的管理者，v r g i s ：v g t r e e ( 树) 、v r g i s ：v g w a t e r ( 水) 以及v r g i s ：v g f i r e ( 火) 等相应的场景模型类都 是从v r g i s ：v g q u a d t r e e s c e n e m a n a g e 中创建的。如图2 - 4 、图2 5 示为h b b 树 结构在v r g i s 平台中的作用。图2 - 6 为v r g i s 中场景组织与管理类 l l ， v 】良g i s 城域仿真平台的场景组织与优化 v g q u a d t r e e s c e n e m a n a g e r 的部分成员的u m l 类图。 图2 4v r g i s 场景管理结构图 v r g i s 城域仿真平台的场景组织与优化 。i i i 图2 - 5v r g i s 系统u m l 类图 v r g i s 城域仿真平台的场景组织与优化 v r g t k ：q u a d t r e o k e n e m u a g e r t u n 喧n t u n v l e w l d s e t ：v e c t o r c u r r e n t v w i d s e t 3 ：v c t o 嘲i ， 4 p l l t a x l ：b o o i - l b t n d o w n p o s l n s c r e e n ：o p o i 幢 l b t n m o v o p o s l n s c r e e n ：c p o i n t l b t n d o w n p o s l n w o r l d ：v c t o r 3 u n l l 脯o v e p o s l n w o r l d ：v e c t c w 3 v g c u r r o n t m o d e ：i n t i m h u m o f u p d a t e ：i n t * m _ n o d e d i s t a n c e b o u n d r y ：n e a t * 响r u s t u m ：c f r u s t u m * b ) e v o s c e n e t r e e ：b o o i m c u r r e n t v g f i l e p a t h ：c s t d n g m m o u s e d o w n p o i n t ：c p o i n t , t h i t s ：u n s i g n e c li n t m o d e lp i c k ：i n t h e m p ：i n t 量y ep o p s i c ：k v e c t o r 3 q u a d t r e e s c e n e m a n a g e r 0 * - q u a d t r e e s c e n e m a n a g e r 0 * c o n v e r t s e l e c t e d o 埘e c t t o s k y b o x n o d e 0 ：h e e l * c o n v e r t s o i e c t e d o 埘e c t t o w a t e r n o d e 0 ：h e e l + c o n v e i 瞳h l e c t e d o b j e c t t o m e t a l n o d e 0 ：b o o i * a d d f l a g t o s c e n e ( i n o u t & p o i n t ：c p o i n t ) ：v o i d a d d f o u n t a i n t o s c e n e ( i n o u t & p o i n t ：c p o i n t ) ：v o i d a c i c i f i r e t o s c e n e ( i n o u t & p o i n t ：c p o i n t l ：v o i d * a d d s m o k e t o j k e n e ( i n o u t 矗p o i n t ：c p o i n t ) ：v o i d * d r a w s h a d o w s w i t h t r e e ( i nn o d e ：l i c e n e t r e e n o d e r e f p t r ) ：v o i d * r e n d e r h a v v k e y 0 0 ：v o i d * r e n d e r p a t h ( i ；v o i d s o i e c t e d ( i np o i n t ：c p o i n t , i ng h l a s p e c tid o u ) lv o i d i m p o r t m o d 0 ：v o i d * a d d m o d o i t o s c e n e ( i nf u e n m n e ：c s t r i n g ) ：v o i d i n i t t r o e 0 ：v o i d - b u h 盯m e ( i nn o d e ：s c e n e t r e e n d o r e f p t r ) ：v o i d r e i n i t n o d e f o r a d d n o d e ( i nn o d e ：s c e n e t r e e n o d e r e f p 智, i no b m u ：v e c t o r , i no b m i n ：v e c t o r 3 l ：v o i d m o 幽f y t r t r ( i nb o d e ：s c e n e t r e e n o d e r e f p t r ) ：v o i d d e i e t e t r e e n o d e ( i nn o d e ：8 c e n e t r e e n o d e r o i p t r , i n 啊ii n t ) ：v o i d f r e e n o d e ( i nn o d e ：8 c e n e t r e e n o d e r e f p t r ) ：v o i d d r a w a a b b k i n e ( i nn o d e ：s c e n e t r e e n o d e r e f p t r ) ：v o i d - i s e a r c h v i e w t r e d ( i nn o d e ：8 c e n e t r e e n o d e r e f p t r ) ：v o i d d r a w t r o e ( i nn o d e ：s c e n e t r o o n o d e r 卅伊t r ) ：v o i d m w v m w l d s e t ( i nr , o n s t & d n w s o i e c t l 1 n 0 8 ；b o o l - t r u e ) ：v o i d a 嘶u s t l 0 0 0 ：v o i d o l l i s t o n ( i nn o d e ：i h ：e n e t r e e n o c l e r d p t r ) i 洲 r e n d e r s c o n e l ：v o i 图2 - 6 卸b b 管理类的部分成员的眦类图 本文的h b b 树，提出使用了自适应场景模型的动态构造方式。根据场景模 型分布的不同，动态调整生成不同结构的h b b 树，最大限制的减少了h b b 结 构的信息冗余，提高了运算效率。除此之外，当平台执行导入删除模型，以及 执行移动、旋