Constrained delaunay triangulations

Given a set ofn vertices in the plane together with a set of noncrossing, straight-line edges, theconstrained Delaunay triangulation (CDT) is the triangulation of the vertices with the following properties: (1) the prespecified edges are included in the triangulation, and (2) it is as close as possible to the Delaunay triangulation. We show that the CDT can be built in optimalO(n logn) time using a divide-and-conquer technique. This matches the time required to build an arbitrary (unconstrained) Delaunay triangulation and the time required to build an arbitrary constrained (non-Delaunay) triagulation. CDTs, because of their relationship with Delaunay triangulations, have a number of properties that make them useful for the finite-element method. Applications also include motion planning in the presence of polygonal obstacles and constrained Euclidean minimum spanning trees, spanning trees subject to the restriction that some edges are prespecified.An earlier version of the results presented here appeared in theProceedings of the Third Annual Symposium on Computational Geometry (1987).     

Constrained delaunay triangulations

Given a set ofn vertices in the plane together with a set of noncrossing, straight-line edges, theconstrained Delaunay triangulation (CDT) is the triangulation of the vertices with the following properties: (1) the prespecified edges are included in the triangulation, and (2) it is as close as possible to the Delaunay triangulation. We show that the CDT can be built in optimalO(n logn) time using a divide-and-conquer technique. This matches the time required to build an arbitrary (unconstrained) Delaunay triangulation and the time required to build an arbitrary constrained (non-Delaunay) triagulation. CDTs, because of their relationship with Delaunay triangulations, have a number of properties that make them useful for the finite-element method. Applications also include motion planning in the presence of polygonal obstacles and constrained Euclidean minimum spanning trees, spanning trees subject to the restriction that some edges are prespecified.     

Adaptive Skin Meshes Coarsening for Biomolecular Simulation

In this paper, we present efficient algorithms for generating hierarchical molecular skin meshes with decreasing size and guaranteed quality. Our algorithms generate a sequence of coarse meshes for both the surfaces and the bounded volumes. Each coarser surface mesh is adaptive to the surface curvature and maintains the topology of the skin surface with guaranteed mesh quality. The corresponding tetrahedral mesh is conforming to the interface surface mesh and contains high quality tetrahedra that decompose both the interior of the molecule and the surrounding region (enclosed in a sphere). Our hierarchical tetrahedral meshes have a number of advantages that will facilitate fast and accurate multigrid PDE solvers. Firstly, the quality of both the surface triangulations and tetrahedral meshes is guaranteed. Secondly, the interface in the tetrahedral mesh is an accurate approximation of the molecular boundary. In particular, all the boundary points lie on the skin surface. Thirdly, our meshes are Delaunay meshes. Finally, the meshes are adaptive to the geometry.     

Generating rooted triangulations without repetitions

We use the reverse search technique to give algorithms for generating all graphs onn points that are 2- and 3-connected planar triangulations withr points on the outer face. The triangulations are rooted, which means the outer face has a fixed labelling. The triangulations are produced without duplications inO(n ²) time per triangulation. The algorithms useO(n) space. A program for generating all 3-connected rooted triangulations based on this algorithm is available by ftp.This research was supported by N.S.E.R.C. Grant Number A3013, F.C.A.R. Grant Number EQ1678, and a bilateral exchange from J.S.P.S./N.S.E.R.C.     

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.     

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.     

Geometric accuracy analysis for discrete surface approximation

In geometric modeling and processing, computer graphics and computer vision, smooth surfaces are approximated by discrete triangular meshes reconstructed from sample points on the surfaces. A fundamental problem is to design rigorous algorithms to guarantee the geometric approximation accuracy by controlling the sampling density. This paper gives explicit formulae to the bounds of Hausdorff distance, normal distance and Riemannian metric distortion between the smooth surface and the discrete mesh in terms of principle curvature and the radii of geodesic circum-circle of the triangles. These formulae can be directly applied to design sampling density for data acquisitions and surface reconstructions. Furthermore, we prove that the meshes induced from the Delaunay triangulations of the dense samples on a smooth surface are convergent to the smooth surface under both Hausdorff distance and normal fields. The Riemannian metrics and the Laplace–Beltrami operators on the meshes are also convergent to those on the smooth surfaces. These theoretical results lay down the foundation for a broad class of reconstruction and approximation algorithms in geometric modeling and processing.Practical algorithms for approximating surface Delaunay triangulations are introduced based on global conformal surface parameterizations and planar Delaunay triangulations. Thorough experiments are conducted to support the theoretical results.     

