Encontrar um modo de criar imagens fotorealísticas tem sido uma meta da Computação Gráfica por muitos anos [GLA 89]. Neste sentido, os aspectos que possuem principal importância são a modelagem e a iluminação. Ao considerar aspectos de modelagem, a obtenção de realismo mostra-se bastante difícil quando se pretende, através de técnicas tradicionais de modelagem, modelar objetos cujas formas não são bem definidas. Dentre alguns exemplos destes tipos de objetos, podem-se citar fogo, fumaça, nuvens, água, etc. Partindo deste fato, Reeves [REE 83] introduziu uma técnica denominada sistemas de partículas para efetuar a modelagem de fogo e explosões. Um sistema de partículas pode ser visto como um conjunto de partículas que evoluem ao longo do tempo. Os procedimentos envolvidos na animação de um sistema de partículas são bastante simples. Basicamente, a cada instante de tempo, novas partículas são geradas, os atributos das partículas antigas são alterados, ou estas partículas podem ser extintas de acordo com certas regras pré-definidas. Como as partículas de um sistema são entidades dinâmicas, os sistemas de partículas são especialmente adequados para o uso em animação. Ainda, dentre as principais vantagens dos sistemas de partículas quando comparados com as técnicas tradicionais de modelagem, podem-se citar a facilidade da obtenção de efeitos sobre as partículas (como borrão de movimento), a necessidade de poucos dados para a modelagem global do fenômeno, o controle por processos estocásticos, o nível de detalhamento ajustável e a possibilidade de grande controle sobre as suas deformações. Entretanto, os sistemas de partículas possuem algumas limitações e restrições que provocaram o pouco desenvolvimento de algoritmos específicos nesta área. Dentre estas limitações, as principais são a dificuldade de obtenção de efeitos realísticos de sombra e reflexão, o alto consumo de memória e o fato dos sistemas de partículas possuírem um processo de animação específico para cada efeito que se quer modelar. Poucos trabalhos foram desenvolvidos especificamente para a solução destes problemas, sendo que a maioria se destina à modelagem de fenômenos através de sistemas de partículas. Tendo em vista tais deficiências, este trabalho apresenta métodos para as soluções destes problemas. É apresentado um método para tornar viável a integração de sistemas de partículas em ambientes de Ray Tracing, através do uso de uma grade tridimensional. Também, são apresentadas técnicas para a eliminação de efeitos de aliasing das partículas, assim como para a redução da quantidades de memória exigida para o armazenamento dos sistemas de partículas. Considerando aspectos de animação de sistemas de partículas, também é apresentado uma técnica de aceleração para a detecção de colisões entre o sistema de partículas e os objetos de uma cena, baseada no uso de uma grade pentadimensional. Aspectos relativos à implementação, tempo de processamento e fatores de aceleração são apresentados no final do trabalho, assim como as possíveis extensões futuras e trabalhos sendo realizados. / Finding a way to create photorealistic images has been a goal of Computer Graphics for many years [GLA 89]. In this sense, the aspects that have main importance are modeling and illumination. Considering aspects of modeling, the obtention of realism is very difficult when it is intended to model fuzzy objects using traditional modeling techniques. Among some examples of these types of objects, fire, smoke, clouds, water, etc. can be mentioned. With this fact in mind, Reeves [REE 83] introduced a technique named particle systems for modeling of fire and explosions. A particle system can be seen as a set of particles that evolves over time. The procedures involved in the animation of particle systems are very simple. Basically, at each time instant, new particles are generated, the attributes of the old ones are changed, or these particles can be extinguished according to predefined rules. As the particles of a system are dynamic entities, particle systems are specially suitable for use in animation. Among the main advantages of particle systems, when compared to traditional techniques, it can be mentioned the facility of obtaining effects such as motion blur over the particles, the need of few data to the global modeling of a phenomen, the control by stochastic processes, an adjustable level of detail and a great control over their deformations. However, particle systems present some limitations and restrictions that cause the little development of specific algorithms in this area. Among this limitations, the main are the difficulty of obtention of realistic effects of shadow and reflection, the high requirement of memory and the fact that particle systems need a specific animation process for each effect intended to be modeled. Few works have been developed specifically for the solution of these problems; most of them are developed for the modeling of phenomena through the use of particle systems. Keeping these deficiencies in mind, this work presents methods for solving these problems. A method is presented to make practicable the integration of particle systems and ray tracing, through the use of a third-dimensional grid. Also, a technique is presented to eliminate effects of aliasing of particles, and to reduce the amount of memory required for the storage of particle systems. Considering particle systems animation, a technique is also presented to accelerate the collision detection between particle systems and the objects of a scene, based on the use of a fifth-dimensional grid. Aspects related to the implementation, processing time and acceleration factors are presented at the end of the work, as well as the possible future extensions and ongoing works.

