Boas vindas

Os Tamborins Estão Tocando!

Caro visitante,  Estamos finalmente, com uma reformulação do blog em curso! Depois de quatro anos, com mudança de gerenciador e remane...

Otimização de Desempenho em Planejadores de Caminho Usando Campos Potenciais

Trabalho de Conclusão de Curso de Graduação
(indexado pela 1ªvez em 30/11/2011)

Autor: Leonardo Garcia Fischer 
Instituição: UFRGS - Instituto de Informática
Orientador: Luciana Porcher Nedel e Renato Silveira
Ano: 2008
País: Brasil

Resumo
A animação de personagens autônomos interessa a muitas áreas, tais como  filmes, jogos e simulações. O seu principal objeto de estudo é a  definição de maneiras de reproduzir, de forma realística, um dado ser  (seja ele vivo, mecânico ou mesmo imaginário). Diversas técnicas já  foram propostas tentando se alcançar alta qualidade na animação final.  Porém, percebe-se que essas propostas são cada vez mais complexas,  dificultando o seu uso em aplicações de tempo real. Dessa forma, o  desempenho do algoritmo que executa a animação pode ser tão importante  quanto à qualidade da própria animação. Uma técnica que gere resultados  de alta qualidade, mas que não possa ser executada em tempo real será  bastante limitada quanto à sua aplicabilidade. Nesse sentido, esse  trabalho apresenta o estudo de um desses algoritmos, apresentando uma  forma de melhorar o seu desempenho, visando o seu uso em aplicações de  tempo real. Esse ganho de desempenho será alcançado utilizando as  características paralelizáveis do algoritmo estudado. Para alcançar  esse objetivo, este trabalho utiliza o alto paralelismo das placas  gráficas atuais para estender o trabalho iniciado por Dapper (DAPPER et  al., 2007).  Em seu trabalho, Dapper utilizou os campos potenciais  gerados a partir da solução numérica de problemas de valores de contorno  envolvendo a equação de Laplace (funções harmônicas). Esses campos  potenciais são capazes de gerar caminhos livres de mínimos locais, com  trajetórias suaves, e por isso foram utilizados para gerar o caminho a  ser seguido pelo agente autônomo. Como será visto, esses campos  potenciais podem ser obtidos mais rapidamente se os cálculos envolvidos  forem paralelizados. Também será apresentado uma série de testes que  demonstram que a implementação paralela do algoritmo é capaz de melhorar  o seu desempenho. Nos testes, foi possível detectar que a nova  implementação é capaz de ser até 56 vezes mais rápida que a versão  seqüencial. Isso torna o algoritmo aplicável para uso em tempo real,  mesmo em situações com centenas de personagens autônomos na cena. Por  fim, será apresentada uma série de outras contribuições feitas ao  projeto. Entre essas, destaca-se um sistema de ramificação de  trajetórias para definir caminhos, e a melhoria da qualidade do código  existente no início dos trabalhos, como forma de melhorar os trabalhos  futuros.

Palavras-chave: Planejamento de caminhos, GPGPU, Cuda, Paralelismo, Computação Gráfica

Para o texto completo, clique aqui!