Parallel interactive ray tracing and exploiting spatial coherence

Dissertação de mestrado em Engenharia de InformáticaRay tracing is a rendering technique that allows simulating a wide range of light transport phenomena, resulting on highly realistic computer generated imaging. Ray tracing is, however, computationally very demanding, compared to other techniques such as rasterization that achieves shorter rendering times by greatly simplifying the physics of light propagation, at the cost of less realistic images. The complexity of the ray tracing algorithm makes it unusable for interactive applications on machines without dedicated hardware, such as GPUs. The extreme task independent nature of the algorithm offers great potential for parallel processing, increasing the available computational power by using additional resources. This thesis studies different approaches and enhancements on the decomposition of workload and load balancing in a distributed shared memory cluster in order to achieve interactive frame rates. This thesis also studies approaches to enhance the ray tracing algorithm, by reducing the computational demand without decreasing the quality of the results. To achieve this goal, optimizations that depend on the rays’ processing order were implemented. An alternative to the traditional image plan traversal order, scan line, is studied, using space-filling curves. Results have shown linear speed-ups of the used ray tracer in a distributed shared memory cluster. They have also shown that spatial coherence can be used to increase the performance of the ray tracing algorithm and that the improvement depends of the traversal order of the image plane.O ray tracing é uma técnica de síntese de imagens que permite simular um vasto conjunto de fenómenos da luz, resultando em imagens geradas por computador altamente realistas. O ray tracing é, no entanto, computacionalmente muito exigente quando comparado com outras técnicas tais como a rasterização, a qual consegue tempos de síntese mais baixos mas com imagens menos realistas. A complexidade do algoritmo de ray tracing torna o seu uso impossível para aplicações interativas em máquinas que não disponham de hardware dedicado a esse tipo de processamento, como os GPUs. No entanto, a natureza extremamente paralela do algoritmo oferece um grande potencial para o processamento paralelo. Nesta tese são analisadas diferentes abordagens e optimizações da decomposição das tarefas e balanceamento da carga num cluster de memória distribuída, por forma a alcançar frame rates interativas. Esta tese também estuda abordagens que melhoram o algoritmo de ray tracing, ao reduzir o esforço computacional sem perder qualidade nos resultados. Para esse efeito, foram implementadas optimizações que dependem da ordem pela qual os raios são processados. Foi estudada, nomeadamente, uma travessia do plano da imagem alternativa à tradicional, scan line, usando curvas de preenchimento espacial. Os resultados obtidos mostraram aumento de desempenho linear do ray tracer utilizado num cluster de memória distribuída. Demonstraram também que a coerência espacial pode ser usada para melhorar o desempenho do algoritmo de ray tracing e que estas melhorias dependem do algoritmo de travessia utilizado