[pt] Diversas aplicações, em matemática, computação gráfica, medicina, geofísica e outras áreas, têm explorado a representação de sólidos por superfícies de contorno, em particular malhas poligonais. As malhas podem aproximar com muita precisão as propriedades geométricas da superfície de contorno de um sólido e ainda guardar importantes propriedades topológicas das superfícies como gênero, bordo e conexidade. Devido à grande complexidade dessas malhas, elas são geralmente processadas em meios computacionais usando alguma estrutura de dados. Essas estruturas guardam, além da geometria da malha, informações de incidências e adjacências entre os elementos da malha e exigem uma capacidade de armazenamento e processamento em função da complexidade da malha. Apesar da evolução dos recursos computacionais disponíveis para a manipulação destas estruturas, malhas extremamente complexas com milhões de elementos inviabilizam o armazenamento, processamento e transmissão de sua estrutura de dados nos meios computacionais. Muitas pesquisas recentes estão voltadas para a obtenção de processos de simplificação de malhas que permitam representar a mesma superfície com menos elementos na estrutura de dados e processos de compressão que codifiquem os modelos em formatos menores para efeitos de transmissão e armazenamento em mídia. Neste trabalho, desenvolvemos operadores, em uma estrutura de dados compacta, para a simplificação de malhas através da decimação de células da superfície. Objetivamos, com esses operadores, obter uma malha menos complexa que preserve as propriedades topológicas da superfície original e ainda, controlar as propriedades geométricas como volume, área e aspecto visual da mesma. Apresentamos ainda algumas aplicações para os processos de simplificação desenvolvidos com esses operadores. / [en] Many applications, in mathematics, computer graphics, medical imaging, geophysics and others, have used the representation of solids by their boundary surface, usually polygonal meshes. Those meshes can represent, with high precision, the geometric properties of the boundary surface of solid and also store important topological surface properties as genus, boundary and connected components. Because of the high complexity of such meshes, they are usually processed by the computers using specific data structures. These structures store, beyond the mesh geometry, information about incidence and adjacency relations among the mesh elements. They require computational resources for storage and processing according to the mesh complexity. Even with the development of the computational resources available for handling such structures, very large meshes with millions of elements are hard to store, to process and to exchange through the web. Many recent researches are looking for mesh simplification process that allows to represent the same surface with fewer elements and compression process to encode it in compact ways for transmition and storage. In this work, we develop topological operators, in a concise data structure, for simplifying meshes by the decimation of its cells. One of our goals, with these operators, is to obtain a mesh with a low complexity that preserves the topological properties from the original surface without loosing the control of the geometric proprieties as volume, area and visual aspect.

[pt] Este trabalho tem por objetivo estudar algoritmos para a obtenção de representações simplificadas para modelos de terreno. Dados de terreno são considerados de difícil tratamento devido à sua complexidade e dimensão. Uma das técnicas mais utilizadas para amenizar a complexidade dos dados de terreno são os métodos de simplificação de superfícies. Dentre os vários métodos de simplificação de superfícies, os que têm fornecido melhores resultados são os métodos de simplificação por inserção gulosa baseada no erro vertical local. Apesar de suas qualidades, percebemos algumas falhas na qualidade perceptual das soluções fornecidas por este método quando aplicado a dados de terreno com regiões nas quais as altitudes apresentam diferentes graus de variabilidade. Neste trabalho investigamos a existência de métodos melhores para abordagem deste problema. Propomos métodos de inserção gulosa que utilizem critérios de seleção em que o erro vertical local seja modificado de acordo com a variabilidade da superfície.

[pt] O presente trabalho visa integrar a representação gráfica de dados vetoriais encontrados em Sistemas de Informação Geográfica (SIG) com a visualização de modelos tridimensionais de terrenos em multi-resolução. A multiresolução do terreno implica em dificuldades para a renderização dos dados vetoriais de forma coerente, uma vez que estes dados, em geral, só armazenam informações bi-dimensionais. As soluções mais comumente empregadas usam mapeamento convencional de texturas, trazendo uma qualidade visual baixa. Para melhorar a qualidade da imagem gerada, adotamos o mapeamento de textura com correção perspectiva, similar ao que tem sido empregado para geração de mapas de sombras. Além disso, para obter eficiência na visualização de dados vetoriais complexos, apresentamos um algoritmo de multi-resolução destes dados. Na solução proposta, a simplificação dos dados vetoriais é desacoplada da multi-resolução utilizada no modelo tridimensional do terreno. Com isso, nossa solução pode ser adotada em diferentes visualizadores de terreno. Apresentamos resultados que ilustram a eficiência da solução proposta. / [en] This work aims to integrate the graphical representation of vectorial data found in Geographic Information Systems (GIS) and the visualization for multi-resolution 3D terrain models. The multi-resolution approach on terrain rendering brings some difficulties on the process of rendering the vectorial data in a consistent manner, since these data, in general, only store bi-dimensional information. The solutions most commonly used are based on conventional texture mapping, resulting in low visual quality. In order to improve image quality, we adopt texture mapping with perspective correction, in a way similar to the techniques used for shadow map generation. Besides, willing to obtain efficiency on complex vectorial data visualization, a multi-resolution algorithm of these data is presented. In our proposed solution, vectorial data simplification is decoupled from the multi-resolution technique used on the tri-dimensional terrain model. Thus, our solution can be used with different terrain viewers. We present results that illustrate the efficiency of the proposed solution.

