<p>Denna rapport presenterar ett alternativt sätt att ljussätta terräng i datorgrafik. Tidigare modeller har vanligtvis byggt på lokal ljussättning, som inte tar hänsyn till kringliggande geometri, och har med en extra process approximerat effekten av ljusinteraktionen. Genom att använda sig av en teknik som kallas precomputed radiance transfer (PRT) kan man förberäkna hur en punkt interagerar med ljus för olika inkommande riktningar och undviker därmed att göra detta under programkörningen. Det är viktigt att denna teknik även fungerar tillsammans med level-of-detail (LOD) terrängrenderingsalgoritmer eftersom rendering av alla trianglar i terrängen för varje skärmuppdatering inte är optimalt för dagens grafikkort. Man vill därför representera den underliggande terrängen med fler trianglar närmare betraktaren och färre längre bort. Motiveringen till detta är att trianglar längre ifrån betraktaren kommer resultera i färre pixlar på skärmen, så att rendera större trianglar gör en liten visuell skillnad. Arbetet visar på att tekniken fungerar med LOD-terrängrenderingsalgoritmer med bra prestanda och visuell kvalitet.</p>

Shadows provide an important cue in computer graphics. In this thesis we focus on real-time soft shadow algorithms. Two new techniques are presented, both run entirely on modern graphics hardware. "Soft Shadows Using Precomputed Visibility Distance Functions" renders fake soft shadows in static scenes using precomputed visibility information. The technique handles dynamic local light sources and contains special computation steps to generate smooth shadows from hard visibility functions. The resulting images are not physically accurate, nevertheless the method renders plausible images that imitate global illumination. "Soft Projected Shadows" is a simple method for simulating natural shadow penumbra for projected grayscale shadow textures. Shadow blurring is performed entirely in image space and needs only a couple of special blurring passes on pixel shader 2.0 hardware. The technique treats shadow receivers as nearly planar surfaces and doesn’t handle self shadowing, but executes very fast and renders plausible soft shadows. Multiple overlapping shadow casters in a single shadow map are natively supported without any performance overhead.

Denna rapport presenterar ett alternativt sätt att ljussätta terräng i datorgrafik. Tidigare modeller har vanligtvis byggt på lokal ljussättning, som inte tar hänsyn till kringliggande geometri, och har med en extra process approximerat effekten av ljusinteraktionen. Genom att använda sig av en teknik som kallas precomputed radiance transfer (PRT) kan man förberäkna hur en punkt interagerar med ljus för olika inkommande riktningar och undviker därmed att göra detta under programkörningen. Det är viktigt att denna teknik även fungerar tillsammans med level-of-detail (LOD) terrängrenderingsalgoritmer eftersom rendering av alla trianglar i terrängen för varje skärmuppdatering inte är optimalt för dagens grafikkort. Man vill därför representera den underliggande terrängen med fler trianglar närmare betraktaren och färre längre bort. Motiveringen till detta är att trianglar längre ifrån betraktaren kommer resultera i färre pixlar på skärmen, så att rendera större trianglar gör en liten visuell skillnad. Arbetet visar på att tekniken fungerar med LOD-terrängrenderingsalgoritmer med bra prestanda och visuell kvalitet.

Computing complex lighting simulations such as global illumination is a computationally intensive task. Various real time solutions exist to approximate aspects of global illumination such as shadows, however, few of these methods offer single pass rendering solutions for soft shadows (self and other) and inter-reflections. In contrast, Precomputed Radiance Transfer (PRT) is a real-time computer graphics technique which pre-calculates an object's response to potential incident light. At run time, the actual incident light can be used to quickly illuminate the surface, rendering effects such as soft self-shadows and inter-reflections. In this thesis, we show that by calculating PRT lighting coefficients densely over a surface as texture data, additional surface detail can be encoded by integrating other computer graphics techniques, such as normal mapping. By calculating transfer coefficients densely over the surface of a mesh as texture data, greater fidelity can be achieved in lighting coarse meshes than simple interpolation can achieve. Furthermore, the lighting on low polygon objects can be enhanced by drawing surface normal and occlusion data from highly tessellated, detailed meshes. By applying such data to a decimated, simplified mesh, a more detailed and visually pleasing reconstruction can be displayed for a lower cost. In addition, this thesis introduces Hierarchical PRT, which extends some surface effects, such as soft shadows, between objects. Previous approaches to PRT used a more complex neighborhood transfer scheme in order to extend these lighting effects. Hierarchical PRT attempts to capture scene information in a tree data structure which represents coarse lighting relationships between objects. Potential occlusions can be found at run time by utilizing the same spherical harmonic representation used to represent surface lighting to instead store light "filters" between scene tree nodes. Such "filters" can be combined over a set of nodes in the scene to obtain the net shadowing of an object with good performance. We present both visually pleasing results on simplified meshes using normal mapping and textured PRT and initial results using Hierarchical PRT that captures low frequency lighting information for a small number of dynamic objects which shadow static scene objects with good results.

