约束三角剖分理论与方法研究

论文摘要

约束三角剖分在有限元分析和信息可视化等工程领域具有重要的应用背景,同时它也是计算几何和计算机辅助几何设计的一个热点问题。约束三角剖分由无约束三角剖分发展而来,由于用户给定的是完全离散的数据点,而需要模拟的是尽量接近实际情况的连续的面片(曲面),但是由于实际模拟场景的复杂性和某些客体表面所存在特殊形状,这样在实际应用中不可避免的会产生错误的剖分结果,为了避免这种情况的发生,一种重要的有效途径是通过事先给定一些约束条件来指导和约束具体的三角剖分过程,这便是约束三角剖分。借助于Delaunay准则,可以对平面上的离散数据点剖分出最优化的三角网格,当用户给定约束条件时,这些约束条件必须要出现在结果三角网格中,会在很大程度上破坏局部最优性,现如今对此类平面约束三角剖分已有很多成熟的算法。不像平面三角剖分存在最优剖分准则,即Delaunay准则,空间三角剖分很难确定相应的最优准则,大多数算法以剖分出来的三角网格不违背实际情况为原则。在实际应用中,从不连续的数据点出发剖分出的三角网格时常发生与物体表面实际情况相悖的情况,特别是实际应用中很多客体和场景具有空洞、弯绕、螺旋、山脊、山谷这些特殊情况,此时采用传统的三角剖分算法很可能会出现错误的剖分结果。本文首先对约束三角剖分进行分类,并对每个类别的经典算法经行介绍,然后针对这些算法某方面的局限性(特别是空间约束三角剖分)提出了创新性的改进。本文提出的平面约束三角剖分较之以往算法可省略了求外接圆这一步骤,可很大程度上减小时间复杂度。空间三角剖分方面,对空间约束三角剖分的约束条件进行详细的规划和总结,详细的分析了约束条件特别是多约束条件下各约束之间的关系,并针对每种约束都给出了剖分方法,另外,针对本文提出的基于外部约束的三角剖分的特点对其应用领域进行了拓展,使之可以通过使用外部剖分对三维客体表面进行修改。实践方面,对论文中提及的各种主要约束都给出了实验结果,并对实验结果进行分析。最后总结出一些尚待解决的问题和进一步工作。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 论文的选题背景与意义
• 1.2 约束三角剖分的分类及研究现状
• 1.2.1 约束三角剖分的分类
• 1.2.1.1 平面约束三角剖分
• 1.2.1.2 空间三角剖分
• 1.2.2 约束三角剖分的研究现状
• 1.3 本文的主要工作
• 第二章 基本概念与算法
• 2.1 平面三角剖分的基本概念和算法
• 2.1.1 平面三角剖分的基本概念
• 2.1.2 平面三角剖分的基本算法
• 2.1.2.1 无约束三角剖分
• 2.1.2.2 平面约束三角剖分算法
• 2.2 空间三角剖分的基本概念和算法
• 2.2.1 空间三角剖分的基本概念
• 2.2.2 空间三角剖分的基本算法
• 2.2.2.1 平面投影法
• 2.2.2.2 直接剖分算法
• 2.2.2.3 基于影响域的空间三角剖分算法
• 2.3 本章小结
• 第三章 平面约束三角剖分研究
• 3.1 传统的三角网生成算法基本思想
• 3.2 分析与讨论
• 3.3 一种基于区域最大张角选择的平面约束三角剖分算法
• 3.3.1 概念解释
• 3.3.2 基本思想
• 3.3.3 算法过程
• 3.4 实验结果和讨论
• 3.5 本章小结
• 第四章 基于内部约束的空间三角剖分研究
• 4.1 三维约束条件分类
• 4.1.1 内部约束的分类
• 4.1.2 外部约束的分类
• 4.2 几何完整性判断
• 4.2.1 线段与三角形的相交判断
• 4.2.2 三角形与三角形的相交判断
• 4.3 针对各类内部约束条件的约束三角剖分算法
• 4.4 实验结果与讨论
• 4.5 本章小结
• 第五章 基于外部约束的空间三角剖分研究
• 5.1 外部约束的相交性判断
• 5.2 基于外部约束的三角剖分算法的实现
• 5.3 基于外部约束的三角剖分局部修改
• 5.4 实验结果和讨论
• 5.5 本章小结
• 第六章 总结与展望
• 6.1 已完成的工作及创新点
• 6.2 进一步工作展望
• 参考文献
• 致谢
• 攻读硕士学位期间撰写和发表的学术论文