Segundo Thalmann em 1996, animação é a visualização da variação do estado de objetos em relação ao tempo. A meta principal da animação modelada por computador é sintetizar o efeito desejado de movimento que é uma mistura de fenômenos naturais, percepção e imaginação. O sistema de animação deve providenciar ferramentas de controle de movimento para traduzir os desejos do usuário na linguagem do sistema. O controle dos movimentos de uma animação pode ser dividido em duas classes de algoritmos: a classe intencional, dirigida aos aspectos de controle em alto nível, onde as intenções de uma animação são expressas e a classe concreta, dirigida aos aspectos específicos de animação de objetos. A relação hierárquica destas classes favorece a implementação de um motor de animação usando camadas de abstração. Uma das abordagens atuais para a construção de um motor de animação para atores humanóides é um sistema implementado em camadas. A camada inferior lida com os movimentos individuais das articulações. As intermediárias são responsáveis por encapsular conjuntos de movimentos que atuam como tarefas simples. O encapsulamento destas tarefas é feito por camadas superiores que lidam com ações sensíveis ao ambiente. Por fim, a camada de mais alto nível atua no nível cognitivo onde um mecanismo dotado de capacidade de raciocínio comanda ações aos atores de acordo com as informações do contexto e também de acordo com as intenções, crenças e desejos dos atores. Este trabalho visa analisar uma proposta de implementação de um motor de animação para simular o comportamento de atores humanóides, gerando animações em três dimensões via World Wide Web. Dois modelos de animação baseados no formalismo AFS (Autômato Finito com Saída) que lidam com camadas específicas de abstração de um sistema de animação serão apresentados. O modelo AGA-J é uma extensão do modelo AGA para lidar com a classe concreta de movimentos de atores humanóides em 3D e serve como camada de fundação para outros modelos. O modelo AGA gera sequências animadas a partir de um conjunto de AFS que representam os atores da animação e um conjunto de fitas de entrada que determinam os comportamentos dos atores. O alfabeto de saída é representado por imagens e efeitos sonoros e a animação se dá pela sequência das saídas dos autômatos. O modelo AGA-T é um modelo orientado a tarefas, baseado em autômatos probabilísticos e eventos. Este modelo atua como uma camada de nível superior sobre o AGA-J, e foi projetado para lidar com alguns aspectos da classe intencional, sobretudo o encapsulamento de movimentos através de tarefas. O formalismo de AFS foi escolhido para a construção dos modelos porque propicia muitas características importantes: saída configurável através da análise da fita de saída; reusabilidade pelo fato de vários atores poderem usar o mesmo AFS; e recuperação de informação, observando o estado atual dos autômatos dos atores que compõem a animação. / According to Thalmann in 1996, animation is the visualization of changings on object states during time. The first goal of computer animation is to synthesize the desired motion effect that is a mix of natural phenomena, perception and imagination. An animation system must provide motion control tools to translate the user intentions into the system language. The motion control can be divided in two classes of algorithms: the intentional class, directed towards the high-level control aspects where the animation intentions are expressed; and the concrete class, which deals with specific aspects of object animation. The hierarchical relationship between these two classes benefits the implementation of an animation engine based on abstraction layers. One recent approach for building an animation engine to represent humanoid actors is a system implemented in layers. The lowest layer deals with individual joint movements, while the middle layers are responsible for encapsulating a set of movements acting as simple tasks. The task encapsulation is performed by high-level layers dealing with environment sensitive actions. Finally, the highest-level layer acts in the cognitive level, where a reasoning mechanism commands actions to the actors according to the context information, the beliefs, desires and intentions of the actors. This work explores an implementation proposal of an animation engine for simulating the behavior of humanoid actors, generating 3D animations to theWorld Wide Web. Two animation models based on the Finite Automata with Output formalism that deal with specific abstraction layers of an animation system will be presented. The AGA-J model is an extension of the AGA model for dealing with the concrete class of 3D movements of humanoid actors and it suits as a foundation layer for other models. The AGA model generates animated sequences by a set of Finite Automata with Output that implements the animation actors and a set of input tapes which determines the behavior of the actors. The output alphabet is represented by images, and sound effects, and the animation is produced by the sequence of the automata output. The AGA-T model is a task-oriented model, based on probabilistic automata and events. This model acts as a high-level layer over the AGA-J, and it was designed for dealing with some aspects of the intentional class, mainly the movement encapsulation by tasks. The Finite Automata with Output formalism was chosen for model construction because it provides many important features: adaptable output by analysis of output tape; reusability by the fact of many actors can use the same automaton; and information retrieval by observation of current state of the automata composing the animation.

