A iluminação indireta é capaz de elevar consideravelmente a qualidade visual de cenas renderizadas, mas é também uma operação custosa. Por este motivo, há muito esforço de pesquisa voltado para a renderização de iluminação indireta em tempo real. Apesar de atualmente existirem técnicas poderosas para a iluminação indireta em tempo real, elas fornecem ao artista apenas um controle grosseiro do equilíbrio entre qualidade e desempenho. Nós propomos uma Malha de Luzes Virtuais para calcular a iluminação indireta difusa numa cena, inspirados pelo uso de outras malhas auxiliares, como Malhas de Navegação e Malhas de Colisão. Uma Malha de Luzes Virtuais (MLV) é uma malha simplificada de luzes poligonais usadas para aproximar a luz refletida pela geometria real. Juntamente com a MLV, nós projetamos uma estrutura de dados de aceleração para atingir um desempenho eficiente com iluminação indireta usando uma MLV complexa. O uso da MLV apresenta algumas características vantajosas: maior controle artístico dos atributos da iluminação indireta; a possibilidade de integração com técnicas existentes como animação esquelética e geração procedural; e integração simples com ferramentas e processos de produção de arte existentes. Nossos resultados experimentais mostram que a iluminação indireta controlada por artistas é uma alternativa viável a métodos existentes. / Indirect illumination on a rendered scene can add a great deal to its visual quality, but it is also a costly operation. Therefore, a lot of research targets how to render indirect illumination in real-time. While powerful techniques for real-time indirect illumination currently exist, they provide only coarse-grained artistic control over the trade-off between quality and speed. We propose a Virtual Light Mesh to compute the scene’s diffuse indirect illumination, inspired by the use of other current auxiliary meshes such as Navigation Meshes and Collision Meshes. A Virtual Light Mesh (VLM) is a simplified mesh of polygonal lights used to approximate the light bounced by the real geometry. Together with the VLM, we design an acceleration data structure for efficient indirect illumination performance with a complex VLM. The use of VLM presents some positive properties: greater artistic control of the indirect illumination characteristics; the possibility of integration with existing techniques such as skeletal animation and procedural generation; and simple integration into existing asset production tools and pipelines. Our experimental results show that artist controlled indirect illumination is a viable alternative to existing methods.

Uma interface com o usuário é composta por duas "vias" de comunicação, uma que vai do usuário até o sistema e outra que vai do sistema até o usuário. Cada uma destas "vias" possui um formalismo que define a comunicação associado. Neste trabalho, estes formalismos são descritos com uma gramática de atributos. Esta gramática foi expandida de forma a permitir a definição dos elementos que compõe a interface do usuário, e da estrutura que irá controlar a seqüência de execução das tarefas oferecidas pelos sistemas de aplicação. Ao longo do trabalho são discutidas algumas técnicas de descrição do formalismo de comunicação entre interface e sistema, são abordados os estilos de interação e apresentada as expansões aplicadas sobre gramáticas de atributos. Um exemplo auxilia a compreensão do uso da linguagem proposta, e um protótipo permite a validação das definições. / A user interface is composed by two "ways" of communication, one from the user to the system and the other linking the system to the user. Each of these "ways" has it's own mechanism. In this work, these mechanisms are described through an attribute grammar. This grammar has been expanded to allow the definition of the structure of the interface elements and the control of the execution of the tasks that the application system implements. Through this work, technics that describe the communication between the interface and the system, interaction styles and the extensions made on attribute grammar are discussed. An example is given to explain the use of the proposed mechanism and a prototype validates ideas discussed.

