Global illumination is an important area of computer graphics, having direct applications in architectural visualization, lighting design and entertainment. Indirect illumination effects such as soft shadows, color bleeding, caustics and glossy reflections provide essential visual information about the interaction of different regions of the environment. Global illumination is a research area that deals with these illumination effects. Interactivity is also a desirable feature for many computer graphics applications, especially with unrestricted manipulation of the environment and lighting conditions. However, the design of methods that can handle both unrestricted interactivity and global illumination effects on environments of reasonable complexity is still an open challenge. <br /><br /> We present a new formulation of the light transport equation, called <em>pencil light transport</em>, that makes progress towards this goal by exploiting graphics hardware rendering features. The proposed method performs the transport of radiance over a scene using sets of pencils. A pencil object consists of a center of projection and some associated directional data. We show that performing the radiance transport using pencils is suitable for implementation on current graphics hardware. The new algorithm exploits optimized operations available in the graphics hardware architecture, such as pinhole camera rendering of opaque triangles and texture mapping. We show how the light transport equation can be reformulated as a sequence of light transports between pencils and define a new light transport operator, called the <em>pencil light transport operator</em>, that is used to transfer radiance between sets of pencils.

Conhecido pelo seu alto custo computacional e grande qualidade das imagens sintetizadas, o traçado de raios vem sendo mais recentemente explorado pela comunidade científica em pesquisas por uma taxa de quadro interativa e constante. Almejando um novo modo de aceleração do traçado de raios, uma nova abordagem denominada traçado de raios assistido pela unidade de processamento gráfico é apresentada neste trabalho. Seu objetivo é dar base à formulação de algoritmos que façam um uso melhor dos recursos disponíveis nas placas de vídeo frequentemente encontradas nos computadores convencionais atuais. Com base nesta abordagem, várias contribuições são propostas nesta dissertação. Além de apresentar conceitos básicos de traçado de raios e uma revisão literária de seus tópicos mais importantes, este trabalho também explica e exemplifica alguns algoritmos clássicos de traçado de raios que serão utilizados como base para outros algoritmos aqui apresentados. Como principal contribuição é proposto e implementado um algoritmo, que calcula os pontos iniciais de varredura de subdivisões espaciais do traçado de raios primários de mapas de alturas a partir de um distance-buffer (mapa de distâncias) sintetizado pela unidade de processamento gráfico da placa de vídeo. Um segundo algoritmo é também proposto, onde um object-buffer (mapa de objetos) é sintetizado pela placa de vídeo para acelerar a varredura de estruturas de subdivisão espacial em cenas com primitivas genéricas do traçado de raios. Contribuições pontuais são realizadas neste trabalho no campo de síntese de mapas de alturas pela definição dos seguintes algoritmos: o algoritmo de reconstrução bilinear analítica, o algoritmo de interpolação biquadrátrica dupla, o algoritmo de predição por planos de altura inclinados e o algoritmo de mapeamento de nível de detalhe de reconstrução da superfície para o modelo de voxels. Uma breve discussão a respeito do futuro de algoritmos de traçado de raios assistido pela unidade de processamento gráfico e de sua implementação em aglomerados gráficos é apresentada no final deste trabalho, explorando novas possibilidades para a sua continuidade, desencadeando novas linhas de pesquisa correlacionadas. / Known by its high computational cost and by the high quality rendered imagens, ray tracing has been most recently explored by the scientific community in researches for interactive and constant frame rate. Aiming for a new way for optimizing ray tracing, a new approach called GPU-assisted ray tracing is defined in this work. Its objective is to be a first step in the formulation of ray tracing algorithms that take better advantage of graphics processing units commonly found in personal computers nowadays. Based on this approach, several contributions are proposed in this work. Besides presenting the basic concepts for ray tracing and a literature review of the most relevant topics, this work also explains and exemplifies some classical algorithms that are used as a base for the new algorithms here presented. As main contribution, we propose and implement an algorithm that calculates the initial points for traversing spatial subdivision structures, for tracing primary rays in height maps from a distance-buffer rendered by the video card. A second algorithm is proposed as well, where an object-buffer is rendered by the video card to accelerate the traversal of rays in spatial subdivision structures for scenes with generic primitives. Individual contributions are made, in this work, in rendering height maps by defining the following algorithms: the analytic bilinear reconstruction algorithm, the double bi-quadratic interpolation algorithm, the prediction by inclined height planes algorithm and the level of detail mapping for surface reconstruction in voxel-based models algorithm. A brief discussion about the future of GPU-assisted ray tracing algorithms and its implementation in graphical clusters is presented at the end of this work, exploiting new possibilities for its continuation and for related research topics.