A simulação do movimento de humanos virtuais em mundos sintéticos é necessária a áreas tais como: jogos eletrônicos, filmes, ambientes virtuais colaborativos como Second Life R , simulação de pedestres, sistemas de treinamento e simulação de evacuações em situações de emergência. Contudo, mesmo sendo um importante tópico de pesquisa desde a década de 70, a simulação de comportamentos para personagens virtuais ainda é um desafio. O principal objetivo deste trabalho é estender a técnica proposta por Dapper et al. (DAPPER, 2007) onde foi apresentado um planejador de movimento para humanos virtuais que fornece trajetórias suaves e dependentes de parâmetros individuais dos agentes, permitindo a navegação de grupos de forma mais eficiente. Neste trabalho, é proposto um algoritmo para controlar o movimento de grupos em ambientes interativos e uma estratégia para manter a formação durante o deslocamento. O método é baseado em campos potenciais, ou seja, na solução numérica de problemas de valores de contorno envolvendo a equação de Laplace. O método proposto, é composto de duas camadas. Na primeira camada, um mapa para o controle do grupo é criado para possibilitar o controle de cada indivíduo, enquanto que na segunda camada, um algoritmo de planejamento de caminho é utilizado para o movimento do grupo como um todo. A técnica proposta combina o planejamento de movimento para grupos com a navegação baseada em esboços. Os resultados mostram que a técnica é robusta e pode ser utilizada em tempo-real. / The motion simulation of the movement of virtual humans in synthetic worlds is necessary for areas such as: electronic games, movies, collaborative virtual environments such as Second Life R , pedestrian simulation, training systems, simulation of evacuations in emergency situations. However, although being an important research topic since the 70s, the simulation of behaviors for virtual characters is still a challenge. Dapper et al. (DAPPER, 2007) developed a motion planner that provides smooth trajectories dependent on the individual parameters of the agents. The main goal of this work is to extend the technique proposed by Dapper, allowing for a more efficient control and navigation of groups. In this work, an algorithm for the control of group motion in interactive environments is proposed, along with a strategy for maintaining the group formation during the motion. The method is based on potential fields, more specifically, on the numeric solution of boundary-value problems involving the Laplace equation. The proposed method has two layers. In the first layer, a map for group control is created in order to allow for the control of every individual, while in the second layer a path planning algorithm is used for the movement of the group as a whole. The proposed technique combines the planning of group movements with a sketch-based navigation. The results show that the technique is robust and can be used in real-time.

A descrição de animação modelada sempre foi motivo de pesquisa na área de Computação Gráfica. Visando simplificar a especificação do movimento, diversas técnicas surgiram: animação por quadros-chave, algorítmica (ou procedimental), baseada em distorções dos objetos e baseada em comportamento, entre outras. Este trabalho apresenta uma nova abordagem para a obtenção de animação, mais especificamente, animação modelada pela definição de comportamento, na qual a ideia básica é que o usuário não deve ter o controle total e absoluto sobre todas as ações dos atores, mas sim deve ter uma noção de como a seqüência deve se desenvolver. Esta abordagem desenvolveu-se a partir de um estudo realizado das principais técnicas existentes para a obtenção desse tipo de animação, procurando reconhecer as características positives de cada uma, a fim de tentar reuni-las em uma abordagem Única. Foram estudadas as seguintes abordagens: caminhos pré-definidos, sensor-effector, regras de comportamento, algoritmos genéticos e relações. No sentido de facilitar ao máximo esta especificação, surgiu outro objetivo importante para o trabalho: a criação de um protótipo, o qual deveria possuir uma interface gráfica, buscando automatizar e simplificar as operações necessárias definição das animações. O desenvolvimento deste protótipo serviu como meio para validar a abordagem, provando que esta pode ser efetivamente utilizada para a criação de seqüências animadas, com algumas limitações impostas por sua própria natureza. O protótipo permite a definição de animações de uma forma totalmente interativa, facilitando a descrição de comportamentos e a manipulação dos atores em uma cena. Possui ainda ulna função de pré-visualização, para visualizar as animações rapidamente e funções para gravação dos quadros individuais. / The description of modeled animation had always been a research subject in Computer Graphics. To make the movement description easier, some methods then have appeared: keyframing, algorythmic animation, physically-based, based in object distortion, based in behavior description, among others. This work presents a new approach to obtain computer animation, specifically, behavioral modelled animation, where the main idea is that the user shouldn't have total control about all actors' actions, but only a notion on how the sequence should look like. This approach was developed from a study of the present research in behavioral animation, trying to recognize the good points of each method and join them in a single approach. The following methods were studied: predefined paths, sensor-effector, behavior rules, genetic algorithms and relations. In the sense to ease at the most this specification, another goal showed up: the creation of a prototype, which should have a graphical interface, looking for the automatization and simplification of the needed operations for sequence definition. The development of this prototype served as a means to validate the new approach, proving that it can be used for the creation of animated sequences, with some limitations imposed by its own features. The prototype allows the definition of animations in a fully interactive way, easing behavior description and actor manipulation in a scene. There is a preview function, to watch animations quickly and easily. Also are provided functions for saving individual frames.