Este trabalho descreve um conjunto de técnicas para a recuperação de imagens baseada nos aspectos cromático e estrutural das mesmas. A abordagem aqui descrita utiliza mecanismos que permitem a preservação de informação espacial referente aos conteúdos extraídos da imagem de forma que a sua precisão possa ser ajustada de acordo com a necessidade da consulta. Um outro importante aspecto aqui considerado, é a possibilidade de se optar por um dos seguintes espaços de cores para a verificação de distâncias entre cores no momento da recuperação: RGB, L*u*v*, ou L*a*b*. Com estas diferentes possibilidades de espaços de cores, será verificada a influência que os mesmos podem provocar no processo de recuperação de imagens baseado em aspectos cromáticos. O conjunto de técnicas para a recuperação de imagens abordadas neste trabalho levou à construção do sistema RICE, um ambiente computacional através do qual pode-se realizar consultas a partir de um repositório de imagens. Para a verificação do desempenho dos diferentes parâmetros ajustáveis na recuperação de imagens aqui descrita e implementada no sistema RICE, foram utilizadas curvas de “Recall x Precision”. / This work describes a set of image retrieval techniques by color and shape similarity. The approach presented here allows to preserve spacial relantionships of the contents extracted from the image. And it can be adjusted accordingly to the query needs. Another important feature considered here, is the possibility of choosing between the RGB, L*u*v*, and L*a*b* color spaces to compute color distances during the image retrieval operation. With these three options of color spaces, the influence of each one in the image retrieval process based in chromatic contents will be verified. The set of techniques for image retrieval described here led to development of the RICE system, a computational environment for image retrieval by color and shape similarity. Furthermore, the recall x precision graph was applied in order to verify the performance of the RICE system in several configuration modes of image retrieval.

Este trabalho descreve uma técnica para a implementação de mesas digitalizadoras de alta resolução. Inicialmente é examinado o princípio de funcionamento das mesas digitalizadoras capacitivas, sendo, a seguir, detalhadas as principais causas de erros. Os resultados apresentados foram obtidos através da construção de um protótipo de baixa resolução e de programas de simulação. / This work describes a technique for implementing high resolution digitizers and tablets. Firstly, the operating principle of capacitive digitizers is examined, and, then, the main causes of errors are discussed in detail. The results shown were obtained through the implementation of low resolution prototype and simulating programs.

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.

O rastreamento de objetos em vídeos representa um importante problema na área de processamento de imagens, quer seja pelo grande número de aplicações envolvidas, ou pelo grau de complexidade que pode ser apresentado. Como exemplo de aplicações, podemos citar sua utilização em áreas como robótica móvel, interface homem-máquina, medicina, automação de processo industriais até aplicações mais tracionais como vigilância e monitoramento de trafego. O aumento na complexidade do rastreamento se deve principalmente a interação do objeto rastreado com outros elementos da cena do vídeo, especialmente nos casos de oclusões parciais ou totais. Quando uma oclusão ocorre a informação sobre a localização do objeto durante o rastreamento é perdida parcial ou totalmente. Métodos de filtragem estocástica, utilizados para o rastreamento de objetos, como os Filtros de Partículas não apresentam resultados satisfatórios na presença de oclusões totais, onde temos uma descontinuidade na trajetória do objeto. Portanto torna-se necessário o desenvolvimento de métodos específicos para tratar o problema de oclusão total. Nesse trabalho, nós desenvolvemos uma abordagem para tratar o problema de oclusão total no rastreamento de objetos utilizando Filtro de Partículas baseados em Monte Carlo via Cadeia de Markov (MCCM) com função geradora de partículas adaptativa. Durante o rastreamento do objeto, em situações onde não há oclusões, nós utilizamos uma função de probabilidade geradora simétrica. Entretanto, quando uma oclusão total, ou seja, uma descontinuidade na trajetória é detectada, a função geradora torna-se assimétrica, criando um termo de “inércia” ou “arraste” na direção do deslocamento do objeto. Ao sair da oclusão, o objeto é novamente encontrado e a função geradora volta a ser simétrica novamente. / The object tracking on video is an important task in image processing area either for the great number of involved applications, or for the degree of complexity that can be presented. How example of application, we can cite its use from robotic area, machine-man interface, medicine, automation of industry process to vigilance and traffic control applications. The increase of complexity of tracking is occasioned principally by interaction of tracking object with other objects on video, specially when total or partial occlusions occurs. When a occlusion occur the information about the localization of tracking object is lost partially or totally. Stochastic filtering methods, like Particle Filter do not have satisfactory results in the presence of total occlusions. Total occlusion can be understood like discontinuity in the object trajectory. Therefore is necessary to develop specific method to handle the total occlusion task. In this work, we develop an approach to handle the total occlusion task using MCMC-Particle Filter with adaptive sampling probability function. When there is not occlusions we use a symmetric probability function to sample the particles. However, when there is a total occlusion, a discontinuity in the trajectory is detected, and the probability sampling function becomes asymmetric. This break of symmetry creates a “drift” or “inertial” term in object shift direction. When the tracking object becomes visible (after the occlusion) it is found again and the sampling function come back to be symmetric.

