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

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