Spatial and spectral analysis of sampling patterns for Monte Carlo integration

L’échantillonnage est une étape clé dans le rendu graphique. Il permet d’intégrer la lumière arrivant en un point de la scène pour en calculer sa couleur. Généralement, la méthode utilisée est l’intégration Monte Carlo qui approxime cette intégrale en choisissant un nombre fini d’échantillons. La réduction du biais et de la variance de l’intégration Monte Carlo est devenue une des grandes problématiques en rendu réaliste. Les techniques trouvées consistent à placer les points d’échantillonnage avec intelligence de façon à rendre la distribution la plus uniforme possible tout en évitant les régularités. Les années 80 ont été de ce point de vue un tournant dans ce domaine, avec l’apparition de nouvelles méthodes stochastiques. Ces méthodes ont, grâce à une meilleure compréhension des liens entre intégration Monte Carlo et échantillonnage, permis de réduire le bruit et la variance des images générées, et donc d’améliorer leur qualité. En parallèle, la complexité des méthodes d’échantillonnage s’est considérablement améliorée, permettant d’obtenir des méthodes à la fois rapides et efficaces en termes de qualité. Cependant, ces avancées ont jusqu’à là été faites par tâtonnement et se sont axées sur deux points majeurs : l’amélioration de l’uniformité du motif d’échantillonnage et la suppression des régularités. Bien que des théories permettant de borner l’erreur d’intégration existent, elles sont souvent limitées, voire inapplicables dans le domaine de l’informatique graphique. Cette thèse propose de rassembler les outils d’analyse des motifs d’échantillonnages et de les mettre en relation. Ces outils peuvent caractériser des propriétés spatiales, comme la distribution des distances entre points, ou bien spectrales à l’aide de la transformée de Fourier. Nous avons ensuite utilisé ces outils afin de donner une expression simple de la variance et du biais dans l’intégration Monte Carlo, en utilisant des prérequis compatibles avec le rendu d’image. Finalement, nous présentons une boite à outils théorique permettant de déterminer la vitesse de convergence d’une méthode d’échantillonnage à partir de son profil spectral. Cette boite à outils est notamment utilisée afin de classifier les méthodes d’échantillonnage existantes, mais aussi pour donner des indications sur les principes fondamentaux nécessaires à la conception de nouveaux algorithmes d’échantillonnageSampling is a key step in rendering pipeline. It allows the integration of light arriving to a point of the scene in order to calculate its color. Monte Carlo integration is generally the most used method to approximate that integral by choosing a finite number of samples. Reducing the bias and the variance of Monte Carlo integration has become one of the most important issues in realistic rendering. The solutions found are based on smartly positioning the samples points in a way that maximizes the uniformity of the distribution while avoiding the regularities. From this point of view, the 80s were a turning point in this domain, as new stochastic methods appeared. With a better comprehension of links between Monte Carlo integration and sampling, these methods allow the reduction of noise and of variance in rendered images. In parallel, the complexity of sampling methods has considerably enhanced, enabling to have fast as well as good quality methods. However, these improvements have been done by trial and error focusing on two major points : the improvement of sampling pattern uniformity, and the suppression of regularities. Even though there exists some theories allowing to bound the error of the integration, they are usually limited, and even inapplicable in computer graphics. This thesis proposes to gather the analysis tools of sampling patterns and to connect them together. These tools can characterize spatial properties such as the distribution of distances between points, as well as spectral properties via Fourier transformation. Secondly, we have used these tools in order to give a simple expression of the bias and the variance for Monte Carlo integration ; this is done by using prerequisites compatible with image rendering. Finally, we present a theoretical toolbox allowing to determine the convergence speed of a sampling method from its spectral profile. This toolbox is used specifically to give indications about the design principles necessary for new sampling algorithm