Šiame darbe pristatysime du alternatyvius, vienus iš pačių populiariausių, realaus laiko šešėlių generavimo metodus. Tai šešėlių planų (angl. shadow maps) ir šešėlių tūrių (angl. shadow volumes) metodai. Kadangi šie metodai turi įvairių skirtingų privalumų ir trūkumų, yra nuolat tobulinami, kartais kuriami ir iš jų ir hibridiniai algoritmai, kurie perimtų kuo daugiau šių dviejų technikų gerųjų savybių. Todėl šiame darbe pamėginsime nustatyti ir įvertinti, kuriais atvejais yra vienas geresnis už kitą. / In this work we introduce to two alternative, most popular real time shadow rendering techniques. This is shadow map (or mapping) and shadow volumes techniques. Because those two methods have diferent advantages and weaknesses, there are always in development, and sometimes hybrid algorithms are created, which would absorb more good features from them. So in this work we tried to determine and rate in which cases one is better than another.

Skuggor är centrala för hur människan uppfattar världen. Inom datorspel och andra interaktiva 3D-applikationer är det viktigt att underlätta förståelsen av scenen och det finns även ofta en stark vilja att skapa realistiska miljöer. Detta samt att skuggsättning är en komplicerad och prestandakrävande operation gör det till ett viktigt område inom realtidsgrafik. Vi undersöker i denna avhandling relationen mellan prestandan (renderingstiden) för de två populära metoderna för skuggsättning inom realtidsgrafik, shadow mapping och shadow volumes. Undersökningen avgränsas till två utvalda varianter av de ursprungliga algoritmerna. I och med lanseringen av den nya versionen av Direct3D, version 10, öppnas möjligheten för optimeringar av algoritmerna genom användandet av framförallt geometry shaders. På grund av detta implementerar vi algoritmerna både med och utan den nya funktionalitet som introduceras i Direct3D 10 för att besvara om det är möjligt att förbättra prestandan för algoritmerna i Direct3D 10. Resultatet visar tydligt shadow mapping-algoritmens överlägsenhet för annat än scener med mycket få polygoner. Variabler så som ljusets infallsvinkel och objekts storlek har liten inverkan på det slutgiltiga resultatet för när vilken algoritm har bättre prestanda. Resultatet visar även tydligt att användandet av geometry shaders ger en mycket kraftig försämring av prestandan för båda algoritmerna. / Inom interaktiv 3D-grafik som exempelvis datorspel är det viktigt att skapa realistiska miljöer. Att rita ut en realistisk 3D-värld såpass snabbt att användaren inte kan se enskilda bildrutor kräver mycket kraft av datorn. Det är därför viktigt att datorprogrammet använder snabba och effektiva algoritmer. Skuggor är viktigt för att skapa realistiska 3D-miljöer. Detta arbete jämför snabbheten och effektiviteten mellan två olika metoder för att bestämma vad i 3D-världen som ligger i skugga.

This master's project focuses on basic techniques of creating shadows in 3D computer graphics. Two basic techniques are compared. Those are shadow maps and shadow volumes. Another technique combining previouse two is proposed.

Background. Shadow mapping is a method that is used for generating and imitating shadows in 3D-spaces. This technique has been used in the entertainment media industry in the form of games, movies and 3D renderings of environments to create a more realistic experience for consumers. Shadow mapping is not a perfect technique, and is performance costing on the GPU; however, some methods save performance by reducing the complexity of geometrical shapes and textures depending on the distance between observer and object. These techniques are based on that the observer will not notice the complexity reductions; can the usage of such methods be extended to textures covered in shadows without any consequences in the aspect of visual appearance and preference? Objectives. This thesis aims to examine if there is a possibility to extend the usage of LOD techniques to shadowed textures and to analyze individuals’ preferences of texture variants that are covered in shadows. Additionally, proposing the method of lowering texture resolution by using DirectX:s sampler data type, which is configurable to increase the level of details with mipmapping when sampling textures. Methods. This document presents a user study using the Two-alternative forced choice method and PsychoPy application to create a visual test. The visual test was conducted in a controlled and observed environment with volunteering participants. The objective of the visual test was to go through several sets of different images, and to choose which image of each set that was preferred. The stimulus was repeated with the initial images fading in and out slowly to prevent carry over effects. After the test participants were asked to fill out a questionnaire. The questionnaire assessed if they noticed any differences within the shadows, and if they had any additional thoughts about the experiment. Results. The results from the study were then evaluated through a binomial test that yielded that there was no statistically significant difference in preference between the lowered texture resolution in shadows and normal texture resolution in shadows. Separately evaluating the environments showed that there was a preference for shadowed low-resolution textures in environments that were dark. The environments with high illumination had more varied results. There were 17 participants that volunteered in the test and were ranging from the ages 18 to 29. Conclusions. With the results presented it was shown that the shadowed lowresolution textures were preferred in environments with low illumination. This suggests that the proposed concept method is better suited for similar environments. However, several factors may have affected the results. Factors such as images being too dark, the lack of exaggerated images, images fading in and out too fast, few participants, more partaking will assure there is less chance for bias.

