Fast Tile-Based Adaptive Sampling with User-Specified Fourier Spectra


We introduce a novel tile-based method for adaptive two-dimensional sampling with user-specified spectral properties. Our approach achieves several orders of magnitude speed improvement over current spectrum-controlled sampling methods through a deterministic, hierarchical construction of self-similar, equi-area tiles whose spatial distribution is free of spurious spectral peaks. A lookup table of sample points, computed offline using any existing procedure that optimizes point sets to shape their Fourier spectrum, is then used to populate the tiles. The result is a linear-time, adaptive, and high-quality sampling of arbitrary density functions that conforms to the desired spectral distribution.

ACM Transactions on Graphics (Proceedings of SIGGRAPH)

Caption: Using a carefully-designed set of subdivision rules, our approach constructs a self-similar, equi-area tiling that provides an even, unstructured distribution of tile centroids. Per-tile sampling points are then generated through offline optimization of the tile centroids in a series of local patches using any existing point set optimizer; the resulting offsets between original and optimized point locations are stored in a lookup table. These offset vectors are finally used at runtime to convert tile centroids into point set distributions with spectral properties closely matching those of the optimizer, but several orders of magnitude faster than current spectrum-controlled sampling methods.

      author = {Florent Wachtel and Adrien Pilleboue and David Coeurjolly and Katherine Breeden and Gurprit Singh and Gaël Cathelin and Fernando de Goes and Mathieu Desbrun and Victor Ostromoukhov},
      doi = {10.1145/2601097.2601107},
      issn = {0730-0301},
      journal = {ACM Transactions on Graphics (Proceedings of SIGGRAPH)},
      language = {en},
      month = {August},
      number = {4},
      pages = {56:1-56:11},
      title = {Fast Tile-Based Adaptive Sampling with User-Specified Fourier Spectra},
      url = {},
      volume = {33},
      year = {2014}