Analyzing surface sampling patterns using the localized pair correlation function

Weize Quan; Jianwei Guo; Dong-Ming Yan; Weiliang Meng; Xiaopeng Zhang

doi:10.1007/s41095-016-0050-8

Computational Visual Media 2016, 2(3): 219-230 https://doi.org/10.1007/s41095-016-0050-8

Research Article |

Open Access | Issue | Published: 13 May 2016

Analyzing surface sampling patterns using the localized pair correlation function

Show Author's Information Hide Author's Information Weize Quan^¹, Jianwei Guo^¹, Dong-Ming Yan^¹(

), Weiliang Meng^¹, Xiaopeng Zhang^¹(

)

1 NLPR-LIAMA, Institute of Automation, Chinese Academy of Sciences, Beijing 100190, China.

Keywords:

spectral analysis, point distribution, pair correlation function (PCF), mesh surface

Cite this article:

Quan W, Guo J, Yan D-M, et al. Analyzing surface sampling patterns using the localized pair correlation function. Computational Visual Media, 2016, 2(3): 219-230. https://doi.org/10.1007/s41095-016-0050-8

Download citation

EndNote(RIS)

BibTeX

575

Views

Downloads

Citations

Crossref

N/A

WoS

Scopus

CSCD

Abstract Full text About this article

Abstract

Point distributions with different characteristics have a crucial influence on graphics applications. Various analysis tools have been developed in recent years, mainly for blue noise sampling in Euclidean domains. In this paper, we present a new method to analyze the properties of general sampling patterns that are distributed on mesh surfaces. The core idea is to generalize to surfaces the pair correlation function (PCF) which has successfully been employed in sampling pattern analysis and synthesis in 2D and 3D. Experimental results demonstrate that the proposed approach can reveal correlations of point sets generated by a wide range of sampling algorithms. An acceleration technique is also suggested to improve the performance of the PCF.

Full text

Abstract

Full text

Outline

About this article

Analyzing surface sampling patterns using the localized pair correlation function

Show Author's information Hide Author's Information Weize Quan^¹, Jianwei Guo^¹, Dong-Ming Yan^¹(

), Weiliang Meng^¹, Xiaopeng Zhang^¹(

)

1 NLPR-LIAMA, Institute of Automation, Chinese Academy of Sciences, Beijing 100190, China.

Abstract

Keywords: spectral analysis, point distribution, pair correlation function (PCF), mesh surface

References(34)

[1]

Mitchell, D. P. Generating antialiased images at low sampling densities. In: Proceedings of the 14th Annual Conference on Computer Graphics and Interactive Techniques, 65-72, 1987.

DOI

[2]

Fattal, R. Blue-noise point sampling using kernel density model. ACM Transactions on Graphics Vol. 28, No. 3, Article No. 48, 2011.

DOI Google Scholar

[3]

Deussen, O.; Hanrahan, P.; Lintermann, B.; Mĕhh, R.; Pharr, M.; Prusinkiewicz, P. Realistic modeling and rendering of plant ecosystems. In: Proceedings of the 25th Annual Conference on Computer Graphics and Interactive Techniques, 275-286, 1998.

DOI

[4]

Tzeng, S.; Wei, L.-Y. Parallel white noise generation on a GPU via cryptographic hash. In: Proceedings of the 2008 Symposium on Interactive 3D Graphics and Games, 79-87, 2008.

DOI

[5]

Ostling, A.; Harte, J.; Green, J. Self-similarity and clustering in the spatial distribution of species. Science Vol. 290, No. 5492, 671a-671, 2000.

DOI Google Scholar

[6]

Lagae, A.; Dutré, P. A comparison of methods for generating Poisson disk distributions. Computer Graphics Forum Vol. 27, No. 1, 114-129, 2008.

DOI Google Scholar

[7]

Ulichney, R. Digital Halftoning. The MIT Press, 1987.

DOI

[8]

Schlömer, T.; Deussen, O. Accurate spectral analysis of two-dimensional point sets. Journal of Graphics, GPU, and Game Tools Vol. 15, No. 3, 152-160, 2011.

DOI Google Scholar

[9]

Wei, L.-Y.; Wang, R. Differential domain analysis for non-uniform sampling. ACM Transactions on Graphics Vol. 30, No. 4, Article No. 50, 2011.

DOI Google Scholar

[10]

Öztireli, A. C.; Gross, M. Analysis and synthesis of point distributions based on pair correlation. ACM Transactions on Graphics Vol. 31, No. 6, Article No. 170, 2012.

DOI Google Scholar

[11]

Lloyd, S. A. Least squares quantization in PCM. IEEE Transactions on Information Theory Vol. 28, No. 2, 129-137, 1982.

DOI Google Scholar

[12]

Cook, R. L. Stochastic sampling in computer graphics. ACM Transactions on Graphics Vol. 5, No. 1, 51-72, 1986.

DOI Google Scholar

[13]

McCool, M.; Fiume, E. Hierarchical Poisson disk sampling distributions. In: Proceedings of the Conference on Graphics Interface, 94-105, 1992.

[14]

Yan, D.-M.; Guo, J.-W.; Wang, B.; Zhang, X.-P.; Wonka, P. A survey of blue-noise sampling and its applications. Journal of Computer Science and Technology Vol. 30, No. 3, 439-452, 2015.

DOI Google Scholar

[15]

Cline, D.; Jeschke, S.; White, K.; Razdan, A.; Wonka, P. Dart throwing on surfaces. Computer Graphics Forum Vol. 28, No. 4, 1217-1226, 2009.

