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

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

基于Delaunay三角网的任意多边形三角剖分算法研究

文章通过分析现有多边形三角剖分算法,给出一种基于Delaunay三角网的任意复杂多边形三角剖分的改进算法。算法首先忽略多边形顶点与边线间的逻辑关系,将其看做散乱顶点的集合,然后采用Delaunay三角化方法对点集进行合理剖分,再依据多边形顶点及边线间的逻辑关系,逐一将那些不合理的三角网剔除,最终重新组合出符合要求的三角网格。     

带特征线约束的Delaunay三角剖分最优算法的研究及实现

为了提高特征线约束的Delaunay三角剖分的速度和功率,从两个方面进行改进;一是生成无约束的Delaunay三角网时,采用进行剖分算法;二是在约束线上插入点时,应用取三角形外接圆与特征线交点的方法。并行剖分算法具有较好的加速性能;“交点”插入算法考虑了特征线的影响域及Delaunay三角形规则的边界条件,在满足全局Delaunay三角剖分的前提下,使插入的点最少,对原有的网格影响最小。     

GIS中TIN模型的实现算法

文章在总结采用前人的三角剖分算法的基础上,提出了一种快速,有效,由不规则点集生成TIN的算法,并通过Visual C++语言实现.所生成的三角网满足Delaunay准则;并通过实例验证了算法的有效性.     

三维散乱点云快速曲面重建算法

提出了一种基于Delaunay三角剖分的三维散乱点云快速曲面重建算法。算法首先计算点云的Delaunay三角剖分, 从Delaunay四面体提取初始三角网格, 根据Voronoi体元的特征构造优先队列并生成种子三角网格, 然后通过区域生长的方式进行流形提取。实验结果表明, 该算法可以高效、稳定地重构具有复杂拓扑结构、非封闭曲面甚至是非均匀采样的点云数据。与传统的基于Delaunay的方法比较, 该算法仅需要进行一次Delaunay三角剖分, 无须极点的计算, 因此算法的重构速度快。     

通用点线面集Delaunay三角剖分与动态编辑

总结并提出了一种通用点线面集Delaunay三角剖分与动态编辑的统一算法。可以实现离散点的Delaunay三角剖分,约束线、面的Delaunay三角剖分,任意多边形内带特征约束(包括点、线、面)的三角剖分,一般Delaunay三角剖分的外边界都是其离散点集的凸包,且内岛屿一般没有挖掉,本算法实现了Delaunay三角剖分时内、外边界的保界处理。     

基于最优凸壳技术的Delaunay三角剖分算法

提出了一种基于最优凸壳技术的Delaunay三角剖分算法。该算法对离散点进行扫描线方式排序,利用最优凸壳技术进行凸壳的生成和三角网联结,最后利用有向边的拓扑结构进行三角网优化。该算法不但避免了所有的交点测试,而且使得新加入点与凸壳边的平均比较次数不大于4,从而实现了高效的三角剖分。     

基于格网划分的Delaunay三角剖分算法研究

为了提高海量数据的Delaunay三角网的构网速度,本文采用格网划分的三角剖分方法,首先将数据按照线性四叉树方式划分为若干格网块,构建块内子三角网,然后按照自下而上的合并方式对块进行合并,形成全局Delaunay三角网。在此基础上,为了避免出现过小锐角的情况,通过加入约束角来对三角格网进行优化。     

基于Delaunay三角剖分的半径补偿新算法

合理的半径补偿算法能有效提高逆向工程的最终精度.在分析了现有半径补偿算法及其相应优缺点的基础上,针对三角网格法,通过Delaunay三角剖分思想的引入,提出了一种基于Delaunay三角剖分的半径补偿新算法,并对其中三角剖分的优化准则、边界点的处理等关键技术进行了详细的阐述,最后以增压器叶轮为例,实现了叶轮叶面测量数据的半径补偿.     

基于Bowyer-Watson三角网生成算法的研究

不规则三角网（Triangulated Irregular Network,TIN）在表示地形的形态方面具有较好的表现,其生成算法一直备受关注。讨论了三角网的数据结构的设计,采用逐点插入算法中的Bowyer-Watson算法思想为研究重点,设计并实现了该算法,对算法实验过程中可能出现的交叉现象进行分析,给出算法的改进。该改进算法已用于地形的可视化建模中,获得了较好的效果,对于三角剖分的相关研究具有一定的价值。     

基于特征线梯度约束SFS的月面地形重构方法

