Analysis of Forced Random Sampling

Information

• Publication Type: Master Thesis
• Workgroup(s)/Project(s):
  • Rendering and Modeling
  • VRVis Competence Center
• Date: October 2014
• Diploma Examination: 7. October 2014
• First Supervisor: Michael Wimmer
• Keywords: global illumination, Poisson disk sampling

Abstract

Stochastic sampling is an indispensable tool in computer graphics which allows approximating complex functions and integrals in finite time. Applications which rely on stochastic sampling include ray tracing, remeshing, stippling and texture synthesis. In order to cover the sample domain evenly and without regular patterns, the sample distribution has to guarantee spatial uniformity without regularity and is said to have blue-noise properties. Additionally, the samples need to be distributed according to an importance function such that the sample distribution satisfies a given sampling probability density function globally while being well distributed locally. The generation of optimal blue-noise sample distributions is expensive, which is why a lot of effort has been devoted to finding fast approximate blue-noise sampling algorithms. Most of these algorithms, however, are either not applicable in real time or have weak blue-noise properties.

Forced Random Sampling is a novel algorithm for real-time importance sampling. Samples are generated by thresholding a precomputed dither matrix with the importance function. By the design of the matrix, the sample points show desirable local distribution properties and are adapted to the given importance. In this thesis, an efficient and parallelizable implementation of this algorithm is proposed and analyzed regarding its sample distribution quality and runtime performance. The results are compared to both the qualitative optimum of blue-noise sampling and the state of the art of real-time importance sampling, which is Hierarchical SampleWarping. With this comparison, it is investigated whether Forced Random Sampling is competitive with current sampling algorithms.

The analysis of sample distributions includes several discrepancy measures and the sample density to evaluate their spatial properties as well as Fourier and differential domain analyses to evaluate their spectral properties. With these established methods, it is shown that Forced Random Sampling generates samples with approximate blue-noise properties in real time. Compared to the state of the art, the proposed algorithm is able to generate samples of higher quality with less computational effort and is therefore a valid alternative to current importance sampling algorithms.

Additional Files and Images

Weblinks

No further information available.

BibTeX

@mastersthesis{CORNEL-2014-AFRS,
  title =      "Analysis of Forced Random Sampling",
  author =     "Daniel Cornel",
  year =       "2014",
  abstract =   "Stochastic sampling is an indispensable tool in computer
               graphics which allows approximating complex functions and
               integrals in finite time. Applications which rely on
               stochastic sampling include ray tracing, remeshing,
               stippling and texture synthesis. In order to cover the
               sample domain evenly and without regular patterns, the
               sample distribution has to guarantee spatial uniformity
               without regularity and is said to have blue-noise
               properties. Additionally, the samples need to be distributed
               according to an importance function such that the sample
               distribution satisfies a given sampling probability density
               function globally while being well distributed locally. The
               generation of optimal blue-noise sample distributions is
               expensive, which is why a lot of effort has been devoted to
               finding fast approximate blue-noise sampling algorithms.
               Most of these algorithms, however, are either not applicable
               in real time or have weak blue-noise properties.  Forced
               Random Sampling is a novel algorithm for real-time
               importance sampling. Samples are generated by thresholding a
               precomputed dither matrix with the importance function. By
               the design of the matrix, the sample points show desirable
               local distribution properties and are adapted to the given
               importance. In this thesis, an efficient and parallelizable
               implementation of this algorithm is proposed and analyzed
               regarding its sample distribution quality and runtime
               performance. The results are compared to both the
               qualitative optimum of blue-noise sampling and the state of
               the art of real-time importance sampling, which is
               Hierarchical SampleWarping. With this comparison, it is
               investigated whether Forced Random Sampling is competitive
               with current sampling algorithms.  The analysis of sample
               distributions includes several discrepancy measures and the
               sample density to evaluate their spatial properties as well
               as Fourier and differential domain analyses to evaluate
               their spectral properties. With these established methods,
               it is shown that Forced Random Sampling generates samples
               with approximate blue-noise properties in real time.
               Compared to the state of the art, the proposed algorithm is
               able to generate samples of higher quality with less
               computational effort and is therefore a valid alternative to
               current importance sampling algorithms. ",
  month =      oct,
  address =    "Favoritenstrasse 9-11/E193-02, A-1040 Vienna, Austria",
  school =     "Institute of Computer Graphics and Algorithms, Vienna
               University of Technology ",
  keywords =   "global illumination, Poisson disk sampling",
  URL =        "https://www.cg.tuwien.ac.at/research/publications/2014/CORNEL-2014-AFRS/",
}