Nos últimos anos a utilização de pontos como primitiva gráfica básica vem mostrandose uma poderosa e versátil ferramenta para a computação gráfica. Considerável esforço de pesquisa vem sendo dedicado para encontrar formas eficientes de aquisição, representação, processamento, renderização e animação para conjuntos de pontos. As representações baseadas em pontos têm-se destacado como uma estratégia eficiente em computação desde que se tornou comum extrair modelos geométricos a partir de Scanners 3D, os quais geram grandes quantidades de pontos que aproximam a geometria do objeto. Este trabalho apresenta um conjunto de métodos para tratar a visibilidade aproximada para nuvens de pontos sem informação de conectividade e topologia. Primeiramente é proposto uma abordagem baseada em clusters para acelerar o operador de remoção de pontos proposto por Katz et al. A principal motivação para esta otimização é a possibilidade de conseguir um equilíbrio entre a velocidade e a qualidade do resultado. Também é apresentado uma técnica de renderização baseada em pontos acelerada por hardware chamada Surface Splatting. Esta abordagem utiliza mapeamento de textura com alpha blending para aproximar um filtro de reamostragem Elliptical Weighted Average no espaço de objeto. Juntamente com o Geometry Shader das modernas placas gráficas, produz de forma eficiente imagens de alta qualidade de superfícies amostradas por surfels. Por último é proposto um novo operador de remoção de pontos ocultos acelerado por hardware baseados na técnica de splatting juntamente com um operador morfológico de erosão modificado para reduzir o efeito de silhuetas no resultado final do operador. A motivação para a criação deste novo operador é a baixa eficiência demonstrada pelos métodos existentes para a utilização em aplicações em tempo real onde as nuvens de pontos são muito densas. Todas as técnicas apresentadas neste trabalho podem ser utilizadas em visualização científica com taxas interativas, em particular na visualização direta de geometria baseada em pontos. / In recent years the use of points as a fundamental graphics primitive has proved to be a powerful and versatile tool for computer graphics. Considerable research has been devoted to the efficient representation, modeling, processing, rendering and animation of point-sampled geometry. The point-based representation has gained increasing attention in computer graphics because 3D scanning systems easily extract large information from real-world objects. On the other hand, point sets are more flexible when compared to triangle meshes, because they are not required to maintain consistent topological information. This work presents a set of tools to determine the visibility and also to render a point-based geometry efficiently. Firstly, a cluster-based approach is proposed to speed up the hidden point removal operator proposed by Katz et al. The main idea of this study is to trade-off speed and quality in dynamic scenes of moving or deforming point clouds. After that, a hardware based point rendering technique called Surface Splatting is introduced. This approach uses the texture mapping with alpha blending and the Geometry Shader to approximate the Elliptical Weighted Average filter in object space. This efficient technique produces high quality images as surfel-based geometry. Finally, a new hidden point removal operator is presented. This operator, based on the splatting technique and also hardware accelerated, applies a morphological erosion operation in the depth buffer to reduce the silhouette effect in the final image. The motivation to develop a new operator is the low efficiency demonstrated by existing hidden point removal methods in real time applications, where the point cloud is very dense. All the techniques introduced in this work can be used in scientific visualization with interactive frame rates, particularly when visualizing point-based geometry sets.

