Strålföljning är en rendering teknik som använts för icke realtid rendering men har med hjälp av accelerationsstrukturer och GPUer lyckats uppnå rendering i realtid. För att använda strålföljning i spel eller dynamiska scener behövs accelerationsstrukturerna byggas om i realtid på grund av detta har denna undersökning valt att utföra en komparativstudie där accelerationsstrukturerna Boundary Volume Hierachy (BVH) och K-dimensional tree (KD-träd) undersöks angående konstruktionstider på GPUn. Undersökning gjordes via skapandet av olika scener som med hjälp av en brusfunktion, även en BVH och en KD-träd lösning implementerades baserat på Lauterbach et al (2009) och Li et al (2017) respektive. För att testa strukturerna implementerades en strålföljnings algoritm baserad på Whitted (1980). Resultaten visar att BVH konstruerar upp sin struktur snabbare än KD-träd i alla scener. Som framtida arbeten vore det intressant att ytterligare undersöka andra algoritmer samt att jämföra algoritmerna i spel scener.

This paper deals with techniques for acquiring data for character animation driven from video. Among other, it also presents several Motion Capture systems and animation data formats BVH and CSM. It also contains an example application demonstrating attained accomplishments. These are reviewed and there is instituted a course of future proceeding.

En vanligt förekommande teknik för att påskynda sökningen av en skärpunkt i en 3d-scen är accelerationsstrukturer. Valet av accelerationsstruktur är ofta en avvägning mellan kort konstruktionstid och en struktur som effektivt påskyndar sökningen. I denna studie har två algoritmer undersökts för att se vilken som lämpar sig mest till användande inom interaktiva applikationer. Algoritmernas konstruktionstid, skalbarhet och resulterande effektivitet har studerats i sex scener. Av de två algoritmer som utvärderats tyder resultaten på att Linear Bounding Volume Hierarchy (Karras 2012a) är den, över lag, mest lämpade för användande inom interaktiva applikationer. Den andra algoritmen (Wald 2007) kan lämpa sig väl inom områden då ett stort antal strålar skall emitteras i en scen med låg geometrisk komplexitet. / <p>Det finns övrigt digitalt material (t.ex. film-, bild- eller ljudfiler) eller modeller/artefakter tillhörande examensarbetet som ska skickas till arkivet.</p>

Demonstration videos can be found on fr.linkedin.com/in/doriangomez/ / Cette thèse porte sur la modélisation procédurale de mondes virtuels étendus dans le domaine de l’informatique graphique. Nous proposons d’exploiter les propriétés de visibilité entre régions élémentaires de la scène, que nous appelons tuiles, pour contrôler sa construction par pavage rectangulaire. Deux objectifs distincts sont visés par nos travaux : (1) fournir aux infographistes un moyen efficace pour générer du contenu 3D pour ces scènes virtuelles de très grande taille, et (2) garantir, dès la création du monde, des performances de rendu et de visualisation efficace. Pour cela, nous proposons plusieurs méthodes de détermination de la visibilité en 2D et en 3D. Ces méthodes permettent l’évaluation d’ensembles potentiellement visibles (PVS) en temps interactif ou en temps réel. Elles sont basées sur les calculs de lignes séparatrices et de lignes de support des objets, mais aussi sur l’organisation hiérarchique des objets associés aux tuiles. La première technique (2D) garantit l’occultation complète du champ visuel à partir d’une distance fixe, spécifiée par le concepteur de la scène, depuis n’importe quel endroit sur le pavage. La seconde permet d’estimer et de localiser les tuiles où se propage la visibilité, et de construire le monde en conséquence. Afin de pouvoir générer des mondes variés, nous présentons ensuite l’extension de cette dernière méthode à la 3D. Enfin, nous proposons deux méthodes d’optimisation du placement des objets sur les tuiles permettant d’améliorer leurs propriétés d’occultation et leurs impacts sur les performances de rendu tout en conservant l’atmosphère créée par l’infographiste par ses choix de placement initiaux. / This thesis deals with procedural modeling applied to extended worlds for computer graphics.We study visibility applied to tiling patterns, aiming at two distinct objectives : (1) providing artists with efficient tools to generate 3D content for very extended virtual scenes, and (2) guaranteeing that this content improves performance of subsequent renderings, during its construction. We propose several methods for 2D and 3D visibility determination, in order to achieve interactive or real-time evaluation of potentially visible sets (PVS). They are based on the concepts of separating and supporting lines/planes, as well as objects hierarchies over tiles. Our first 2D method guarantees full occlusion of the visual field (view frustum) beyond a fixed distance, regardless of the observer’s location on a tiling. The second method enables fast estimation and localization of visible tiles, and builds up a virtual world accordingly. We also extend this method to 3D. Finally, we present two methods to optimize objects locations on tiles, and show how to improve rendering performance for scenes generated on the fly.

Mobile technology is improving in quality and capability faster now than ever before. When first introduced, cell phones were strictly used to make voice calls; now, they play satellite radio, MP3s, streaming television, have GPS and navigation capabilities, and have multi-megapixel video cameras. In the near future, cell phones will have programmable graphics processing units (GPU) that will allow users to play games similar to those currently available for top-of-the-line game consoles. Personal digital assistants enable users with full email, scheduling, and internet browsing capabilities in addition to those features offered on cell phones. Underlying all this mobile technology and entertainment is a battery whose technology has just barely tripled in the past 15 years, compared to available disk capacity that has increased over 1,000-fold. Ray tracing is a rendering technique used to generate photorealistic images that include reflections, refraction, participating media, and can fairly easily be extended to include photon mapping for indirect illumination and caustics. In recent years, ray tracing has been implemented on the GPU using various acceleration structures to facilitate rendering. Until now, all studies have used build time and achievable frame rates to determine which acceleration structure is best for ray tracing. We present the very first results comparing both CPU and GPU raytracing using various acceleration structures in terms of energy consumption. By exploring per-pixel costs, we provide insight on the energy consumption and frame rates that can be experienced on cell phones and other mobile devices based on currently available screen resolutions. Our results show that the choice in processing unit has the greatest affect on energy and time costs of ray tracing, followed by the size of the viewport used, and the choice of acceleration structure has the least impact on efficiency. For mobile devices enabled with a programmable GPU, whether it is a cell phone, PDA, or laptop computer, a bounding volume hierarchy implemented on the GPU is the most energy-efficient acceleration structure for ray tracing. Ray tracing on cellular phones with smaller screen resolutions is most energy-efficient using a CPU-based Kd-Tree implementation.

Zoomable user interfaces (ZUIs) have been studied for a long time and many applications are built upon them. Most applications, however, only use two dimensions to express the content. This report presents a solution using all three dimensions where the base features are built as a framework with uniform grids and scene graphs as primary data structures. The purpose of these data structures is to improve performance while maintaining flexibility when creating and handling three-dimensional objects. A 3D-ZUI is able to represent the view of the world and its objects in a more lifelike manner. It is possible to interact with the objects much in the same way as in real world. By developing a prototype framework as well as some example applications, the usefulness of 3D-ZUIs is illustrated. Since the framework relies on abstraction and object-oriented principles it is easy to maintain and extend it as needed. The currently implemented data structures are well motivated for a large scale 3D-ZUI in terms of accelerated collision detection and picking and they also provide a flexible base when developing applications. It is possible to further improve performance of the framework, for example by supporting different types of culling and levels of detail