Voromoi图和Delaunay三角剖分的计算及应用

论述了Ｖｏｒｏｎｏｉ图及其几何对偶Ｄｅｌａｕｎａｙ三角剖分的计算方法，重点探讨了Ｄｅｌａｕｎａｙ三角剖分的优化性质及其有限元网格自动生成过程中的应用，在此基础上提出了一种自动生成三角形有限元网格的新算法。     

三角网格中的孔洞修补算法

提出一种三角网格中的孔洞修补算法, 先应用最小内角原则, 对孔洞直接进行三角剖分得到孔洞剖分的新三角形集合, 然后依据孔洞边界顶点密度, 应用圆和最大内角优化原则, 对新三角形集合进行加点细分得到初始补丁网格, 最后应用λ-μ方法对初始补丁网格进一步优化, 得到最终的补丁网格. 实验结果表明, 该算法效率高、 准确性好.     

一种基于重新划分的三角形网格简化方法

提出了一种基于重新划分的三角形网格简化算法。该算法的基本思想是:根据模型特征或由用户定义一定数量的新点,再根据某些原则将新点分布到原模型上,生成一个中间网格。然后移去生成的中间网格中的旧项点并对形成的多边形区域进行带约束的三角剖分,最后形成以新点为顶点的三角形网格。     

混凝土随机颗粒模型的网格自动剖分方法

基于计算几何学原理,用一容易被广大工程技术人员接受的方法,实现了对混凝土随机颗粒模型三角形有限元网格的自动剖分,这个网格可以被各种微值方法所采用,同时自动形成Ｖｏｒｏｎｏｉ图的方法,也可在工程中广泛利用。     

基于Delaunay三角剖分的指纹识别

针对指纹识别过程中指纹匹配算法的准确性以及识别效果等问题, 结合计算几何中Delaunay三角剖分方法的特点, 将其引入指纹匹配处理, 提出一种基于三角网格的指纹匹配方法.该方法通过对细节点的拓扑结构进行三角划分, 得到三角形网格.最后利用三角形的几何不变性按照匹配与配型两个步骤进行指纹识别.经实验验证该方法是一种行之有效的指纹匹配方法, 有效地提高了最终的识别效果.     

基于三角剖分和轮廓分析的船舶焊缝特征识别

为了实现船舶焊接件数字模型中焊缝特征的精确识别,进而提高焊接机器人焊接工艺选择的快速性和准确性,提出了基于三角剖分和轮廓分析的焊缝特征识别算法。首先通过角系数法判断多边形的凹凸顶点,基于凹顶点和三角形旋向的Delaunay三角剖分,构造三维模型表面的三角形网格并生成STL文件；然后基于相邻三角面片的法向量夹角,提取出模型的轮廓线及点；最后根据接头空间位置和最小轮廓线距离识别出焊接接头和坡口形状。测试结果表明,基于三角形旋向的网格剖分适用于如“梳子”等复杂多边形,与其他相关方法相比,其网格平均和关联质量系数分别平均增加12.06%和12.26%,有效降低了畸形三角形的产生并提高了网格质量,而融合轮廓分析后不仅能实现4类接头及10种坡口的焊缝特征识别,而且具有高效、高准确率优势,从而验证了算法的有效性。     

一种改进的螺旋边三角剖分算法

提出了一种改进的螺旋边三角剖分算法.本算法引用“自然邻近点集”的概念,以螺旋边三角剖分算法的边界环为基础向外生长三角形,以包围盒算法搜索边界点的邻近点集,估计边界点的法向量,将边界点及其邻近点集投影到切平面上并进行局部二维Delaunay三角剖分,从而确定边界点的自然邻近点集,最后将自然邻近点集以适当的方式添加到边界环上.这样,既避免了拼接问题又能搜索到自然邻近点集,三角剖分后的网格基本上接近最优Delaunay网格.实验结果表明,本算法能高效、稳定地重构出散乱数据点的三角网格.     

基于参数模型两种剖分方式的射线追踪比较

 通过对比研究参数模型矩形和三角网格两种剖分方式的射线追踪正演过程，指出基于三角网格剖分参数模型的射线追踪具有如下特点：① 参数模型和反射界面定义具有一致性，可在界面的处理上提高精度；② 剖分网格个数相对矩形网格剖分方式大大减少，可大大减少计算量和存储量；③ 运行变量的选择与网格内平方慢度的三参数表述形式相结合，使得在射线追踪过程中参数的更新量表达式相当简洁。因而基于参数模型三角网格剖分方式的射线追踪具有更快的计算速度和更高的计算精度。     

一种改进的区域增长三角剖分方法

传统的区域增长三角剖分方法很难保证含有尖锐边界的物体表面网格剖分的正确性,针对这一问题,本文提出一种改进的区域增长三角剖分方法。通过引入并计算边界边的权值来确定网格生长的方向,网格生长过程是由权值小的边逐步扩展到权值大的边,从而实现物体表面由"平坦"到"不平坦"的剖分过渡,并且相应的网格拓扑操作及队列更新机制保证了边界边队列的正确性。实验表明,该方法能生成反映原始物体表面形状的三角网格,并成功实现了对含有尖锐边界的物体表面的三角剖分。     

多边形区域内储层建模结点三角剖分算法研究