Conhecido pelo seu alto custo computacional e grande qualidade das imagens sintetizadas, o traçado de raios vem sendo mais recentemente explorado pela comunidade científica em pesquisas por uma taxa de quadro interativa e constante. Almejando um novo modo de aceleração do traçado de raios, uma nova abordagem denominada traçado de raios assistido pela unidade de processamento gráfico é apresentada neste trabalho. Seu objetivo é dar base à formulação de algoritmos que façam um uso melhor dos recursos disponíveis nas placas de vídeo frequentemente encontradas nos computadores convencionais atuais. Com base nesta abordagem, várias contribuições são propostas nesta dissertação. Além de apresentar conceitos básicos de traçado de raios e uma revisão literária de seus tópicos mais importantes, este trabalho também explica e exemplifica alguns algoritmos clássicos de traçado de raios que serão utilizados como base para outros algoritmos aqui apresentados. Como principal contribuição é proposto e implementado um algoritmo, que calcula os pontos iniciais de varredura de subdivisões espaciais do traçado de raios primários de mapas de alturas a partir de um distance-buffer (mapa de distâncias) sintetizado pela unidade de processamento gráfico da placa de vídeo. Um segundo algoritmo é também proposto, onde um object-buffer (mapa de objetos) é sintetizado pela placa de vídeo para acelerar a varredura de estruturas de subdivisão espacial em cenas com primitivas genéricas do traçado de raios. Contribuições pontuais são realizadas neste trabalho no campo de síntese de mapas de alturas pela definição dos seguintes algoritmos: o algoritmo de reconstrução bilinear analítica, o algoritmo de interpolação biquadrátrica dupla, o algoritmo de predição por planos de altura inclinados e o algoritmo de mapeamento de nível de detalhe de reconstrução da superfície para o modelo de voxels. Uma breve discussão a respeito do futuro de algoritmos de traçado de raios assistido pela unidade de processamento gráfico e de sua implementação em aglomerados gráficos é apresentada no final deste trabalho, explorando novas possibilidades para a sua continuidade, desencadeando novas linhas de pesquisa correlacionadas. / Known by its high computational cost and by the high quality rendered imagens, ray tracing has been most recently explored by the scientific community in researches for interactive and constant frame rate. Aiming for a new way for optimizing ray tracing, a new approach called GPU-assisted ray tracing is defined in this work. Its objective is to be a first step in the formulation of ray tracing algorithms that take better advantage of graphics processing units commonly found in personal computers nowadays. Based on this approach, several contributions are proposed in this work. Besides presenting the basic concepts for ray tracing and a literature review of the most relevant topics, this work also explains and exemplifies some classical algorithms that are used as a base for the new algorithms here presented. As main contribution, we propose and implement an algorithm that calculates the initial points for traversing spatial subdivision structures, for tracing primary rays in height maps from a distance-buffer rendered by the video card. A second algorithm is proposed as well, where an object-buffer is rendered by the video card to accelerate the traversal of rays in spatial subdivision structures for scenes with generic primitives. Individual contributions are made, in this work, in rendering height maps by defining the following algorithms: the analytic bilinear reconstruction algorithm, the double bi-quadratic interpolation algorithm, the prediction by inclined height planes algorithm and the level of detail mapping for surface reconstruction in voxel-based models algorithm. A brief discussion about the future of GPU-assisted ray tracing algorithms and its implementation in graphical clusters is presented at the end of this work, exploiting new possibilities for its continuation and for related research topics.

Recently, methods were developed to render various global illumination effects with rasterization GPUs. Among those were hardware based ray tracing and photon mapping. However, due to current GPU??s inherent architectural limitations, the efficiency and throughput of these methods remained low. In this thesis, we propose a coherent rendering system that addresses these issues. First, we introduce new photon mapping and ray racing acceleration algorithms that facilitate data coherence and spatial locality, as well as eliminating unnecessary random memory accesses. A high level abstraction of the combined ray tracing and photon mapping streaming pipeline is introduced. Based on this abstraction, an efficient ray tracing and photon mapping GPU is designed. Using an event driven simulator, developed for this GPU, we verify and validate the proposed algorithms and architecture. Simulation results have validated better interactive performances compared to the current GPUs.

