Exact Computation of Delaunay and Power Triangulations

In this paper we present a topologically correct and efficient version of the algorithm by Guibas and Stolfi (Algorithmica 7 (1992), pp. 381-413) for the exact computation of Delaunay and power triangulations in two dimensions. The algorithm avoids numerical errors and degeneracies caused by the accumulation of rounding errors in fixed length floating point arithmetic when constructing these triangulations.Most methods for computing Delaunay and power triangulations involve the calculation of two basic primitives: the INCIRCLE test and the CCW orientation test. Both primitives require the computation of the sign of a determinant. The key to our method is the exact computation of this sign and is based on an algorithm for determining the sign of the sum of a finite set of normalized floating point numbers of fixed mantissa length (machine numbers) exactly. The exact computation of the primitives allows the construction of the correct Delaunay and power triangulations. The method has been implemented and tested for the incremental construction of Delaunay and power triangulations. Tests have been conducted for different distributions of points for which non-exact algorithms may encounter difficulties, for example, slightly perturbed points on a grid or on a circle. Experimental results show that the performance of our implementation is comparable with that of a simple implementation of the incremental algorithm in single precision floating point arithmetic. For random distribution of points the exact algorithm is only 4 times slower than the inexact implementation. The algorithm is easy to implement, robust and portable as long as the input data to the algorithm remains exact.     

一种基于格子分块的快速Delaunay三角剖分算法

介绍了一种基于分块格子构造的快速Delaunay平面剖分算法,先对点集以方格为单位分组,每组分别进行Delaunay三角网生成,再把分组构成的网格合并成一个整体。该算法易于理解和实现,占用内存少,运算速度快,具有近优的线性时间复杂度。最后给出的实例也证明了算法的可靠性和实用性。     

Computing correct Delaunay triangulations

In recent years the practical computation of Delaunay triangulations, resp. Voronoi diagrams has received a lot of attention in the literature. While the Delaunay triangulation is an important basic tool in geometric optimization algorithms, it is nontrivial to achieve a numerically stable computer implementation. In this technical note we assume that all generating points are grid points of a regularM byM lattice in the plane. Depending onM we derive the necessary word length a binary computer must have for integer representation in order to obtain exact Delaunay triangulations. This analysis is carried out for theL ₁-,L ₂- andL _∞-metric.     

三维散乱点集的曲面三角剖分

根据三维散乱点集构造曲面剖分在 CAGD/CAD、反求工程等方面有着十分广泛的应用 .本文回顾了三维散乱点集曲面三角剖分的两种主要方法即平面投影法和直接剖分法 ,对几种常用的算法作了较为详细的描述 ,同时对剖分算法中经常出现的数据结构作了详细的介绍 .由于剖分采用的优化准则决定了剖分结果 ,因此本文讨论了几种常用的剖分优化准则 ,并举例对几种优化准则进行了较详细的分析比较 .最后简要地讨论了算法复杂度以及目前剖分的主要研究方向 ,并指出在实际工程应用中对复杂曲面采样得到的散乱点集 ,要得到光顺和保形的三角剖分 ,需要新的剖分准则和算法 .     

Localized Delaunay Refinement for Volumes

Delaunay refinement, recognized as a versatile tool for meshing a variety of geometries, has the deficiency that it does not scale well with increasing mesh size. The bottleneck can be traced down to the memory usage of 3D Delaunay triangulations. Recently an approach has been suggested to tackle this problem for the specific case of smooth surfaces by subdividing the sample set in an octree and then refining each subset individually while ensuring termination and consistency. We extend this to localized refinement of volumes, which brings about some new challenges. We show how these challenges can be met with simple steps while retaining provable guarantees, and that our algorithm scales many folds better than a state‐of‐the‐art meshing tool provided by CGAL.     

基于分治算法构建Delaunay三角网的研究

提出了一种构建Delaunay三角网的分治算法,该算法利用方格网管理离散点数据,仅需分别对每格中的点进行排序;此外,通过对凸包顶点数据进行分区管理,在搜寻凸包支撑线时,能预先确定出支撑点的范围,减少了搜索工作量,提高了三角网的合并速度。     

GPU Local Triangulation: an interpolating surface reconstruction algorithm

A GPU capable method for surface reconstruction from unorganized point clouds without additional information, called GLT (GPU Local Triangulation), is presented. The main objective of this research is the generation of a GPU interpolating reconstruction based on local Delaunay triangulations, inspired by a pre‐existing reconstruction algorithm. Current graphics hardware accelerated algorithms are approximating approaches, where the final triangulation is usually performed through either marching cubes or marching tetrahedras. GPU‐compatible methods and data structures to perform normal estimation and the local triangulation have been developed, plus a variation of the Bitonic Merge Sort algorithm to work with multi‐lists. Our method shows an average gain of one order of magnitude over previous research.     

