Search

Despite the lack of theoretical and practical convergence support, the Nelder–Mead (NM) algorithm is widely used to solve unconstrained optimization problems. It is a derivative-free algorithm, that attempts iteratively to replace the worst point of a simplex by a better one. The present paper proposes a way to extend the NM algorithm to inequality constrained optimization. This is done through a search step of the mesh adaptive direct search (Mads) algorithm, inspired by the NM algorithm. The proposed algorithm does not suffer from the NM lack of convergence, but instead inherits from the totality of the Mads convergence analysis. Numerical experiments show an important improvement in the quality of the solutions produced using this search step.

In this paper, we present a generalized prismatic hybrid meshing method for viscous flow simulations. One major difficulty in implementing a robust prismatic hybrid meshing tool is to handle boundary layer mesh collisions and normally an extra data structure (e.g. quadtree in 2D and octree in 3D) is required. The proposed method overcomes this difficulty via an heuristic approach and it only relies on Constrained Delaunay Triangulation/Tetrahedralization(CDT). No extra data structures are required. Geometrical reasoning is used to approximate the maximum marching distance of each point by walking through the CDT. This is combined with post-processing of marching vectors and distance and prohibition of multilevel differences to form an automatic and robust mechanism to remove boundary layer mesh collisions. Benefiting from the matureness of CDT techniques, the proposed method is robust, efficient and simple to implement. Its capability is demonstrated by generating quality prismatic hybrid meshes for industrial models with complex geometries. The proposed method is believed to be able considerably reduce the effort to implement a robust hybrid prismatic mesh generator for viscous flow simulations.

Delaunay meshes (DM) are a special type of triangle mesh where the local Delaunay condition holds everywhere. We present an efficient algorithm to convert an arbitrary manifold triangle mesh M into a Delaunay mesh. We show that the constructed DM has O ( Kn ) vertices, where n is the number of vertices in M and K is a model-dependent constant. We also develop a novel algorithm to simplify Delaunay meshes, allowing a smooth choice of detail levels. Our methods are conceptually simple, theoretically sound and easy to implement. The DM construction algorithm also scales well due to its O ( nK log K ) time complexity. Delaunay meshes have many favorable geometric and numerical properties. For example, a DM has exactly the same geometry as the input mesh, and it can be encoded by any mesh data structure. Moreover, the empty geodesic circumcircle property implies that the commonly used cotangent Laplace-Beltrami operator has non-negative weights. Therefore, the existing digital geometry processing algorithms can benefit the numerical stability of DM without changing any codes. We observe that DMs can improve the accuracy of the heat method for computing geodesic distances. Also, popular parameterization techniques, such as discrete harmonic mapping, produce more stable results on the DMs than on the input meshes.

A novel mesh deformation technique is developed based on the Delaunay graph mapping (DGM) method and the radial basis function (RBF) method. The algorithm combines the advantages of the efficiency of DGM mesh deformation and the better control of the near surface mesh quality from the RBF method. The Delaunay graph is used to divide the mesh domain into a number of sub-domains. On each of the sub-domains, the radial basis function is applied to build a much smaller sized translation matrix between the original mesh and the deformed mesh, resulting in a similar efficiency for the mesh deformation as compared to the fast Delaunay graph mapping method. Furthermore, by separating the translation and rotation motion, the mesh quality near the wall can be substantially improved for extremely large rotational deformation. The paper will show how the near-wall mesh quality is controlled and improved by the new method while the computational time is maintained to be comparable to the original Delaunay graph mapping method.

Delaunay triangulation is gradually playing an important role in the field of finite element analysis, image recognition, and medical visualization. Considering the quality and partition efficiency, a new Delaunay triangulation method based on constrained maximum circumscribed circle is proposed. First, according to two important criteria, the empty circle features and the maximized minimum angle characteristics, we established constrained conditions. Then, we iterated the container vertices, structure triangular face linked lists, and finally got the Delaunay data. The experimental results showed that the efficiency of the improved triangulation dissection method increased by 9.47% compared with traditional triangulation algorithms in irregular triangle vertex data.

Aiming at complex configuration and large deformation, an efficient hybrid method for dynamic mesh generation is presented in this paper, which is based on Radial Basis Functions (RBFs) and Delaunay graph mapping. Based on the computational mesh, a set of very coarse grid named as background grid is generated firstly, and then the computational mesh can be located at the background grid by Delaunay graph mapping technique. After that, the RBFs method is applied to deform the background grid by choosing partial mesh points on the boundary as the control points. Finally, Delaunay graph mapping method is used to relocate the computational mesh by employing area or volume weight coefficients. By applying different dynamic mesh methods to a moving NACA0012 airfoil, it can be found that the RBFs-Delaunay graph mapping hybrid method is as accurate as RBFs and is as efficient as Delaunay graph mapping technique. Numerical results show that the dynamic meshes for all test cases including one two-dimensional (2D) and two three-dimensional (3D) problems with different complexities, can be generated in an accurate and efficient manner by using the present hybrid method.

