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

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

二维任意域内点集的Delaunay三角划分的研究

传统的Ｄｅｌａｕｎａｙ三角划分不适合许多实际的应用，本文提出了三维任意域内点集的Ｄｅｌａｕｎａｙ三角划的概念，研究了其存储性、唯一性的条件以及一个三角划分是ＤＴＡＤ的充要条件，ＤＴＡＤ具有最小角最大以及平均形态比最大的性质，因此它是给定区域和点集的最佳三角划分，本文同时阐述了它的对偶图。     

三维任意区域中点集的三角剖分算法

本文在已有算法基础上，发展了一种三维任意区域中点集的三角剖分算法。该算法不仅可用于三维点集的标准Ｄｅｌａｕｎａｙ三角剖分，而且可用于带有约束表面及内部含有孔洞情况，可以处理非凸区域的三角剖分问题。算法对点在空间的位置滑任何限制。     

约束Delaunay三角剖分地嵌入约束边的多对角线交换算法

在不允许改变原有点集的场合,实现约事束Ｄｅｌａｕｎａｙ三角剖分的一种有效算法是,将边界点与内点一起进行标准Ｄｅｌａｕｎａｙ三角剖分,然后强行嵌入不在剖分中的约束边,最后删除城外三角形。其中,任意一条待嵌入约束边所经三角形构成的多边形区域称为该约束边的域,影响域内部的每条边称为对象线。     

二维Delaunay三角划分的平均形态比最大性质

本文提出了三角划分的一种新的准则；平均形态比最大准则，证明了二维Ｄｅｌａｕｎａｙ三角划分具有最大的平均形态比，从而证明了平均形态比最大准则，最小角最大准则、Ｃｉｒｃｌｅ准则的等价性，这个性质在理论上进一步说明了Ｄｅｌａｕｎａｙ三角划分的最优性，为有限元网格划分的质量评估提供了理论依据，并为寻求三维三角划分的最优准则提供了线索。     

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

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

一种常用的二维任意域的Delaunay三角剖分算法的健壮性补充

由于对任意给定的平面点集通过Ｄｅｌａｕｎａｙ三角剖分进行处理可得到具有整体最优性的三角形网络,因而该方法得到了广泛的重视。但研究发现,常用的二维任意域Ｄｅｌａｕｎａｙ三角剖分算法＾［１,２］是有缺陷的,它在构成Ｄｅｌａｕｎａｙ三角形候选点的选择过程中,可以使候选点出现“位置违约”的错误,即在候造节点链表中,虽然可出现依据算法的判据有条件成为Ｄｅｌａｕｎａｙ三角形的构成点,但采用该点构成Ｄｅｌａｕｎ     

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

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

任意平面域渐变三角形网格的自动划分

结合前沿生成法和Ｄｅｌａｕｎａｙ三角化方法的优点,利用节点间距函数来控制区域内网格尺寸变化,并优先处理前沿上的最长边,尽可能在局部生成边长逐渐减小的Ｄｅｌａｕｎａｙ三角形,最终实现区域内网格的疏密过渡。     

满足全局Delaunay特性的带特征约束的散乱数据最优三角剖分

本文给出了一种新的全局满足Ｄｅｌａｕｎａｙ特性的带特征约束散乱数据的优化三角剖分算法．统一的数据结构允许散乱数据带有外部边界或内部孔洞,并且约束特征可以是有向折线或封闭多边形．由于采用了“对半划分增量型附加特征点插入”算法,从而可以用较少的附加点来使全局Ｄｅｌａｕｎａｙ特性得到满足．     

三维约束Delaunay三角化的实现

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

约束Delaunay三角剖分中强行嵌入约束边的多对角线交换算法

在不允许改变原有点集的场合,实现约束Ｄｅｌａｕｎａｙ 三角剖分的一种有效算法是：将边界点与内点一起进行标准Ｄｅｌａｕｎａｙ 三角剖分,然后强行嵌入不在剖分中的约束边,最后删除域外三角形．其中,任意一条待嵌入约束边所经三角形构成的多边形区域称为该约束边的影响域,影响域内部的每条边称为对角线．文中对一般形状影响域中对角线的可交换性进行了研究,并在此基础上,结合对已有算法的分析和借鉴,提出并证明了两种强行嵌入约束边的多对角线交换算法,即递减算法与循环算法．其中的循环算法具有编程简单和运算速度快的特点     

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

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

3维任意域内点集的Delaunay四面体化研究

Delaunay空球准则广泛应用于3维四面体剖分算法,但标准的Delaunay四面体化只适用于点集的凸包区域,且要求不存在多点共球。为了将Delaunay四面体化更广泛地应用于网络剖分,通过引入局部优化三角形面代替Deluany严格的空球准则,提出了3维任意域内点集Deluanay四面体化(DTETAD)的概念,并首先通过若干关键定理的证明,研究了一个四面体划分是DETEAD的充要条件,然后建立了DTETAD的空球准则。该研究成果为拓展Delaunay算法在更广泛范围的应用提供了理论依据。     

An efficient and collision-free hole-filling algorithm for orthodontics

Hole filling of teeth and gums is an essential stage in orthodontics after segmentation. The patching mesh should keep the morphological features of generic teeth and gums while avoiding collision between two adjacent teeth. This paper presents an efficient hole-filling algorithm to reconstruct the missing part of teeth and gums. Our proposed method involves four necessary steps: boundary construction and projection, hole triangulation in 2D, back projection of vertices to 3D, and mesh fairing. By combining constrained Delaunay triangulation in 2D with back projection of vertices to 3D using mean value coordinates, we achieve high robustness of hole triangulation and a high-quality initial patching mesh. In addition, we propose an automatic method to control the deformation degree to avoid collision. Our experiments demonstrate that the proposed method can achieve satisfactory results, not only in morphology, but also in efficiency. The results are very similar to real teeth and gums and can meet the requirements of orthodontics in medicine.     

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

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

二维几何特征自适应有限元网格生成(一)--几何特征识别

发现二维形体边界均匀离散点集Delaunay三角剖分所具有的4个性质．根据这4个性质所描述的Delaunay三角剖分和形体几何特征之间的关系提出几何特征自动识别方法,并建立网格自适应机制,实现三维形体几何特征和部分力学特性自适应有限元网格自动生成．     

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

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

A highly solid model boundary preserving method for large-scale parallel 3D Delaunay meshing on parallel computers

In this paper, we propose a novel parallel 3D Delaunay triangulation algorithm for large-scale simulations on parallel computers. Our method keeps the 3D boundary representation model information during the whole parallel 3D Delaunay triangulation process running on parallel computers so that the solid model information can be accessed dynamically and the meshing results can be very approaching to the model boundary with the increase of meshing scale. The model is coarsely meshed at first and distributed on CPUs with consistent partitioned shared interfaces and partitioned model boundary meshes across processors. The domain partition aims at minimizing the edge-cuts across different processors for minimum communication cost and distributing roughly equal number of mesh vertices for load balance. Then a parallel multi-scale surface mesh refinement phase is iteratively performed to meet the mesh density criteria followed by a parallel surface mesh optimization phase moving vertices to the model boundary so as to fit model geometry feature dynamically. A dynamic load balancing algorithm is performed to change the partition interfaces if necessary. A 3D local non-Delaunay mesh repair algorithm is finally done on the shared interfaces across processors and model boundaries. The experimental results demonstrate our method can achieve high parallel performance and perfect scalability, at the same time preserve model boundary feature and generate high quality 3D Delaunay mesh as well.