Background. The A* algorithm is a well-established pathfinding technique frequently used in video game development. However, a disadvantage of the A* algorithm is that it becomes computationally inefficient and impractical to utilize whenthousands of agents demand an optimal path. A solution to mitigate this issue isthe use of the flow field algorithm. This algorithm employs a goal-based pathfindingstrategy, which allows for the movement of a large number of units through the useof a single direction map (flow field map) that indicates the direction units must take to progress toward their goal. Objectives. The main objective of this study is to examine the performance and scalability of precomputed flow field maps with regard to execution time and memory utilization, with the objective of determining the feasibility of precomputed maps as an alternative to maps generated at runtime. Furthermore, the study implements and investigates compression techniques to minimize the memory footprint of precomputed flow field maps. Methods. The study adopts an experimental research design to assess the performance of the two implementations under various conditions of grid size and movement system. Performance evaluation is accomplished through the measurement and comparison of execution time and memory consumption. Additionally, a directional accuracy test is performed to quantify the potential loss of accuracy in the vectors stored in the precomputed flow field maps. Results. The precomputed flow field maps provide constant access time, with a time complexity of O(1), regardless of the grid size and the type of movement system. The memory usage of these maps increases significantly with the growth of the grid size. A doubling of the grid size leads to a more than fifteen-fold increase in memory usage. The techniques proposed in the study significantly reduced the memory footprint by a factor of thirty-two and by a factor of eight, depending on the selected movement system. The average loss in accuracy was approximately 0.35 degrees for the proposed any-angle compression technique. Conclusions. The use of precomputed flow field maps has limitations, including being limited to static environments and having high memory requirements. On the other hand, they provide constant access time for pathfinding information, independent of the grid dimensions, movement system, and the number of target nodes. Whether precomputed flow field maps are better than the traditional runtime implementation depends on the intended use.

Les ombres sont un élément important pour la compréhension d'une scène. Grâce à elles, il est possible de résoudre des situations autrement ambigües, notamment concernant les mouvements, ou encore les positions relatives des objets de la scène. Il y a principalement deux types d'ombres: des ombres dures, aux limites très nettes, qui résultent souvent de lumières ponctuelles ou directionnelles; et des ombres douces, plus floues, qui contribuent à l'atmosphère et à la qualité visuelle de la scène. Les ombres douces résultent de grandes sources de lumière, comme des cartes environnementales, et sont difficiles à échantillonner efficacement en temps réel. Lorsque l'interactivité est prioritaire sur la qualité, des méthodes d'approximation peuvent être utilisées pour améliorer le rendu d'une scène à moindre coût en temps de calcul. Nous calculons interactivement les ombres douces résultant de sources de lumière environnementales, pour des scènes composées d'objets en mouvement et d'un champ de hauteurs dynamique. Notre méthode enrichit la méthode d'exponentiation des harmoniques sphériques, jusque là limitée aux bloqueurs sphériques, pour pouvoir traiter des champs de hauteurs. Nous ajoutons également une représentation pour les BRDFs diffuses et glossy. Nous pouvons ainsi combiner les visibilités et BRDFs dans un même espace, afin de calculer efficacement les ombres douces et les réflexions de scènes complexes. Un algorithme hybride, qui associe les visibilités en espace écran et en espace objet, permet de découpler la complexité des ombres de la complexité de la scène. / Shadows provide important visual cues to a viewer about the relative positions of objects in a scene, as well as certain properties of the lighting in an environment, such as orientation, size, and intensity. The importance of shadows in visual simulations is even more striking when any element of an environment, such as characters in a scene or the light sources themselves, are animated over time. The simulation of so-called "hard" shadows from small point or directional light sources is a very mature field in computer graphics, with many concrete and well-established solutions. On the other hand, efficiently approximating the shadowing effects from larger "area" light sources, such as ceiling lights or environment maps captured from the real world, remains an open problem. Indeed, in many applications, the availability of a high-performance solution to this problem trumps the need for an accurate solution. Our work aims to solve the problem of approximating soft shadows interactively, in scenes where the geometric elements and lighting are both allowed to be animated over time. We decompose dynamic scene elements into deformable objects, approximated with a collection of non-deformable animated spheres, and height field geometry. By leveraging a novel spherical harmonic basis-space exponentiation formulation, we are able to very quickly accumulate the shadowing effects from these many dynamic blockers, while also encoding their local reflectance behaviour in a similar reduced basis representation. Our proof-of-concept implementation uses a hybrid, multi-resolution image- and object-space visibility marching algorithm that decouples geometric complexity from radiometric complexity. We demonstrate our method on several scenes with dynamic blockers and complex illumination.