O processo de parametrização de malhas em planos é um tópico de pesquisa bastante explorado. Apesar do grande esforço despendido no desenvolvimento de técnicas mais eficientes e robustas, pouco se tem investido no uso das representações paramétricas geradas por estas técnicas. Este trabalho apresenta contribuições relacionadas ao uso do espaço paramétrico para computações eficientes. A principal motivação vem do fato de alguns algoritmos serem mais eficientes quando aplicados sobre a versão paramétrica da malha. Algoritmos para o cálculo de distância mínima, por exemplo, podem ter um aumento significativo de eficiência quando aplicados em versões paramétricas de malhas. Nossos resultados demonstram que esses aumentos de eficiência podem chegar a cerca de uma ordem de magnitude em alguns casos. As contribuições deste trabalho possuem aplicação direta em três campos de pesquisa relacionados à computação gráfica: displacement mapping, cálculo de distâncias sobre superfícies e movimentação de agentes. A contribuição relacionada a displacement mapping, apresentada no capítulo 4, é utilizada para aumentar a performance de renderização e a qualidade visual de terrenos em jogos. O novo método de cálculo de distâncias proposto, apresentado no capítulo 5, aumenta a eficiência de vários algoritmos de cálculo de distância sobre superfícies de malhas. Este novo método também é utilizado em uma nova técnica para cálculo de movimentação de agentes em superfícies de malhas arbitrárias. Esta técnica é apresentada no capítulo 6. O potencial da nova técnica de cálculo de distância sobre malhas não está restrito aos exemplos apresentados. Em geral, qualquer técnica que utilize o cálculo de distância sobre superfícies de malhas de triângulos se beneficia das contribuições deste trabalho, podendo-se citar como exemplos a geração de texturas procedurais, rotulamento de superfícies, re-triangulação de malhas e segmentação de malhas, entre outros. / The process of parameterizing a mesh to the plane is an ongoing research topic. Although there are several works dedicated to parameterization techniques the use of the resulting parameterizations has received less attention. This work presents contributions related to the use of the parametric space to improve the computational efficiency of several algorithms. The main motivation comes from the fact that some algorithms are more efficiently computed on the parametric version of the mesh, compared to the 3-D version. For example, shortest distances can be computed, usually, an order of magnitude faster on the parametric space. The contributions of this work can be applied to at least three research fields related to computer graphics: displacement mapping, distance computation on the surface of triangular meshes and agent path planning. The contribution related to displacement mapping, presented in chapter 4, is used to increase the rendering performance and visual quality of terrains in games. The new method to compute distances, presented in chapter 5, increases the efficiency of several distance computation algorithms. This new method was also used on a novel agent path planning algorithm, to navigate agents on the surface of arbitrary meshes. This technique is presented in chapter 6. The potential of the new distance computation method is not restricted to the applications presented in this thesis. In general, any technique that uses distance computation on the surface of triangular meshes can have the performance improved by the method. We can cite the following applications: procedural texture generation, surface labeling, re-meshing, mesh segmentation, etc.