Malhas simpliciais são utilizadas em várias áreas da Computação Gráfica e Engenharia, como por exemplo, em vizualização, simulação, prototipação, além de outras aplicações. Este tipo de malha é, geralmente, utilizada como aproximações discretas de espaços contínuos, onde eles oferecem representações flexíveis e eficientes. Muito esforço é gasto visando gerar malhas de boa qualidade, porém, em alguns casos as malhas acabam sendo modificadas. Entretanto, este tipo de operação é geralmente custosa e inflexível, o que pode resultar na geraão de malhas bem diferentes das originais. A habilidade de manipular cenas dinâmicas revela-se um dos problemas mais desafiadores da computação gráfica. Este trabalho propõe um método alternativo para atualizar malhas simpliciais que vai além de mudanças geométricas e topológicas. Tal método explora uma das propriedade das Tringulações de Delaunay com Pesos, que permite a usá-las para definir implicitamente as relações de conectividade de uma malha. Ao contrário de manter as informações de conectividade explicitamente, a atual abordagem simplesmente armazena uma coleção de pesos associados a cada vértice. Além disso, criamos um algoritmo para calcular uma Tringulação de Delaunay com Pesos a partir de uma dada triangulação. O algoritmo consiste em uma busca em largura que atribui pesos aos vértices, e uma estratégia de de subdivisão para assegurar que a triangulação reconstruída será correspondente à original. Este método apresenta diversas aplicações e, em particular, permite a criação de um sistema simples de realizar combinação entre triangulações, que será ilustrada com exemplos em 2D e 3D. / Simplicial meshes are used in many fields of Computer Graphics and Engineering, for instance, in visualization, simulation, prototyping, among other applications. This kind of mesh is often used as discrete approximations of continuous spaces, where they offer flexible and efficient representations. Considerable effort is spent in generating good quality meshes, but in some applications the meshes can be modified over time. However, this kind of operation is often very expensive and inflexible, sometimes leading to results very different from the original meshes. The ability to handle dynamic scenes reveals itself as one of the most challenging problems in computer graphics. This work proposes an alternative technique for updating simplicial meshes that undergo geometric and topological changes. It explores the property that a Weighted Delaunay Triangulation (WDT) can be used to implicitly define the connectivity of a mesh. Instead of explicitly maintaining connectivity information, this approach simply keeps a collection of weights associated to each vertex. It consists of an algorithm to compute a WDT from any given triangulation, which relies on a breadth-first traversal to assign weights to vertices, and a subdivision strategy to ensure that the reconstructed triangulation conforms with the original one. This technique has many applications and, in particular, it allows for a very simple method of merging triangulations, which is illustrated with both 2D and 3d examples.