Vid köp av konfigurerbara produkter som till exempel hus eller sängar på internet är det viktigt att kunden kan erbjudas en realistisk visualisering för att kunna få en känsla för hur den färdiga produkten kommer att se ut. En metod för att skapa visualiseringen är att från en miljö uppbyggd av 3d-modeller som anpassas efter kundens val skapa en rendering i realtid. För att den renderade bilden ska se realistisk ut och få hög kvalitet är det nödvändigt att i förväg utföra tunga beräkningar för hur ljuset sprider sig i scenen, så kallad bakning. Hur hanteringen av innehållet och bakningen effektivt ska göras är ett område där det saknas studier men där det finns stor potential för effektivisering. Därför har denna designstudie utförts där syftet är att öka kunskapen om hur hanteringen av innehållet och ljusberäkningar kan effektiviseras. Utvecklingen har utförts med Action Design Research där tre iterationer har fullföljts. Principer från Continuous Delivery har använts för att utveckla en IT-artefakt som automatiserar processen som krävs från det att en ny ändring har lagts in i versionshanteringssystemet till det att det finns ett färdigt paket med innehållet som behövs för att göra en visualisering. Resultatet består av nya komponenter skrivna i C# för Unity och skript skrivet med Python. Resultatet från studien visar att det är möjligt att med hjälp av principer från Continuous Delivery effektivisera processen inom det här området och att antalet manuella steg och den krävda arbetstiden kraftigt kan reduceras. Utifrån designstudien har fem nya designprinciper kunnat formuleras som är lämpliga att använda där program används som inte är har ett bra stöd för att köras automatiskt och att steg i processen kan vara beräkningsmässigt tunga. De går att applicera på fallet med hantering av innehållet i Unity men bör också vara relevanta för att hantera ett mer generellt fall där det finns en process med många manuella steg och beräkningsmässigt tunga steg. / When purchasing configurable products (for example, houses or beds) on the Internet, it is important that the customer can be offered a realistic visualization in order to get a feel for how the finished product will look. One method for creating the visualization is to create a real-time rendering from an environment built of 3D models that is adapted to the customer's choice. In order for the rendered image to look realistic and get high quality, it is necessary to perform heavy calculations in advance for how the light spreads in the scene (baking). How to effectively manage the content and baking is an area where there is little research but where there is great potential for improving the work flow. Therefore, this design study has been carried out where the purpose is to increase the knowledge of how the handling of the content and light calculations can be improved. The development has been carried out with Action Design Research, where three iterations have been completed. Continuous Delivery principles have been used to develop an IT artifact that automates the process required from the time a new change is added to the version management system until there is a complete package of content needed for visualization. The result consists of new components written in C# for Unity and scripts written with Python. The results of the study show that it is possible to streamline the process in this area using principles from Continuous Delivery and that the number of manual steps and the required working time can be greatly reduced. Based on the design study, five new design principles have been formulated that are suitable for use where programs are used that do not have good support for automating this and that contains steps in the process can be computationally heavy. They can be applied to the case of handling the contents of Unity but should also be relevant to dealing with a more general case where there is a process with many manual steps and computationally heavy steps.