“Differential domain analysis for non-uniform sampling” by Wei and Wang

Sampling is a core component for many graphics applications including rendering, imaging, animation, and geometry processing. The efficacy of these applications often crucially depends upon the distribution quality of the underlying samples. While uniform sampling can be analyzed by using existing spatial and spectral methods, these cannot be easily extended to general non-uniform settings, such as adaptive, anisotropic, or non-Euclidean domains.We present new methods for analyzing non-uniform sample distributions. Our key insight is that standard Fourier analysis, which depends on samples’ spatial locations, can be reformulated into an equivalent form that depends only on the distribution of their location differentials. We call this differential domain analysis. The main benefit of this reformulation is that it bridges the fundamental connection between the samples’ spatial statistics and their spectral properties. In addition, it allows us to generalize our method with different computation kernels and differential measurements. Using this analysis, we can quantitatively measure the spatial and spectral properties of various non-uniform sample distributions, including adaptive, anisotropic, and non-Euclidean domains.

1. Alliez, P., Meyer, M., and Desbrun, M. 2002. Interactive geometry remeshing. In SIGGRAPH ’02, 347–354. Google Scholar
2. Balzer, M., Schlomer, T., and Deussen, O. 2009. Capacity-constrained point distributions: A variant of Lloyd’s method. In SIGGRAPH ’09, 86:1–8. Google Scholar
3. Bonetti, M., and Pagano, M. 2005. The interpoint distance distribution as a descriptor of point patterns, with an application to spatial disease clustering. Statistics in Medicine 24, 5, 753–73.Google ScholarCross Ref
4. Bowers, J., Wang, R., Wei, L.-Y., and Maletz, D. 2010. Parallel Poisson disk sampling with spectrum analysis on surfaces. In SIGGRAPH Asia ’10, 166:1–10. Google Scholar
5. Bracewell, R. 1999. The Fourier Transform and Its Applications. McGraw-Hill.Google Scholar
6. Clarberg, P., Jarosz, W., Akenine-Möller, T., and Jensen, H. W. 2005. Wavelet importance sampling: efficiently evaluating products of complex functions. In SIGGRAPH ’05, 1166–1175. Google Scholar
7. Cook, R. L. 1986. Stochastic sampling in computer graphics. ACM Trans. Graph. 5, 1, 51–72. Google ScholarDigital Library
8. Couch, II, L. W. 2001. Digital and Analog Communication Systems, 6th ed. Prentice Hall, New Jersey. Google Scholar
9. Dale, M. R. T., Dixon, P., Fortin, M.-J., Legendre, P., Myers, D. E., and Rosenberg, M. S. 2002. Conceptual and mathematical relationships among methods for spatial analysis. ECOGRAPHY, 25, 558–577.Google ScholarCross Ref
10. Dippé, M. A. Z., and Wold, E. H. 1985. Antialiasing through stochastic sampling. In SIGGRAPH ’85, 69–78. Google Scholar
11. Dutre, P., Bala, K., and Bekaert, P. 2002. Advanced Global Illumination. A. K. Peters, Ltd., Natick, MA, USA. Google Scholar
12. Dutt, A., and Rokhlin, V. 1993. Fast Fourier transforms for nonequispaced data. SIAM J. Sci. Comput. 14, 6, 1368–1393. Google ScholarDigital Library
13. Fisher, M., Schröder, P., Desbrun, M., and Hoppe, H. 2007. Design of tangent vector fields. In SIGGRAPH ’07, 56. Google Scholar
14. Fu, Y., and Zhou, B. 2008. Direct sampling on surfaces for high quality remeshing. In SPM ’08, 115–124. Google Scholar
15. Glassner, A. S. 1994. Principles of Digital Image Synthesis. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA. Google Scholar
16. Huang, J., Zhang, M., Ma, J., Liu, X., Kobbelt, L., and Bao, H. 2008. Spectral quadrangulation with orientation and alignment control. In SIGGRAPH Asia ’08, 147:1–9. Google Scholar
17. Karni, Z., and Gotsman, C. 2000. Spectral compression of mesh geometry. In SIGGRAPH ’00, 279–286. Google ScholarDigital Library
18. Kopf, J., Cohen-Or, D., Deussen, O., and Lischinski, D. 2006. Recursive Wang tiles for real-time blue noise. In SIGGRAPH ’06, 509–518. Google Scholar
19. Lagae, A., and Dutré, P. 2008. A comparison of methods for generating Poisson disk distributions. Computer Graphics Forum 21, 1, 114–129.Google ScholarCross Ref
20. Lau, D., Ulichney, R., and Arce, G. 2003. Fundamental characteristics of halftone textures: blue-noise and green-noise. IEEE Signal Processing Magazine 20, 4 (July), 28–38.Google ScholarCross Ref
21. Li, H., Wei, L.-Y., Sander, P., and Fu, C.-W. 2010. Anisotropic blue noise sampling. In SIGGRAPH Asia ’10, 167:1–12. Google Scholar
22. Lloyd, S. 1983. An optimization approach to relaxation labeling algorithms. Image and Vision Computing 1, 2.Google ScholarCross Ref
23. Mitchell, D. P. 1987. Generating antialiased images at low sampling densities. In SIGGRAPH ’87, 65–72. Google Scholar
24. Ostromoukhov, V., Donohue, C., and Jodoin, P.-M. 2004. Fast hierarchical importance sampling with blue noise properties. In SIGGRAPH ’04, 488–495. Google Scholar
25. Ostromoukhov, V. 2007. Sampling with polyominoes. In SIGGRAPH ’07, 78. Google Scholar
26. Öztireli, A. C., Alexa, M., and Gross, M. 2010. Spectral sampling of manifolds. In SIGGRAPH ASIA ’10, 168:1–8. Google Scholar
27. Palacios, J., and Zhang, E. 2007. Rotational symmetry field design on surfaces. In SIGGRAPH ’07, 55. Google Scholar
28. Pharr, M., and Humphreys, G. 2004. Physically Based Rendering: From Theory to Implementation. Morgan Kaufmann Publishers Inc. Google Scholar
29. Potts, D., Steidl, G., and Tasche, M., 2000. Fast Fourier transforms for nonequispaced data: A tutorial.Google Scholar
30. Ripley, B. D. 1977. Modeling spatial patterns. J. R. Stat. Soc. 39, 2, 172–212.Google Scholar
31. Schlomer, T., and Deussen, O. 2010. Towards a standardized spectral analysis of point sets with applications in graphics. Tech. rep., University of Konstanz.Google Scholar
32. Schmidt, R., Grimm, C., and Wyvill, B. 2006. Interactive decal compositing with discrete exponential maps. In SIGGRAPH ’06, 605–613. Google Scholar
33. Scott, D. W. 1992. Multivariate density estimation: theory, practice, and visualization. Wiley.Google Scholar
34. Shirley, P. 1991. Discrepancy as a quality measure for sample distributions. In Eurographics ’91, 183–194.Google Scholar
35. Turk, G. 1992. Re-tiling polygonal surfaces. In SIGGRAPH ’92, 55–64. Google Scholar
36. Ulichney, R. 1987. Digital Halftoning. MIT Press, Cambridge, MA. Google Scholar
37. Wei, L.-Y. 2008. Parallel Poisson disk sampling. In SIGGRAPH ’08, 20:1–9. Google Scholar
38. Wei, L.-Y. 2010. Multi-class blue noise sampling. In SIGGRAPH ’10, 79:1–8. Google Scholar
39. Wolberg, G. 1994. Digital Image Warping. IEEE Computer Society Press, Los Alamitos, CA, USA. Google Scholar