针对月面着陆器在下降过程中可能得不到足够的匹配点进行着陆区地形恢复的问题,提出了基于特征边缘线梯度比例约束的明暗恢复形状(shape from shading)算法。以Lommel-Seeliger反射模型模拟月球表面反射情况,建立辐照度方程。以地形特征边缘提取结果为基础,经过最小二乘拟合后,求解临近点的梯度比例因子,并通过表面光滑模型约束,演化得到剩余影像点的梯度比例因子,实现了对辐照度方程的量化约束,使得SFS问题正则化。采用模拟影像和真实月面影像对所提出的算法进行了测试分析,实验结果表明,所提出的算法能够有效的进行三维地形恢复,且恢复精度优于经典SFS算法中对实际地形恢复效果最好的Tsai算法。     

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

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

基于标准差的地形三维表面模型建立方法*

针对二维数据域的Delaunay三角剖分推广到空间时存在的关键问题,提出一种基于标准差的地形三维表面模型建立算法.与空外接圆准则相比,该算法在计算时考虑了附加高程信息,引入标准差作为构网判断准则.剖析了标准差的含义,为什么使用标准差以及基于标准差的剖分准则,最后给出基于标准差的地形三维表面模型建立算法的具体步骤,并通过一个具体实例对算法进行了验证.     

基于Loose r-sample的网格质量保持技术

为保证虚拟手术系统中的网格质量,提出一种基于Loose r-sample理论的快速表面网格重建算法。记录满足Loose r-sample采样定理的点集,用以描述物体的轮廓。通过约束Delaunay方法对该点集进行三角化,标记顶点和Delaunay单元,重构新的网格。实验结果表明,该算法能够保证生成网格的质量,简化仿真复杂度。     

DEM生成算法并行化研究

数字高程模型DEM（Digital Dlevation Model），是一种表示三维空间连续起伏状态的数学模型，如今在各行业应用十分广泛。针对DEM生成过程中计算复杂、数据量大的特点，在分析几种常用的DEM生成算法的基础上，以线性内插算法为样本，对DEM生成算法的并行化处理问题进行了深入研究。研究中，分别从数据并行和算法并行的角度，对DEM生成算法并行化进行了分析，并在网络分布式机群下进行了数据处理实验，取得了较好的并行处理效果。最后，进一步根据实验结果，讨论了责任发解方法的并行效率，提出了DEM生成算法并行化的有效途径。     

Delaunay三角网高效构建及地形仿真应用

针对基于离散点的Delaunay三角网构建过程中待插入点的定位耗时问题,提出Delaunay三角网高效构建算法,并将其用于三维地形仿真应用中。对大量数据点进行分块排序预处理后,运用空间自相关理论使下一个待插入点总是紧邻新近插入点,融合最短路径定位算法和三角形面积法,结合三角形重心与点、有向线段的关系遍历三角形,减少遍历时间。在对三角网进行LOP局部优化时,采用Delaunay四叉树保存待调整的所有边的节点信息,提高遍历效率。实验结果证明,该算法构建的三维地表真实感较强,并且具有较低的时间复杂度。     

SAR imaging simulation for an inhomogeneous undulated lunar surface based on triangulated irregular network

Based on the statistics of the lunar cratered terrain, e.g., population, dimension and shape of craters, the terrain feature of cratered lunar surface is numerically generated. According to the inhomogeneous distribution of the lunar surface slope, the triangulated irregular network (TIN) is employed to make the digital elevation of lunar surface model. The Kirchhoff approximation of surface scattering is then applied to simulation of lunar surface scattering. The synthetic aperture radar (SAR) image for comprehensive cratered lunar surface is numerically generated using back projection (BP) algorithm of SAR imaging. Making use of the digital elevation and Clementine UVVIS data at Apollo 15 landing site as the ground truth, an SAR image at Apollo 15 landing site is simulated. The image simulation is verified using real SAR image and echoes statistics. Supported by the National Matural Science Foundation of China (Grant No. 40637033)     

基于图片序列的三维表面重建

根据非透明物体内部不可见的实际,提出了一种基于图片序列的三维表面重建算法.该算法首先利用传统的八叉树算法重建出物体的三维模型,然后利用一种新颖的表面点提取算法提取出物体表面点,最后利用这些表面点进行三角网格剖分,进而重建出光滑的三维物体表面.在表面点的提取过程中,算法对处于不同状态(处于立方体的顶点、棱、面)的点赋予不...     

一种面向三维点集的快速表面重构算法

在对目前比较流行的空间三角化算法进行对比研究的基础上 ,对 Hugues Hoppe提出的算法进行了改进 ,即借鉴 Marching Cubes算法的基本思想 ,首先通过自动选取适当的参数 ,用包围盒方法将三维散乱点划分为数据区域 ;然后求取点的切平面及法向 ,同时采用广度优先算法遍历数据点来调整法向和快速地求取 Marching Cubes的等势函数 ;最后用基于查表法的 Marching Cubes来输出三角面片 ,即得到表面模型 .实验结果表明 ,改进后的算法效率有较大的提高 .新算法不仅适用于表面三维散乱点数据 ,也可以对体数据进行重构 ,具有一定的通用性 .