Global illumination is an important area of computer graphics, having direct applications in architectural visualization, lighting design and entertainment. Indirect illumination effects such as soft shadows, color bleeding, caustics and glossy reflections provide essential visual information about the interaction of different regions of the environment. Global illumination is a research area that deals with these illumination effects. Interactivity is also a desirable feature for many computer graphics applications, especially with unrestricted manipulation of the environment and lighting conditions. However, the design of methods that can handle both unrestricted interactivity and global illumination effects on environments of reasonable complexity is still an open challenge. <br /><br /> We present a new formulation of the light transport equation, called <em>pencil light transport</em>, that makes progress towards this goal by exploiting graphics hardware rendering features. The proposed method performs the transport of radiance over a scene using sets of pencils. A pencil object consists of a center of projection and some associated directional data. We show that performing the radiance transport using pencils is suitable for implementation on current graphics hardware. The new algorithm exploits optimized operations available in the graphics hardware architecture, such as pinhole camera rendering of opaque triangles and texture mapping. We show how the light transport equation can be reformulated as a sequence of light transports between pencils and define a new light transport operator, called the <em>pencil light transport operator</em>, that is used to transfer radiance between sets of pencils.

Recently, methods were developed to render various global illumination e&#64256;ects with rasterization GPUs. Among those were hardware based ray tracing and photon mapping. However, due to current GPU??s inherent architectural limitations, the e&#64259;ciency and throughput of these methods remained low. In this thesis, we propose a coherent rendering system that addresses these issues. First, we introduce new photon mapping and ray racing acceleration algorithms that facilitate data coherence and spatial locality, as well as eliminating unnecessary random memory accesses. A high level abstraction of the combined ray tracing and photon mapping streaming pipeline is introduced. Based on this abstraction, an e&#64259;cient ray tracing and photon mapping GPU is designed. Using an event driven simulator, developed for this GPU, we verify and validate the proposed algorithms and architecture. Simulation results have validated better interactive performances compared to the current GPUs.

O advento das unidades de processamento gráfico (GPUs) programáveis forneceram um novo modelo computacional que pode ser utilizado em diversas aplicações. Baseadas em arquitetura de fluxo paralelo, a atual geração de GPUs oferece processadores de vértices e de fragmentos programáveis que podem aumentar drasticamente a performance comparada com soluções implementadas exclusivamente em CPUs. Entretanto obter performance ótima no modelo computacional da GPU, que é complexo e altamente paralelo, com ferramentas de depuração limitadas é uma tarefa difícil e importante. Neste trabalho nós descrevemos uma abordagem simples para avaliar diversas soluções baseadas em GPU para uma dada solução. Ela consiste de um modelo de estimativa de performance que procura reproduzir, dentro de faixas toleráveis de erro, a medida de performance para a unidade de processamento de fragmentos. Nós avaliamos a nossa proposta utilizando as últimas gerações de placas gráficas da NVidia e da ATI usando um conjunto de medidas sintéticas bem como um estudo de caso de uma aplicação em tempo-real. / The advent of Graphics Processing Units (GPUs) with programmable shaders brought a new computational model that can be used in several applications. Based on a parallel streaming architecture, current GPU generations offer a vertex and fragment shader that can drastically improve performance if compared to CPU-only solutions. However, obtaining optimal performance in the highly parallel and complex GPU model with limited debugging tools is a challenging and important task. In this work we describe a simple approach to evaluate several GPU alternatives to a given solution. It consists of a performance estimation model that aims to reproduce within acceptable errors the measured performance of the fragment shader. We evaluate our proposal using last generation cards from NVIDIA and ATI using synthetic benchmarks as well as a real-time graphics application case-study.

O advento das unidades de processamento gráfico (GPUs) programáveis forneceram um novo modelo computacional que pode ser utilizado em diversas aplicações. Baseadas em arquitetura de fluxo paralelo, a atual geração de GPUs oferece processadores de vértices e de fragmentos programáveis que podem aumentar drasticamente a performance comparada com soluções implementadas exclusivamente em CPUs. Entretanto obter performance ótima no modelo computacional da GPU, que é complexo e altamente paralelo, com ferramentas de depuração limitadas é uma tarefa difícil e importante. Neste trabalho nós descrevemos uma abordagem simples para avaliar diversas soluções baseadas em GPU para uma dada solução. Ela consiste de um modelo de estimativa de performance que procura reproduzir, dentro de faixas toleráveis de erro, a medida de performance para a unidade de processamento de fragmentos. Nós avaliamos a nossa proposta utilizando as últimas gerações de placas gráficas da NVidia e da ATI usando um conjunto de medidas sintéticas bem como um estudo de caso de uma aplicação em tempo-real. / The advent of Graphics Processing Units (GPUs) with programmable shaders brought a new computational model that can be used in several applications. Based on a parallel streaming architecture, current GPU generations offer a vertex and fragment shader that can drastically improve performance if compared to CPU-only solutions. However, obtaining optimal performance in the highly parallel and complex GPU model with limited debugging tools is a challenging and important task. In this work we describe a simple approach to evaluate several GPU alternatives to a given solution. It consists of a performance estimation model that aims to reproduce within acceptable errors the measured performance of the fragment shader. We evaluate our proposal using last generation cards from NVIDIA and ATI using synthetic benchmarks as well as a real-time graphics application case-study.