Efficient and good Delaunay meshes from random points

We present a Conforming Delaunay Triangulation (CDT) algorithm based on maximal Poisson disk sampling. Points are unbiased, meaning the probability of introducing a vertex in a disk-free subregion is proportional to its area, except in a neighborhood of the domain boundary. In contrast, Delaunay refinement CDT algorithms place points dependent on the geometry of empty circles in intermediate triangulations, usually near the circle centers. Unconstrained angles in our mesh are between 30° and 120°, matching some biased CDT methods. Points are placed on the boundary using a one-dimensional maximal Poisson disk sampling. Any triangulation method producing angles bounded away from 0° and 180° must have some bias near the domain boundary to avoid placing vertices infinitesimally close to the boundary.Random meshes are preferred for some simulations, such as fracture simulations where cracks must follow mesh edges, because deterministic meshes may introduce non-physical phenomena. An ensemble of random meshes aids simulation validation. Poisson-disk triangulations also avoid some graphics rendering artifacts, and have the blue-noise property.We mesh two-dimensional domains that may be non-convex with holes, required points, and multiple regions in contact. Our algorithm is also fast and uses little memory. We have recently developed a method for generating a maximal Poisson distribution of n output points, where n=Θ(Area/r²) and r is the sampling radius. It takes O(n) memory and O(nlogn) expected time; in practice the time is nearly linear. This, or a similar subroutine, generates our random points. Except for this subroutine, we provably use O(n) time and space. The subroutine gives the location of points in a square background mesh. Given this, the neighborhood of each point can be meshed independently in constant time. These features facilitate parallel and GPU implementations. Our implementation works well in practice as illustrated by several examples and comparison to Triangle.     

Reconstructing Surfaces and Functions on Surfaces from Unorganized Three-Dimensional Data

Creating a computer model from an existing part is a common problem in reverse engineering. The part might be scanned with a device like the laser range scanner, or points might be measured on its surface with a mechanical probe. Sometimes, not only the spatial location of points, but also some associated physical property can be measured. The problem of automatically reconstructing from this data a topologically consistent and geometrically accurate model of the object and of the sampled scalar field is the subject of this paper. The proposed algorithm can deal with connected, orientable manifolds of unrestricted topological type, given a sufficiently dense and uniform sampling of the object's surface. It is capable of automatically reconstructing both the model and a scalar field over its surface. It uses Delaunay triangulations, Voronoi diagrams, and α-shapes for efficiency of computation and theoretical soundness. It generates a representation of the surface and the field based on Bernstein—Bézier polynomials, with the surface modeled by implicit patches (A-patches), that are guaranteed to be smooth and single-sheeted. Received June 1, 1994; revised February 2, 1995, and August 14, 1995.     

Filtering Relocations on a Delaunay Triangulation

Updating a Delaunay triangulation when its vertices move is a bottleneck in several domains of application. Rebuilding the whole triangulation from scratch is surprisingly a very viable option compared to relocating the vertices. This can be explained by several recent advances in efficient construction of Delaunay triangulations. However, when all points move with a small magnitude, or when only a fraction of the vertices move, rebuilding is no longer the best option. This paper considers the problem of efficiently updating a Delaunay triangulation when its vertices are moving under small perturbations. The main contribution is a set of filters based upon the concept of vertex tolerances. Experiments show that filtering relocations is faster than rebuilding the whole triangulation from scratch under certain conditions.     

On the number of higher order Delaunay triangulations

Higher order Delaunay triangulations are a generalization of the Delaunay triangulation that provides a class of well-shaped triangulations, over which extra criteria can be optimized. A triangulation is order-k Delaunay if the circumcircle of each triangle of the triangulation contains at most k points. In this paper we study lower and upper bounds on the number of higher order Delaunay triangulations, as well as their expected number for randomly distributed points. We show that arbitrarily large point sets can have a single higher order Delaunay triangulation, even for large orders, whereas for first order Delaunay triangulations, the maximum number is 2ⁿ⁻³. Next we show that uniformly distributed points have an expected number of at least 2^{ρ₁n(1+o(1))} first order Delaunay triangulations, where ρ₁ is an analytically defined constant (ρ₁≈0.525785), and for k>1, the expected number of order-k Delaunay triangulations (which are not order-i for any i<k) is at least 2^{ρ_kn(1+o(1))}, where ρ_k can be calculated numerically.     

A pyramidal data structure for triangle-based surface description

A hierarchical model for approximating 2-1/2-dimensional surfaces is described. This model, called a Delaunay pyramid, is a method for compression of spatial data and representation of a surface at successively finer levels of detail. A Delaunay pyramid is based on a sequence of Delaunay triangulations of suitably defined subsets of the set of data points. A triangle-oriented encoding structure for a Delaunay pyramid is presented, and its storage complexity is evaluated. An algorithm for constructing a Delaunay pyramid is described, and a method for solving the point location and evaluation on such a model is discussed     

