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

  • ©Li-Yi Wei and Rui Wang




    Differential domain analysis for non-uniform sampling



    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

ACM Digital Library Publication: