空间散点集Delaunay四面体剖分切割算法

提出最大空圆凸多边形和最大空球凸多面体的概念，在此基础上，提出一种空间散乱点集Delaunay四面体剖分算法，即对空间散乱点集首先进行最大空球凸多面体剖分，然后在多面体内部作Delaunay四面体剖分，这种方法消除了“退化”现象（平面3个以上点共圆或空间4个以上点共球面）引起的潜在错误，最后分析了一类常见的Delaunay四面体剖分算法的潜在错误。     

空间散乱点集Delaunay四面体剖分切割算法

提出最大空圆凸多边形和最大空球凸多面体的概念 .在此基础上 ,提出一种空间散乱点集 Delaunay四面体剖分算法 ,即对空间散乱点集首先进行最大空球凸多面体剖分 ,然后在多面体内部作 Delaunay四面体剖分 .这种方法消除了“退化”现象 (平面 3个以上点共圆或空间 4个以上点共球面 )引起的潜在错误 .最后分析了一类常见的 De-launay四面体剖分算法的潜在错误     

约束四面体剖分和三维物体表面重建

该文提出了约束曲面和约束最大空球凸多面体的概念,在此基础上设计了一种在空间区域上做约束Delaunay四面体剖分的算法。该算法的基本思路是首先对空间区域进行约束最大空球凸多面体剖分,然后在各个约束最大空球凸多面体内部做Delaunay四面体剖分。利用约束Delaunay四面体剖分算法,该文进一步设计了一种三维物体表面重建算法。     

约束四面体部分和三维物体表面重建

该文提出了约束曲面和约束最大空球凸多面体的概念，在此基础上设计了一种在空间区域上约束Delaunay四面体部分的算法，该算法的基本思路是首先对空间区域进行约束最大空球凸多面体剖分，然后在各个约束最大空球凸多面体内部做Delaunay四面体剖分，利用约束Delaunay四面体剖分算法，该文进一步设计了一种三维物体表面重建算法。     

一种三维离散点数据生成非结构四面体算法

3D离散点数据的Delaunay三角剖分是构造曲面网格的关键技术之一。针对常用的基于三角网递推原理的Delaunay四面体局部构造生成算法中往往存在的四面体不相容问题,本文提出在当前点的局部计算中构造新四面体时,除了参考当前局部计算之前已生成的四面体集约束关系外,同时考虑当前点局部计算过程中生成的四面体集约束关系的非结构四面体生成算法,从而改善了新生成四面体与已有四面体的不相容性。文中最后给出的实验结果验证了本文算法的有效性。     

面向四面体网格生成的Delaunay refinement器官表面重建

为满足生物医学仿真系统对器官几何模型在Delaunay表面重构和四面体建模两方面的需求,提出一种面向四面体网格生成的Delaunay refinement表面重构算法.算法将从医学体数据中经过等值面提取和简化的初始表面作为输入和边界限定条件,为每个限定点计算局部特征尺寸并构建保护球,计算保护球与限定线段的交点并与限定点一起作为初始点集,生成Delaunay辅助四面体网格,引入一个迭代细分过程恢复边界,最终获得Delaunay重构表面.针对细分过程中的收敛性问题,文中给出了详细的理论证明和算法实例.此外,通过Delaunay四面体生成的对比实验表明该算法在Delaunay器官表面重构和四面体建模两方面兼具有效性和优越性.     

利用Voronoi图改进离散数据重构曲面算法

本文利用Delaunay三角剖分和 Voronoi图的性质,实现了一种对散乱点重构闭合曲面的方法。该方法在搜索策略上进行了改进：首先对输入点进行三角剖分,产生相互独立的四面体,构建一个凸包;然后利用Delaunay三角剖分产生Voronoi图;最后根据Voronoi图的性质,选择包含在形体内部的四面体,提取出边界三角形,完成散乱点边界重构。计算复杂度和Delaunay四面体数量成正比,在自动形状重构时形状边界提取过程的计算复杂度为O(n),算法适用于各种涉及图形重构的工程应用。     

基于EMST的平面点集Delaunay三角剖分

提出一种基于欧几里德最小支撑树(EMST)的平面点集Delaunay三角剖分算法.该算法使用线性时间的随机算法求出平面点集的EMST,逐次加入一边构成三角网络,按照最小角最大化的三角化准则,通过局部变换得到平面点集的Delaunay三角剖分.采用的随机化算法有效节省了寻找EMST的计算时间,提高了整个算法的效率.     

平面散乱点集约束Delaunay三角形剖分切割算法