New Bounds on the Size of Optimal Meshes

The theory of optimal size meshes gives a method for analyzing the output size (number of simplices) of a Delaunay refinement mesh in terms of the integral of a sizing function over the input domain. The input points define a maximal such sizing function called the feature size. This paper presents a way to bound the feature size integral in terms of an easy to compute property of a suitable ordering of the point set. The key idea is to consider the pacing of an ordered point set, a measure of the rate of change in the feature size as points are added one at a time. In previous work, Miller et al. showed that if an ordered point set has pacing ?, then the number of vertices in an optimal mesh will be O(?^dn), where d is the input dimension. We give a new analysis of this integral showing that the output size is only θ(n+nlog?). The new analysis tightens bounds from several previous results and provides matching lower bounds. Moreover, it precisely characterizes inputs that yield outputs of size O(n).     

Fast Updating of Delaunay Triangulation of Moving Points by Bi‐cell Filtering

Updating a Delaunay triangulation when data points are slightly moved is the bottleneck of computation time in variational methods for mesh generation and remeshing. Utilizing the connectivity coherence between two consecutive Delaunay triangulations for computation speedup is the key to solving this problem. Our contribution is an effective filtering technique that confirms most bi‐cells whose Delaunay connectivities remain unchanged after the points are perturbed. Based on bi‐cell flipping, we present an efficient algorithm for updating two‐dimensional and three‐dimensional Delaunay triangulations of dynamic point sets. Experimental results show that our algorithm outperforms previous methods.     

A Weighted Delaunay Triangulation Framework for Merging Triangulations in a Connectivity Oblivious Fashion

Simplicial meshes are useful as discrete approximations of continuous spaces in numerical simulations. In some applications, however, meshes need to be modified over time. Mesh update operations are often expensive and brittle, making the simulations unstable. In this paper we propose a framework for updating simplicial meshes that undergo geometric and topological changes. Instead of explicitly maintaining connectivity information, we keep a collection of weights associated with mesh vertices, using a Weighted Delaunay Triangulation (WDT). These weights implicitly define mesh connectivity and allow direct merging of triangulations. We propose two formulations for computing the weights, and two techniques for merging triangulations, and finally illustrate our results with examples in two and three dimensions.     

Generating well-shaped d-dimensional Delaunay Meshes

A d-dimensional simplicial mesh is a Delaunay triangulation if the circumsphere of each of its simplices does not contain any vertices inside. A mesh is well shaped if the maximum aspect ratio of all its simplices is bounded from above by a constant. It is a long-term open problem to generate well-shaped d-dimensional Delaunay meshes for a given polyhedral domain. In this paper, we present a refinement-based method that generates well-shaped d-dimensional Delaunay meshes for any PLC domain with no small input angles. Furthermore, we show that the generated well-shaped mesh has O(n) d-simplices, where n is the smallest number of d-simplices of any almost-good meshes for the same domain. Here a mesh is almost-good if each of its simplices has a bounded circumradius to the shortest edge length ratio.     

Randomized incremental construction of Delaunay and Voronoi diagrams

In this paper we give a new randomized incremental algorithm for the construction of planar Voronoi diagrams and Delaunay triangulations. The new algorithm is more “on-line” than earlier similar methods, takes expected timeO(n?gn) and spaceO(n), and is eminently practical to implement. The analysis of the algorithm is also interesting in its own right and can serve as a model for many similar questions in both two and three dimensions. Finally we demonstrate how this approach for constructing Voronoi diagrams obviates the need for building a separate point-location structure for nearest-neighbor queries.     

GEOMPACK — a software package for the generation of meshes using geometric algorithms

We describe the mathematical software package GEOMPACK, which contains standard Fortran 77 routines for the generation of two-dimensional triangular and three-dimensional tetrahedral finite element meshes using efficient geometric algorithms. This package results from our research into mesh generation and geometric algorithms. It contains routines for constructing two- and three-dimensional Delaunay triangulations, decomposing a general polygonal region into simple or convex polygons, constructing the visibility polygon of a simple polygon from a viewpoint, and other geometric algorithms, from which our mesh generation method is built and others can be implemented. Our method generates meshes in polygonal or polyhedral regions specified by their boundary representation and possible interfaces between subregions.     

