Delaunay算法的研究与探讨

计算机图形学是一种用数学算法将二维或者三维图形转化为计算机显示器的栅格形式的科学。其主要研究的基本内容就是如何在计算机中表示出图形,或怎样利用计算机来进行图形的计算处理以及显示的原理和算法。当前,在计算机图形学中,科学可视化是最活跃的分支之一,得到普遍的应用。特别是地质领域,其地质研究和工程勘查领域都离不开可视化技术,众多的珍贵地层钻探数据必须用有效的方式进行直观地表达。Delaunay三角网是一种主要的数字地形模型表示法,它经过二十多年的发展,其生成算法已日趋成熟。因此,就Delaunay的基本概况、Delaunay方法的基本原理、Delaunay三角网生成算法、合成算法的研究与实现四个方面来对Delaunay算法探究。     

基于数字地面模型的立式金属罐底量测量方法研究

针对如何准确测量出发生不规则变形的立式金属罐底量,提出一种基于数字地面模型的测量方法,该方法通过解算由罐底三维坐标点构建的不规则三角网所对应体积而求出罐底量。所构建不规则三角网能够以等高线形式完整表达罐底的起伏特征,为后期罐底变形研究提供参考。实验中以容量比较法为标准,对几何测量法和数字地面模型测量法进行对比实验研究,结果表明该方法适用于立式金属罐的底量测量,相对误差较几何测量法平均降低了2.5%。     

随机中心聚集半色调算法

目的由误差扩散半色调算法得到的二值图像存在明显的规律性纹理,针对该问题提出随机中心聚集半色调算法。方法利用蓝噪声半色调阈值矩阵算法生成随机均匀分布的种子点,采用三角网生长算法构建Delaunay三角网格,在确定三角网像素成员后,根据像素点在三角形区域内的分布位置得到该位置像素的阈值,最后通过将连续调图像与阈值矩阵的阈值比较得到半色调图像。结果同误差扩散算法相比,提出的方法可以减少半色调图像的人工纹理,图像视觉效果较好。结论文中算法可以改善半色调图像质量,实验结果证明了该方法的有效性。     

基于规则格网的地图等高线快速追踪算法

地图中等高线是表达地貌起伏形态的有效方法。利用已知点高程数据内插等高点是构建等高线的关键,本文提出了一种基于规则格网通过插值决速追踪等高点的算法,研究了等高线的平滑算法,该方法可应用于类似等值线的追踪和建立。     

增删点后的Voronoi图生成算法

Voronoi图可广泛应用于模式识别、计算机图形学、计算机辅助设计、地理信息系统等领域。利用Voronoi图及其对偶图Delaunay三角网构建的不规则三角网TIN能充分地反映地形地貌特征,对TIN的统一管理和动态调用可较好地应用到数字高程模型的建立中。通过联机增量和减量算法来来实现增删点后的Voronoi图的生成,具有能够动态修改点集、速度快、效率高等优势。     

一种基于地表特征的全球剖分模型

提出一种基于地表特征的全球剖分(TAMM)模型,通过采用自适应多分辨率椭球面三角格网生成方法以及带约束条件的Delaunay三角网构建方法,实现对全球无缝、自适应多分辨率、高精度表达.     

面向四面体网格生成的曲面Delaunay三角化算法

提出了一种曲面域Delaunay三角网格的直接构造算法。该算法在曲面网格剖分的边界递归算法和限定Delaunay四面体化算法的基础上,利用曲面采样点集的空间Delaunay四面体网格来辅助曲面三角网格的生成,曲面上的三角网格根据最小空球最小准则由辅助四面体网格中选取,每个三角形都满足三维Delaunay空球准则,网格质量有保证,并且极大的方便了进一步的曲面边界限定下的Delaunay四面体化的进行。     

基于相邻关系的等高线树建立算法研究

等高线树在提取地形线、地貌综合等方面具有重要的应用意义。常用的等高线树表达的是等高线的层次关系,直接表达等高线的包含和邻接关系,建树过程复杂,对数据要求较高,需要对数据进行预处理。本文将图幅内等高线按照是否闭合分为两类,分别对两类等高线群进行建树,最后将两个独立的等高线树合并,形成完整的等高线树。最后生成的等高线树表示了等高线之间的相邻关系,再借助其高程值就可以判断出等高线之间的包含邻接关系,算法容易理解,程序实现简单。     

基于Voronoi最小邻近点集的Delaunay三角化方法

针对局部条件下网格生成的需求,提出一种基于节点的Delaunay三角化生成算法,该算法以Delaunay三角形及其对偶Voronoi图的局部性特征为基础,通过在局部搜索最小Voronoi邻近点集,来生成约束点附近的局部网格,通过建立背景索引网格,来提高算法效率。给出算法的原理证明、程序实现、效率分析和测试结果,并给出了算法的应用领域。     

应用Voronoi图的点群范围自动识别

运用动态阈值对点群Delaunay三角网进行"蚕食"处理,获得不同视觉邻近距离下的点群分布范围多边形,在多边形边界外侧构建一系列虚拟边界点,在构建中使用两个重要参数:扩展距离、扩展方向.由虚拟边界点与初始点群共同组成新点群,通过对新点群Voronoi图的构建,确定边界点Voronoi区域的准确范围.最后,以点群状分布的教育资源优化配置为例,说明了该方法的具体应用.     

无网格方法数值结果的可视化方法与实现