Métodos tradicionais de animação de fluidos têm dificuldade em resolver escoamentos que envolvem aberturas estreitas e geometrias finas. Abordagens anteriores artificialmente inflaram ou voxelizaram geometrias de objetos finos, sacrificando a geometria e topologias corretas do domínio de simulação, impedindo que o escoamento interaja corretamente com regiões estreitas. No trabalho desenvolvido, apresentamos uma técnica de simulação de fluidos que respeita geometrias complexas de maneira precisa e supera obstáculos comuns em ambientes com aberturas estreitas e geometrias finas. A nossa solução baseia-se no recorte preciso de células do grid regular, gerando uma malha conformal à geometria e topologicamente correta. Nós utilizamos uma abordagem de bordas incorporadas (cut-cells): em cada passo do tempo, a malha de triângulos representando a superfície sólida de um objeto no domínio de simulação é recortada pelas células que intercepta, potencialmente gerando múltiplas sub-células distintas. A malha resultante é conformal ao objeto incorporado e se reduz ao grid regular em regiões que não estão em contato com a superfície. Nós estendemos as abordagens tradicionais de advecção de velocidade e projeção da pressão para dar suporte a essa estrutura de malha aprimorada. Em geral, nossa abordagem é capaz de representar melhor detalhes de geometrias que são menores que uma célula do grid, corretamente recuperando condições de contorno no-slip e free-slip, enquanto mantém uma convergência para a solução da pressão de segunda ordem no espaço. Para melhorar a advecção em regiões próximas às bordas irregulares, introduzimos um método de interpolação que funciona em células poliédricas arbitrárias, utilizando-se do método de interpolação spherical barycentric coordinates (SBC). Essa abordagem possibilita que as linhas características do escoamento respeitem a geometria sem penetrá-la, em contraste com métodos tradicionais de interpolação lineares ou cúbicos. Finalmente, nós melhoramos os métodos de advecção com um método FLIP modificado. Nosso método resolve uma dificuldade inerente a advecção Semi-Lagrangiana no contexto de geometrias deslocando-se através do domínio de simulação: as células que são varridas por sólidos em locomoção perdem sua informação de velocidade e tem de ser preenchidas com velocidades extrapoladas de células vizinhas. Nosso esquema FLIP garante que a informação de velocidade viaje corretamente com as superfícies, não necessitando de nenhum método de extrapolação. / Fluid animation methods based on Eulerian grids have long struggled to resolve flows involving narrow gaps and thin solid features. Past approaches have artificially inflated or voxelized boundaries, although this sacrifices the correct geometry and topology of the fluid domain and prevents flow through narrow regions. We present a boundary-respecting fluid simulator that overcomes these challenges. Our solution is to intersect the solid boundary geometry with the cells of a background regular grid to generate a topologically correct, boundary-conforming cut-cell mesh. We extend both pressure projection and velocity advection to support this enhanced grid structure. For pressure projection, we introduce a general graph-based scheme that properly preserves discrete incompressibility even in thin and topologically complex flow regions, while nevertheless yielding symmetric positive definite linear systems. For advection, we exploit polyhedral interpolation to improve the degree to which the flow conforms to irregular and possibly non-convex cell boundaries, and propose a modified PIC/FLIP advection scheme to eliminate the need to inaccurately reinitialize invalid cells that are swept over by moving boundaries. The method naturally extends the standard Eulerian fluid simulation framework, and while we focus on thin boundaries, our contributions are beneficial for volumetric solids as well. Our results demonstrate successful one-way fluid-solid coupling in the presence of thin objects and narrow flow regions even on very coarse grids.

A enorme quantidade de trajetórias contendo múltiplas dimensões, e o aumento de complexidade que esses dados ocasionam, impõem desafios ao visualizar e analisar estas informações. Visualização de Trajetórias deve lidar com alterações tanto na dimensão de espaço quanto na dimensão de tempo. Porém, os atributos de cada trajetória podem ocasionar uma melhor compreensão sobre seus comportamentos e características. Dessa forma, eles não deveriam ser neglicenciados. Neste trabalho, nós abordamos este problema interpretando séries temporais multivariadas com foco nos atributos das trajetórias, em um espaço de configuração que codifica um explícito relacionamento entre as variáveis das séries temporais. Nós propomos uma técnica original de clusterização de trajetórias, chamada Attribute Field k-means (AFKM). Ela usa um espaço de configuração dinâmica para gerar clusters baseados nos atributos e parâmetros definidos pelo usuário. Além disso, incorporando uma interface de sketching, nosso método é capaz de encontrar clusters que aproximam os exemplos de trajetórias desenhados pelo usuário. Nós também desenvolvemos um protótipo para explorar as trajetórias e clusters gerados pelo AFKM, de um modo interativo. Nossos resultados, em sintéticos e reais conjuntos de dados de séries temporais, provam a eficiência e o poder de visualização do nosso método. / The amount of high-dimensional trajectory data and its increasing complexity imposes a challenge when visualizing and analysing this information. Trajectory Visualization must deal with changes both in space and time dimensions, but the attributes of each trajectory may provide insights about its behavior and important aspects. Thus, they should not be neglected. In this work, we tackle this problem by interpreting multivariate time series as attribute-rich trajectories in a configuration space that encodes an explicit relationship among the time series variables. We propose a novel trajectory-clustering technique called Attribute Field k-means (AFKM). It uses a dynamic configuration space to generate clusters based on attributes and parameters set by the user. Furthermore, by incorporating a sketching-based interface, our approach is capable of finding clusters that approximates the input sketches. In addiction, we developed a prototype to explore the trajectories and clusters generated by AFKM in an interactive manner. Our results on synthetic and real time series datasets prove the efficiency and visualization power of our approach.