A Monte Carlo light transport simulation is used in scattering-aware color 3D printing pipeline (Elek et al. [2017], Sumin et al. [2019]) to drive an iterative optimization loop. Its purpose is to find a material arrangement that yields the closest match in terms of surface appearance towards a target. As the light transport prediction takes up about 90% of the time it poses a significant bottleneck towards a practical application of this technology. The dense volumetric textures also require a lot of memory. Explicitly simulating every light interaction is particularly challenging in the setting of 3D printouts due to the heterogeneity, high density and high albedo of the media. In this thesis, we explore existing volumetric rendering techniques (Křivánek et al. [2014], Herholz et al. [2019]) and finally engineer a customized estimator for our setting, improving the performance considerably. Additionally, we investigate various storage solutions for the volumetric data and successfully reduce the memory footprint. All the algorithms are available in the form of Mitsuba renderer plugins.

Fault diagnosis plays an important role in improving the circuit design process and the manufacturing yield. With the increasing number of gates in modern circuits, determining the source of failure in a defective circuit is becoming more and more challenging. In this research, we present an efficient effect-cause diagnosis framework for combinational VLSI circuits. The framework consists of three stages to obtain an accurate and reasonably precise diagnosis. First, an improved critical path tracing algorithm is proposed to identify an initial suspect list by backtracing from faulty primary outputs toward primary inputs. Compared to the traditional critical path tracing approach, our algorithm is faster and exact. Second, a novel probabilistic ranking model is applied to rank the suspects so that the most suspicious one will be ranked at or near the top. Several fast filtering methods are used to prune unrelated suspects. Finally, to refine the diagnosis, fault simulation is performed on the top suspect nets using several common fault models. The difference between the observed faulty behavior and the simulated behavior is used to rank each suspect. Experimental results on ISCAS85 benchmark circuits show that this diagnosis approach is efficient both in terms of memory space and CPU time and the diagnosis results are accurate and reasonably precise.

La génération d'images de synthèse pour la production cinématographique n'a cessé d'évoluer durant ces dernières décennies. Pour le non-expert, il semble que les effets spéciaux aient atteint un niveau de réalisme ne pouvant être dépassé. Cependant, les logiciels mis à la disposition des artistes ont encore du progrès à accomplir. En effet, encore trop de temps est passé à attendre le résultat de longs calculs, notamment lors de la prévisualisation d'effets spéciaux. La lenteur ou la mauvaise qualité des logiciels de prévisualisation pose un réel problème aux artistes. Cependant, l'évolution des cartes graphiques ces dernières années laisse espérer une potentielle amélioration des performances de ces outils, notamment par la mise en place d'algorithmes hybrides rasterisation/ lancer de rayons, tirant profit de la puissance de calcul de ces processeurs, et ce, grâce à leur architecture massivement parallèle. Cette thèse explore les différentes briques logicielles nécessaires à la mise en place d'un pipeline de rendu complexe sur carte graphique, permettant une meilleure prévisualisation des effets spéciaux. Différentes contributions ont été apportées à l'entreprise durant cette thèse. Tout d'abord, un pipeline de rendu hybride a été développé (cf. Chapitre 2). Par la suite, différentes méthodes d'implémentation de l'algorithme de Path Tracing ont été testées (cf. Chapitre 3), de façon à accroître les performances du pipeline de rendu sur GPU. Une structure d'accélération spatiale a été implémentée (cf. Chapitre 4), et une amélioration de l'algorithme de traversée de cette structure sur GPU a été proposée (cf. Section 4.3.2). Ensuite, une nouvelle méthode de décorrélation d'échantillons, dans le cadre de la génération de nombres aléatoires a été proposée (cf. Section 5.4) et a donné lieu à une publication [Dufay et al., 2016]. Pour finir, nous avons tenté de combiner l'algorithme de Path Tracing et les solutions Many Lights, toujours dans le but d'améliorer la prévisualisation de l'éclairage global. Cette thèse a aussi donné lieu à la soumission de trois mémoires d'invention et a permis le développement de deux outils logiciels présentés en Annexe A. / Image synthesis for movie production never stopped evolving over the last decades. It seems it has reached a level of realism that cannot be outperformed. However, the software tools available for visual effects (VFX) artists still need to progress. Indeed, too much time is still wasted waiting for results of long computations, especially when previewing VFX. The delays or poor quality of previsualization software poses a real problem for artists. However, the evolution of graphics processing units (GPUs) in recent years suggests a potential improvement of these tools. In particular, by implementing hybrid rasterization/ray tracing algorithms, taking advantage of the computing power of these processors and their massively parallel architecture. This thesis explores the different software bricks needed to set up a complex rendering pipeline on the GPU, that enables a better previsualization of VFX. Several contributions have been brought during this thesis. First, a hybrid rendering pipeline was developed (cf. Chapter 2). Subsequently, various implementation schemes of the Path Tracing algorithm have been tested (cf. Chapter 3), in order to increase the performance of the rendering pipeline on the GPU. A spatial acceleration structure has been implemented (cf. Chapter 4), and an improvement of the traversal algorithm of this structure on GPU has been proposed (cf. Section 4.3.2). Then, a new sample decorrelation method, in the context of random number generation was proposed (cf. Section 5.4) and resulted in a publication [Dufay et al., 2016]. Finally, we combined the Path Tracing algorithm with the Many Lights solution, always with the aim of improving the preview of global illumination. This thesis also led to the submission of three patents and allowed the development of two software tools presented in Appendix A.