文章提出了一种基于切割的平面散乱点集约束Delaunay三角剖分算法。该算法的基本思路是首先对平面散乱点集作约束最大空圆凸多边形剖分,然后对多边形的内部再作约束Delaunay三角形剖分。文章还证明了平面散乱点集的约束最大空圆凸多边形剖分是唯一的以及约束Delaunay三角剖分的不唯一性仅仅体现在约束最大空圆凸多边形的内部。使用约束最大空圆凸多边形的概念消除了由于“退化”现象（三个以上的点共圆）带来的算法上的潜在错误。     

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

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

Tetrahedralization of point sets using expanding spheres

The expanding sphere algorithm computes an alpha shape tetrahedralization of a point set. Starting with a seed tetrahedron, the circumscribing sphere is squeezed through each face until it either touches another point or exceeds a preset radius. If no point is found, that face of the tetrahedron is part of the surface of an object. If a point is found, a new tetrahedron is constructed. This process is iterated until all the faces of the tetrahedra have been processed and no more connected points can be found. If there are points left over, the process is iterated, creating additional objects. The algorithm generates a list of objects, with an alpha shape tetrahedralization and a surface triangulation for each. Any points that cannot be made part of a valid tetrahedron are also returned in the extra points list. The algorithm is efficient for uniformly distributed point sets, with a running time that is linear in the number of points for such sets. Since the operations are local, it is also robust.     

On shape Delaunay tessellations

Shape Delaunay tessellations are a generalization of the classical Delaunay triangulation of a finite set of points in the plane, where the empty circle condition is replaced by emptiness of an arbitrary convex compact shape. We present some new and basic properties of shape Delaunay tessellations, concerning flipping, subgraph structures, and recognition.     

A note on lee and schachter's algorithm for delaunay triangulation

Lee and Schachter have presented an algorithm for the Delaunay triangulation of a set of points whose convex hull is a rectangular region. An addendum to that algorithm is presented which gives the Delaunay triangulation of a set of points with an arbitrary convex hull. Timing results are also given.     

二维任意域内点集的Delaunay三角划分生成算法

本文研究二维任意域内点集的Ｄｅｌａｕｎａｙ三角划分（简记为ＤＴＡＤ）的生成算法只有边界点的ＤＴＡＤ用环切边界的方法生成．本文讨论了ＤＴＡＤ的插入、删除性质，提出了以此为基础的生成核插入算法．     

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

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

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

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

Automatic Surface Reconstruction from Point Sets in Space

In this paper an algorithm is proposed that takes as input a generic set of unorganized points, sampled on a real object, and returns a closed interpolating surface. Specifically, this method generates a closed 2-manifold surface made of triangular faces, without limitations on the shape or genus of the original solid. The reconstruction method is based on generation of the Delaunay tetrahedralization of the point set, followed by a sculpturing process constrained to particular criteria. The main applications of this tool are in medical analysis and in reverse engineering areas. It is possible, for example, to reconstruct anatomical parts starting from surveys based on TACs or magnetic resonance.     

Properties of n-dimensional triangulations

This paper establishes a number of mathematical results relevant to the problem of constructing a triangulation, i.e., a simplical tessellation of the convex hull of an arbitrary finite set of points in n-space.

The principal results of the present paper are

1. (a) A set of n + 2 points in n-space may be triangulated in at most 2 different ways.

2. (b) The ‘sphere test’ defined in this paper selects a preferred one of these two triangulations.

3. (c) A set of parameters is defined that permits the characterization and enumeration of all sets of n + 2 points in n-space that are significantly different from the point of view of their possible triangulations.

4. (d) The local sphere test induces a global sphere test property for a triangulation.

5. (e) A triangulation satisfying the global sphere property is dual to the n-dimensional Dirichlet tessellation, i.e., it is a Delaunay triangulation.

     

Determining gouge-free ball-end mills for 3D surface machining from point cloud data

This paper presents an algorithm to automatically determine the optimal size of the ball-end milling tool used for the three-axis finish machining of free-form surfaces directly from discrete coordinate data points. The tool is considered optimal if it is of the largest possible diameter that can access every data point without causing an overcut situation or gouging the other data points. Two well-developed techniques in computational geometry, Voronoi diagram and Delaunay triangulation, are used to establish the geometric relationship among data points from which the information required to determine the optimal tool size is extracted. The result of Delaunay triangulation is a set of tetrahedrons, with the data points as vertices, which define a corresponding set of empty circum-spheres. Each data point is a vertex of several tetrahedrons and the largest of the corresponding circum-spheres represents a valid estimation of the optimal tool size at the point. Since the data points are only a sample of the original 3D surface, accuracy of the estimated tool size can be improved by using the approximated normal vector at the data point. The estimated tool size is evaluated by comparing it to its theoretical value. Extensive simulation tests show that a robust and accurate method of determining the optimal ball-end mill size has been developed.