A simulação de pedestres representados como humanos virtuais em um mundo sintético é de grande interesse em áreas como cinema, arquitetura e jogos. Esta atividade pode ser definida como navegação em ambientes virtuais e envolve principalmente a especificação do ambiente, a definição da posição inicial do agente, assim como sua posição final (ou objetivo). Tendo estes parâmetros definidos, um algoritmo de planejamento de movimento, ou de caminhos, em particular, pode ser usado para encontrar uma trajetória a ser seguida por ele. Entretanto, em um mundo real, se considerar-se várias pessoas, todas na mesma posição inicial e procurando atingir o mesmo objetivo, cada uma seguirá por um caminho diferente. Ou seja, para uma mesma tarefa, a estratégia utilizada por cada pessoa para alcançar seu objetivo vai depender de sua constituição física, personalidade, humor e raciocínio. Levando em consideração estas questões, este trabalho apresenta um estudo sobre planejamento de movimento para pedestres. Como resultado prático foi desenvolvido um planejador que fornece trajetórias suaves e variadas. As trajetórias são dependentes de características individuais de cada agente, que podem ser alteradas dinâmicamente. O método adotado é baseado na utilização de campos potenciais gerados pela solução numérica de problemas de valores de contorno envolvendo a equação de Laplace (funções harmônicas) e o problema de Sturm-Liouville. Campos potenciais gerados desta forma produzem caminhos suaves e são livres de mínimos locais. O comportamento de cada agente é determinado pela alteração de seu campo potencial individual, gerado a cada passo da simulação. Dessa forma, é possível alterar dinamicamente o padrão da trajetória e ao mesmo tempo evitar colisões com obstáculos móveis (demais agentes na simulação). Por outro lado, os comportamentos gerados podem tanto ser usados de forma isolada, como combinados em movimentos complexos. Assim, é possível utilizar funções que definem trajetórias ou quantificar um desvio à esquerda ou à direita quando o agente avista um obstáculo a sua frente. A implementação do método, incluindo técnicas para controlar a velocidade e orientação do agente, e situações de simulação como comportamentos em corredores e regiões abertas, são apresentadas e discutidas. / The simulation of pedestrians represented as virtual humans in a synthetic world is of great interest in areas as cinema, architecture and games. This activity can be defined as navigation in virtual environments and involves mainly the specification of the environment, the definition of the agent’s initial position as well as its target position in the world (also called goal). By setting these parameters, a motion planning algorithm, or a path-planning algorithm in particular can be used to find a trajectory to be followed by it. However, in a real world, if we consider several persons (all in the same initial position) trying to reach the same target position, each individual path followed will be different. That is, for the same task, the strategy used by each person to reach their goal will depend on their physical constitution (body type), personality, mood and reasoning. Taking these questions into consideration, this work presents a study about motion planning for pedestrians. As a practical result, a planner which supplies smooth and varied trajectories was developed. The trajectories are also depending on the individual characteristics of each agent, which can be dynamically changed. The method adopted is based on the use of potential fields generated by numerical solutions of boundary value problems involving the equation of Laplace (harmonic functions) and the problem of Sturm- Liouville. Potential fields generated in this manner produce smooth and local minima free trajectories. The behavior of each agent is determined by the alteration of its individual potential field which is generated to each step of the simulation. Thus, it is possible to dynamically modify the standard of the trajectory and at the same time to prevent collisions with mobile obstacles (other agents in the simulation). On the other hand, the produced behaviors can be used isolatedly or combined in complex moves. Therefore, it is possible to use a function that defines a trajectory. It is also possible to quantify a detour to the left or to the right when the agent sights an obstacle ahead. The implementation of the method, including speed control techniques and agent’s orientation, and situations like simulation of behaviors in corridors or open regions, will be presented and argued.

