Árvores de busca pré-computadas: planejamento para animação interativa orientada a objetivos

Apresentamos uma abordagem inovadora para a síntese interativa de movimentos para personagens navegando em ambientes complexos. Focamos na eficiência em tempo de execução para geração de movimentos, permitindo assim a animação interativa de um grande número de personagens simultaneamente. A ideia principal é pré-computar árvores de busca de clipes de movimento que possam ser aplicadas a ambientes arbitrários. Dado um objetivo de navegação em relação a uma posição corporal atual, os melhores caminhos de solução disponíveis e sequências de movimento podem ser extraídos de forma eficiente durante a execução através de uma série de buscas em tabelas. Para posições de início e objetivo distantes, primeiro usamos um planejador rápido de nível grosseiro para gerar um caminho aproximado de sub-objetivos intermediários para guiar cada iteração da fase de busca em tempo de execução. Demonstramos a eficiência de nossa técnica em uma variedade de exemplos em uma aplicação interativa com múltiplos personagens autônomos navegando em ambientes dinâmicos. Cada personagem responde em tempo real a alterações arbitrárias dos usuários nos obstáculos ou objetivos de navegação do ambiente. A fase em tempo de execução é mais de duas ordens de magnitude mais rápida do que os métodos de planejamento existentes ou técnicas tradicionais de síntese de movimento. Nossa técnica não é útil apenas para geração autônoma de movimentos em jogos, realidade virtual e simulações interativas, mas também para animar multidões massivas de personagens offline para efeitos especiais em filmes. Categorias e Descritores de Assunto (de acordo com ACM CCS): I.3.7 Gráficos de Computador: Gráficos Tridimensionais e Realismo: Animação.