Virtual crowd rendering have been used in film industry with offine rendering methods for a long time. But its existence in interactive real-time applications such as video games is not so common due to the limited rendering power of current graphics hardware. This thesis describes a novel method to improve shadow mapping performance of a crowded scene by taking into account the screen space visibility of the casted shadow of a crowd instance when rendering the shadow maps. A grid-based visibility mask creation method is proposed which is irrelevant to scene complexity. This improves the rendering performance especially when there are many occluded instances of the crowd which is a common scenario in urban environments and accelerates the usage of crowds in real time applications, such as games. We compute visibility of all agents in a crowd in parallel on the graphics processing unit(GPU) without having a requirement of a stencil buer or light direction dependent shadow mask. Technique also improves the view space rendering time by reducing the visibility check cost of the agents that are located on the invisible areas of the scene. The methodology introduced in this thesis gets more effective in each shadow map rendering pass by re-using the same visibility mask for shadow caster culling and enables many local lights with shadows. We also give a brief information about the state of the art of crowd rendering and shadowing, explaining how suitable the method with the implementations of different shadow mapping approaches. The technique is very well compatible with the modern crowd rendering techniques such as skinned instancing, dynamic level of detail(LOD) determination and GPU-based simulation.

Shadows have captivated humanity since the dawn of time; with the current age being no exception – shadows are core to realism and ambience, be it to invoke a classic Baroque interplay of lights, darks and colours as the case in Rembrandt van Rijn’s Militia Company of Captain Frans Banning Cocq or to create a sense of mystery as found in film noir and expressionist cinematography. Shadows, in this traditional sense, are regions of blocked light – the combined effect of placing an object between a light source and surface. This dissertation focuses on real-time shadow generation as a subset of 3D computer graphics. Its main focus is the critical analysis of numerous real-time shadow rendering algorithms and the construction of an empirically derived system for the high-speed rendering of shadows. This critical analysis allows us to assess the relationship between shadow rendering quality and performance. It also allows for the isolation of key algorithmic weaknesses and possible bottleneck areas. Focusing on these bottleneck areas, we investigate several possibilities of improving the performance and quality of shadow rendering; both on a hardware and software level. Primary performance benefits are seen through effective culling, clipping, the use of hardware extensions and by managing the polygonal complexity and silhouette detection of shadow casting meshes. Additional performance gains are achieved by combining the depth-fail stencil shadow volume algorithm with dynamic spatial subdivision. Using this performance data gathered during the analysis of various shadow rendering algorithms, we are able to define a fuzzy logic-based expert system to control the real-time selection of shadow rendering algorithms based on environmental conditions. This system ensures the following: nearby shadows are always of high-quality, distant shadows are, under certain conditions, rendered at a lower quality and the frames per second rendering performance is always maximised. / Dissertation (MSc)--University of Pretoria, 2009. / Computer Science / unrestricted

[pt] O mapeamento de sombras é uma técnica de renderização amplamente utilizada para a geração de sombras de superfícies arbitrárias em tempo real. No entanto, devido a sua natureza amostrada, apresenta dois problemas de difícil resolução: o aspecto chamuscado de objetos e a aparência serrilhada das bordas das sombras. Em particular, o sombreamento de modelos CAD (Computer-Aided Design) apresenta desafios ainda maiores, devido à existência de objetos estreitos com silhuetas complexas e o elevado grau de complexidade em profundidade. Neste trabalho, fazemos uma análise detalhada dos problemas de chamuscamento e serrilhamento, revisando e completando trabalhos de diferentes autores. Apresentamos ainda algumas propostas para melhoria de algoritmos existentes: o alinhamento de amostras independente de programas de vértice, um parâmetro generalizado para o LiSPSM (Light- Space Perspective Shadow Map), e um esquema de particionamento adaptativo em profundidade. Em seguida, investigamos a eficácia de diferentes algoritmos quando aplicados a modelos CAD, avaliando-os em critérios como facilidade de implementação, qualidade visual e eficiência computacional. / [en] Shadow mapping is a widely used rendering technique for shadow generation on arbitrary surfaces. However, because of the limited resolution available for sampling the scene, the algorithm presents two difficult problems to be solved: the incorrect self-shadowing of objects and the jagged appearance of shadow borders, also known as aliasing. Generating shadows for CAD (Computer-Aided Design) models presents additional challenges, due to the existence of many thin complex-silhouette objects and the high depth complexity. In this work, we present a detailed analysis of self-shadowing and aliasing by reviewing and building on works from different authors. We also propose some impromevents to existing algorithms: sample alignment without vertex shaders, a generalized parameter for the LiSPSM (Light-Space Perspective Shadow Map) algorithm, and an adaptive z- partitioning scheme. Finally, we investigate the effectiveness of different algorithms when applied to CAD models, considering ease of implementation, visual quality and computational efficiency.