Realistic Image synthesis, usually, requires long computations and the simulation of the light interacting with a virtual scene. One of the most computationally intensive simulation in this area is the visualization of solid participating media. This media can describe many different types of object with the same physical parameters (e.g. marble, air, fire, skin, wax ...). Simulating the light interacting with it requires the computation of many independent photons interactions inside the medium. However, those interactions can be computed in parallel, using the power of modern Graphic Processor Unit, or GPU, computing. This work present an overview over different methodologies, that can affect the performance of this type of simulations on the GPU. Different existing ideas are analyzed, compared and modified with the scope of speeding up the computation respect to the classic CPU implementation. 1

This paper involves implementing a forward path tracer in C++ using OpenMP in order to examine the effects of Samples per Pixel (SPP) on output images given in different environments. Output images of scenes with different amounts of lighting are rendered in different resolutions. These renders are timed and output images are saved to files. Looking at these results, varying the SPP-value results in drastic changes in render time and image quality. Such performance differences ultimately affect the possibilities for the developed path tracer and its applications. / Denna rapport undersöker effekten av Samples per Pixel (SPP) på renderade bilder genom implementerandet av en forward path tracer i C++. Bilderna består av olika scener med olika ljustyrkor i olika bildstorlekar. Dessa resultat visar att ändring av SPP-värden leder till drastiska förändringar i bildkvalitet och renderingstid. Dessa faktorer påverkar i slutändan möjligheterna till vidare appliceringar av path tracer implementationen.

<p dir="ltr">Polarization and spectral imaging technology has wide application prospects and economic value in environmental detection, target recognition, remote sensing detection and industrial detection. However, the acquisition of hyperspectral or spectro-polarimetric imaging data is difficult and expensive in general. This study aims to develop a synthetic thermal imaging dataset using computer simulation. The study seeks to explore the simulation performance of Monte-Carlo path tracing algorithm in the fields of spectroscopy and thermal imaging. The goal is to provide a novel tool for effective and accurate dataset generation for thermal imaging neural networks training.</p>

Obtaining an accurate whole program path (WPP) that captures a program’s runtime behaviour in terms of a control-flow trace has a number of well-known benefits, including opportunities for code optimization, bug detection, program analysis refinement, etc. Existing techniques to compute WPPs perform sub-optimal instrumentation resulting in significant space and time overheads. Our goal in this thesis is to minimize these overheads without losing precision. To do so, we design a novel and scalable whole program analysis to determine instrumentation points used to obtain WPPs. Our approach is divided into three components: (a) an efficient summarization technique for inter-procedural path reconstruction, (b) specialized data structures called conflict sets that serve to effectively distinguish between pairs of paths, and (c) an instrumentation algorithm that computes the minimum number of edges to describe a path based on these conflict sets. We show that the overall problem is a variant of the minimum hitting set problem, which is NP-hard, and employ various sound approximation strategies to yield a practical solution. We have implemented our approach and performed elaborate experimentation on Java programs from the DaCapo benchmark suite to demonstrate the efficacy of our approach across multiple dimensions. On average, our approach necessitates instrumenting only 9% of the total number of CFG edges in the program. The average runtime overhead incurred by our approach to collect WPPs is 1.97x, which is only 26% greater than the overhead induced by only instrumenting edges guaranteed to exist in an optimal solution. Furthermore, compared to the state-of-the-art, we observe a reduction in runtime overhead by an average and maximum factor of 2.8 and 5.4, respectively.