In this paper, we present a fully automatic Delaunay based sculpting algorithm for approximating the shape of a finite set of points S in R 2 . The algorithm generates a relaxed Gabriel graph ( R G G ) that consists of most of the Gabriel edges and a few non-Gabriel edges induced by the Delaunay triangulation. Holes are characterized through a structural pattern called as body-arm formed by the Delaunay triangles in the void regions. R G G is constructed through an iterative removal of Delaunay triangles subjected to circumcenter (of triangle) and topological regularity constraints in O ( n log n ) time using O ( n ) space. We introduce the notion of directed boundary samples which characterizes the two dimensional objects based on the alignment of their boundaries in the cavities. Theoretically, we justify our algorithm by showing that under given sampling conditions, the boundary of R G G captures the topological properties of objects having directed boundary samples. Unlike many other approaches, our algorithm does not require tuning of any external parameter to approximate the geometric shape of point set and hence human intervention is completely eliminated. Experimental evaluations of the proposed technique are done using L 2 error norm measure, which is the symmetric difference between the boundaries of reconstructed shape and the original shape. We demonstrate the efficacy of our automatic shape reconstruction technique by showing several examples and experiments with varying point set densities and distributions.

A fast unstructured mesh generation algorithm based on conforming centroidal Voronoi Delaunay triangulation (CfCVDT) algorithm (Ju, 2007) is proposed in this paper. In the new algorithm, the constrained Delaunay triangulation (CDT) algorithm is used only for the generation of the initial mesh. The mesh quality shall be continuously improved by updating the positions of vertices and flipping edges in a number of iterations. Since the most time consuming procedure in CfCVDT algorithm is the CDT in each iteration which has been successfully avoided in this new algorithm the efficiency has been significantly improved. Furthermore, the meshes generated by this algorithm have similar high quality features as that generated by CfCVDT. When complex interfaces are involved, our algorithm can keep the mesh conforming to the interfaces very efficiently. By using various density functions, this algorithm can produce high quality non-uniform meshes for potentially many applications. A fast high quality triangular mesh generation algorithm (FCfCVDT) is proposed based on the CfCVDT algorithm.The FCfCVDT algorithm significantly improves the efficiency of CfCVDT algorithm at the same time maintains the mesh quality.It is capable of generating high quality body/interface fitted meshes for complicate domains/interfaces.

TetGen is a C++ program for generating good quality tetrahedral meshes aimed to support numerical methods and scientific computing. The problem of quality tetrahedral mesh generation is challenged by many theoretical and practical issues. TetGen uses Delaunay-based algorithms which have theoretical guarantee of correctness. It can robustly handle arbitrary complex 3D geometries and is fast in practice. The source code of TetGen is freely available. This article presents the essential algorithms and techniques used to develop TetGen. The intended audience are researchers or developers in mesh generation or other related areas. It describes the key software components of TetGen, including an efficient tetrahedral mesh data structure, a set of enhanced local mesh operations (combination of flips and edge removal), and filtered exact geometric predicates. The essential algorithms include incremental Delaunay algorithms for inserting vertices, constrained Delaunay algorithms for inserting constraints (edges and triangles), a new edge recovery algorithm for recovering constraints, and a new constrained Delaunay refinement algorithm for adaptive quality tetrahedral mesh generation. Experimental examples as well as comparisons with other softwares are presented.

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. We propose a novel parallel 3D Delaunay meshing algorithm for large-scale simulations.The model information is kept during parallel triangulation process.A 3D local non-Delaunay mesh repair algorithm is proposed.The meshing results can be very approaching to the model boundary.The method can achieve high parallel performance and perfect scalability.