An algorithm for the construction of intrinsic delaunay triangulations with applications to digital geometry processing

Summary The discrete Laplace–Beltrami operator plays a prominent role in many digital geometry processing applications ranging from denoising to parameterization, editing, and physical simulation. The standard discretization uses the cotangents of the angles in the immersed mesh which leads to a variety of numerical problems. We advocate the use of the intrinsic Laplace–Beltrami operator. It satisfies a local maximum principle, guaranteeing, e.g., that no flipped triangles can occur in parameterizations. It also leads to better conditioned linear systems. The intrinsic Laplace–Beltrami operator is based on an intrinsic Delaunay triangulation of the surface. We detail an incremental algorithm to construct such triangulations together with an overlay structure which captures the relationship between the extrinsic and intrinsic triangulations. Using a variety of example meshes we demonstrate the numerical benefits of the intrinsic Laplace–Beltrami operator.     

Automatic Delaunay mesh generation method and physically-based mesh optimization method on two-dimensional regions

Delaunay mesh generation method is a common method for unstructured mesh (or unstructured grid) generation. Delaunay mesh generation method can conveniently add new points to the existing mesh without remeshing the whole domain. However, the quality of the generated mesh is not high enough if compared with some mesh generation methods. To obtain high-quality mesh, this paper developed an automatic Delaunay mesh generation method and a physically-based mesh optimization method on two-dimensional regions. For the Delaunay mesh generation method, boundary-conforming problem was ensured by create nodes at centroid of mesh elements. The definition of node bubbles and element bubbles was provided to control local mesh coarseness and fineness automatically. For the physically-based mesh optimization method, the positions of boundary node bubbles are predefined, the positions of interior node bubbles are adjusted according to interbubble forces. Size of interior node bubbles is further adjusted according to the size of adjacent node bubbles. Several examples show that high-quality meshes are obtained after mesh optimization.

     

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.     

Interpolation by geometric algorithm

We present a novel geometric algorithm to construct a smooth surface that interpolates a triangular or a quadrilateral mesh of arbitrary topological type formed by n vertices. Although our method can be applied to B-spline surfaces and subdivision surfaces of all kinds, we illustrate our algorithm focusing on Loop subdivision surfaces as most of the meshes are in triangular form. We start our algorithm by assuming that the given triangular mesh is a control net of a Loop subdivision surface. The control points are iteratively updated globally by a simple local point-surface distance computation and an offsetting procedure without solving a linear system. The complexity of our algorithm is O(mn) where n is the number of vertices and m is the number of iterations. The number of iterations m depends on the fineness of the mesh and accuracy required.     

Efficient mesh optimization schemes based on Optimal Delaunay Triangulations

In this paper, several mesh optimization schemes based on Optimal Delaunay Triangulations are developed. High-quality meshes are obtained by minimizing the interpolation error in the weighted L¹ norm. Our schemes are divided into classes of local and global schemes. For local schemes, several old and new schemes, known as mesh smoothing, are derived from our approach. For global schemes, a graph Laplacian is used in a modified Newton iteration to speed up the local approach. Our work provides a mathematical foundation for a number of mesh smoothing schemes often used in practice, and leads to a new global mesh optimization scheme. Numerical experiments indicate that our methods can produce well-shaped triangulations in a robust and efficient way.     

Point placement algorithms for Delaunay triangulation of polygonal domains

In some applications of triangulation, such as finite-element mesh generation, the aim is to triangulate a given domain, not just a set of points. One approach to meeting this requirement, while maintaining the desirable properties of Delaunay triangulation, has been to enforce the empty circumcircle property of Delaunay triangulation, subject to the additional constraint that the edges of a polygon be covered by edges of the triangulation. In finite-element mesh generation it is usually necessary to include additional points besides the vertices of the domain boundary. This motivates us to ask whether it is possible to trinagulate a domain by introducing additional points in such a manner that the Delaunay triangulation of the points includes the edges of the domain boundary. We present algorithms that given a multiply connected polygonal domain withN vertices, placeK additional points on the boundary inO(N logN + K) time such that the polygon is covered by the edges of the Delaunay triangulation of theN + K points. Furthermore,K is the minimum number of additional points such that a circle, passing through the endpoints of each boundary edge segment, exists that does not contain in its interior any other part of the domain boundary. We also show that by adding only one more point per edge, certain degeneracies that may otherwise arise can be avoided.