科学计算可视化是科学计算中不可缺少的一个组成部分,其主要任务是将数值模拟产生的大量复杂的数据信息通过计算机技术转换成图形、图像信息。无网格方法是一种基于点的数值计算方法,各离散点之间没有联结信息,其数值结果的可视化后处理是一件很困难的事情,尤其当离散点随机分布时,更是如此。Delaunay 三角化是十分理想的散乱数据的可视化工具,它可以根据一组随机分布的离散点数据生成唯一的近似等边三角形。首先介绍了 Voronoi 图与 Delaunay 三角化的基本原理,然后介绍了实现 Delaunay 三角剖分的算法及无网格方法数值结果可视化的实现方法,最后给出了无网格方法可视化的若干应用实例。     

The construction of improved‐quality mesh on a curved surface using mapping factors

Abstract

The Delaunay triangulation is broadly used on flat surfaces to generate well‐shaped elements. But the properties of Delaunay triangulation do not exist on curved surfaces whose Jacobians are different. In this paper we will present a modified algorithm to improve the shape of triangulation for the curved surface. The experiment results show that making use of “mapping factors” in the Delaunay triangulation and Laplacian method can produce better mesh (most aspect ratios≤3) on a curved surface.     

二维任意域约束Delaunay三角化的实现

本文设计了一种逐点加入一局部换边法,提出并证明了二维约束边在约束Ｄｅｌａｕｎａｙ三角化中存在的条件,并据此用中点加点法实现了二维任意域的Ｄｅｌａｕｎａｙ三角剖分,生成的网格均符合Ｄｅｌａｕｎａｙ优化准则,网格的优化在网格生成过程中完成,算法复杂度与点数呈近似线性关系,给出了算法在平面域剖分和包含复杂断层的石油地质勘探散乱数据点集剖分的应用实例。     

Delaunay triangulation of non-convex planar domains

This paper investigates the possibility of integrating the two currently most popular mesh generation techniques, namely the method of advancing front and the Delaunay triangulation algorithm. The merits of the resulting scheme are its simplicity, efficiency and versatility. With the introduction of ‘non-Delaunay’ line segments, the concept of using Delaunay triangulation as a means of mesh generation is clarified. An efficient algorithm is proposed for the construction of Delaunay triangulations over non-convex planar domains. Interior nodes are first generated within the planar domain. These interior nodes and the boundary nodes are then linked up together to produce a valid triangulation. In the mesh generation process, the Delaunay property of each triangle is ensured by selecting a node having the smallest associated circumcircle. In contrast to convex domains, intersection between the proposed triangle and the domain boundary has to be checked; this can be simply done by considering only the ‘non-Delaunay’ segments on the generation front. Through the study of numerous examples of various characteristics, it is found that high-quality triangular element meshes are obtained by the proposed algorithm, and the mesh generation time bears a linear relationship with the number of elements/nodes of the triangulation.     

基于Delaunay三角剖分的层析图像离散数据表面重建算法

提出一种基于Delaunay三角剖分思想的层析图像离散数据的表面重建算法。该算法考虑了组成最优重建表面的三角片的形态特点,以三角片集的内角矢量最大为优化目标,根据Delaunay三角剖分思想,采用局部判定的方法,逐次选取最佳几何形态的三角片,组成最优的重建表面。     

One machine,one minute,three billion tetrahedra

This paper presents a new scalable parallelization scheme to generate the 3D Delaunay triangulation of a given set of points. Our first contribution is an efficient serial implementation of the incremental Delaunay insertion algorithm. A simple dedicated data structure, an efficient sorting of the points, and the optimization of the insertion algorithm have permitted to accelerate reference implementations by a factor three. Our second contribution is a multithreaded version of the Delaunay kernel that is able to concurrently insert vertices. Moore curve coordinates are used to partition the point set, avoiding heavy synchronization overheads. Conflicts are managed by modifying the partitions with a simple rescaling of the space-filling curve. The performances of our implementation have been measured on three different processors: an Intel core-i7, an Intel Xeon Phi, and an AMD EPYC, on which we have been able to compute three billion tetrahedra in 53 seconds. This corresponds to a generation rate of over 55 million tetrahedra per second. We finally show how this very efficient parallel Delaunay triangulation can be integrated in a Delaunay refinement mesh generator, which takes as input the triangulated surface boundary of the volume to mesh.     

Robust boundary triangulation and delaunay triangulation of arbitrary planar domains

A simple and robust boundary triangulation algorithm is proposed and, based on it, completely automatic Delaunay mesh generation procedures are developed. The algorithm is equally applicable to convex, non-convex and multiply connected planar domains. In this approach, given the nodes, the number of triangles formed is precisely known and any desired control over mesh generation is possible.     

The boundary recovery and sliver elimination algorithms of three‐dimensional constrained Delaunay triangulation

A boundary recovery and sliver elimination algorithm of the three‐dimensional constrained Delaunay triangulation is proposed for finite element mesh generation. The boundary recovery algorithm includes two main procedures: geometrical recovery procedure and topological recovery procedure. Combining the advantages of the edges/faces swappings algorithm and edges/faces splittings algorithm presented respectively by George and Weatherill, the geometrical recovery procedure can recover the missing boundaries and guarantee the geometry conformity by introducing fewer Steiner points. The topological recovery procedure includes two phases: ‘dressing wound’ and smoothing, which will overcome topology inconsistency between 3D domain boundary triangles and the volume mesh. In order to solve the problem of sliver elements in the three‐dimensional Delaunay triangulation, a method named sliver decomposition is proposed. By extending the algorithm proposed by Canvendish, the presented method deals with sliver elements by using local decomposition or mergence operation. In this way, sliver elements could be eliminated thoroughly and the mesh quality could be improved in great deal. Copyright © 2006 John Wiley & Sons, Ltd.