Otimização de desempenho em planejadores de caminho usando campos potenciais

Abstract

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 repro-duzir, 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 im-portante 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, apresen-tando 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 para-lelizáveis do algoritmo estudado. Para alcançar esse objetivo, este trabalho utiliza o alto paralelismo das placas gráfi-cas 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ôni-cas). 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 me-lhorar os trabalhos futuros.

The autonomous agent animation concerns many areas, such as movies, games and simulations. Its main objective is how to define methods of reproducing a certain being in a realist way (be it alive, mechanic or even imaginary). Several techniques have al-ready been proposed in order to achieve high quality in the final animation. However, we can notice that these proposals are more and more complex, which difficults its use in real time applications. Thus, the algorithm's performance which accomplishes the animation can be as im-portant as the quality of the animation itself. A technique which produces high quality results, though it cannot be performed in real time, will be limited enough when it comes to applicability. Therein, this work shows the study of one of these algorithms, featuring a way of improving its performance and aiming at using it in real time applications. This perfor-mance advantage will be achieved by using parallel characteristics of the algorithm. Then, this work uses the actual video boards' high parallelism to extend Dapper's work (DAPPER et al., 2007). In his work, Dapper used the potential fields developed from a numerical solution of boundary value problems involving the Laplace's equation (harmonic functions). These potential fields can create paths with mild courses, free of local minimun. Because of this they were used to produce the path to be followed by the autonomous agent. As we will see, these potential fields can be achieved much more quickly if we parallelize the calculations involved in. It will be presented as well a series of tests which showed that the algorithm's paral-lel implementation can improve its performance. The tests showed that the new imple-mentation is up to 56 times faster than the sequential implementation. This makes the algorithm applicable for use in real time, even in situations with thousands of autonom-ous agents in the scene. Finally, a set of other contributions made to the project will be showed, among which two of them stand out: a system of ramification of paths to define routes and the improvement of the already existent code as a form of enriching later works.