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.

Este trabalho apresenta uma análise dos principais algoritmos de poligonização de isosuperfícies na GPU. O resultado desta análise mostra tanto como a GPU pode ser modificada para oferecer suporte a este tipo de algoritmo quanto como os algoritmos podem ser modificados para se adaptar as características das GPUs atuais. As técnicas usadas em versões de GPU do Marching Cubes são extendidas e uma poligonização com menos artefatos é gerada. São propostas versões paralelas do Dual Contouring e do Macet, algoritmos que melhoram a aproximação e a forma das malhas de triângulos, respectivamente. Ambas técnicas extraem isosuperfícies a partir de grandes volumes de dados em menos de um segundo, superando versões de CPU em até duas ordens de grandeza. As contribuições desse trabalho incluem uma versão orientada a tabelas do Dual Contouring (DC) para grids estruturados. A tabela é utilizada na especificação da topologia dos quadriláteros, que ajuda a implementação e a eficiência de cache em cenários paralelos. A tabela é adequada para a expansão de streams na GPU em ambos geometry shader e Histogram Pyramids. Além disso, nossa versão de aproximação de características das isosuperfícies é mais simples que a Decomposição de Valores Singulares e também que a Decomposição QR. O posicionamento dos vértices não requer uma diagonalização de matrizes. Ao invés disso, usa-se uma simples interpolação trilinear. Afim de avaliar a eficiência das técnicas apresentadas neste trabalho, comparamos nossas técnicas com versões do Marching Cubes na GPU do estado da arte. Também incluímos uma análise detalhada da arquitetura de GPU para a extração de isosuperfícies, usando ferramentas de avaliação de desempenho da indústria. Essa análise apresenta os gargalos das placas gráficas na extração de isosuperfícies e ajuda na avaliação de possíveis soluções para as GPUs das próximas gerações.

Orientador: Celso Setsuo Kurashima. / Dissertação (mestrado) - Universidade Federal do ABC. Programa de Pós-Graduação em Engenharia de Informação.

Orientador: Aluir Porfírio Dal Poz / Resumo: A aquisição de informações espaciais é uma das tarefas mais dispendiosa e morosa na implantação e na manutenção de Sistemas de informação Geográfica (SIG's). Nos últimos 30 anos, inúmeras pesquisas foram realizadas objetivando o melhoramento do tempo e custo da aquisição de dados espaciais. No que se refere a aquisição de dados espaciais a partir de imagens digitais, é possível notar que os métodos desenvolvidos até então estão mais próximos desta meta quando os respectivos níveis de automação são mais altos. Como as soluções totalmente automáticas não estão ainda no mesmo nível de confiabilidade dos métodos manuais, soluções semi-automáticas combinando a habilidade natural de operadores humanos em tarefas de reconhecimento e a capacidade de algoritmos computacionais em realizar tarefas de medidas precisas e morosas, têm sido propostas. Seguindo esta tendência, este trabalho propõe uma metodologia semi-automática para a extração de rodovias em imagens digitais de média e alta resolução baseada no algoritmo de otimização global de programação dinâmica. É importante enfatizar que os trabalhos relacionados com extração de feições através de programação dinâmica sempre usam imagens de baixa resolução, na qual as rodovias manifestam-se como estruturas lineares. Ao contrário, rodovias em imagens de média e alta resolução se manifestam como faixas alongadas. Assim, como neste caso o objetivo básico é extrair o eixo da rodovia, este trabalho propõe uma modificação na função custo usada numa metodologia preexistente baseada em programação dinâmica, permitindo que o eixo central da rodovia seja precisamente extraído pela metodologia modificada. A diferença básica entre este método modificado e o original é uma função de injunção, proposta com o objetivo de incorporar características de bordas de rodovia...(Resumo completo, clicar acesso eletrônico abaixo) / Abstract: The acquisition of spatial information is one of most expensive and time consuming tasks in developing and maintaining Geographical Information Systems (GIS's). In the last 30 years, countless researches have been accomplished aiming at improvement of spatial data acquisition time and cost. Related to the spatial data acquisition from digital images, it is possible to notice that the methods developed until now are closer to that goal when the respective levels of automation are higher. As fully automatic solutions are not in same level of reliability of manual procedures, semi-automatic solutions combining the natural skill of humans operators in recognizing tasks and the power of computational algorithm in carrying out precise and time consuming measurement tasks, have been proposed. Following this trend, this work proposes a semi-automatic methodology for road extraction from mediumand high-resolution digital images based on the global optimization algorithm of dynamic programming. It is important to emphasize that related works on feature extraction by dynamic programming always use low-resolution images, in which roads manifest as linear structures. As opposed to this, roads in medium- and high-resolution manifest as elongated regions. Thus, as in this case the basic objective is to extract the road centerline, this work proposes a modification of cost function used in a preexisting dynamic programming approach, allowing the road centerline to be precisely extracted by the modified method. The basic difference between this modified method and the original one is the proposed constraint function embodying some road edge characteristics, as e.g. the anti-parallelism of gradient vectors at two pixels situated on opposite road edges and belonged to the same road crosssection...(Complete abstract click electronic access below) / Mestre

Submitted by Erika Demachki (erikademachki@gmail.com) on 2014-08-28T17:16:10Z No. of bitstreams: 2 A importância das matrizes e transformações lineares na computação gráfica.pdf: 7639607 bytes, checksum: 2c9e545bdc634d88ba4a2b09d95c3c62 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2014-08-28T17:16:10Z (GMT). No. of bitstreams: 2 A importância das matrizes e transformações lineares na computação gráfica.pdf: 7639607 bytes, checksum: 2c9e545bdc634d88ba4a2b09d95c3c62 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2013-03-22 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / Linear algebra and in particular the theory of matrices and the theory of linear transformations are areas of mathematics that can be applied not only within the mathematics, but also in many other areas of human knowledge, such as physics, chemistry, biology, all engineering, computing, economics, etc... We present examples through the importance of the matrices and linear transformations in the theory of graphic computation. / A álgebra linear e, em particular a teoria das matrizes e a teoria das transforma ções lineares são áreas da matemática que podem ser aplicadas não só dentro da própria matemática, mas também em várias outras áreas do conhecimento humano, como física, química, biologia, todas as engenharias, computação, economia, etc. Neste trabalho apresentamos através de alguns exemplos, a importância das matrizes e das transformações lineares na teoria da computação grá ca.