Encontrar um modo de criar imagens fotorealísticas tem sido uma meta da Computação Gráfica por muitos anos [GLA 89]. Neste sentido, os aspectos que possuem principal importância são a modelagem e a iluminação. Ao considerar aspectos de modelagem, a obtenção de realismo mostra-se bastante difícil quando se pretende, através de técnicas tradicionais de modelagem, modelar objetos cujas formas não são bem definidas. Dentre alguns exemplos destes tipos de objetos, podem-se citar fogo, fumaça, nuvens, água, etc. Partindo deste fato, Reeves [REE 83] introduziu uma técnica denominada sistemas de partículas para efetuar a modelagem de fogo e explosões. Um sistema de partículas pode ser visto como um conjunto de partículas que evoluem ao longo do tempo. Os procedimentos envolvidos na animação de um sistema de partículas são bastante simples. Basicamente, a cada instante de tempo, novas partículas são geradas, os atributos das partículas antigas são alterados, ou estas partículas podem ser extintas de acordo com certas regras pré-definidas. Como as partículas de um sistema são entidades dinâmicas, os sistemas de partículas são especialmente adequados para o uso em animação. Ainda, dentre as principais vantagens dos sistemas de partículas quando comparados com as técnicas tradicionais de modelagem, podem-se citar a facilidade da obtenção de efeitos sobre as partículas (como borrão de movimento), a necessidade de poucos dados para a modelagem global do fenômeno, o controle por processos estocásticos, o nível de detalhamento ajustável e a possibilidade de grande controle sobre as suas deformações. Entretanto, os sistemas de partículas possuem algumas limitações e restrições que provocaram o pouco desenvolvimento de algoritmos específicos nesta área. Dentre estas limitações, as principais são a dificuldade de obtenção de efeitos realísticos de sombra e reflexão, o alto consumo de memória e o fato dos sistemas de partículas possuírem um processo de animação específico para cada efeito que se quer modelar. Poucos trabalhos foram desenvolvidos especificamente para a solução destes problemas, sendo que a maioria se destina à modelagem de fenômenos através de sistemas de partículas. Tendo em vista tais deficiências, este trabalho apresenta métodos para as soluções destes problemas. É apresentado um método para tornar viável a integração de sistemas de partículas em ambientes de Ray Tracing, através do uso de uma grade tridimensional. Também, são apresentadas técnicas para a eliminação de efeitos de aliasing das partículas, assim como para a redução da quantidades de memória exigida para o armazenamento dos sistemas de partículas. Considerando aspectos de animação de sistemas de partículas, também é apresentado uma técnica de aceleração para a detecção de colisões entre o sistema de partículas e os objetos de uma cena, baseada no uso de uma grade pentadimensional. Aspectos relativos à implementação, tempo de processamento e fatores de aceleração são apresentados no final do trabalho, assim como as possíveis extensões futuras e trabalhos sendo realizados. / Finding a way to create photorealistic images has been a goal of Computer Graphics for many years [GLA 89]. In this sense, the aspects that have main importance are modeling and illumination. Considering aspects of modeling, the obtention of realism is very difficult when it is intended to model fuzzy objects using traditional modeling techniques. Among some examples of these types of objects, fire, smoke, clouds, water, etc. can be mentioned. With this fact in mind, Reeves [REE 83] introduced a technique named particle systems for modeling of fire and explosions. A particle system can be seen as a set of particles that evolves over time. The procedures involved in the animation of particle systems are very simple. Basically, at each time instant, new particles are generated, the attributes of the old ones are changed, or these particles can be extinguished according to predefined rules. As the particles of a system are dynamic entities, particle systems are specially suitable for use in animation. Among the main advantages of particle systems, when compared to traditional techniques, it can be mentioned the facility of obtaining effects such as motion blur over the particles, the need of few data to the global modeling of a phenomen, the control by stochastic processes, an adjustable level of detail and a great control over their deformations. However, particle systems present some limitations and restrictions that cause the little development of specific algorithms in this area. Among this limitations, the main are the difficulty of obtention of realistic effects of shadow and reflection, the high requirement of memory and the fact that particle systems need a specific animation process for each effect intended to be modeled. Few works have been developed specifically for the solution of these problems; most of them are developed for the modeling of phenomena through the use of particle systems. Keeping these deficiencies in mind, this work presents methods for solving these problems. A method is presented to make practicable the integration of particle systems and ray tracing, through the use of a third-dimensional grid. Also, a technique is presented to eliminate effects of aliasing of particles, and to reduce the amount of memory required for the storage of particle systems. Considering particle systems animation, a technique is also presented to accelerate the collision detection between particle systems and the objects of a scene, based on the use of a fifth-dimensional grid. Aspects related to the implementation, processing time and acceleration factors are presented at the end of the work, as well as the possible future extensions and ongoing works.

