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.


On-line documents:
Complete article [Acrobat pdf file, 3.5 Mb]
Companion Video [High-Quality MPEG-4 .mov, 50 Mb] [Low-Quality MPEG-4 .mov, 17 Mb]
Lookup Tables [8x21, ASCII format] [13x21, ASCII format] [21x21, ASCII format]
PowerPoint slides of the SIGGRAPH presentation [HTML] (Better quality with Internet Explorer)
Example code in C++ and documentation


    author = {Victor Ostromoukhov and Charles Donohue and Pierre-Marc Jodoin},
    title = {Fast Hierarchical Importance Sampling with Blue Noise Properties},
    journal = {ACM Transactions on Graphics},
    year = {2004},
    volume = {23},
    number = {3},
    pages = {488-495},
    publisher = {ACM Press},
    address = {New York, NY, USA},
    note = {Proc. SIGGRAPH 2004},
    url = {},