基于BSP和四叉树的场景管理研究

论文摘要

建立更加广阔,更加丰富的虚拟现实场景是可视化工作不断追求的目标。其核心内容之一是对场景数据的管理。随着硬件条件的不断发展和软件技术的提高,人们对可视化效果的要求也在提高,人们希望看到更加复杂多变,细节更加丰富的场景。在一定时期内硬件设备的条件是一定的,如果不使用任何算法对场景进行管理,那么场景的复杂程度和渲染速度直接成反比。这样,在现有的硬件条件下,想要创造更丰富的场景是很难实现的。所以,研究不同场景特点和人视觉的规律,总结其内在联系的存在,寻找与场景复杂度无关的算法是十分必要的,也是必然的发展趋势。本文主要对以下三方面进行研究:通过对四叉树分块地形的研究,采用部分载入加动态读取的方法实现了超大地形实时渲染,并使用了分片连锁快速的LOD(Level ofDetail)算法进行加速。通过对BSP树(二叉空间分割树)进行研究,改进了BSP树的分割算法,克服了传统BSP树的部分缺点,减少了其叶子节点数量。使用Portal将室内BSP场景和室外四叉树场景进行联系,实现室内外场景的无缝融合。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 应用背景
• 1.2 三维场景管理技术的概念
• 1.3 三维场景管理的意义
• 1.4 场景管理遇到的问题及研究现状
• 1.5 研究的问题和思路
• 1.5.1 研究问题
• 1.5.2 解决的问题和技术思路
• 1.6 论文组织结构
• 2 三维场景相关知识准备
• 2.1 场景管理概要
• 2.1.1 产生和发展
• 2.1.2 场景管理器的流程
• 2.1.3 场景加速算法分类
• 2.2 计算机图形系统
• 2.2.1 图形API
• 2.2.2 现代图形处理器特性
• 2.3 数学准备
• 2.3.1 四元数与矩阵
• 2.3.2 父空间变换和子空间变换
• 2.4 本章小结
• 3 室外场景
• 3.1 室外地形的特点
• 3.2 分块地形和四叉树场景管理
• 3.2.1 分块地形
• 3.2.2 四叉树管理
• 3.2.3 HeightMap和DisplacementMap
• 3.3 室外场景数据的生成
• 3.3.1 规则网格（Regular Square Grid）模型和不规则三角网（Triangulated Irregular Network）模型
• 3.3.2 地形数据规定
• 3.3.3 法线数据的计算
• 3.4 分块数据生成
• 3.4.1 顶点索引的生成
• 3.5 LOD技术
• 3.5.1 LOD总述
• 3.5.2 三种LOD算法分析
• 3.5.3 连锁分片地形简化算法
• 3.6 大型场景的读取
• 3.6.1 数据载入
• 3.6.2 数据更新
• 3.7 纹理生成
• 3.7.1 纹理方案
• 3.7.2 纹理坐标的生成
• 3.8 与室内场景相联系
• 3.8.1 地形中实体的挂接
• 3.9 本章小结
• 4 室内场景
• 4.1 室内场景的特点
• 4.2 BSP场景分析
• 4.2.1 基本概念、原理
• 4.2.2 Portal技术
• 4.2.3 传统BSP场景树的特点分析
• 4.2.4 对传统BSP场景树的改进
• 4.3 建立BSP树
• 4.3.1 数据导入
• 4.3.2 划分步骤
• 4.4 Portal与PVS数据的建立
• 4.4.1 Portal的生成
• 4.4.2 PVS数据的定义
• 4.4.3 与室外地形场景相连接
• 4.4.4 建立PVS数据的算法
• 4.5 本章小结
• 5 运行时场景加速
• 5.1 场景剔除流程
• 5.1.1 视点定位
• 5.1.2 场景剔除
• 5.2 关键算法分析
• 5.2.1 视截体定义
• 5.2.2 视截体对节点的剔除
• 5.2.3 Portal对视截体的裁剪
• 5.3 本章小结
• 6 程序实现及实验结果
• 6.1 程序总体设计
• 6.1.1 管理器设计
• 6.1.2 通用树形结构设计
• 6.2 其它技术的使用
• 6.2.1 S3TC压缩技术和DDS文件
• 6.2.2 3DS文件
• 6.2.3 SIMD指令优化算法
• 6.2.4 Shader的使用
• 6.3 实验和结果
• 6.3.1 软硬件平台
• 6.3.2 实验测试方案
• 6.3.3 实验结果
• 6.3.4 实验结果分析
• 6.3.5 实验总结
• 7 总结与展望
• 致谢
• 参考文献