In this paper, we present a scalable three-dimensional hybrid parallel Delaunay image-to-mesh conversion algorithm (PDR.PODM) for distributed shared memory architectures. PDR.PODM is able to explore parallelism early in the mesh generation process thanks to the aggressive speculative approach employed by the Parallel Optimistic Delaunay Mesh generation algorithm (PODM). In addition, it decreases the communication overhead and improves data locality by making use of a data partitioning scheme offered by the Parallel Delaunay Refinement algorithm (PDR). PDR.PODM supports fully functional volume grading by creating elements with varying size. Small elements are created near boundary or inside the critical regions in order to capture the fine features while big elements are created in the rest of the mesh. We tested PDR.PODM on Blacklight, a distributed shared memory (DSM) machine in Pittsburgh Supercomputing Center. For the uniform mesh generation, we observed a weak scaling speedup of 163.8 and above for up to 256 cores as opposed to PODM whose weak scaling speedup is only 44.7 on 256 cores. PDR.PODM scales well on uniform refinement cases running on DSM supercomputers. The end result is that PDR.PODM can generate 18 million elements per second as opposed to 14 million per second in our earlier work. The varying size version sharply reduces the number of elements compared to the uniform version and thus reduces the time to generate the mesh while keeping the same fidelity. Represents the surface with topological and geometrical guarantees.Recovers the surface and meshes the volume simultaneously in parallel.Supports parallel graded mesh generation for multi-material objects.

Several sampling criteria had been proposed for C^2 smooth surfaces such that the reconstructed meshes from point samples are homeomorphic to the original surfaces. In this paper, based on a widely used sample criterion, we present proofs that give the upper and lower bounds of mesh quality (in terms of several triangle aspect ratios) for the reconstructed mesh. To make the proposed theoretical bounds useful in practical applications with real-world point data, we propose a novel mesh reconstruction method that works in three steps: (1) approximate Delaunay mesh reconstruction; (2) point data upsampling and (3) hole filling. Finally, examples are presented, which illustrate the effectiveness of the proposed method.

We propose the first working GPU algorithm for the 2D Delaunay refinement problem. Our algorithm adds Steiner points to an input planar straight line graph (PSLG) to generate a constrained Delaunay mesh with triangles having no angle smaller than an input θ. It is shown to run from a few times to an order of magnitude faster than the well-known Triangle software, which is the fastest CPU Delaunay mesh generator. Our implementation handles degeneracy and is numerically robust. It is proven to terminate with finite output size for an input PSLG with no angle smaller than 60° and θ ≥ 20.7°. In addition, we notice meshes generated by our algorithm are of similar sizes to that by Triangle, which has incorporated good consideration in keeping output small in size.

A new edge-based partition for triangle meshes is presented, the Seven Triangle Quasi-Delaunay partition (7T-QD). The proposed partition joins together ideas of the Seven Triangle Longest-Edge partition (7T-LE), and the classical criteria for constructing Delaunay meshes. The new partition performs similarly compared to the Delaunay triangulation (7T-D) with the benefit of being more robust and with a cheaper cost in computation. It will be proved that in most of the cases the 7T-QD is equal to the 7T-D. In addition, numerical tests will show that the difference on the minimum angle obtained by the 7T-QD and by the 7T-D is negligible.

To increase the efficiency when processing large data sets, a novel parallel algorithm is proposed for constructing the Delaunay triangulation of a planar point set based on a twofold-divide-and-conquer scheme. This algorithm automatically divides the planar point set into several non-overlapping subsets along the x-axis and y-axis directions alternately, according to the number of points and their spatial distribution. Next, the Guibas–Stolfi divide-and-conquer algorithm is applied to construct Delaunay sub-triangulations in each subset. Finally, the sub-triangulations are merged based on the binary tree. All three sequential steps are processed using multitasking parallel technology. Our results show that the proposed parallel algorithm is efficient for constructing the Delaunay triangulation with a good speed-up.

Delaunay refinement is a technique for generating unstructured meshes of triangles for use in interpolation, the finite element method, and the finite volume method. In theory and practice, meshes produced by Delaunay refinement satisfy guaranteed bounds on angles, edge lengths, the number of triangles, and the grading of triangles from small to large sizes. This article presents an intuitive framework for analyzing Delaunay refinement algorithms that unifies the pioneering mesh generation algorithms of L. Paul Chew and Jim Ruppert, improves the algorithms in several minor ways, and most importantly, helps to solve the difficult problem of meshing nonmanifold domains with small angles. Although small angles inherent in the input geometry cannot be removed, one would like to triangulate a domain without creating any new small angles. Unfortunately, this problem is not always soluble. A compromise is necessary. A Delaunay refinement algorithm is presented that can create a mesh in which most angles are 30° or greater and no angle is smaller than arcsin [ ( 3 / 2 ) sin ( ϕ / 2 ) ] ∼ ( 3 / 4 ) ϕ , where ϕ ⩽ 60 ° is the smallest angle separating two segments of the input domain. New angles smaller than 30° appear only near input angles smaller than 60°. In practice, the algorithm's performance is better than these bounds suggest. Another new result is that Ruppert's analysis technique can be used to reanalyze one of Chew's algorithms. Chew proved that his algorithm produces no angle smaller than 30° (barring small input angles), but without any guarantees on grading or number of triangles. He conjectures that his algorithm offers such guarantees. His conjecture is conditionally confirmed here: if the angle bound is relaxed to less than 26.5°, Chew's algorithm produces meshes (of domains without small input angles) that are nicely graded and size-optimal.

