T3 - Estudo do Algoritmo de Traçado de Raios

O objetivo deste trabalho é melhorar ou refazer o programa de ray tracing usado pelos alunos na matéria INF1761, de modo que se mantenha didático e seja mais eficiente. A página oficial do enunciado do trabalho contém outras informações. Este trabalho foi desenvolvido em conjunto com os alunos Fabrício Cardoso e Peter Dam. Os resultados (programa modificado e apresentação do trabalho) podem ser encontrados na seção de downloads ao final da página.

There is an old joke that goes: "Ray tracing is the technology of the future and it always will be!" - David Kirk, NVIDIA


1 - Análise do tempo

Primeiramente, realizamos a análise do tempo médio gasto para renderizar as imagens a 400x400 pixels na máquina de testes (Intel Core 2 Duo T5800 @ 2.00GHz, 3067MB RAM, NVIDIA GeForce 9600M GT 512MB). O compilador C utilizado foi o do Visual Studio 2008 (VS9), em modo Debug, sem opções de otimização. É necessário ressaltar que a análise de tempo médio para comparar ganhos e perdas de performance usada neste trabalho pode sofrer variações devido à carga corrente no processador no momento dos testes. Procurou-se reduzir o número de aplicações e serviços executando no momento dos testes para evitar que a multiplexação de tarefas do sistema operacional causasse grandes desvios na análise.

Cena Tempo médio (s)
 5balls  3.760
 bolas  6.833
 cavalo  51.979
 esfera  1.887
 esfera_planos  1.950
 esferas  1.482
 espelho  1.420
 pessoa  2.652
 pool  11.388
 room  10.983
 wall  2.636

2 - Melhorias propostas

Uma das melhorias propostas no enunciado do trabalho era utilizar macros para reduzir as chamadas de função, visto que nos módulos algebra.c e color.c do programa de ray tracer, as chamadas de função recebem parâmetros por cópia e muitas das funções possuem poucas linhas, porém, é preferível usar inline dado seus benefícios sobre macros [1, 2]. Uma melhoria proposta por nós é substituir a atual linguagem de descrição de cena por Lua [3, 4], visando uma melhor experiência do usuário ao criar a cena e permitir sua customização através de scripting. Outra melhoria proposta é a implementação de texturas, elemento faltante no código original.

3 - Resultados obtidos

3.1 - Inlining

O uso de inlining pode tanto trazer melhorias ao tempo de execução do código, ao evitar desvios na execução com chamadas de função, quanto acrescentar problemas, como aumentar a probabilidade de cache misses ao inserir mais instruções e aumentar o tempo de compilação. Além do mais, não deveria caber ao programador decidir quando uma função deve ser inline, e sim ao compilador.

Os novos resultados e o ganho em cima do tempo anterior estão listados a seguir (valores arredondados para 3 casas decimais):

Cena  T. M. anterior (s)
Inlining (s)
 Diferença (s)
 Diferença (%)
 5balls  3.760  3.666 0.094
 2.5
 bolas  6.833  6.645 0.188  2.751
 cavalo  51.979  50.264 1.715  3.299
 esfera  1.887  1.170 0.717  37.997
 esfera_planos  1.950  1.388 0.562  28.821
 esferas  1.482  1.513 -0.031  -2.092
 espelho  1.420  1.389 0.031  2.183
 pessoa  2.652  2.668 -0.016  -0.603
 pool  11.388  11.637 -0.249  -2.187
 room  10.983  10.608 0.375  3.414
 wall  2.636  2.621 0.015  0.569

Podemos ver que a melhora introduzida por forçar o compilador a usar inlining não foi tão significativa em cenas de geometria mais complexa, como as cenas 5balls, cavalo e pool.

3.2 - Conversão para Lua

Para a conversão do script de descrição de cena para Lua, criamos os módulos de definição luaInterface.h e de implementação luaInterface.c. A linkagem com a biblioteca de Lua permitiu uma melhor legibilidade do código, ao atribuirmos nomes aos dados para indexação nas tabelas, permitiu a automação dos scripts, de forma que é possível criar, por exemplo, 100 esferas que possuam uma correlação entre suas posições usando as estruturas de controle de Lua, como evidenciado no extrato de código abaixo.

Exemplo de automação de script com Lua


Dessa forma, criou-se oportunidades para a descrição de cenas mais complexas, mantendo um mínimo de legibilidade no código e com redução no esforço por parte do usuário, permitindo que o mesmo faça uso da flexibilidade de Lua.

3.3 - Mapeamento de texturas

O código para mapeamento de texturas está disponível no extrato abaixo.

Mapeamento de Textura


Com a implementação do mapeamento de texturas, tivemos a seguinte modificação na tabela de tempo.

Cena  T. M. anterior (s)
Inlining (s)
 Textura (s)
 Diferença (s)
 Diferença (%)
 5balls*  3.760  3.666  3.651 0.109
2.899
 bolas  6.833  6.645  6.645 0.188
2.751
 cavalo  51.979  50.264  50.264 1.715
3.299
 esfera*  1.887  1.170  1.185 0.702
37.202
 esfera_planos  1.950  1.388  1.373 0.577
29.590
 esferas  1.482  1.513  1.482 0
0
 espelho  1.420  1.389  1.435 -0.015
-1.056
 pessoa  2.652  2.668  2.636 0.016
0.603
 pool*  11.388  11.637  11.419 -0.031
-0.272
 room*  10.983  10.608  10.592 0.391
3.560
 wall*  2.636  2.621  2.776 -0.14
-5.311

* - cenas com textura aplicada

A parede a direita na imagem demonstração do ray tracing com textura pode aparentar estar com defeito na aplicação de texturas. Cabe-nos ressaltar que esse aparente defeito é devido à construção da parede à direita ser feita com 4 caixas para delimitar a janela, e não com uma caixa apenas com uma operação XOR para criar a abertura. Nota-se a ausência da quarta parede ao observar o espelho ao fundo da cena.



4 - Conclusão

O uso de inlining para buscar uma otimização do código nem sempre é um método que traz uma melhoria considerável no código, podendo ser ignorado pelo compilador a menos que forçado. A obtenção de um tempo decorrido correto está sujeita a variações na medida causadas por diversos fatores, como cache misses e troca de contexto do processador pelo escalonador de tarefas do sistema operacional.

O uso de Lua como linguagem de script para as cenas permitiu a criação de cenas mais complexas pela automatização de algumas tarefas e a extensão do script por parte do usuário, que pode escrever seus próprios métodos e módulos complementares, aumentando assim a gama de possibilidades (reservadas as limitações do programa de ray tracing).

Os resultados (programa modificado e apresentação do trabalho) podem ser encontrados na seção de downloads abaixo.

Apresentação sobre o trabalho:


5 - Referências

[1] MSDN Library. Inline function vs macro. Disponível em: http://msdn.microsoft.com/en-us/library/bf6bf4cf.aspx
[2] Wikipedia. Inline expansion. Disponível em: http://en.wikipedia.org/wiki/Inline_expansion
[3] Ierusalimschy, R., de Figueiredo, L., Celes,W. Lua - an extensible extension language. In: Software: Practice & Experience 26 #6, pp 635–652, 1996, John Wiley & Sons. Também disponível em http://www.lua.org/spe.html
[4] Lua as a data description language. Disponível em: http://lua-users.org/lists/lua-l/2004-06/msg00028.html

Č
ċ
Bruno Araujo,
23/09/2013 17:37
ċ
Bruno Araujo,
23/09/2013 17:17
Comments