点序对Delaunay三角剖分局部优化的影响

局部变换法和Watson算法是属于逐点添加、局部优化的离散点集Delaunay三角剖分的常用方法,不同的加点次序对这两种算法的局部优化影响较大。研究发现按位置相邻次序加点的方法易产生外接圆较大的扁平三角形,引起较多三角形的局部优化,而按随机次序加点,网格生成过程中网格单元相对匀称,局部优化的三角形较少。以激光点扫描采集的数据为例,统计分析了局部优化三角形的数量及分布特征,点数大于50000时,相邻次序加点方法局部优化三角形的总量是随机次序加点方法的1.6倍以上。建立离散数据的矩形空间索引,按索引轮流加点,点序对局部优化的影响降低,相邻次序加点方法局部优化的三角形总量是随机次序加点方法的1.1~1.3倍,其中随机次序加点与没有空间索引的随机次序相比,局部优化的三角形数量仅增加了约1%。     

一种基于点云数据的快速曲面重构方法

研究激光扫描中的点云数据重构技术,提出一种基于规则点云数据的快速曲面重构方法。分析相邻扫描线之间数据点的相对位置关系,在三角剖分的基础上,设计改进的扫描线剖分算法,根据激光逐行扫描的特点,对点云数据进行不规则三角网格划分,利用几何关系进行配对构网,并在所建三角模型的基础上实现三角网格的局部优化和纹理映射,得到重建模型。实验结果表明,与传统Delaunay空间三角剖分算法相比,该算法可明显提高三角构网速度和质量,消除空洞,改善重建效果。     

基于图的任意域内点集的Delaunay三角剖分算法

本文提出了一种基于图的二维任意域内点集的Ｄｅｌａｕｎａｙ三角剖分算法．该算法首先求出任意域内点集的约束最小生成树，然后逐次加入一边构造三角形网格，最后通过局部优化变换，得到二维任意域内点集的Ｄｅｌａｕｎａｙ三角剖分．本文还给出了该算法在有限元网格自动生成过程中的应用.     

点与三角形位置关系对三角网格拓扑的影响

逐点添加、局部优化的Watson算法和局部变换法是生成大规模离散点集Delaunay三角网格的常用方法。点与三角形位置关系判别和三角形外接圆包含点的测试分别是局部变换法和Watson算法正确生成Delaunay三角网格的重要环节。计算误差会导致点与三角形位置关系以及三角形外接圆包含点的错误判别,从而生成几何拓扑关系不正确的三角网格。采用相对位置坐标可以提高面积坐标和外接圆圆心、半径的计算精度。以等高线地图采集的地形数据为例,用改进的算法生成了包含393252个离散点的Delaunay三角网格。     

约束三角剖分在雨量等值线的应用

雨量等值线在水文、防汛领域应用广泛,Delaunay三角剖分具有空外接圆和最大的最小角度两个良好性质,对于非规则分布的离散点数据进行三角剖分内插是生成等值线的最常用的算法,但实际应用中往往都术是凸壳进行三角化,而是有限定边（或限定点）对三角剖分进行约束。该文在标准Delaunay三角剖分基础上,分析了逐点插入法的基本原理,基于此提出了一种解决有限定边的约束三角网格剖分生成等值线的方法,给出了限定边进行三角剖分的算法,同时对边界采用网格加密和邻域内插算子进行边界附件插值,提高等值线的边界拟合精度,并在雨量等值线生成中得到较好应用。     

基于贪心算法与多边形剖分的印鉴匹配算法

将计算几何中平面点集的三角剖分方法之一贪心算法与多边形三角剖分方法引入印鉴匹配,研究了一种基于三角网格(用贪心算法进行平面点集的三角剖分)的印鉴匹配方法.用贪心算法对基于线条的细节点集进行三角剖分,而对于基于多边形的细节点直接进行多边形的三角剖分.通过对两种细节点(基于线条的细节点和基于多边形的细节点)的拓扑结构进行三角划分,把空间上位置相近的细节点按照一定的规则相连,得到三角形网格.然后基于该网格寻找若干参考点对,并根据获得的参考点对将两幅印鉴图像进行姿势调整.最后使用获得的参考点时实现基于点模式的印鉴匹配,经分析该方法是一种行之有效的印鉴识别方法.     