[pt] O uso de modelos computacionais baseados em malhas 3D se torna cada vez mais frequente em diversas áreas da computação como em jogos, animações e simuladores de realidade virtual, por exemplo. Entretanto, malhas que possuem uma grande quantidade de elementos exigem um alto poder computacional para serem manipuladas. A fim de resolver este problema são utilizados métodos de simplicação para reduzir o número de elementos, preservando a topologia que o modelo apresenta. Neste trabalho é introduzido um método de Difusão Geométrica Markoviana - difusão calculada na forma de probabilidades de transição e construída sobre um conjunto de pontos organizados geometricamente - aplicado na malha. Esse método combina uma estratégia baseada em uma Cadeia de Markov de base geométrica, que controla probabilisticamente o comportamento das normais na malha, com métodos de simplicação que são capazes de avaliar o impacto que a remoção de um elemento provoca na estrutura da malha. Métricas de avaliação são utilizadas para comparar o erro cometido em relação à malha original. / [en] Computational models based on 3D meshes are ubiquitous in are such as game, animations and virtual reality. However, very large data sets are frequently produced, e.g. by scanners 3D and fluid dynamics simulations, wich require high computer power to be handled. Mesh simplification tecniques, preserving the topology and the geometry of the mesh, are then implemented to bring the datea to a size suited to be used in such areas. In this work we introduce a new tecnique wich we call Markov Geometric Diffusion based on probability transition matrix tecniques and built upon a data set organized geometricallyas a mesh. This method puts together a strategy based on a geometrically constructed Markov chain, wich control, in a probabilistic way, a normal vector field to the mesh, with a simplification method capable of estimating the impact of element removal in the mesh structure. Several error evaluation metrics are used tocompare the error of the simplified mesh with the original one.

[pt] À medida que o processo de digitalização avança em diversos setores, a criação de modelos digitais 3D torna-se cada vez mais necessária. Normalmente, esses modelos são construídos por designers 3D, exigindo um esforço manual considerável quando o objeto modelado é complexo. Além disso, como o designer não tem uma referência precisa na maioria dos casos, o modelo resultante está sujeito a erros de medição. No entanto, é possível minimizar o esforço de construção e o erro de medição usando técnicas de aquisição 3D e modelos CAD previamente construídos. A saída típica de uma técnica de aquisição 3D é uma nuvem de pontos 3D bruta, que precisa de processamento para reduzir o ruído inerente e a falta de informações topológicas. Os modelos CAD são normalmente usados para documentar um processo de projeto de engenharia, apresentando alta complexidade e muitos detalhes irrelevantes para muitos processos de visualização. Portanto, dependendo da aplicação, devemos simplificar bastante o modelo CAD para atender aos seus requisitos. Nesta tese, nos concentramos na construção de modelos digitais 3D a partir dessas fontes. Mais precisamente, apresentamos um conjunto de algoritmos de processamento de geometria para automatizar diferentes etapas de um fluxo de trabalho típico usado para esta construção. Primeiro, apresentamos um algoritmo de redução de ruído de nuvem de pontos que visa preservar as feições nítidas da superfície subjacente. Este algoritmo inclui soluções para a estimativa normal e problemas de detecção de feições nítidas. Em segundo lugar, apresentamos uma extensão do algoritmo de redução de ruído de nuvem de pontos para processar malhas triangulares, onde tiramos proveito da topologia explícita definida pela malha. Por fim, apresentamos um algoritmo para a simplificação extrema de modelos CAD complexos, que tendem a se aproximar da superfície externa do objeto modelado. Os algoritmos propostos são comparados com métodos de última geração, apresentando resultados competitivos e superando-os na maioria dos casos de teste. / [en] As the digitalization process advances in several industries, the creation of 3D digital models is becoming more and more required. Commonly, these models are constructed by 3D designers, requiring considerable manual effort when the modeled object is complex. In addition, since the designer does not have an accurate reference in most cases, the resulting model is prone to measurement errors. However, it is possible to minimize the construction effort and the measurement error by using 3D acquisition techniques and previously constructed CAD models. The typical output of a 3D acquisition technique is a raw 3D point cloud, which needs processing to reduce the inherent noise and lack of topological information. CAD models are typically used to document an engineering design process, presenting high complexity and too many details irrelevant to many visualization processes. So, depending on the application, we must severely simplify the CAD model to meet its requirements. In this thesis, we focus on the construction of 3D digital models from these sources. More precisely, we present a set of geometry processing algorithms to automatize different stages of a typical workflow used for this construction. First, we present a point cloud denoising algorithm that seeks to preserve the sharp features of the underlying surface. This algorithm includes solutions for the normal estimation and sharp feature detection problems. Second, we present an extension of the point cloud denoising algorithm to process triangle meshes, where we take advantage of the explicit topology defined by the mesh. Finally, we present an algorithm for the extreme simplification of complex CAD models, which tends to approximate the outer surface of the modeled object. The proposed algorithms are compared with state-of-the-art methods, showing competitive results and outperforming them in most test cases.