Although some nice properties of the Delaunay triangle-based structure have been exploited in many fingerprint authentication systems and satisfactory outcomes have been reported, most of these systems operate without template protection. In addition, the feature sets and similarity measures utilized in these systems are not suitable for existing template protection techniques. Moreover, local structural change caused by nonlinear distortion is often not considered adequately in these systems. In this paper, we propose a Delaunay quadrangle-based fingerprint authentication system to deal with nonlinear distortion-induced local structural change that the Delaunay triangle-based structure suffers. Fixed-length and alignment-free feature vectors extracted from Delaunay quadrangles are less sensitive to nonlinear distortion and more discriminative than those from Delaunay triangles and can be applied to existing template protection directly. Furthermore, we propose to construct a unique topology code from each Delaunay quadrangle. Not only can this unique topology code help to carry out accurate local registration under distortion, but it also enhances the security of template data. Experimental results on public databases and security analysis show that the Delaunay quadrangle-based system with topology code can achieve better performance and higher security level than the Delaunay triangle-based system, the Delaunay quadrangle-based system without topology code, and some other similar systems.

In this paper, we present a Delaunay refinement algorithm for meshing 3D medical images. We prove that (a) all the tetrahedra of the output mesh have \ratio\ less than 2, (b) all the boundary facets have planar angles larger than 30 degrees, (c) the symmetric (2-sided) Hausdorff distance between the object surface and mesh boundary is bounded from above by a user-specified parameter, and (d) the mesh boundary is ambient isotopic to the object surface. The first two guarantees assure that our algorithm removes most of the poorly shaped elements, making the mesh suitable for subsequent finite element analysis. The last two guarantees assure that the mesh boundary is a good geometrical and topological approximation of the object surface. Our long term goal is to develop a real time image-to-mesh conversion algorithm; towards that direction, our algorithm recovers the object surface and meshes the interior volume at the same time without sampling the object surface as a preprocessing step, unlike other Delaunay meshing techniques. Experimental evaluation of our algorithm on real medical data corroborates the theory.

A Frontal-Delaunay surface meshing algorithm for closed 2-manifolds embedded in R3 is presented. This new algorithm is an extension of existing restricted Delaunay-refinement techniques, in which the point-placement scheme is modified to improve element quality in the presence of mesh size constraints. Specifically, it is shown that the use of off-centre Steiner vertices, positioned along facets in the associated Voronoi diagram, typically leads to an improvement in the shape- and size-quality of the resulting surface tessellation. The new method can be viewed as a hybridisation of conventional Delaunay-refinement and advancing-front techniques, in which new vertices are positioned to satisfy both element size and shape constraints. It is shown that by restricting point-placement to faces of the associated Voronoi diagram, the new Frontal-Delaunay algorithm maintains many of the theoretical guarantees commonly associated with conventional restricted Delaunay-refinement techniques. The performance of the new Frontal-Delaunay scheme is investigated experimentally, via a series of comparative studies designed to contrast the performance of the new algorithm with a typical Delaunay-refinement technique. It is shown that the new Frontal-Delaunay algorithm inherits many of the benefits of both Delaunay-refinement and advancing-front type methods, typically leading to the construction of very high quality triangulations in practice. Experiments are conducted using a range of complex benchmarks, verifying the robustness and practical performance of the proposed scheme.

A novel method for boundary constrained tetrahedral mesh generation is proposed based on Advancing Front Technique (AFT) and conforming Delaunay triangulation. Given a triangulated surface mesh, AFT is firstly applied to mesh several layers of elements adjacent to the boundary. The rest of the domain is then meshed by the conforming Delaunay triangulation. The non-conformal interface between two parts of meshes are adjusted. Mesh refinement and mesh optimization are then preformed to obtain a more reasonable-sized mesh with better quality. Robustness and quality of the proposed method is shown. Convergence proof of each stage as well as the whole algorithm is provided. Various numerical examples are included as well as the quality of the meshes.

