“Fast hierarchical importance sampling with blue noise properties” by Ostromoukhov, Donohue and Jodoin

  • ©Victor Ostromoukhov, Charles Donohue, and Pierre-Marc Jodoin




    Fast hierarchical importance sampling with blue noise properties



    This paper presents a novel method for efficiently generating a good sampling pattern given an importance density over a 2D domain. A Penrose tiling is hierarchically subdivided creating a sufficiently large number of sample points. These points are numbered using the Fibonacci number system, and these numbers are used to threshold the samples against the local value of the importance density. Pre-computed correction vectors, obtained using relaxation, are used to improve the spectral characteristics of the sampling pattern. The technique is deterministic and very fast; the sampling time grows linearly with the required number of samples. We illustrate our technique with importance-based environment mapping, but the technique is versatile enough to be used in a large variety of computer graphics applications, such as light transport calculations, digital halftoning, geometry processing, and various rendering techniques.


    1. AGARWAL, S., RAMAMOORTHI, R., BELONGIE, S., AND JENSEN, H. 2003. Structured importance sampling of environment maps. ACM Trans. on Graphics 22, 3 (July), 605–612. Google ScholarDigital Library
    2. ALLIEZ, P., MEYER, M., AND DESBRUN, M. 2002. Interactive geometry remeshing. ACM Trans. on Graphics 21, 3, 347–354. Google ScholarDigital Library
    3. BAYER, B. 1973. An optimum method for two-level rendition of continuous-tone pictures. In IEEE Int. Conf. on Communications, 11–15.Google Scholar
    4. COHEN, J., AND DEBEVEC, P. 2001. LightGen, HDRShop plugin. http://www.ict.usc.edu/~jcohen/lightgen/lightgen.html.Google Scholar
    5. COHEN, M., SHADE, J., HILLER, S., AND DEUSSEN, O. 2003. Wang tiles for image and texture generation. ACM Trans. on Graphics 22, 3 (July), 287–294. Google ScholarDigital Library
    6. COOK, R. 1986. Stochastic sampling in computer graphics. ACM Trans. on Graphics 5, 1 (Jan.), 51–72. Google ScholarDigital Library
    7. DEBEVEC, P. 1998. Rendering synthetic objects into real scenes: Bridging traditional and image-based graphics with global illumination and high dynamic range photography. In Proc. SIGGRAPH ’98, 189–198. Google ScholarDigital Library
    8. DU, Q., FABER, V., AND GUNZBURGER, M. 1999. Centroidal Voronoi tessellations: Applications and algorithms. SIAM Review 41, 4 (Dec.), 637–676. Google ScholarDigital Library
    9. FOLEY, J., VAN DAM, A., FEINER, S., AND HUGHES, J. 1990. Computer Graphics, Principles and Practice, 2nd ed. Addison-Wesley. Google ScholarDigital Library
    10. GARDNER, M. 1977. Extraordinary nonperiodic tiling that enriches the theory of tiles. Scientific American 236, 110–121.Google ScholarCross Ref
    11. GLASSNER, A. 1995. Principles of Digital Image Synthesis. Morgan Kaufmann. Google ScholarDigital Library
    12. GLASSNER, A. 1998. Andrew Glassner’s notebook: Penrose tiling. IEEE Computer Graphics & Applications 18, 4, 78–86. Google ScholarDigital Library
    13. GRAHAM, R., KNUTH, D., AND PATASHNIK, O. 1994. Concrete Mathematics: a foundation for Computer Science, 2nd ed. Chapter 6.6. Addison-Wesley. Google ScholarDigital Library
    14. GRÜNBAUM, B., AND SHEPHARD, G. 1986. Tilings and Patterns. W. H. Freeman. Google ScholarDigital Library
    15. HILLER, S., DEUSSEN, O., AND KELLER, A. 2001. Tiled blue noise samples. In Proc. Vision Modeling and Visualization, 265–272. Google ScholarDigital Library
    16. HOFF, K., CULVER, T., KEYSER, J., LIN, M., AND MANOCHA, D. 1999. Fast computation of generalized voronoi diagrams using graphics hardware. In Proc. SIGGRAPH ’99, 277–286. Google ScholarDigital Library
    17. KNUTH, D. 1997. The Art of Computer Programming, Volume 1, Fundamental Algorithms, 3rd ed. page 86. Addison-Wesley. Google ScholarDigital Library
    18. KOLLIG, T., AND KELLER, A. 2001. Efficient bidirectional path tracing by randomized quasi-monte carlo integration. Niederreiter, K. Fang, and F. Hickernell, Eds., Monte Carlo and Quasi-Monte Carlo Methods 2000, 290–305.Google Scholar
    19. KOLLIG, T., AND KELLER, A. 2002. Efficient multidimensional sampling. Computer Graphics Forum 21, 3, 557–564.Google ScholarCross Ref
    20. KOLLIG, T., AND KELLER, A. 2003. Efficient illumination by high dynamic range images. In Eurographics Symposium on Rendering: 14th Eurographics Workshop on Rendering, 45–51. Google ScholarDigital Library
    21. LLOYD, S. 1983. An optimization approach to relaxation labeling algorithms. Image and Vision Computing 1, 2, 85–91.Google ScholarCross Ref
    22. MACKAY, A. 1982. Crystallography and the Penrose pattern. Physica 114A, 609–613.Google ScholarCross Ref
    23. MCCOOL, M., AND FIUME, E. 1992. Hierarchical poisson disk sampling distributions. In Proc. Graphics Interface ’92, 94–105. Google ScholarDigital Library
    24. MITCHELL, D. 1991. Spectrally optimal sampling for distributed ray tracing. In Proc. SIGGRAPH ’91, vol. 25, 157–164. Google ScholarDigital Library
    25. NIEDERREITER, H. 1992. Random Number Generation and Quasi-Monte-Carlo Methods. Soc. for Industrial and Applied Mathematics. Google ScholarDigital Library
    26. OSTROMOUKHOV, V., HERSCH, R., AND AMIDROR, I. 1994. Rotated dispersion dither: a new technique for digital halftoning. In Proc. SIGGRAPH ’94, 123–130. Google ScholarDigital Library
    27. OSTROMOUKHOV, V. 2001. A simple and efficient error-diffusion algorithm. In Proc. SIGGRAPH 2001, 567–572. Google ScholarDigital Library
    28. PENROSE, R. 1974. The role of aesthetics in pure and applied mathematical research. Bull. Inst. Math. & its Applns. 10, 266–271.Google Scholar
    29. PENROSE, R. 1979. Pentaplexity, a class of non-periodic tilings of the plane. The Mathematical Intelligencer 2, 32–37.Google ScholarCross Ref
    30. SECORD, A., HEIDRICH, W., AND STREIT, L. 2002. Fast primitive distribution for illustration. In 13th Eurographics Workshop on Rendering, 215–226. Google ScholarDigital Library
    31. SHIRLEY, P. 1991. Discrepancy as a quality measure for sample distributions. In Proc. Eurographics ’91, 183–194.Google Scholar
    32. SOCOLAR, J. 1989. Simple octagonal and dodecagonal quasicrystals. Physical Revue B39, 10519–10551.Google ScholarCross Ref
    33. STEINHARDT, P., AND OSTLUND, S. 1987. The Physics of Quasicrystals. World Scientific.Google Scholar
    34. SURAZHSKY, V., ALLIEZ, P., AND GOTSMAN, C. 2003. Isotropic remeshing of surfaces: a local parameterization approach. In Proc. of 12th Int. Meshing Roundtable.Google Scholar
    35. ULICHNEY, R. 1987. Digital Halftoning. MIT Press. Google ScholarDigital Library
    36. ULICHNEY, R. A. 1988. Dithering with blue noise. Proc. of the IEEE 76, 56–79.Google ScholarCross Ref
    37. VEACH, E. 1997. Robust Monte Carlo Methods for Light Transport Simulation. PhD thesis. Stanford University. Google ScholarDigital Library
    38. ZHOU, B., AND FANG, X. 2003. Improving mid-tone quality of variable-coefficient error diffusion using threshold modulation. ACM Trans. on Graphics 22, 3 (July), 437–444. Google ScholarDigital Library

ACM Digital Library Publication: