平面线段集三角剖分的算法

本文提出了计算平面线段集三角剖分的两种算法，第一个算法是利用平面扫描的思想，当扫描线达到事件点时，处理事件点，即将事件点与已被扫描的某些点连接，这样便将已扫描的区域三角剖分，当扫描线达到最左边的事件点时，处理该事件点，就完成了平面线段集的三角剖分，第二个算法基于逐层计算凸壳，并将凸壳改变为多边形，这样便便形成嵌套的多边形层，这些多边形覆盖线段集凸壳内的区域，然后三角剖分每个多边形，即完成平面线段集的三角剖分，两个算法的时间复杂性分别为O（nlogn),O(mnlogn)，其中n为线段集中线估的数目，m为凸壳的层数。     

面向并行的动态增量式Delaunay三角剖分算法

三角剖分是计算机图形学中的重要话题。并行三角剖分算法的发展对传统三角剖分算法提出了新需求,其中之一即是给定一个点数不断增大的点集,实现对该点集三角剖分的快速增量更新。虽然现今已有一些增量三角剖分算法,但都无法支持新增点落入原有三角剖分之外的情况。为解决此问题,提出了三角剖分的外扩技术,基于插入法设计了增量三角剖分算法TID。该算法能够支持任意次、任意数量、任意位置点的增量添加。TID算法能够对任意分布的点集均给出唯一三角剖分结果。对TID算法的性能评估表明,TID算法比现有算法具有更高的计算效率,且增量功能引入的额外开销较小。此外,该算法已成功作为局地三角剖分算法用于并行三角剖分算法中。     

一个利用法矢的散乱点三角剖分算法

曲面上散乱点的三角剖分在曲面重建中发挥着重要作用，借助于曲面上的法矢信息和三维Delaunay三角剖分算法，该文给出了一种新的散乱点三角剖分算法，输入一组散乱点以及所在曲面S在这些散乱点处的一致定向的法矢信息，该算法将产生一张插值散乱点的三角网格曲面M，并且曲面M可以近似地看成是曲面S的三角剖分，算法的主要步骤分为两步：首先通过曲面S的一致定向的法矢信息，在曲面S的同一侧添加辅助点，利用这些辅助点来剔除Delaunay三角剖分中产生的不需要的三角片；然后将剩余的三角片连接成一张完整的网格曲面，与基于中轴的三角剖分算法相比，该文算法需要更少和更简单的计算，与局部三角剖分算法相比，该文算法可以更有效地避免重建后的曲面产生自交，该文的算法可用于任意拓扑的光滑曲面重建。     

一个通用的快速三角化算法

提出了一个适用于任意平面多边形区域及散乱点集的通用三角化算法。当算法应用于多边形区域时,首先对各个顶点和区域内部的散乱点按扫描方式排序,然后依次扫描各点,扩展生成新的三角形,从而获得局部已剖分区域,并最终完成整个区域的三角化。将上述过程作适当改动后,可被用于平面散乱点集的三角网格化,该通用算法除了具有快速三角化的特点之外,还采用局部域的优化组合来体现最优化准则,因此算法更具有可操作性和实用性。     

三维散乱点集的曲面三角剖分

根据三维散乱点集构造曲面剖分在 CAGD/CAD、反求工程等方面有着十分广泛的应用 .本文回顾了三维散乱点集曲面三角剖分的两种主要方法即平面投影法和直接剖分法 ,对几种常用的算法作了较为详细的描述 ,同时对剖分算法中经常出现的数据结构作了详细的介绍 .由于剖分采用的优化准则决定了剖分结果 ,因此本文讨论了几种常用的剖分优化准则 ,并举例对几种优化准则进行了较详细的分析比较 .最后简要地讨论了算法复杂度以及目前剖分的主要研究方向 ,并指出在实际工程应用中对复杂曲面采样得到的散乱点集 ,要得到光顺和保形的三角剖分 ,需要新的剖分准则和算法 .     

平面点集三角剖分的算法

提出平面点集三角剖分的一种新的算法，该算法首先逐层求凸包，然后分割环或成三角形，最后调整相邻环域的三角剖分便圾获得最小权三角剖分。     

用随机增量局部转换算法实现三维点集的Delaunay三角剖分

Delaunay三角剖分作为计算几何中的一个核心问题,尤其适用于三维网格生成.因此就需要开发出高效、健壮性的算法来实现.本文在原有算法的基础上提出了随机增量局部转换的算法来实现三维点集的Delaunay三角剖分.采用不退化的四点生成最初的三角剖分,每次加入一点,通过局部交换使新的三角剖分保持Delaunay性质,直到处理完所有点.还讨论了局部交换的思想和对不同面类型的处理方法,给出了两个剖分实例.     

人脸特征约束点的三维表情合成*

针对目前很多三维表情合成算法计算量大、方法比较复杂、真实感不强的特点,结合人脸分布特征,提出了一种基于Delaunay三角剖分的三维表情合成新算法。该方法通过对人脸特征点集的快速三角剖分避免了病态三角网格,有效提高了合成后人脸表情的真实度,降低了算法复杂度。大量实际人脸表情合成的实验结果表明,该算法通过少量的特征点生成的三维人脸表情更加真实,可有效快捷地合成各种真实的人脸表情。     

两维区域三角剖分的新算法

提出一种两维区域三角剖分的新算法,算法首先递归应用求两维点集凸包的Graham扫描法,在原始区域的点集中求出一系列的凸包,同时原始两维区域也被这些凸包划分为多个独立的子区域,然后对相邻两个凸包之间的子区域进行三角剖分,从而实现对整个原始两维区域的三角剖分.和以往得算法相比,提出的算法的时间效率大大提高了,并且在作者参与的军队2110建设项目应用中也体现了良好的效果.     

