Fast hierarchical importance sampling with blue noise properties
- 1 August 2004
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Graphics
- Vol. 23 (3) , 488-495
- https://doi.org/10.1145/1015706.1015750
Abstract
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.This publication has 20 references indexed in Scilit:
- Wang Tiles for image and texture generationACM Transactions on Graphics, 2003
- Structured importance sampling of environment mapsACM Transactions on Graphics, 2003
- Improving mid-tone quality of variable-coefficient error diffusion using threshold modulationACM Transactions on Graphics, 2003
- Efficient Multidimensional SamplingComputer Graphics Forum, 2002
- Interactive geometry remeshingACM Transactions on Graphics, 2002
- Penrose tilingIEEE Computer Graphics and Applications, 1998
- Simple octagonal and dodecagonal quasicrystalsPhysical Review B, 1989
- Dithering with blue noiseProceedings of the IEEE, 1988
- An optimization approach to relaxation labelling algorithmsImage and Vision Computing, 1983
- Mathematical GamesScientific American, 1977