Efficient and good Delaunay meshes from random points

• Published in: Computer aided design 2011-11, Vol.43 (11), p.1506-1515
• Main Authors: Ebeida, Mohamed S., Mitchell, Scott A., Davidson, Andrew A., Patney, Anjul, Knupp, Patrick M., Owens, John D.
• Format: Article
• Language: English
• Subjects: Aids; Algorithms; Boundaries; Computational geometry and topology; Computer simulation; Computer-aided design, engineering, and manufacturing; Finite element method; Geophysical applications; Mesh generation; Product and assembly modeling; Sampling; Subroutines; Triangulation
• ISSN: 0010-4485; 1879-2685
• DOI: 10.1016/j.cad.2011.08.012

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/r2) 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. ► Conforming Delaunay triangulation algorithm based on maximal Poisson-disk sampling. ► Angles between 30° and 120°. ► Two-dimensional non-convex domains with holes, planar straight-line graphs. ►O(n) space, E(nlogn) time; efficient in practice. Background squares ensure all computations are local.