AnO(N) algorithm to automatically generate geometric triangulations satisfying the Delaunay circumsphere criteria

This paper presents an algorithm for the generation of Delaunay triangulations for general nonmanifold geometric models. Octree concepts are used for point placement and providing the linear, with respect to the number of elements, growth rate of the algorithm. Compatibility and classification procedures are used in conjunction with point injection procedures to ensure that the final Delaunay triangulation is a geometric triangulation of the domain of interest.     

基于凸壳技术的Delaunay三角网生成算法

该文提出了一种针对散乱点集的快速构建Delaunay的算法。该算法首先对散乱点按有向角进行排序,以排序后的点顺序为基础,利用凸壳特性快速将散乱点联结成三角网,最后利用拓扑结构快速将其优化为Delaunay三角网。在联网过程中,充分利用有序点子集的凸壳特性,避免了所有的交点测试,从而保证了对散乱点集生成Delaunay三角网的效率。     

Parallel divide‐and‐conquer scheme for 2D Delaunay triangulation

This work describes a parallel divide‐and‐conquer Delaunay triangulation scheme. This algorithm finds the affected zone, which covers the triangulation and may be modified when two sub‐block triangulations are merged. Finding the affected zone can reduce the amount of data required to be transmitted between processors. The time complexity of the divide‐and‐conquer scheme remains O(n log n), and the affected region can be located in O(n) time steps, where n denotes the number of points. The code was implemented with C, FORTRAN and MPI, making it portable to many computer systems. Experimental results on an IBM SP2 show that a parallel efficiency of 44–95% for general distributions can be attained on a 16‐node distributed memory system. Copyright © 2006 John Wiley & Sons, Ltd.     

三维散乱点云快速曲面重建算法

提出了一种基于Delaunay三角剖分的三维散乱点云快速曲面重建算法。算法首先计算点云的Delaunay三角剖分, 从Delaunay四面体提取初始三角网格, 根据Voronoi体元的特征构造优先队列并生成种子三角网格, 然后通过区域生长的方式进行流形提取。实验结果表明, 该算法可以高效、稳定地重构具有复杂拓扑结构、非封闭曲面甚至是非均匀采样的点云数据。与传统的基于Delaunay的方法比较, 该算法仅需要进行一次Delaunay三角剖分, 无须极点的计算, 因此算法的重构速度快。     

The drawability problem for minimum weight triangulations

A graph is minimum weight drawable if it admits a straight-line drawing that is a minimum weight triangulation of the set of points representing the vertices of the graph. We study the problem of characterizing those graphs that are minimum weight drawable. Our contribution is twofold: We show that there exist infinitely many triangulations that are not minimum weight drawable. Furthermore, we present non-trivial classes of triangulations that are minimum weight drawable, along with corresponding linear time algorithms that take as input any graph from one of these classes and produce as output such a drawing. One consequence of our work is the construction of triangulations that are minimum weight drawable but not Delaunay drawable – that is, not drawable as a Delaunay triangulation.     

Delaunay三角网通用合并算子及分治算法的简化

Delaunay三角网在未来地学数值模拟中将发挥重要作用。分治算法是一种著名的经典构网算法,但其子网合并过程十分复杂,限制了其应用。提出使用通用算子的概念,并用从以往算法中独立出来的算子和3个新算子来简化分治算法的子网合并。扩展三角形算子用于构造每个新三角形并维护三角网的拓扑关系和边界链表。凹边界填充算子对边界链表用递归来自动完成凹边界的智能三角形填充。子网合并算子先用一个新三角形连接两个子三角网,再合并边界链表,调用凹边界填充算子填充子网间的缝隙区域。所有算子都基于有向边的数据结构和用链表管理的三角网外边界,借助链表操作,使算法的构建简洁而又高效。除分治法外,这些算子还被成功用于构建其他算法。由随机点集以及LiDAR点云的测试表明,所有算法的构网均准确无误且分治算法的执行效率较高。     

基于Delaunay三角剖分的图象变形技术研究

提出了一种新的图象变形方法 ,即基于 Delaunay三角剖分的图象变形方法 .与四边形网格方法相比 ,用三角形网格定义特征区域 ,特征点的选取更自由、数目更少 .针对变形过程中运算量最大的坐标变换 ,提出了一种基于 Bresenham算法的坐标变换算法 .该算法完全采用加减运算 ,避免了乘法及舍入取整运算 ,大大加快了图象变形的运算速度 .计算机仿真试验表明 ,在同等数目控制点的条件下 ,该算法变形效果及运算速度均优于四边形网格方法 .