O advento das unidades de processamento gráfico (GPUs) programáveis forneceram um novo modelo computacional que pode ser utilizado em diversas aplicações. Baseadas em arquitetura de fluxo paralelo, a atual geração de GPUs oferece processadores de vértices e de fragmentos programáveis que podem aumentar drasticamente a performance comparada com soluções implementadas exclusivamente em CPUs. Entretanto obter performance ótima no modelo computacional da GPU, que é complexo e altamente paralelo, com ferramentas de depuração limitadas é uma tarefa difícil e importante. Neste trabalho nós descrevemos uma abordagem simples para avaliar diversas soluções baseadas em GPU para uma dada solução. Ela consiste de um modelo de estimativa de performance que procura reproduzir, dentro de faixas toleráveis de erro, a medida de performance para a unidade de processamento de fragmentos. Nós avaliamos a nossa proposta utilizando as últimas gerações de placas gráficas da NVidia e da ATI usando um conjunto de medidas sintéticas bem como um estudo de caso de uma aplicação em tempo-real. / The advent of Graphics Processing Units (GPUs) with programmable shaders brought a new computational model that can be used in several applications. Based on a parallel streaming architecture, current GPU generations offer a vertex and fragment shader that can drastically improve performance if compared to CPU-only solutions. However, obtaining optimal performance in the highly parallel and complex GPU model with limited debugging tools is a challenging and important task. In this work we describe a simple approach to evaluate several GPU alternatives to a given solution. It consists of a performance estimation model that aims to reproduce within acceptable errors the measured performance of the fragment shader. We evaluate our proposal using last generation cards from NVIDIA and ATI using synthetic benchmarks as well as a real-time graphics application case-study.

Um dos algoritmos para cálculo de sombras mais eficientes existentes atualmente é o Shadow Mapping de Williams. Ele é simples, robusto e facilmente mapeável para o hardware gráfico existente. Este algoritmo conta com duas etapas. A primeira é responsável pela geração de um depth buffer (Shadow Map) a partir do ponto de vista da luz. Na segunda etapa a imagem final da cena é gerada a partir do ponto de vista da câmera. De maneira a determinar se os pixels da imagem final estão iluminados ou em sombra, cada pixel é transformado para o espaço da luz e testado contra o Shadow Map. Shadow Maps tradicionais armazenam apenas um valor de profundidade por célula, fazendo com que os testes de sombra retornem valores binários. Isso pode ocasionar o surgimento de aliasing nas bordas das sombras. Este trabalho apresenta uma nova abordagem capaz de produzir melhores resultados de suavização que, em conjunto com o algoritmo de PCF (Percentage Closer Filtering), reduz o serrilhado das bordas das sombras através do uso de filtros de menor tamanho. O novo algoritmo estende os conceitos de Shadow Map e de teste de sombra de forma a suportarem múltiplos valores de profundidade. Esta nova abordagem apresenta potencial para implementação em hardware, e também pode ser implementada explorando a programabilidade das recentes placas gráficas. / William’s Shadow Mapping is one of the most efficient hard shadow algorithms. It is simple, robust and can be easily mapped to the actual grapics hardware. It is a two-pass technique. In the first pass a depth buffer (Shadow Map) is created from the light’s view point. In the second pass the final image is rendered from the camera’s view point. In order to decide whether each pixel in the camera’s view is lit or in shadow with respect to the light source, the pixel is transformed into the light space, and tested against the Shadow Map. Shadow maps store a single depth value per cell, leading to a binary outcome by the shadow test, and are prone to produce aliased shadow borders. This work presents a new approach that produces better estimates of shadow percentages and, in combination with percentage closer filtering (PCF), reduces aliasing artifacts using smaller kernel sizes. The new algorithm extends the notions of shadow map and shadow test to support the representation of multiple depth values per shadow map cell, as well as multi-valued shadow test. This new approach has the potential for hardware implementation, but can also be implemented exploiting the programmable capabilities of recent graphics cards.