Segundo Thalmann em 1996, animação é a visualização da variação do estado de objetos em relação ao tempo. A meta principal da animação modelada por computador é sintetizar o efeito desejado de movimento que é uma mistura de fenômenos naturais, percepção e imaginação. O sistema de animação deve providenciar ferramentas de controle de movimento para traduzir os desejos do usuário na linguagem do sistema. O controle dos movimentos de uma animação pode ser dividido em duas classes de algoritmos: a classe intencional, dirigida aos aspectos de controle em alto nível, onde as intenções de uma animação são expressas e a classe concreta, dirigida aos aspectos específicos de animação de objetos. A relação hierárquica destas classes favorece a implementação de um motor de animação usando camadas de abstração. Uma das abordagens atuais para a construção de um motor de animação para atores humanóides é um sistema implementado em camadas. A camada inferior lida com os movimentos individuais das articulações. As intermediárias são responsáveis por encapsular conjuntos de movimentos que atuam como tarefas simples. O encapsulamento destas tarefas é feito por camadas superiores que lidam com ações sensíveis ao ambiente. Por fim, a camada de mais alto nível atua no nível cognitivo onde um mecanismo dotado de capacidade de raciocínio comanda ações aos atores de acordo com as informações do contexto e também de acordo com as intenções, crenças e desejos dos atores. Este trabalho visa analisar uma proposta de implementação de um motor de animação para simular o comportamento de atores humanóides, gerando animações em três dimensões via World Wide Web. Dois modelos de animação baseados no formalismo AFS (Autômato Finito com Saída) que lidam com camadas específicas de abstração de um sistema de animação serão apresentados. O modelo AGA-J é uma extensão do modelo AGA para lidar com a classe concreta de movimentos de atores humanóides em 3D e serve como camada de fundação para outros modelos. O modelo AGA gera sequências animadas a partir de um conjunto de AFS que representam os atores da animação e um conjunto de fitas de entrada que determinam os comportamentos dos atores. O alfabeto de saída é representado por imagens e efeitos sonoros e a animação se dá pela sequência das saídas dos autômatos. O modelo AGA-T é um modelo orientado a tarefas, baseado em autômatos probabilísticos e eventos. Este modelo atua como uma camada de nível superior sobre o AGA-J, e foi projetado para lidar com alguns aspectos da classe intencional, sobretudo o encapsulamento de movimentos através de tarefas. O formalismo de AFS foi escolhido para a construção dos modelos porque propicia muitas características importantes: saída configurável através da análise da fita de saída; reusabilidade pelo fato de vários atores poderem usar o mesmo AFS; e recuperação de informação, observando o estado atual dos autômatos dos atores que compõem a animação. / According to Thalmann in 1996, animation is the visualization of changings on object states during time. The first goal of computer animation is to synthesize the desired motion effect that is a mix of natural phenomena, perception and imagination. An animation system must provide motion control tools to translate the user intentions into the system language. The motion control can be divided in two classes of algorithms: the intentional class, directed towards the high-level control aspects where the animation intentions are expressed; and the concrete class, which deals with specific aspects of object animation. The hierarchical relationship between these two classes benefits the implementation of an animation engine based on abstraction layers. One recent approach for building an animation engine to represent humanoid actors is a system implemented in layers. The lowest layer deals with individual joint movements, while the middle layers are responsible for encapsulating a set of movements acting as simple tasks. The task encapsulation is performed by high-level layers dealing with environment sensitive actions. Finally, the highest-level layer acts in the cognitive level, where a reasoning mechanism commands actions to the actors according to the context information, the beliefs, desires and intentions of the actors. This work explores an implementation proposal of an animation engine for simulating the behavior of humanoid actors, generating 3D animations to theWorld Wide Web. Two animation models based on the Finite Automata with Output formalism that deal with specific abstraction layers of an animation system will be presented. The AGA-J model is an extension of the AGA model for dealing with the concrete class of 3D movements of humanoid actors and it suits as a foundation layer for other models. The AGA model generates animated sequences by a set of Finite Automata with Output that implements the animation actors and a set of input tapes which determines the behavior of the actors. The output alphabet is represented by images, and sound effects, and the animation is produced by the sequence of the automata output. The AGA-T model is a task-oriented model, based on probabilistic automata and events. This model acts as a high-level layer over the AGA-J, and it was designed for dealing with some aspects of the intentional class, mainly the movement encapsulation by tasks. The Finite Automata with Output formalism was chosen for model construction because it provides many important features: adaptable output by analysis of output tape; reusability by the fact of many actors can use the same automaton; and information retrieval by observation of current state of the automata composing the animation.

