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.
翻译:我们为Poisson-disk 尺寸取样( NAMAS) 提供了接近最大度的三角方位算法( NAPS ), 以生成可变解分解分解的点分布。 nMAPS 由两个主要阶段组成。 在第一阶段, 初始点分布是使用基于单元格的拒绝算法生成的。 在第二阶段, 样本中的洞是使用高效的背景网格检测的, 并填充以获得接近最大值的覆盖。 广泛的测试显示, nMAPS 在可接受点数的运行期间, 生成线性解解的可变分辨率网格。 我们通过模拟三维离裂网络( DFN) 及其周围的体积来显示 NMAPS 能力。 骨折的分解边界是2D- NMAPS 的种子, 匹配的面部位是三维的面, 快速度是三维的种子, 运行的三维的种子是三维的种子 。 在两维的三角网络中, 运行最深的三维 。