In the field of computer graphics, maximal Poisson-disk sampling (MPS) is a fundamental research topic. An ideal sampling set should satisfy unbiased sampling property, minimal distance property, and maximal sampling property. In general, MPS is obtained by Dart Throwing, as we all know, the drawback of this method is unable to precisely control the number of samples. In view of the above problem, this work proposes a novelty algorithm that can precisely control the number of samples of two-dimensional radius-equal MPS, and satisfy other properties simultaneously. Unlike existing methods, the proposed method controls the number of samples by adjusting sampling radius. Firstly, according to user-specified the number of samples and sampling domain (closed polygon), initial samples are randomly obtained, then Delaunay triangulation is conducted, and taking as current sampling radius the shortest edge length of the triangulation. Secondly, iteratively removing the endpoint of global shortest edge with larger neighborhood-averaged edge length, and then using Dart Throwing to randomly insert it into gap region that is calculated at current sampling radius. By iteratively adjusting the position of points, the sampling radius increases gradually, finally, MPS with fixed number of sampling point can be achieved. Experimental results show that this method generates point sets with high quality, at the same time, ensures the excellent blue-noise property for MPS.
国家自然科学基金(61271431,61372168,61620106003,61571439)
Figure 1
(Color online) The workflow of our method. (a) Initial sampling; (b) and (c) show the sampling after 100 and 300 iterations, respectively; (d) final result
Figure 2
(Color online) Illustration of gap primitives. (a) Triangle; (b) quadrilateral; (c) pentagon; (d) hexagon
Figure 3
(Color online) Illustration of one iteration
Figure 4
Comparison of the sampling quality
Figure 5
Sampling and triangulation in polygonal domains
Figure 6
Histograms of the relative radius of FPO and our method
Figure 7
PCF analysis of points with different numbers. (a) 0.5k; (b) 1k; (c) 2k; (d) 20k
Figure 10
(Color online) Timing comparison
| Method | $\delta_X$ | $Q_{\rm min}$ | $Q_{\rm avg}$ | $\theta_{\rm min}$ | $\overline{\theta}_{\rm min}$ | $\theta_{\rm max}$ | $\theta_{<30^\circ}$ | $\theta_{>90^\circ}$ | $V_{567}%$ |
| FPO | 0.925 | 0.567 | 0.856 | 35.12 | 50.90 | 107.51 | 0.00 | 6.50 | 99.61 |
| SER | 0.781 | 0.509 | 0.813 | 30.54 | 46.11 | 114.41 | 0.00 | 14.50 | 96.48 |
| MPS | 0.780 | 0.487 | 0.806 | 30.19 | 45.30 | 117.11 | 0.00 | 15.07 | 96.53 |
| OURS | 0.855 | 0.514 | 0.833 | 30.21 | 47.97 | 113.85 | 0.00 | 12.60 | 98.30 |
| OURS CV($%$) | 0.19 | 3.44 | 0.38 | 0.22 | 0.47 | 1.76 | 0.00 | 2.46 | 0.31 |
| |
|---|
| 输入: 采样点数$N$和采样区域$\Omega$ |
| 输出: 采样点集$X$ |
| 初始化: 在$\Omega$中随机产生$N$个采样点, 并进行Delaunay三角化(DT); |
| |
|
寻找DT的全局最短边, 删除其中邻域平均边长较大的端点; |
|
局部更新DT, 更新采样半径为当前DT的最短边长; |
|
执行gap检测操作; |
|
|
|
将删除的顶点插入到DT的最大外接圆的圆心; |
|
BREAK; //算法结束; |
|
|
|
执行gap基元提取操作; |
|
在空隙区域中随机产生一个采样点, 将其插入到$X$中; |
|
动态更新DT; |
| |
| Boundary name | $\delta_X$ | $Q_{\rm min}$ | $Q_{\rm avg}$ | $\theta_{\rm min}$ | $\overline{\theta}_{\rm min}$ | $\theta_{\rm max}$ | $\theta_{<30^\circ}$ | $\theta_{>90^\circ}$ | $V_{567}%$ |
| Wavy | 0.816 | 0.513 | 0.813 | 30.62 | 45.82 | 114.01 | 0.00 | 14.25 | 94.85 |
| Face | 0.822 | 0.502 | 0.818 | 31.12 | 45.30 | 115.33 | 0.00 | 13.96 | 94.12 |
| Dolphin | 0.810 | 0.490 | 0.813 | 30.70 | 46.03 | 116.84 | 0.00 | 14.23 | 93.95 |
| S | 0.830 | 0.512 | 0.813 | 31.02 | 46.12 | 113.08 | 0.00 | 13.32 | 94.33 |
Download PDF