O processo de parametrização de malhas em planos é um tópico de pesquisa bastante explorado. Apesar do grande esforço despendido no desenvolvimento de técnicas mais eficientes e robustas, pouco se tem investido no uso das representações paramétricas geradas por estas técnicas. Este trabalho apresenta contribuições relacionadas ao uso do espaço paramétrico para computações eficientes. A principal motivação vem do fato de alguns algoritmos serem mais eficientes quando aplicados sobre a versão paramétrica da malha. Algoritmos para o cálculo de distância mínima, por exemplo, podem ter um aumento significativo de eficiência quando aplicados em versões paramétricas de malhas. Nossos resultados demonstram que esses aumentos de eficiência podem chegar a cerca de uma ordem de magnitude em alguns casos. As contribuições deste trabalho possuem aplicação direta em três campos de pesquisa relacionados à computação gráfica: displacement mapping, cálculo de distâncias sobre superfícies e movimentação de agentes. A contribuição relacionada a displacement mapping, apresentada no capítulo 4, é utilizada para aumentar a performance de renderização e a qualidade visual de terrenos em jogos. O novo método de cálculo de distâncias proposto, apresentado no capítulo 5, aumenta a eficiência de vários algoritmos de cálculo de distância sobre superfícies de malhas. Este novo método também é utilizado em uma nova técnica para cálculo de movimentação de agentes em superfícies de malhas arbitrárias. Esta técnica é apresentada no capítulo 6. O potencial da nova técnica de cálculo de distância sobre malhas não está restrito aos exemplos apresentados. Em geral, qualquer técnica que utilize o cálculo de distância sobre superfícies de malhas de triângulos se beneficia das contribuições deste trabalho, podendo-se citar como exemplos a geração de texturas procedurais, rotulamento de superfícies, re-triangulação de malhas e segmentação de malhas, entre outros. / The process of parameterizing a mesh to the plane is an ongoing research topic. Although there are several works dedicated to parameterization techniques the use of the resulting parameterizations has received less attention. This work presents contributions related to the use of the parametric space to improve the computational efficiency of several algorithms. The main motivation comes from the fact that some algorithms are more efficiently computed on the parametric version of the mesh, compared to the 3-D version. For example, shortest distances can be computed, usually, an order of magnitude faster on the parametric space. The contributions of this work can be applied to at least three research fields related to computer graphics: displacement mapping, distance computation on the surface of triangular meshes and agent path planning. The contribution related to displacement mapping, presented in chapter 4, is used to increase the rendering performance and visual quality of terrains in games. The new method to compute distances, presented in chapter 5, increases the efficiency of several distance computation algorithms. This new method was also used on a novel agent path planning algorithm, to navigate agents on the surface of arbitrary meshes. This technique is presented in chapter 6. The potential of the new distance computation method is not restricted to the applications presented in this thesis. In general, any technique that uses distance computation on the surface of triangular meshes can have the performance improved by the method. We can cite the following applications: procedural texture generation, surface labeling, re-meshing, mesh segmentation, etc.

Este trabalho aplica a Teoria de Autômatos na proposição de uma nova alternativa para prover animações 2D na World Wide Web, verificando as contribuições alcançadas para as questões relacionadas ao espaço de armazenamento, reutilização e manutenção do conteúdo e suporte à recuperação de informação. Para este objetivo, é proposto o modelo AGA (Animação Gráfica baseada em Autômatos Finitos), o qual especifica a animação a partir de uma estrutura baseada em autômatos finitos com saída. Esse modelo é definido de tal forma que os mesmos autômatos utilizados na especificação, ao serem simulados, realizam o controle da animação durante a apresentação. O modelo AGA apresenta características que favorecem a redução do espaço de armazenamento da animação, provêem suporte à recuperação de informação, colaboram com a reutilização e manutenção do conteúdo das animações. Uma implementação multiplataforma foi desenvolvida para apresentar animações especificadas nesse modelo na Web. Essa implementação proporciona a elaboração de consultas ao conteúdo da animação, além dos recursos tradicionais de reprodução. A partir dessa implementação, o AGA foi submetido a um estudo de caso prático, onde os resultados obtidos são comparados com o produzidos pelo GIF (Graphic Interchange Format). Esse comparativo demonstra que o AGA possui várias vantagens em relação à estrutura adotada pelo GIF. O modelo AGA é estendido utilizando autômatos temporizados para prover restrições temporais às especificações e também ampliar as funcionalidades de interação com o observador da animação. Essa extensão, chamada de modelo AGA-S (Animação Gráfica baseada em Autômatos Temporizados Sincronizados), é definida a partir do autômato temporizado proposto por Alur e Dill. Para esse modelo, é definida uma operação formal para sincronização dos componentes da animação e adicionada uma estrutura baseada em autômatos finitos para controlar a interação do observador com a animação.