La croissance rapide dans le domaine des semi-conducteurs fait que les circuits digitaux deviennent de plus en plus complexes. La capacité à identifier la cause réelle d'une défaillance dans un circuit digital est donc critique. Le diagnostic logique est une procédure qui permet de localiser une erreur observée dans un circuit fautif, l'analyse de défaillance peut être ensuite appliquée pour déterminer la cause réelle de cette erreur. Un diagnostic efficace et précis est donc fondamental pour améliorer les résultats de l'analyse de défaillance et augmenter éventuellement le rendement de production."Effet à Cause" et "Cause à Effet" sont deux approches classiques pour le diagnostic logique. Ce diagnostic fournit une liste de suspects au niveau porte logique. Cependant, cette approche n'est pas précise dans le cas où le défaut est localisé à l'intérieur de la cellule logique.Dans cette thèse, nous proposons une nouvelle méthode de diagnostic intra-cell basé sur l'approche "Effet à Cause" pour améliorer la précision de la localisation de défaut au niveau transistor. L'approche proposée utilise l'algorithme CPT (Traçage de chemins critiques) appliqué au niveau transistor. Pour chaque cellule suspecte, nous appliquons un CPT avec les vecteurs de test fautifs. Le résultat obtenu est une liste de suspects préliminaires. Chaque suspect peut être un noeud (G, S, D) de transistor. Par la suite, nous appliquons un CPT avec les vecteurs de test non-fautifs pour minimiser la liste de suspects. La méthode proposée donne la localisation précise du défaut pour une erreur observée. Par ailleurs, la méthode est indépendante du modèle de faute invoqué. / The rapid growth in semiconductor field results in an increasing complexity of digital circuits. The ability to identify the root cause of a failing digital circuit is becoming critical for defect localization. Logic diagnosis is the process of isolating the source of observed errors in a defective circuit, so that a physical failure analysis can be performed to determine the root cause of such errors. Effective and precise logic diagnosis is crucial to speed up the failure analysis and eventually to improve the yield.“Effect-Cause” and “Cause-Effect” are the two classical approaches for logic diagnosis. Logic diagnosis provides a list of gates as suspects. However, this approach may not leads to accurate results in the case of the defect is inside a gate.We propose a new intra-cell diagnosis method based on “Effect-Cause” approach to improve the defect localization accuracy at transistor level. The proposed approach exploits the CPT (Critical Path Tracing) applied at transistor level. For each suspected cell, we apply the CPT for every given failing test vector. The result is a preliminary list of candidates. Each candidate can be a net or a transistor drain, gate or source. After that, we apply the CPT for each passing test vector in order to narrow down the the list of candidates. The proposed method gives precise localization of the root cause of the observed errors. Moreover, it does not require the explicit use of a fault model.

This thesis that implemented Monte Carlo path tracing and voxel cone tracing for global illumination on GPU compared the performance and visual result. The Monte Carlo path tracing algorithm is implemented in CUDA to do parallel computing on GPU and accelerate the computing speed. The voxel cone tracing, a global illumination algorithm for real-time computing, runs on OpenGL through the GPU graphics pipeline. The results show that the Monte Carlo Path Tracing on CPU single core takes over 10 hours, around 4 hours with 4 cores, on GPU it takes around 48 minutes, while the voxel cone tracing on the same GPU takes 2 ms. The quality of the image generated by the Monte Carlo path tracing contains much more transparent, reflection, and shadow details than that using the voxel cone tracing algorithm. / <p>Examensarbetet är utfört vid Institutionen för teknik och naturvetenskap (ITN) vid Tekniska fakulteten, Linköpings universitet</p>

Light transport simulation is used in realistic image synthesis to create physically plausible images of virtual scenes. Important components of the scenes are participating media (e.g. air, water, skin etc.). Efficient computation of light transport in participating media robust to their large diversity is still an open problem. We implemented the UPBP algorithm recently developed by Křivánek et al. It addresses the problem by combining several complementary previous methods using multiple importance sampling, and excels at rendering scenes where the previous methods alone fail. The implementation is available online, we focused on its thorough description to facilitate and support further research in this field. Powered by TCPDF (www.tcpdf.org)