Delaunay三角网构建及可视化方法与实现

论文摘要

TIN（不规则三角网）是将离散数据点连成一系列连续的三角形网格，三角网的大小和形状取决于离散数据点的位置和密度。在TIN建模中，Delaunay三角网被视为最优的，它既可适应规则分布数据，也可适应不规则分布数据，能够灵活地处理特殊地形。因此，一般Delaunay三角网和带约束条件Delaunay三角网的构建、基于Delaunay三角网的三维地形可视化以及基于三角形折叠的地形模型简化是本文重点研究的四个内容。在基于离散点的一般Delaunay三角网构建方面，本文重点研究逐点插入算法，在插入点定位问题中，引入快速点定位算法并对其进行改进，从而保证了算法的高效性。在带约束条件的Delaunay三角网构建方面，承接上一章的算法先生成初始三角网，然后将约束边嵌入其中，针对“插入-交换”算法的不足之处，加入切点处理使算法更具健壮性。针对Delaunay三角网在表示地形上不够形象与直观这一情况，本文利用Direct3D图形库，在VC++开发环境下实现了基于Delaunay三角网的三维地形可视化。最后，在地形模型简化方面，本文在基于三角形折叠算法的基础上，引入法向量度量参数，同时加入边界判断，利用Direct3D自动计算三角面片的法向量这一特性实现了地形模型的简化，并能较好地保持原始模型的特征。

论文目录

• 摘要
• Abstract
• 目录
• 图表目录
• 1 绪论
• 1.1 引言
• 1.2 研究内容和研究意义
• 1.3 国内外研究现状
• 1.3.1 Delaunay 三角网的构建
• 1.3.2 基于 Delaunay 三角网的三维地形可视化
• 1.4 研究思路和关键问题
• 1.5 论文的组织结构
• 2 基于离散点的 Delaunay 三角网构建
• 2.1 Delaunay 三角网的定义及性质
• 2.2 Delaunay 三角网生成算法
• 2.2.1 静态三角网生成算法
• 2.2.2 动态三角网生成算法
• 2.2.3 算法时间复杂度分析
• 2.3 Delaunay 三角网逐点插入算法
• 2.3.1 数据结构
• 2.3.2 逐点插入算法的关键步骤
• 2.3.3 插入点快速定位算法分析与改进
• 2.3.4 算法实现及分析
• 2.4 小结
• 3 带约束条件的 Delaunay 三角网构建
• 3.1 带约束条件 Delaunay 三角网的定义及性质
• 3.2 约束 Delaunay 三角网的生成算法回顾与分析
• 3.3 基于约束边嵌入算法
• 3.3.1 基本概念
• 3.3.2 约束边嵌入算法分析
• 3.4 改进的约束边嵌入算法
• 3.4.1 数据结构
• 3.4.2 算法描述
• 3.4.3 算法实现及分析
• 3.5 小结
• 4 基于 Direct3D 实现 Delaunay 三角网的三维地形可视化
• 4.1 Direct3D 简介
• 4.1.1 Direct3D 的特点及工作流程
• 4.1.2 Direct3D 的重要概念
• 4.1.3 VC++调用 Direct3D 的方法
• 4.2 Direct3D 绘制三维地形
• 4.2.1 场景设置
• 4.2.2 地形模型映射
• 4.2.3 三维地形绘制
• 4.2.4 可视化实现
• 4.3 地形网格模型简化
• 4.3.1 地形模型简化的常用算法
• 4.3.2 改进的基于法线的三角形折叠算法
• 4.3.3 算法实现及分析
• 4.4 小结
• 5 结论与展望
• 5.1 研究工作总结
• 5.2 进一步研究方向
• 致谢
• 参考文献
• 攻读硕士学位期间发表的论文