实时图形处理关键技术研究

论文摘要

二维折线集、三角网格和点是几何模型表示中的基本元素,分别被广泛用于二维矢量地图和三维物体模型的表示。如何快速地传输和操作由它们表示的几何模型是实时图形处理的主要任务。本文以几何压缩理论与方法为基础,分别分析了矢量地图和三维几何模型中的拓扑数据和几何数据的特点,首先,提出了基于折线简化和单纯复形的矢量地图多分辨率表示和渐进式传输方法,该方法在保持视觉一致性的条件下,将较小分辨率地图的数据量降低为最大分辨率地图的数据量的1/10,提高了矢量地图渐进传输的效率。其次,提出了基于扇形带的三角网格拓扑关系表示方法,该方法在不考虑顶点分裂与融合的情况下,可以保证连接关系的最低压缩率为log 2 （274）比特/顶点。第三,提出了基于广义三角形带的三角网格数据压缩和多分辨率表示方法,该方法可以充分发挥图形处理器的功能,统一了单分辨率和多分辨率三角网格的表示方法。最后,提出了基于KD-树的点模型各向异性量化方法。对KD-树广度优先的遍历可以构造出多分辨率点模型。该方法可以将点与多边形相结合混合表示几何模型,克服了点模型在表示大平面时效率低的缺点。以上方法有效地提高了图形在存储、传输以及绘制等方面的效率,增强了图形处理的实时性。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 图形处理系统
• 1.1.1 计算机中的图形处理系统
• 1.1.2 流计算模型
• 1.1.3 互联网中的图形处理系统
• 1.2 几何模型
• 1.2.1 二维折线模型
• 1.2.2 三角网格模型
• 1.2.3 点模型
• 1.3 实时图形处理
• 1.3.1 几何压缩
• 1.3.2 与GPU 相适应的图形数据结构
• 1.4 信息论和熵编码
• 1.4.1 Huffman 编码
• 1.4.2 算术编码
• 1.5 本文主要工作与内容安排
• 第二章 单纯复形与矢量地图的多尺度表示
• 2.1 基本概念与理论
• 2.1.1 矢量地图及其分辨率
• 2.1.2 子分集合简化
• 2.1.3 单纯形与单纯复形
• 2.1.4 矢量地图的渐进式传输
• 2.2 相关工作
• 2.2.1 矢量地图的传输
• 2.2.2 多段线简化
• 2.2.3 地图对象的选择
• 2.3 矢量地图渐进式传输的C/S 结构
• 2.4 矢量地图的多尺度表示
• 2.4.1 计算最简多段线
• 2.4.2 多尺度地图的数据结构
• 2.4.3 拓扑不一致的简化
• 2.4.4 基于Reactive-tree 的选择
• 2.5 实验结果
• 2.5.1 多段线简化效果
• 2.5.2 子分集合的多分辨率表示
• 2.6 本章小结
• 第三章 三角网格压缩
• 3.1 三角网格
• 3.2 理论基础
• 3.2.1 图论中的三角网格
• 3.2.1.1 图的概念
• 3.2.1.2 图的编码
• 3.2.2 多边形的三角剖分
• 3.2.3 平面点集的三角剖分
• 3.3 三角网格的表示
• 3.3.1 单分辨率网格压缩
• 3.3.1.1 广义三角形带
• 3.3.1.2 拓扑手术
• 3.3.1.3 基于区域增长的压缩
• 3.3.1.4 算法比较
• 3.3.2 几何编码
• 3.3.2.1 量化
• 3.3.2.2 预测编码
• 3.3.2.3 谱方法
• 3.3.2.4 其它属性编码
• 3.3.3 三角网格的多分辨率表示与渐进式传输
• 3.3.3.1 基于增量简化的多分辨率表示
• 3.3.3.2 基于顶点聚合的多分辨率表示
• 3.3.3.3 重采样方法
• 3.4 本章小结
• 第四章 基于扇形带的单分辨率三角网格表示
• 4.1 三角扇形
• 4.2 构造扇形带
• 4.3 压缩率
• 4.4 实验结果与结论
• 4.5 本章小结
• 第五章 基于广义三角形带的单分辨率三角网格表示
• 5.1 算法概述
• 5.2 构造广义三角形带
• 5.3 广义三角形带的编解码
• 5.4 缓冲区的长度
• 5.5 几何信息的压缩
• 5.6 实验结果与结论
• 5.7 本章小结
• 第六章 基于Hamiltonian 三角剖分的多分辨率三角网格表示
• 6.1 Hamiltonian 三角剖分的性质
• 6.2 算法概述
• 6.3 边收缩的距离策略
• 6.4 离散多分辨率表示与渐进式传输
• 6.5 简化质量控制
• 6.6 实验结果与结论
• 6.7 本章小结
• 第七章 点模型及其表示方法
• 7.1 点模型
• 7.1.1 定义
• 7.1.2 法向量
• 7.1.3 处理流程与相关工作
• 7.2 点集的插值与逼近
• 7.2.1 Voronoi 技术
• 7.2.2 径向基函数
• 7.2.3 最小二乘拟合
• 7.2.4 移动最小二乘法
• 7.3 局部曲面分析
• 7.3.1 协方差分析
• 7.3.2 曲面的法线及其方向
• 7.3.3 曲面的曲率
• 7.4 点模型的数据结构
• 7.4.1 群集
• 7.4.2 八叉树
• 7.4.3 KD-树
• 7.5 基于KD-树的点模型表示方法
• 7.5.1 各向异性的量化
• 7.5.2 KD-树的构造
• 7.5.2.1 空间分割
• 7.5.2.2 KD-树编码
• 7.5.2.3 计算可见面编码
• 7.5.2.4 绘制细节控制
• 7.5.3 序列化
• 7.5.4 点与多边形混合表示
• 7.5.5 实验结果
• 7.6 本章小结
• 第八章 结论与未来工作
• 8.1 基于点的几何造型方法
• 8.2 破坏模型
• 致谢
• 参考文献
• 攻读博士学位期间发表的论文著作及完成的科研项目