Name
Abstract | ||
|---|---|---|
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^o and 120^o, 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^o and 180^o 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=@Q(Area/r^2) 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. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1016/j.cad.2011.08.012 | Computer-Aided Design |
Keywords | Field | DocType |
mesh edge,square background mesh,good delaunay mesh,maximal poisson disk sampling,expected time,deterministic mesh,random mesh,constant time,domain boundary,maximal poisson distribution,random point,cdt method,computer aided design,engineering,poisson distribution,mesh generation,delaunay triangulation | Combinatorics,Polygon mesh,Vertex (geometry),Triangulation (social science),Time complexity,Constrained Delaunay triangulation,Mesh generation,Mathematics,Delaunay triangulation,Ruppert's algorithm | Journal |
Volume | Issue | ISSN |
43 | 11 | 0010-4485 |
Citations | PageRank | References |
15 | 0.70 | 32 |
Authors | ||
6 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mohamed S. Ebeida | 1 | 153 | 11.28 |
| Scott A. Mitchell | 2 | 461 | 77.77 |
| Andrew A. Davidson | 3 | 186 | 7.76 |
| Anjul Patney | 4 | 347 | 24.05 |
| Patrick M. Knupp | 5 | 499 | 58.74 |
| John D. Owens | 6 | 3263 | 298.85 |