Amongst the flourishing Delaunay Triangulation methods, growth algorithm has been widely accepted because of its reputation of being simple and elegant. However, the parallelization of growth algorithm has not been fully exploited. In this work, a novel Growth algorithm of Delaunay Triangulation is proposed. The point cloud is first divided into two parts by a suitable curve and the separated areas are calculated by incremental algorithm. Triangles which cross with the curve are generated by a growth algorithm associated with uniform grid. At the process of merging, these grew triangles are used to detect incorrect triangles of the incremental algorithm areas. Method about generating triangles on curve is elaborated and a simple way to detect interferential triangles is also explained. With above method, triangulation calculation can be parallelized. Unlike the traditional divide-and-conquer method, no flip operation is needed in the proposed methodology. Thus, three dimensional applications are also made possible. A comparative research between tradition incremental algorithm and the proposed method has been conducted. Results show, the algorithm has a higher performance with less computation time.

By using Delaunay triangulation algorithm, triangulating with split-merge algorithm and the incremental insertion algorithm, improving the judgment that if the new inserted point meets the Delaunay triangulation "empty circle" criterion in synthesis algorithm, meanwhile, with the corresponding improvement of the LOP optimization algorithm, the design of weldment model in the virtual welding system has achieved good result.

It is so valuable that models merging of Delaunay triangulation are used widely in many applications. This paper researches the algorithm of models merging for Delaunay triangulation. A method for obtaining merged intersection lines and a algorithm for searching fast triangles in the extent of merging intersection lines are proposed, and whole process of models merging are expatiated detailedly. The algorithm is tested in experiments, and the result of experiment shows that this algorithm is very efficient.

A flexible mesh-generation framework for image representation based on Delaunay triangulations is proposed. By fixing the various degrees of freedom available within this framework, two mesh-generation methods, known as ID1 and ID2, are derived. These two methods are shown to perform extremely well, producing meshes of significantly higher quality than state-of-the-art schemes at relatively low computational cost. Furthermore, the ID1 and ID2 methods each provide a mechanism whereby mesh quality can be increased (or decreased) in return for a corresponding increase (or decrease) in computational cost. Lastly, we demonstrate that one component of our proposed methods, called bad-point replacement, can be used as a postprocessing optimization step that, when added to other previously-proposed mesh-generation methods, yields meshes of much greater quality.

This work presents a moving mesh methodology based on the solution of a pseudo flow problem. The mesh motion is modeled as a pseudo Stokes problem solved by an explicit finite element projection method. The mesh quality requirements are satisfied by employing a null divergent velocity condition. This methodology is applied to triangular unstructured meshes and compared to well known approaches such as the ones based on diffusion and pseudo structural problems. One of the test cases is an airfoil with a fully meshed domain. A specific rotation velocity is imposed as the airfoil boundary condition. The other test is a set of two cylinders that move toward each other. A mesh quality criteria is employed to identify critically distorted elements and to evaluate the performance of each mesh motion approach. The results obtained for each test case show that the pseudo-flow methodology produces satisfactory meshes during the moving process.

A method of unstructured tetrahedral mesh generation for general three-dimensional domain of arbitrary shape is presented. The method consists of two steps. First, generating the boundary tetrahedral mesh by the classic Delaunay method, then, using the advancing front method to create internal points and inserting them into the mesh by the Delaunay kernel procedure. The algorithm combines the advantages of the high point placement quality of the advancing front method and the high efficiency and convergence guaranty of the Delaunay algorithm. To get better efficiency, a new front identification and field point generation method is proposed and applied. Several examples have demonstrated the computational efficiency of our method and the high quality of meshes that generated within a reasonable time limit.

The concept of optimal Delaunay triangulation (ODT) and the corresponding error-based quality metric are first introduced. Then one kind of mesh smoothing algorithm for tetrahedral mesh based on the concept of ODT is examined. With regard to its problem of possible producing illegal elements, this paper proposes a modified smoothing scheme with a constrained optimization model for tetrahedral mesh quality improvement. The constrained optimization model is converted to an unconstrained one and then solved by integrating chaos search and BFGS (Broyden-Fletcher-Goldfarb-Shanno) algorithm efficiently. Quality improvement for tetrahedral mesh is finally achieved by alternately applying the presented smoothing scheme and re-triangulation. Some testing examples are given to demonstrate the effectiveness of the proposed approach.

