基于采样半径优化的最大化Poisson圆盘采样  

Maximal Poisson-disk sampling by sampling radius optimization

作　　者：全卫泽[1,2] 郭建伟[1] 张义宽[1] 孟维亮[1] 张晓鹏[1] 严冬明[1] Weize QUAN Jianwei GUO Yi-Kuan ZHANG Weiliang MENG Xiaopeng ZHANG Dong-Ming YAN(National Laboratory of Pattern Recognition, Institute of Automation, Chinese Academy of Sciences, Beijing 100190, China University of Chinese Academy of Sciences, Beijing 100049, China)

机构地区：[1]模式识别国家重点实验室中国科学院自动化研究所,北京100190 [2]中国科学院大学,北京100049

出　　处：《中国科学：信息科学》2017年第4期442-454,共13页Scientia Sinica(Informationis)

基　　金：国家自然科学基金(批准号:61271431;61372168;61620106003;61571439)资助项目

摘　　要：最大化Poisson圆盘采样(maximal Poisson-disk sampling,MPS)是计算机图形学领域的一个基础研究问题.一个理想的采样点集应该满足无偏差采样性质、最小距离属性和最大化性质.传统的最大化Poisson圆盘采样一般通过投镖法(dart throwing)来实现,但是众所周知,该方法的不足之处在于无法精确控制采样点数目.针对该问题,本文提出了一种新的方法可以实现精确控制二维等半径最大化Poisson圆盘采样的点数并且同时满足其他性质.与已有方法不同的是,本文提出的方法通过调整采样半径达到控制采样点数的目的.首先,根据用户指定的采样点数目和采样区域(闭合的多边形)生成随机点集,并进行Delaunay三角化,并且将当前三角化中的最短边长作为当前的采样半径;接着,迭代地移除全局最短边中邻域平均边长较大的采样点,然后采用投镖法将其随机插入到以当前采样半径计算得到的空隙区域内.通过迭代地调整采样点的位置,采样半径不断增大,从而最后实现固定点数的最大化Poisson圆盘采样.大量实验结果表明,该方法可以得到高质量的采样点集,同时很好地保持了采样点集的蓝噪声性质.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.

关 键 词：最大化Poisson圆盘采样 采样半径优化 固定点数 蓝噪声 高质量点集 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]