The aim of master thesis is to describe different calculation of global illumination methods including Light Propagation Volumes. All three steps of LPV calculation are widely described: injection, propagation and rendering. It is also proposed several custom extensions improving graphics quality of this method. Two parts of design and implementation are focused on scene description, rendering system, shadow rendering, implementation of LPV method and proposed extensions. As conclusion, measurement and several images of application are presented, followed by comparison in environment with diffenent parameters, thesis summary with evaluation of achieved results and suggestions of further improvements.

The aim of this thesis was to implement a software that would be able to render, simulate and record a scene with walking pedestrians in real-time, with emphasis on rendering level of realism. The output of the application could serve as an input test data for people counting systems or similar systems for video recognition. The problem was divided into three major subproblems: character animation, artificial intelligence for character movement and advanced rendering techniques. The character animation problem is solved by the skeletal animation of the model. To achieve the characters moving in a scene autonomously path finding(A* algorithm) and group behaviors(steering behaviors) were implemented. Realism in a scene is added by implemented methods such as normal-mapping, variance shadow-mapping, deffered rendering, skydome, lens flare effect and screen space ambient occlusion. Optimaliaztion of the rendering was implemented using octree data structure for space partitioning. Rendering stage of a scene can be easily parametrized through implemented GUI. Implemented application provides the user with easy way of setting a scene with walking pedestrians, setting its visualization and to record the result.

This thesis focuses on 3D computer graphics and the continuous maximisation of rendering quality and performance. Its main focus is the critical analysis of numerous real-time rendering algorithms and the construction of an empirically derived system for the high-speed rendering of shader-based special effects, lighting effects, shadows, reflection and refraction, post-processing effects and the processing of physics. This critical analysis allows us to assess the relationship between rendering quality and performance. It also allows for the isolation of key algorithmic weaknesses and possible bottleneck areas. Using this performance data, gathered during the analysis of various rendering algorithms, we are able to define a selection engine to control the real-time cycling of rendering algorithms and special effects groupings based on environmental conditions. Furthermore, as a proof of concept, to balance Central Processing Unit (CPU) and Graphic Processing Unit (GPU) load for and increased speed of execution, our selection system unifies the GPU and CPU as a single computational unit for physics processing and environmental mapping. This parallel computing system enables the CPU to process cube mapping computations while the GPU can be tasked with calculations traditionally handled solely by the CPU. All analysed and benchmarked algorithms were implemented as part of a modular rendering engine. This engine offers conventional first-person perspective input control, mesh loading and support for shader model 4.0 shaders (via Microsoft’s High Level Shader Language) for effects such as high dynamic range rendering (HDR), dynamic ambient lighting, volumetric fog, specular reflections, reflective and refractive water, realistic physics, particle effects, etc. The test engine also supports the dynamic placement, movement and elimination of light sources, meshes and spatial geometry. Critical analysis was performed via scripted camera movement and object and light source additions – done not only to ensure consistent testing, but also to ease future validation and replication of results. This provided us with a scalable interactive testing environment as well as a complete solution for the rendering of computationally intensive 3D environments. As a full-fledged game engine, our rendering engine is amenable to first- and third-person shooter games, role playing games and 3D immersive environments. Evaluation criteria (identified to access the relationship between rendering quality and performance), as mentioned, allows us to effectively cycle algorithms based on empirical results and to distribute specific processing (cube mapping and physics processing) between the CPU and GPU, a unification that ensures the following: nearby effects are always of high-quality (where computational resources are available), distant effects are, under certain conditions, rendered at a lower quality and the frames per second rendering performance is always maximised. The implication of our work is clear: unifying the CPU and GPU and dynamically cycling through the most appropriate algorithms based on ever-changing environmental conditions allow for maximised rendering quality and performance and shows that it is possible to render high-quality visual effects with realism, without overburdening scarce computational resources. Immersive rendering approaches used in conjunction with AI subsystems, game networking and logic, physics processing and other special effects (such as post-processing shader effects) are immensely processor intensive and can only be successfully implemented on high-end hardware. Only by cycling and distributing algorithms based on environmental conditions and through the exploitation of algorithmic strengths can high-quality real-time special effects and highly accurate calculations become as common as texture mapping. Furthermore, in a gaming context, players often spend an inordinate amount of time fine-tuning their graphics settings to achieve the perfect balance between rendering quality and frames-per-second performance. Using this system, however, ensures that performance vs. quality is always optimised, not only for the game as a whole but also for the current scene being rendered – some scenes might, for example, require more computational power than others, resulting in noticeable slowdowns, slowdowns not experienced thanks to our system’s dynamic cycling of rendering algorithms and its proof of concept unification of the CPU and GPU. / Thesis (PhD)--University of Pretoria, 2012. / Computer Science / unrestricted