一种快速三维散乱点云的三角剖分算法

改进了一种三维散乱点云三角剖分算法。三角剖分是点云数据曲面重构的主要算法之一,但针对三维散乱点云的三角剖分存在剖分效率不高,剖分得到的三角曲面形状无法控制,细节特征表现不足的问题。提出了基于空间栅格划分的三角剖分算法,并提出了一个新的评价函数,以控制三角网格曲面的生长。实验证明,改进后的算法极大的提高了剖分效率,而且能保证最终生成的三角网格曲面平滑而保有丰富的细节特征,适用于在虚拟现实、曲面重构等领域推广使用。     

三维约束Delaunay三角化的实现

分析了约束Delaunay三角化中存在的边界一致性问题,给出了约束Delaunay三角化的理论依据,重点探讨了三维约束Delaunay三角化的可行性条件和范围,同时,给出了三维有限域约束Delaunay三角化的实现方法及其在石油地质勘探数据和机械零件方面的网格剖分实例.这种算法在复杂对象的科学计算和工程分析中发挥了重要作用.     

Delaunay三角网构建方法比较研究

Delaunay三角网构建是3维场景可视化领域的一个热点也是难点问题。归纳总结了现有Delaunay三角网构建研究中的3类方法——逐点插入法、三角网生长法和分治法,以及在各自原理框架下的不同实现算法;比较分析了3种不同方法的优缺点和各自代表性算法的时间复杂度,并详细讨论了Delaunay三角网构建方法在大规模场景渲染和地形可视化领域中未来3个研究方向：混合算法研究、算法支撑技术研究和分布式并行算法研究。     

三维约束Delaunay三角化的研究

概述了约束三角化的研究进展,着重分析了三维约束Ｄｅｌａｕｎａｙ三角化中存在的问题,提出并论证了边界边、边界面片在Ｄｅｌａｕｎａｙ三角化中存在的条件,讨论了存在性条件在实际工程中的应用范围,充实了三维约束Ｄｅｌａｕｎａｙ三角化的研究基础,为三维Ｄｅｌａｕｎａｙ三角化算法的设计提供了理论依据。     

A note on lee and schachter's algorithm for delaunay triangulation

Lee and Schachter have presented an algorithm for the Delaunay triangulation of a set of points whose convex hull is a rectangular region. An addendum to that algorithm is presented which gives the Delaunay triangulation of a set of points with an arbitrary convex hull. Timing results are also given.     

任意多边形内带特征约束的散列数据的最优三角剖分

给出了一种新的基于Ｄｅｌａｕｎａｙ三角形化的任意多边形边界内散列数据的优化三角剖分算法，该算法可允许散列数据任意复杂的折线及封闭多边形环的特征约束。算法用统一的数据结构来记录散列数据、约束特征和三角剖分信息，并且引入了辅助窗的概念，从而使优化剖分和加入约束容易实现。     

基于分类体数据的四面体网格剖分算法

虚拟内窥手术是以真实病人的CT或者MRI扫描数据为基础，首先通过组织分割，在计算机内部建立起三维模型，然后通过虚拟现实技术来模拟窥镜手术全过程的一项技术。其中，人体器官的三维网格建模是该技术中一个十分重要的部分，为了准确地进行了人体器官三维网格建模，在对三维体数据进行组织分割的基础上，提出了一种由分类体数据直接建立三维四面体网格的方法，由于Delaunay三角剖分所产生的网格质量比较高，所以该方法沿用逐点插入算法的思想，以特征点的提取和Steiner布点为基础来生成四面体网格，并通过组织边界的判定准则和利用flip操作来恢复组织边界，实践证明，该方法所生成的网格具有自适应的网格密度。     

三维点集Voronoi图的算法实现

对现有三维点集Voronoi图的生成算法进行深入研究，提出并实现由Delaunay三角剖分构建Voronoi图的算法．首先采用随机增量局部转换计算Delaunay三角剖分，然后再根据对偶特性构建Voronoi图．该算法健壮性很高，适用于处理各种非完全共面三维点集．     

简单多边形快速Delaunay三角剖分算法

简单多边形的Delaunay三角剖分,在计算机图形学及地学问题三维建模领域有着广泛的应用。文中在借鉴他人的基础上,提出了一种时间复杂度为O(mn)的基于三角形权值最大的简单多边形Delaunay三角剖分算法。三角剖分结果中的三角形形态达到了最优或次优,并进行了理论上的严格证明,对算法的时间复杂度进行了分析,并给出了一个实例。实验结果表明,该方法对于随机生成的简单多边形域三角化速度快,平均计算时间呈近似线性。     

高阶Delaunay三角网及生成算法研究

Delaunay三角剖分是构建数字地形模型的有效方法,但是该方法会引起人工大坝和局部极值问题,使得地形模型不能很好地反映原始地形的真实面貌。在Delaunay三角网的基础上提出了一种高阶Delaunay三角网,并给出了高阶Delaunay三角网生成算法。实验结果表明,高阶Delaunay三角网能够有效地减少地形中局部极小的数量,因此,采用高阶Delaunay三角网建立的地形模型更接近于实际地形。     

实现约束Delaunay三角剖分的健壮算法

相对于标准的Ｄｅｌａｕｎａｙ三角剖分，本文给出了复杂区域三角剖分所应满足的两个约束条件及相应的基于轨迹生成和边界裁剪的剖分算法，并证明了该算法符合约束圆准则，文中详细分析了退化及数值误差对剖分结果的影响，着重在提高算法健壮性方面，对该算法做了进一步完善，使它能够完全满足散乱据场网格剖分的分析。