The Delaunay triangulation is the standard choice for building triangulated irregular networks (TINs) to represent terrain surfaces. However, the Delaunay triangulation is based only on the 2D coordinates of the data points, ignoring their elevation. This can affect the quality of the approximating surface. In fact, it has long been recognized that sometimes it may be beneficial to use other, non-Delaunay, criteria that take elevation into account to build TINs. Data-dependent triangulations were introduced decades ago to address this exact issue. However, data-dependent trianguations are rarely used in practice, mostly because the optimization of data-dependent criteria often results in triangulations with many slivers (i.e., thin and elongated triangles), which can cause several types of problems. More recently, in the field of computational geometry, higher order Delaunay triangulations (HODTs) were introduced, trying to tackle both issues at the same time—data-dependent criteria and good triangle shape—by combining data-dependent criteria with a relaxation of the Delaunay criterion. In this paper, we present the first extensive experimental study on the practical use of HODTs, as a tool to build data-dependent TINs. We present experiments with two USGS 30m digital elevation models that show that the use of HODTs can give significant improvements over the Delaunay triangulation for the criteria previously identified as most important for data-dependent triangulations, often with only a minor increase in running times. The triangulations produced have measure values comparable to those obtained with pure data-dependent approaches, without compromising the shape of the triangles, and can be computed much faster.

Generation of watertight manifold triangle meshes from scanned point clouds has emerged as a key task in computer-aided design and inspection. An effective algorithm is presented in this paper, targeting the automatic creation of such triangle meshes from unorganized, scanned data points. The algorithm builds on the initial version of the Umbrella Facet Matching (UFM) algorithm developed by the authors. The mesh generation process starts with Delaunay triangulation of the given point cloud to determine the Delaunay triangle set at each data point. The algorithm then seeks to iteratively generate, in parallel, the local 2-dimensional manifold triangle mesh, resembling the shape of an open umbrella, at each data point from its Delaunay triangle set that fully overlaps with its neighboring umbrellas. Particularly, a four-level inheritance priority queuing mechanism is introduced to enhance the prioritization and ordering of the Delaunay triangles at each data point in order to facilitate the iterativ...

We present a data-parallel algorithm for the construction of Delaunay triangulations on the sphere. Our method combines a variant of the classical Bowyer-Watson point insertion algorithm [2, 14] with the recently published parallelization technique by Jacobsen et al. [7]. It resolves a breakdown situation of the latter approach and is suitable for practical implementation due to its compact formulation. Some complementary aspects are discussed such as the parallel workload, floating-point arithmetics and an application to interpolation of scattered data.

International audience; Consider a weighted graph G whose vertices are points in the plane and edges are line segments between pairs of points. The weight of each edge is the Euclidean distance between its two endpoints. A routing algorithm on G has a competitive ratio of c if the length of the path produced by the algorithm from any vertex s to any vertex t is at most c times the length of the shortest path from s to t in G. If the length of the path is at most c|[st]| (where |[st]| is the length of the line segment [st]), we say that the routing algorithm has a routing ratio of c. The routing algorithm is online if it makes forwarding decisions based on (1) the k-neighborhood in G (for some integer constant k>0) of the current position of the message and (2) limited information stored in the message header. We present an online routing algorithm on the Delaunay triangulation with routing ratio less than 5.90. This improves upon the algorithm with best known routing ratio of 15.48. The algorithm is an adaptation, to the Delaunay triangulation, of the classic routing algorithm by Chew on the L1-Delaunay triangulation. It makes forwarding decisions based on the 1-neighborhood of the current position of the message and the positions of the message source and destination only. This last requirement is an improvement over the best known online routing algorithms on the Delaunay triangulation which require the header of a message to also contain partial sums of distances along the routing path. We show that the routing ratio of Chew's algorithm on the Delaunay triangulation can be greater than 5.72 so the 5.90 upper bound is close to the best possible. We also show that the routing (resp., competitive) ratio of any deterministic k-local algorithm is at least 1.70 (resp., 1.33) for the Delaunay triangulation and 2.70 (resp. 1.12) for theL1-Delaunay triangulation. In the case of the L1-Delaunay triangulation, this implies that even though there always exists a path between s and t whose length is at most 2.61|[st]|, it is not always possible to route a message along a path of length less than 2.70|[st]|.

Despite its great success in improving the quality of a tetrahedral mesh, the original optimal Delaunay triangulation (ODT) is designed to move only inner vertices and thus cannot handle input meshes containing ''bad'' triangles on boundaries. In the current work, we present an integrated approach called boundary-optimized Delaunay triangulation (B-ODT) to smooth (improve) a tetrahedral mesh. In our method, both inner and boundary vertices are repositioned by analytically minimizing the L^1 error between a paraboloid function and its piecewise linear interpolation over the neighborhood of each vertex. In addition to the guaranteed volume-preserving property, the proposed algorithm can be readily adapted to preserve sharp features in the original mesh. A number of experiments are included to demonstrate the performance of our method.