DOI Google Scholar

[16]

Yan, D.-M.; Wonka, P. Gap processing for adaptive maximal Poisson-disk sampling. ACM Transactions on Graphics Vol. 32, No. 5, Article No. 148, 2013.

DOI Google Scholar

[17]

Guo, J.; Yan, D.-M.; Jia, X.; Zhang, X. Efficient maximal Poisson-disk sampling and remeshing on surfaces. Computers & Graphics Vol. 46, Nos. 6–8, 72-79, 2015.

DOI Google Scholar

[18]

Xu, Y.; Hu, R.; Gotsman, C.; Liu, L. Blue noise sampling of surfaces. Computers & Graphics Vol. 36, No. 4, 232-240, 2012.

DOI Google Scholar

[19]

Balzer, M.; Schlömer, T.; Deussen, O. Capacity-constrained point distributions: A variant of Lloyd’s method. ACM Transactions on Graphics Vol. 28, No. 3, Article No. 86, 2009.

DOI Google Scholar

[20]

Chen, Z.; Yuan, Z.; Choi, Y.-K.; Liu, L.; Wang, W. Variational blue noise sampling. IEEE Transactions on Visualization and Computer Graphics Vol. 18, No. 10, 1784-1796, 2012.

DOI Google Scholar

[21]

Yan,

D.-M.

; Lévy,

; Liu,

; Sun,

; Wang,

Isotropic remeshing with fast and exact computation of restricted Voronoi diagram. Computer Graphics Forum Vol. 28, No. 5, 1445-1454, 2009.10.1111/j.1467-8659.2009.01521.x

DOI Google Scholar

[22]

Zhang, S.; Guo, J.; Zhang, H.; Jia, X.; Yan, D.-M.; Yong, J.; Wonka, P. Capacity constrained blue-noise sampling on surfaces. Computers & Graphics Vol. 55, 44-54, 2016.

DOI Google Scholar

[23]

De Goes, F.; Breeden, K.; Ostromoukhov, V.; Desbrun, M. Blue noise through optimal transport. ACM Transactions on Graphics Vol. 31, No. 6, Article No. 171, 2012.

DOI Google Scholar

[24]

Liu, Y.-J.; Chen, Z.; Tang, K. Construction of iso-contours, bisectors, and Voronoi diagrams on triangulated surfaces. IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 33, No. 8, 1502-1517, 2011.

DOI Google Scholar

[25]

Yan, D.-M.; Guo, J.; Jia, X.; Zhang, X.; Wonka, P. Blue-noise remeshing with farthest point optimization. Computer Graphics Forum Vol. 33, No. 5, 167-176, 2014.

DOI Google Scholar

[26]

Schlömer, T.; Heck, D.; Deussen, O. Farthestpoint optimized point sets with maximized minimum distance. In: Proceedings of the ACM SIGGRAPH Symposium on High Performance Graphics, 135-142, 2011.

DOI

[27]

Shirley, P. Discrepancy as a quality measure for sample distributions. In: Proceedings of Eurographics 91, 183-193, 1991.

[28]

Heck, D.; Schlömer, T.; Deussen, O. Blue noise sampling with controlled aliasing. ACM Transactions on Graphics Vol. 32, No. 3, Article No. 25, 2013.

DOI Google Scholar

[29]

Subr, K.; Kautz, J. Fourier analysis of stochastic sampling strategies for assessing bias and variance in integration. ACM Transactions on Graphics Vol. 32, No. 4, Article No. 128, 2013.

DOI Google Scholar

[30]

Bowers, J.; Wang, R.; Wei, L.-Y.; Maletz, D. Parallel Poisson disk sampling with spectrum analysis on surfaces. ACM Transactions on Graphics Vol. 29, No. 6, Article No. 166, 2010.

DOI Google Scholar

[31]

Du, Q.; Gunzburger, M. D.; Ju, L. Constrained centroidal Voronoi tesselations for surfaces. SIAM Journal on Scientific Computing Vol. 24, No. 5, 1488-1506, 2003.

DOI Google Scholar

[32]

Yuksel, C. Sample elimination for generating Poisson disk sample sets. Computer Graphics Forum Vol. 34, No. 2, 25-32, 2015

DOI Google Scholar

[33]

Amenta, N.; Bern, M.; Kamvysselis, M. A new Voronoi-based surface reconstruction algorithm. In: Proceedings of the 25th Annual Conference on Computer Graphics and Interactive Techniques, 415-421, 1998.

DOI

[34]

Xu, C.; Wang, T. Y.; Liu, Y.-J.; Liu, L.; He, Y. Fast wavefront propagation (FWP) for computing exact geodesic distances on meshes. IEEE Transactions on Visualization and Computer Graphics Vol. 21, No. 7, 822-834, 2015.

DOI Google Scholar

About this article

Publication history

Acknowledgements

Rights and permissions

Publication history

Revised: 23 November 2015

Accepted: 18 March 2016

Published: 13 May 2016

Issue date: September 2016

Copyright

Acknowledgements

This work was partially funded by the National Natural Science Foundation of China (Nos. 61372168, 61571439, 61572502, and 61271431), and the National High-tech R&D Program of China (863 Program) (No. 2015AA016402).

Rights and permissions

This article is published with open access at Springerlink.com

The articles published in this journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http:// creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.

Other papers from this open access journal are available free of charge from http://www.springer.com/journal/41095. To submit a manuscript, please go to https://www. editorialmanager.com/cvmj.