Abstract
We present the near-Maximal Algorithm for Poisson-disk Sampling (nMAPS) to generate point distributions for variable resolution Delaunay triangular and tetrahedral meshes in two and three-dimensions, respectively. nMAPS consists of two principal stages. In the first stage, an initial point distribution is produced using a cell-based rejection algorithm. In the second stage, holes in the sample are detected using an efficient background grid and filled in to obtain a near-maximal covering. Extensive testing shows that nMAPS generates a variable resolution mesh in linear run time with the number of accepted points. We demonstrate nMAPS capabilities by meshing three-dimensional discrete fracture networks (DFN) and the surrounding volume. The discretized boundaries of the fractures, which are represented as planar polygons, are used as the seed of 2D-nMAPS to produce a conforming Delaunay triangulation. The combined mesh of the DFN is used as the seed for 3D-nMAPS, which produces conforming Delaunay tetrahedra surrounding the network. Under a set of conditions that naturally arise in maximal Poisson-disk samples and are satisfied by nMAPS, the two-dimensional Delaunay triangulations are guaranteed to only have well-behaved triangular faces. While nMAPS does not provide triangulation quality bounds in more than two dimensions, we found that low-quality tetrahedra in 3D are infrequent, can be readily detected and removed, and a high quality balanced mesh is produced.
| Original language | English |
|---|---|
| Article number | 114094 |
| Journal | Journal of Computational and Applied Mathematics |
| Volume | 407 |
| DOIs | |
| State | Published - Jun 2022 |
Funding
J.K. gratefully acknowledges support from the 2020 National Science Foundation Mathematical Sciences Graduate Internship, USA to conduct this research at Los Alamos National Laboratory, USA . J.D.H. and M.R.S. gratefully acknowledges support from the LANL LDRD program, USA office Grant Numbers #20180621ECR and #20220019DR , the Department of Energy Basic Energy Sciences program (LANLE3W1), USA , and the Spent Fuel and Waste Science and Technology Campaign, Office of Nuclear Energy, of the U.S. Department of Energy . M.R.S. would also like to thank support from the Center for Nonlinear Studies. J.M.R. received support from DOE, Contract No. DE-AC05-00OR22725. Los Alamos National Laboratory is operated by Triad National Security, LLC, for the National Nuclear Security Administration of U.S. Department of Energy (Contract No. 89233218CNA000001). This work was prepared as an account of work sponsored by an agency of the United States Government. The views and opinions of authors expressed herein do not necessarily state or reflect those of the United States Government or any agency thereof, its contractors or subcontractors. LAUR # LA-UR-21-24804.
Keywords
- Conforming Delaunay triangulation
- Discrete fracture network
- Maximal Poisson-disk sampling
- Mesh generation