This article studies the construction of self-stabilizing topologies for distributed systems. While recent research has focused on chain topologies where nodes need to be linearized with respect to their identifiers, we explore a natural and relevant 2-dimensional generalization. In particular, we present a local self-stabilizing algorithm DStab which is based on the concept of “local Delaunay graphs” and which forwards temporary edges in greedy fashion reminiscent of compass routing. DStab constructs a Delaunay graph from any initial connected topology and in a distributed manner in time O(n3) in the worst-case; if the initial network contains the Delaunay graph, the convergence time is only O(n) rounds. DStab also ensures that individual node joins and leaves affect a small part of the network only. Such self-stabilizing Delaunay networks have interesting applications and our construction gives insights into the necessary geometric reasoning that is required for higher-dimensional linearization problems.

Consider an algorithm for generating a triangle mesh interpolating a fixed set of 3D point samples, where the generated triangle set varies depending on some underlying parameters. In this paper we treat such an algorithm as a means of sampling the space of possible interpolant meshes, and then define a more robust algorithm based on drawing multiple such samples from this process and averaging them. As mesh connectivity graphs cannot be trivially averaged, we compute triangle statistics and then attempt to find a set of compatible triangles which maximize agreement between the sample meshes while also forming a manifold mesh. Essentially, each sample mesh ''votes'' for triangles, and hence we call our result a consensus mesh. Finding the optimal consensus mesh is combinatorially intractable, so we present an efficient greedy algorithm. We apply this strategy to two mesh generation processes-ball pivoting and localized tangent-space Delaunay triangulations. We then demonstrate that consensus meshing enables a generic decomposition of the meshing problem which supports trivial parallelization.

We present in this paper an algorithm for meshing implicit surfaces based on the Delaunay triangulation of a point-set adaptively sampled on an implicit surface. To improve the quality of the resulting triangular mesh, we use at each iteration a mesh optimization algorithm with the following objectives: optimizing the connectivity, retrieving the sharp features, regularizing the triangles shapes and minimizing the approximation error. Then, we extend this algorithm in order to handle functionally defined heterogeneous object surfaces, while maintaining a good quality for the triangles' shapes and the mesh features (geometrical sharp features and boundaries between different materials).

A new algorithm is presented to automatic generate conforming Delaunay triangulation of non-manifold geometric domains with acute angle features. The algorithm is based on Delaunay refinement technique, which often failed to terminate when there are small angles in input geometry. By assigning proper weights to vertices on sharp-angled elements and take place Delaunay triangulation with weighted Delaunay triangulation, the algorithm can accept any inputs without any bound on angle and without setting any protected area and adding any new vertices near the sharp-angled elements. The algorithm also guarantees bounded circumradius to shortest edge length for all elements except the ones near small input angles. The proof of terminator and some computation results are also presented.

Mesh generation by Delaunay refinement is a widely used technique for constructing guaranteed quality triangular and tetrahedral meshes. The quality guarantees are usually provided in terms of the bounds on circumradius-to-shortest-edge ratio and on the grading of the resulting mesh. Traditionally circumcenters of skinny elements and middle points of boundary faces and edges are used for the positions of inserted points. However, recently variations of the traditional algorithms are being proposed that are designed to achieve certain optimization objectives by inserting new points in neighborhoods of the center points. In this paper we propose a general approach to the selection of point positions by defining one-, two-, and three-dimensional selection regions such that any point insertion strategy based on these regions is automatically endowed with the theoretical guarantees proven here. In particular, for the input models defined by planar linear complexes under the assumption that no input angle is le...

We present Delaunay refinement algorithms for estimating local feature size on the input vertices of a 2D piecewise linear complex and on the input vertices and segments of a 3D piecewise linear complex. These algorithms are designed to eliminate the need for a local feature size oracle during quality mesh generation of domains containing acute input angles. In keeping with Ruppert's algorithm, encroachment in these algorithms can be determined through only local information in the current Delaunay triangulation. The algorithms are practical to implement and several examples are given.

This article presents an algorithm to construct constrained Delaunay tetrahedralizations of geometric domains bounded by piecewise smooth surfaces. Meshes are built from the bottom-up by first discretizing the boundary curves and then by sampling the smooth surfaces. The sampling procedure refines the Delaunay triangulation restricted to these surfaces, targeting topological violations and poor quality triangles. Unlike previously published algorithms adopting a similar approach, we propose to sample each smooth surface patch independently. This obviates the need for a boundary protection scheme around small dihedral angles in the input and can also lead to coarser constraining triangulations. Starting from a Delaunay tetrahedralization of the point samples, a combination of mesh reconfigurations and vertex insertions is then used to obtain a tetrahedralization constrained to the boundary surfaces. The algorithm is designed to produce tetrahedralizations that can be used in conjunction with a Delaunay refinement algorithm implemented on a Bowyer-Watson framework.

