Analysis of forced random sampling

Abstract

Stochastisches Sampling ist ein für die Computergrafik unerlässliches Hilfsmittel, das die Annäherung komplexer Funktionen und Integrale in endlicher Zeit ermöglicht. Anwendungen, die auf stochastisches Sampling zurückgreifen, sind unter anderem Ray Tracing, Remeshing, Stippling und die Textursynthese. Um den abzutastenden Bereich gleichmäßig und ohne regelmäßige Muster abzudecken, muss die Verteilung räumliche Gleichmäßigkeit ohne Regelmäßigkeit garantieren, was als Blue-Noise-Charakteristik bezeichnet wird. Zusätzlich sollen Samples auch entsprechend einer Gewichtsfunktion verteilt werden (Importance Sampling), sodass die Verteilung der Samples global einer gegebenen Dichtefunktion genügt und lokal noch immer gleichmäßig und irregulär ist. Die Erzeugung optimaler Blue-Noise-Verteilungen ist aufwändig, weshalb in der Vergangenheit vor allem an schnelleren Verfahren mit ähnlich guter Qualität gearbeitet wurde. Die meisten dieser Algorithmen sind jedoch entweder nicht für Echtzeitanwendungen geeignet oder haben deutlich schlechtere Verteilungseigenschaften. Forced Random Sampling ist ein neuartiger Algorithmus für Importance Sampling in Echtzeit. Samples werden erzeugt, indem eine vorberechnete Dithermatrix mit einer auf der Gewichtsfunktion basierenden Schwellwertfunktion verglichen wird. Aufgrund der Konstruktion der Matrix weisen die resultierenden Samples lokal wünschenswerte Verteilungseigenschaften auf und sind zudem global an die gegebene Gewichtsfunktion angepasst. In dieser Arbeit wird eine effiziente und parallelisierbare Implementierung dieses Algorithmus vorgestellt und hinsichtlich der Verteilungsqualität und Laufzeit analysiert. Die Ergebnisse werden sowohl mit dem qualitativen Optimum für Blue Noise Sampling als auch mit dem aktuellen Stand der Technik auf dem Gebiet des Importance Sampling in Echtzeit -- dem Hierarchical Sample Warping -- verglichen. Mithilfe dieses Vergleichs soll untersucht werden, ob Forced Random Sampling mit gängigen Sampling-Algorithmen konkurrieren kann. Die Analyse von Sampleverteilungen umfasst einerseits mehrere Diskrepanzmaße sowie die Dichte zur Beurteilung der räumlichen Verteilungseigenschaften und andererseits Fourier- und Differentialbereichanalysen zur Beurteilung der spektralen Verteilungseigenschaften. Mit diesen bewährten Methoden wird gezeigt, dass Forced Random Sampling zur Erzeugung von Samples mit annähernder Blue-Noise-Charakteristik in Echtzeit verwendet werden kann. Verglichen mit dem derzeitigen Stand der Technik liefert das vorgestellte Verfahren Samples höherer Qualität mit weniger Berechnungsaufwand und ist deshalb eine echte Alternative zu gängigen Importance-Sampling-Algorithmen.

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 Sample Warping. 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.