logo

Journals Books
Advanced Search
Sign in Register

中文

SCIENTIA SINICA Informationis
Download PDF
SCIENTIA SINICA Informationis, Volume 47 , Issue 4 : 442-454(2017) https://doi.org/10.1360/N112016-00167

Maximal Poisson-disk sampling by sampling radius optimization

Weize QUAN 1,2, Jianwei GUO 1, Yi-Kuan ZHANG 1, Weiliang MENG 1, Xiaopeng ZHANG 1, Dong-Ming YAN 1,*
More info
  • ReceivedJul 5, 2016
  • AcceptedOct 23, 2016
  • PublishedMar 14, 2017
Previous Table of Contents Next
Share
Rating

Abstract


Funded by

国家自然科学基金(61271431,61372168,61620106003,61571439)

  • Click to view Download high-quality image

    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

  • Click to view Download high-quality image

    Figure 2

    (Color online) Illustration of gap primitives. (a) Triangle; (b) quadrilateral; (c) pentagon; (d) hexagon

  • Click to view Download high-quality image

    Figure 3

    (Color online) Illustration of one iteration

  • Click to view Download high-quality image

    Figure 4

    Comparison of the sampling quality

  • Click to view Download high-quality image

    Figure 5

    Sampling and triangulation in polygonal domains

  • Click to view Download high-quality image

    Figure 6

    Histograms of the relative radius of FPO and our method

  • Click to view Download high-quality image

    Figure 7

    PCF analysis of points with different numbers. (a) 0.5k; (b) 1k; (c) 2k; (d) 20k

  • Click to view Download high-quality image

    Figure 10

    (Color online) Timing comparison

  • Table 1   Statistics of the sampling and the triangulation quality in periodic domain
    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
  •   

    Algorithm 1 基于采样半径优化的最大化Poisson圆盘采样算法

    输入: 采样点数$N$和采样区域$\Omega$

    输出: 采样点集$X$

    初始化: 在$\Omega$中随机产生$N$个采样点, 并进行Delaunay三角化(DT);

    while TRUE do

    寻找DT的全局最短边, 删除其中邻域平均边长较大的端点;

    局部更新DT, 更新采样半径为当前DT的最短边长;

    执行gap检测操作;

    if 不存在gap三角形 then

    将删除的顶点插入到DT的最大外接圆的圆心;

    BREAK; //算法结束;

    end if

    执行gap基元提取操作;

    在空隙区域中随机产生一个采样点, 将其插入到$X$中;

    动态更新DT;

    end while

  • Table 2   Statistics of the sampling and the triangulation quality in arbitrary boundary conditions
    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