约束三角剖分在雨量等值线的应用

雨量等值线在水文、防汛领域应用广泛,Delaunay三角剖分具有空外接圆和最大的最小角度两个良好性质,对于非规则分布的离散点数据进行三角剖分内插是生成等值线的最常用的算法,但实际应用中往往都不是凸壳进行三角化,而是有限定边(或限定点)对三角剖分进行约束。该文在标准Delaunay三角剖分基础上,分析了逐点插入法的基本原理,基于此提出了一种解决有限定边的约束三角网格剖分生成等值线的方法,给出了限定边进行三角剖分的算法,同时对边界采用网格加密和邻域内插算子进行边界附件插值,提高等值线的边界拟合精度,并在雨量等值线生成中得到较好应用。     

高精度自适应的四边形网格重建

提出了海量数据点集的四边形网格重建算法。首先根据精度要求简化数据 点,按一定规则连接相邻的简化数据点生成多边形网格,对网格中高斯曲率较大的顶点进行 局部细分提高其精度,然后对多边形网格进行整体细分使其全部转化为四边形网格,最后分 裂度较大的顶点对其进行优化。实验结果表明,算法对拓扑结构较为复杂的海量数据点集的 四边形网格重建是行之有效的。     

针对密集点云的快速曲面重建算法

为了能够快速地从高密度散乱点云生成三角形网格曲面,提出一种针对散乱点云的曲面重建算法.首先通过逐层外扩建立原始点云的近似网格曲面,然后对近似网格曲面进行二次剖分生成最终的精确曲面;为了能够处理噪声点云,在剖分过程中所有网格曲面顶点都通过层次B样条进行了优化.相比于其他曲面重建方法,该算法剖分速度快,且能够保证点云到所生成的三角网格曲面的距离小于预先设定容限.实验结果表明,文中算法能够有效地实现高密度散乱点云的三角剖分,且其剖分速度较已有算法有大幅提高.     

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

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

一种基于改进 PointNet++网络的 三维手姿估计方法

针对 PointNet++网络处理点云局部特征时因分组范围区过大导致计算量较大的问题,提出一种改 进的 PointNet++网络的三维手姿估计方法。首先对手势点云进行基于 Delaunay 三角剖分算法与 K 中位数聚类算 法相结合的三角剖分,得到手势点云的三角网格模型,并计算三角网格模型的边长均值;然后以三角网格模型边 长均值为半径,对最远点采样(FPS)的采样点进行球查询搜索,再根据搜索到的采样点个数极值对采样点云进行 K 近邻分组,并最终输入 PointNet 网络,完成三维手姿的位置估计。改进后的 PointNet++网络可以根据不同的点云 密度自动调整网络分组区域的局部提取点个数。实验结果表明,在不影响三维手姿估计精度的情况下,该方法提 高了 PointNet++网络的模型训练速度,并在三维手姿估计中可有效减少特征提取的计算量,使计算机能够更快地 捕捉手姿状态。     

基于局部—全局方法的三角网格优化算法

在基于网格形变的图像缩放算法中,表示图像的网格质量对于这类算法的结果有着很大的影响。为了改善图像网格质量,提出一种基于局部—全局方法的平面三角网格优化算法。在局部阶段利用自定义的最相似规则,为网格中的每一个三角形单元求取与之最相似的正三角形,得到一组目标仿射变换函数;全局阶段采用尽可能刚性方法,利用最小二乘法求取一组满足最小变形能量函数的最优解,使得最终生成的网格由尽可能相似于正三角形的三角形构成。同时,在优化过程中加入约束控制,保护网格中的重要区域不发生改变。实验结果表明,优化后的网格质量得到了明显的改善,有助于图像缩放算法后续工作的进行。     

结合间接邻域的散乱点云三角网格曲面重构