结合储层建模结点数据的特点 ,提出了一种对多边形区域内建模结点数据进行快速三角剖分的算法 .如果区域边界边与剖分三角形可能相交 ,根据边界边顶点与剖分三角形确定的矩形区域的关系 ,对于不同情况 ,通过计算矢量叉积 ,或最坏情况下通过计算交点 ,来确定边界边与剖分三角形是否真正相交 .同时 ,讨论了在剖分过程中 ,对边界边链表进行实时更新 ,逐步减少边界边的思路 .虽然整个算法的时间复杂度最坏情况为 O( 3× m×n) ( m为多边形区域内结点形成的三角形个数 ,n为边界边个数 ) ,但在实际应用中 ,对大批量的储层建模结点数据进行三角剖分时 ,文中提出的算法具有比较高的处理效率     

面向大规模科学计算的三维Delaunay快速插点算法

该文提出一种快速、稳定的Delaunay插点算法.这一算法提高了单机有元建模的规模,可在PC计算机生成千万级有元四面体网格.算法通过点与点之间位置关系,建立对位置信息;据这些信息在查找BASE单元时,提高＂walk-through＂点定位算法的速度.而在生成新单元和建立邻接关系过程中,算法利用CORE表面的三角网格,在性时间内完成CORE附近的新旧单元更新操作,并出算法时间复杂度证明.本文以分别以空间任意点集、正文体删格和机械模三角面片为例,测试应用Delaunay逐点插入算法.算例表明,本算法在一台Intel（R） Core（TM）2 Duo CPU E7200@2.53GHz,1.98GB内存的PC上可生成千万单元量级四面体网格,生成速度达11-15万单元/秒.     

三角网自动连接的聚焦算法

在三角网生长法的基础上，采用面向对象的技术，利用点数组和点索引数组来存贮平面上的散乱数据点，基于Delaunay三角剖分的“圆准则”，提出三角网自动连接的聚焦算法．该算法在扩展新三角形时，将点的搜索范围控制在已知三角形的外接圆内，计算速度大大加快．从给出的算例表明，该算法十分有效，特别适合于大数据量的三角剖分。     

散乱数据点的NURBS曲面重建算法

给出了一个新的散乱数据的NURBS曲面重建算法．算法充分利用邻近点集反映出的局部拓扑和几何信息，基于二维Delaunay三角剖分技术快速地实现每个数据点的局部拓扑重建．然后通过自动矫正局部数据点的非法连接关系，把局部三角网拼接成一张标准NURBS网格．结果表明，本算法非常高效、稳定，可以快速地直接重构出任意拓扑结构的NURBS三角形网格。     

一种高效构建Delaunay三角网的算法

提出了一种基于改进的Graham扫描法的分块构建不规则三角网算法。采用分割合并的思想,先对平面上的离散点集区域进行分块,然后对各个子块用改进的Graham扫描法生成不规则三角网,再从边界边出发依次合并相邻的三角网子集,直到所有子集合并结束。本算法采用分块的思想缩小了构网时的搜索范围,对子块用改进的Graham法生成三角网提高了算法性能。实验结果表明,本算法使构网效率有很大的提高。     

点云数据三角网格生成算法及应用

在引入局部Delaunay边和局部Delaunay三角形的基础上,给出一种平面及空间散乱数据点集的三角网格生成的快速算法,实验表明本算法具有运行速度快、计算准确、存储简单等优点.     

任意采空区边界信息处理与有限元网格生成

建立了任意形状采空区边界信息的管理规则，以已知漏风边界的剖分精度作为区域网格密度函数的依据，用前沿生成法的网格剖分技术自动生成Delaunay三角形单元。优先处理最长前沿边，网格节点间距密度按该边距条件边界的距离的线性函数，来控制区域内网格的尺寸变化，最终实现区域内部网格的疏密逐渐过渡，采用Laplacian优化法进行光顺处理，进一步改善了三角形质量。算例表明，可按任意采空区形状和精度自动生成三角单元，调整方便。     

一种新的四边形的生成算法

Q-Morph算法在用Delaunay方法形成三角网格的基础上，利用已有的网格拓扑关系，提出一种新的四边形生成算法。采用边界推进法来生成四边形网格。该算法生成的网格具有边界敏感性和方位不敏感性，并且能极大地减少网格中不规则点，很大程度上提高了网格质量。     

Parameterization for fitting triangular mesh

In recent years, with the development of 3D data acquisition equipments, the study on reverse engineering has become more and more important. However, the existing methods for parameterization can hardly ensure that the parametric domain is rectangular, and the parametric curve grid is regular. In order to overcome these limitations, we present a novel method for parameterization of triangular meshes in this paper. The basic idea is twofold: first, because the isotherms in the steady temperature do not intersect with each other, and are distributed uniformly, no singularity (fold-over) exists in the parameterization; second, a 3D harmonic equation is solved by the finite element method to obtain the steady temperature field on a 2D triangular mesh surface with four boundaries. Therefore, our proposed method avoids the embarrassment that it is impossible to solve the 2D quasi-harmonic equation on the 2D triangular mesh without the parametric values at mesh vertices. Furthermore, the isotherms on the temperature field are taken as a set of iso-parametric curves on the triangular mesh surface. The other set of iso-parametric curves can be obtained by connecting the points with the same chord-length on the isotherms sequentially. The obtained parametric curve grid is regular, and distributed uniformly, and can map the triangular mesh surface to the unit square domain with boundaries of mesh surface to boundaries of parametric domain, which ensures that the triangular mesh surface or point cloud can be fitted with the NURBS surface.     

有限元网格全自动生成中的初始三角化新方法

基于Ｄｅｌａｕｎａｙ三角化技术提出了一种快速可靠的全自动初始三角化新方法，给出了一种简单有效的边界约束施加方法，所给出的实例表明了所提出的初始三角化方法的性能．