A simple and efficient method is presented in this paper to reliably reconstruct 2D polygonal curves and 3D triangular surfaces from discrete points based on the respective clustering of Delaunay circles and spheres. A Delaunay circle is the circumcircle of a Delaunay triangle in the 2D space, and a Delaunay sphere is the circumsphere of a Delaunay tetrahedron in the 3D space. The basic concept of the presented method is that all the incident Delaunay circles/spheres of a point are supposed to be clustered into two groups along the original curve/surface with satisfactory point density. The required point density is considered equivalent to that of meeting the well-documented r -sampling condition. With the clustering of Delaunay circles/spheres at each point, an initial partial mesh can be generated. An extrapolation heuristic is then applied to reconstructing the remainder mesh, often around sharp corners. This leads to the unique benefit of the presented method that point density around sharp corners does not have to be infinite. Implementation results have shown that the presented method can correctly reconstruct 2D curves and 3D surfaces for known point cloud data sets employed in the literature.

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.

In this paper, an adaptive spatial clustering algorithm based on Delaunay triangulation (ASCDT for short) is proposed. The ASCDT algorithm employs both statistical features of the edges of Delaunay triangulation and a novel spatial proximity definition based upon Delaunay triangulation to detect spatial clusters. Normally, this algorithm can automatically discover clusters of complicated shapes, and non-homogeneous densities in a spatial database, without the need to set parameters or prior knowledge. The user can also modify the parameter to fit with special applications. In addition, the algorithm is robust to noise. Experiments on both simulated and real-world spatial databases (i.e. an earthquake dataset in China) are utilized to demonstrate the effectiveness and advantages of the ASCDT algorithm.

Higher order Delaunay triangulations are a generalization of the Delaunay triangulation which 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^{n-3}$. Next we show that uniformly distributed points have an expected number of at least $2^{\rho_1 n(1+o(1))}$ first order Delaunay triangulations, where $\rho_1$ is an analytically defined constant ($\rho_1 \approx 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^{\rho_k n(1+o(1))}$, where $\rho_k$ can be calculated numerically., Comment: Manuscript accompanying shorter version in CIAC 2010; 13 pages

The present work consists to elaborate a computing program able to generate a Delaunay unstructured triangular meshes around the complex configurations applied in aerodynamics, like airfoil of aircraft, multi-elements airfoils, nacelle, fuselage, etc... While basing on the Delaunay criterion, again called 'in-circle criterion' of the hollow circle that means no point is inside a circle circumscribes a triangle of the mesh. The initial mesh can be set up by joining the trailing-edge point of the airfoil to all the outer boundary points, the surface mesh points for the airfoil are then introduced one at a time, and the internal nodes of the O-mesh generated by using a sequence of conformal transformation of Von Karman Trefftz through the whole domain of the out-flow. Each time a new point is introduced, the triangles failing the 'Delaunay criterion' are located using the tree-search algorithm, forming a convex cavity named 'Delaunay cavity'. These triangles will be broken and will be replaced by new triangles while connecting this new point to each of the points at vertices of this cavity. This generated a new triangulation and the algorithm repeats this process with the next new point until succeed to a Delaunay mesh. A Laplacian filter is used to reposition the mesh points in order to have a regular mesh clever to be exploited by the numerical methods: finite volume method or finite element method.

Divide-and-conquer algorithms provide computational efficiency for constructing Delaunay triangulations; however, their implementation is complicated. Most divide-and-conquer algorithms for Delaunay triangulation utilize edge-based structures, because triangles are frequently deleted and created during the merge process. However, as our proposed divide-and-conquer algorithm does not require existing edges to be deleted in the merge process, a simple array-based data structure can be used for the representation of the triangulation topology. Rather than deleting the edges of the conflicting triangles, which was used in previous methods, the Delaunay property is also preserved with a new flip propagation method in the merge phase. This array-based data structure is much simpler than the commonly used edge-based data structures and requires less memory allocation. The proposed algorithm arranges sites into a permutation vector that represents a kdtree with an array; thus, the space partitioning information is internally represented in the array without any additional data. Since the proposed divide-and-conquer algorithm is compact, the implementation complexity of conventional divideand-conquer triangulation algorithms can be avoided. Despite of the simplicity of this new algorithm, the experimental results indicate that the computational efficiency is comparable to the previous divide-and-conquer algorithms.