对于非均匀散乱点云,多数基于区域生长方法的曲面重构往往容易出现孔洞等缺陷。针对该问题,在K邻域点集的基础上提出间接邻域点集的概念,对以点为生长对象进行区域生长的三角网格曲面重构方法进行了研究,实现三角网格曲面重构。以生长点的邻域点集为样点估算微切平面,将邻域点投影至该平面上,并按照右手定则、逆时针方向进行排序,通过拓扑正确性原则从点列中去除错误的连接点,优化局部网格,选择较好的连接点,实现网格曲面的区域生长。     

三维地质界面网格模型构建算法研究

三维地质模型主要包含地质构造模型和地质属性模型。提出一种局部映射-边界控制的曲面三角化网格模型构建算法,与映射法相比,减少三维空间点映射到二维平面的计算过程,避免因多点到一点的映射关系而生成错误的三角化网格模型。基于地质测量数据特点,原始地质数据经处理后采用点集合形式表示,基于点集数据构建三维三角化网格模型,模拟地质界面的展布形态,控制三角网格质量。采用两种网格边界控制方法,在有边界约束数据和无边界约束数据条件下均能自动更新地质界面三角化网格模型边界。基于断层点数据集测试并展示算法构建的三维三角化网格模型可视化效果,通过断层面三角化网格模型能够反映断层面之间空间位置关系。     

A hybrid ant colony optimization approach for finite element mesh decomposition

This paper examines the application of the ant colony optimization algorithm to the partitioning of unstructured adaptive meshes for parallel explicit time-stepping finite element analysis. The concept of the ant colony optimization technique for finding approximate solutions to combinatorial optimization problems is described.The application of ant colony optimization for partitioning finite element meshes based on triangular elements is described.A recursive greedy algorithm optimization method is also presented as a local optimization technique to improve the quality of the solutions given by the ant colony optimization algorithm. The partitioning is based on the recursive bisection approach.The mesh decomposition is carried out using normal and predictive modes for which the predictive mode uses a trained multilayered feed-forward neural network which estimates the number of triangular elements that will be generated after finite elements mesh generation is carried out.The performance of the proposed hybrid approach for the recursive bisection of finite element meshes is examined by decomposing two mesh examples.     

Adaptive triangular-mesh reconstruction by mean-curvature-based refinement from point clouds using a moving parabolic approximation

We use a moving parabolic approximation (MPA) to reconstruct a triangular mesh that approximates the underlying surface of a point cloud from closed objects. First, an efficient strategy is presented for constructing a hierarchical grid with adaptive resolution and generating an initial mesh from point clouds. By implementing the MPA algorithm, we can estimate the differential quantities of the underlying surface, and subsequently, we can obtain the local quadratic approximants of the squared distance function for any point in the vicinity of the target shape. Thus, second, we adapt the mesh to the target shape by an optimization procedure that minimizes a quadratic function at each step. With the objective of determining the geometrical features of the target surface, we refine the approximating mesh selectively for the non-flat regions by comparing the estimated curvature from the point clouds and the estimated curvatures computed from the current mesh. Finally, we present various examples that demonstrate the robustness of our method and show that the resulting reconstructions preserve geometric details.     

激光三维扫描数据的表面重建

对激光三维扫描系统获得的没有任何附加信息的轮廓线点云数据进行处理，首先采用求最大连通域的方法删除噪声点，利用设定相邻点连线夹角正切阈值的方法精简数据，然后采用基于局部切平面簇的方法对数据点云进行切平面的估算、法向量的调整和计算距离函数，用改进的MC方法输出三维网格，并且应用基于顶点的网格删除算法对三维网格进行简化，在估算切平面的时候采用新的估算原则，提高了重建速度，改善了重建效果，所表述的重建流程，成功地解决了激光扫描系统所得轮廓数据点的表面重建问题。     

在任意拓扑三角形网格上的光滑样条曲面

介绍了一种在控制三角形网格上创建光滑样条曲面的算法,该控制网格能够刻画具有或没有边界的任意自由曲面.生成的曲面有一个4次参数多项式表示并且被表示成一个切平面连续的三角形Bézier片网.曲面对网格的逼近程度受到一个混合比控制,当混合比为0时,产生的曲面插值网格.该算法是一种局部方法,简单且效率高,适合于外形设计.