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.

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.

Made available in DSpace on 2016-06-02T19:06:21Z (GMT). No. of bitstreams: 1 6541.pdf: 10057991 bytes, checksum: 6e34bb08fd8457f2c6ab13a9ae4751a8 (MD5) Previous issue date: 2013-07-11 / Financiadora de Estudos e Projetos / The computational representation of objects by means of polygonal meshes is widely used in various areas such as modeling, simulation, engineering, rendering process and various other CAD (Computer-Aided Design) and CAE (Computer-Aided Engineering) applications. These polygonal meshes are commonly built with triangles and processing these elements is widely studied, making that such techniques are well established and robust. However, there is a growing interest in quadrilateral meshes as they provide important characteristics for applications such as texturing and modeling with splines. With the increasing interest in the study of unstructured quadrilateral surfaces, there is the rise of new processing techniques related to simplification and refinement. This dissertation presents a complete pipeline for indirect generation of quadrilateral surface meshes, proposing a new refinement method of quadrilateral meshes. This new method is a local iterative subdivision process, ensuring the consistency of the mesh at each iteration and has the following main features: ability to guide the quality of generated quadrilaterals; control the number of generated elements; generate a family of models; control quadrilaterals density (adaptivity) and control the alignment of quadrilaterals lines with features lines of the model. The implementation restricts the refinement to homeomorphic models to a sphere. The results presented illustrate the effectiveness of the refinement technique and adaptivity control. / A representação computacional de objetos por meio de malhas poligonais e muito utilizada em diversas áreas como modelagem, simulaçao, engenharia, processo de rendering e diversas outras aplicacoes CAD (Computer-Aided Design) e CAE (Computer-Aided Engineering). Essas malhas poligonais sao comumente construídas com triângulos e o processamento desses elementos e amplamente estudado, fazendo com que essas tecnicas estejam bem consolidadas e robustas. Porem, ha um crescente interesse em malhas de quadrilateros, pois proveem características importantes para aplicacoes como texturizacão e modelagem com splines. Com o crescente aumento do interesse no estudo de superfícies de quadriláteros nao estruturadas, ha o surgimento de novas tecnicas de processamento das mesmas como simplificação e refinamento. Esta dissertacao apresenta um pipeline completo para geracao indireta de malhas superficiais de quadrilateros, propondo um novo metodo de refinamento de malhas de quadrilateros. Este novo metodo consiste em um processo iterativo de subdivisao local, garantindo a consistencia da malha a cada iteraçao e possui como principais características: capacidade de guiar a qualidade dos quadriláteros gerados; controlar o námero de elementos gerados; gerar uma família de modelos; controlar a densidade de quadrilateros (adaptatividade) e controlar o alinhamento dos quadrilateros com as linhas de características do modelo. A implementacao realizada restringe o refinamento para modelos homeomorficos a uma esfera. Os resultados apresentados ilustram a efetividade da tecnica de refinamento e controle da adaptatividade.

Orientadores: Paulo Sollero, Eder Lima de Albuquerque / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Mecanica / Made available in DSpace on 2018-08-05T00:09:39Z (GMT). No. of bitstreams: 1 CreciFilho_Geraldo_M.pdf: 4660836 bytes, checksum: 8b3f339935f071d6175c61d8dae84f24 (MD5) Previous issue date: 2004 / Resumo: Este trabalho apresenta o desenvolvimento de um programa de geração de malhas não estruturadas que serão usadas em análises numéricas pelo método dos elementos de contorno. O método dos elementos de contorno é um dos métodos numéricos de destaque usados atualmente em simulações computacionais. Ele possui algumas características particulares que o tornam mais atrativo em determinados tipos de aplicações, quando comparado com outros métodos numéricos. Dentre essas características, está a vantagem de se discretizar somente o contorno das geometrias para o cálculo da solução aproximada do problema. Isso significa dizer que em casos tridimensionais somente elementos de superfície precisam ser gerados na malha. O gerador de malhas implementado neste trabalho foi desenvolvido para gerar malhas com elementos triangulares-lineares em geometrias tridimensionais compostas por faces planas. A idéia geral consiste em deslocar cada face que compõe a geometria tridimensional para o espaço bidimensional usando-se transformações geométricas e, em seguida, aplicar o algoritmo de triangulação de Delaunay para geração dos elementos. Depois de gerados os elementos, novas transformações geométricas são aplicadas a fim de enviar a face de volta para sua posição original no espaço tridimensional. A continuidade da malha é assegurada promovendo-se a geração dos nós nas arestas antes da geração dos nós no interior das faces. Vários exemplos de malhas em geometrias tridimensionais são apresentados para ilustrar a capacidade do programa desenvolvido e algumas análises numéricas foram feitas para demonstrar a qualidade das malhas em problemas com condições de contorno específicas / Abstract: This work presents the development of an unstructured mesh generator to be used in numerical analysis by the boundary element method. The boundary element method is one of the prominence methods recently used in computational simulations. It has some particular characteristics that make it more favorable in certain types of applications, when compared to other numerical methods. Among those characteristics, one is especially important from the mesh generation point of view. It is the fact that, in boundary element method, it is only necessary the discretization of the geometry boundaries. In other words, in three-dimensional cases only surface elements should be generated. The mesh generator implemented in this work has been developed to generate meshes with triangular-linear elements over threedimensional geometries composed by plane faces. The general idea consists of moving each face belonging to the three-dimensional geometry to bi-dimensional space using geometrical transformations and the Delaunay triangulation algorithm for element generation. After element generation, new geometrical transformations are applied in order to send the meshed face back to its original position in three-dimensional space. The continuity of the final mesh is assured by generating the nodes of the edges of the geometry prior to the generation of the nodes in the interior of the face. Several examples of meshes in three-dimensional geometries are presented to illustrate the capabilities of the developed program and some numerical analyses have been performed to show the quality of the meshes in problems with specific boundary conditions / Mestrado / Mecanica dos Sólidos e Projeto Mecanico / Mestre em Engenharia Mecânica

Orientador: Pedro Jussieu de Rezende / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-06T03:40:47Z (GMT). No. of bitstreams: 1 Figueiredo_FabioDallaCosta_M.pdf: 1782158 bytes, checksum: fa8eb774d4870ff779afab7b7041759f (MD5) Previous issue date: 2005 / Resumo: Problemas de natureza geométrica são encontrados em diversas áreas e, portanto, a análise dos mesmos sob uma ótica algorítmica e imprescindível. Não obstante um amplo tratamento de problemas na geometria euclidiana, relativamente poucos estudos foram feitos em outras geometrias. Em particular, tomando-se como retas sobre o plano as curvas de uma família F que satisfaçam um pequeno conjunto de propriedades, pode-se definir uma geometria de curvas, denotada por GF, a qual foi inicialmente estudada, sob o ponto de vista algorítmico, por Harada [Har00]. Nesta dissertação, estudamos características de famílias de curvas que podem formar uma geometria GF, e sobre ela, primitivas e algoritmos para soluções de problemas. Desenvolvemos ainda um visualizador gráfico, denominado GFViewer, através do qual é possível aprimorar a intuição quanto à forma de construções geométricas, como GF-retas, GF-segmentos, GF-polígonos, GF-bissetores, GF-circunferências, etc. Esse visualizador foi utilizado para testarmos a implementação de alguns algoritmos geométricos sobre certas instâncias de GF. Com a caracterização de algumas famílias de curvas, foi possível construir novos exemplos dessas geometrias. Além disso, na análise dos problemas formulados, verificamos ser plausível a adaptação de algoritmos existentes no caso euclidiano, devido à correlação entre as duas geometrias, de diversas primitivas e predicados / Abstract: Problems of geometric nature are found in many areas, so their study under an algorithmic point of view is indispensable. Even though a vast literature exists on problems for the Euclidian geometry, relatively little has been done on other geometries. In particular, if one takes as lines on the plane the curves of a family F that meet a small set of conditions, one may define a geometry of curves, denoted by GF, which was first studied, under an algorithmic approach, by Harada [Har00]. In this dissertation, we identify characteristics of families of curves that may form a GF geometry, over which we study primitives and algorithms for the solution of geometric problems. We also developed a graphical visualizer, known as GFViewer, through which it is possible to improve the intuition towards the understanding of GF-lines, GFsegments, GF-poligons, GF-bissectors, GF-circles, etc. This visualizer was used to test the implementation of a few geometric algorithms over certain instances of GF. With the characterization of some families of curves, it was possible to build new examples of these geometries. Furthermore, in the analysis of the problems studied, we perceived that it is plausible to adapt algorithms that deal with the euclidian case, due to the correlation between the two geometries, of several primitives and predicates / Mestrado / Teoria da Computação / Mestre em Ciência da Computação

Submitted by isabela.moljf@hotmail.com (isabela.moljf@hotmail.com) on 2017-07-26T12:43:15Z No. of bitstreams: 1 joaopaulopecanhanavarrodeoliveira.pdf: 20245819 bytes, checksum: 0b6a88d7e0946052431cdb43acc011c3 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2017-08-08T18:35:21Z (GMT) No. of bitstreams: 1 joaopaulopecanhanavarrodeoliveira.pdf: 20245819 bytes, checksum: 0b6a88d7e0946052431cdb43acc011c3 (MD5) / Made available in DSpace on 2017-08-08T18:35:21Z (GMT). No. of bitstreams: 1 joaopaulopecanhanavarrodeoliveira.pdf: 20245819 bytes, checksum: 0b6a88d7e0946052431cdb43acc011c3 (MD5) Previous issue date: 2012-08-30 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / A aproximação de superfícies contínuas através de malhas poligonais é importante em várias áreas do conhecimento. Esse tipo de malha é empregado em aplicações como simulações computacionais de engenharia e física, modelagem geométrica e animações. Os modelos de entrada muitas vezes apresentam baixa qualidade, seja na distribuição de seus elementos ou no alinhamento e forma dos polígonos. Neste trabalho é apresentado um método para recobertura de malhas triangulares dado um comprimento de aresta m. A malha de entrada é uma superfície triangular de variedade-2 com topologia e geometria arbitrária, com ou sem borda. Definido o comprimento de aresta alvo m, o algoritmo remove e insere vértices de acordo com um critério, ajustando a quantidade necessária de elementos que o objeto deve conter. Após esta etapa, o modelo entra em uma fase de relaxamento global utilizando uma variação do operador discreto de Laplace-Beltrami, que na formulação aqui proposta utiliza os k primeiros vizinhos de cada vértice, ao contrário da definição clássica que usa apenas os vizinhos mais próximos. Isto é feito de maneira iterativa até que se esgote o número máximo de iterações fornecido no início do processo. Ao final, tem-se uma malha com comprimento de aresta próximo a m e com baixo desvio padrão, i.e., vértices uniformemente distribuídos sobre o modelo; seus triângulos também tendem a ser equiláteros. Os resultados do remalhamento se mostraram quantitativamente satisfatórios, com baixo desvio padrão do comprimento das arestas. O espaço dual pode ser utilizado para geração de malhas trivalentes, compostas majoritariamente por hexágonos em superfícies de baixa curvatura. / The approximation of continuous surfaces by polygonal meshes is very important in several areas. In recent years we have seen the use of this kind of mesh in various industrial applications such as computer simulations, geometric modeling and animation. Often, the input models have poor quality, i.e., bad elements distribution and inconsistent polygon shape. One important feature of poligonal surfaces is vertex distribution and sometimes it is necessary to control the vertices distance with an uniform edge lentgh. This work presents a method for triangular remeshing given a target edge length m. The input is a 2-manifold triangular surface with arbitrary geometry and topology. The proposed algorithm removes and inserts vertices adjusting the amount of necessary elements. Then, the model enters in a global relaxation process using a variation of Laplace-Beltrami discrete operator, which uses the k nearest neighbors of each vertex. This is done in an iteratively fashion until the algorithm reaches the maximum iteration number. At the end, one have a grid with edge length near to m and low standard deviation (vertices uniformly distributed). The triangles also presents good connectivity and high isotropy; the results shown that our remeshing scheme quantitatively improved the mesh quality. The dual space of the final triangular surface can be used for trivalent remeshing. These models are important for physical simulations of nano-carbon surfaces and we dedicated a chapter of our work to discuss this subject.

Orientadores: Pedro Jussieu de Rezende, Flávio Keidi Miyazawa / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-25T08:56:08Z (GMT). No. of bitstreams: 1 Sasaki_AndersonToshiyuki_M.pdf: 1449279 bytes, checksum: 851c64c64afd4605cbfb4946ed5f97a4 (MD5) Previous issue date: 2014 / Resumo: No problema de cobertura mínima por conjuntos (MSC - Minimum Set Cover), são dados um conjunto L de objetos e uma coleção R de conjuntos e deseja-se encontrar uma sub-coleção S de R que seja uma cobertura de L de custo mínimo, ou seja, L está contido na união de todo os conjuntos R de S com a soma dos custos dos conjuntos R de S sendo mínima. Entre as variantes desse problema, existem aquelas advindas de configurações geométricas, em que tanto os elementos de L quanto os conjuntos contidos em R são objetos geométricos. Como tais problemas são, em geral, NP-difíceis, se P ? NP, não é possível encontrar algoritmos exatos de tempo polinomial para os mesmos. Assim, torna-se interessante a busca por algoritmos aproximados eficientes para obtenção de soluções com garantia de qualidade. Nesta dissertação, estudamos diferentes versões do problema de cobertura mínima por discos (MDC ¿ Minimum Disk Cover), em que o conjunto R é um conjunto de discos, e o objetivo é projetar algoritmos aproximados. Tais versões do problema estão relacionadas com a solução de problemas práticos, como o posicionamento de estações-base em projeto de redes sem fio ou de dispositivos em redes de sensores. Para o caso em que o conjunto de objetos geométricos L é constituído de um único segmento de reta no plano, apresentamos um FPTAS. Para outra versão mais geral, na qual o conjunto de objetos geométricos é dado por um sistema de inequações polinomiais algébricas, propomos um algoritmo aproximado, o qual demonstramos ser um PTAS / Abstract: The Minimum Set Cover problem (MSC) can be described as: given a set L of elements and a collection of sets R, find a subcollection S of R that is a minimum-cost covering for L, i.e., L is contained in the union of the sets R in S, and the sum of the costs of the sets R in S is minimum. Among the variants of this problem, there are those that arise from a geometric configuration in which both the elements of L and the sets contained in R are geometric objects. As such problems are, in general, NP-hard, if P ? NP, it is impossible to find polynomial-time exact algorithms for them. Thus, the use of efficient approximation algorithms to find high quality solutions becomes a good approach. In this dissertation, we study different versions of the Minimum Disk Cover problem (MDC), in which the sets in R are disks, and we seek to develop approximation algorithms. These versions are related to practical problems, such as base station positioning problem for wireless network design and placement of devices in a sensor network. For the case in which the set of geometric objects to be covered is given by a single line segment, we present an FPTAS. For a more general case, where the set of geometric objects is given by a system of algebraic polynomial inequalities, we propose an approximation algorithm which we prove to be a PTAS / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientadores: Cid Carvalho de Souza, Pedro Jussieu de Rezende / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-25T16:57:43Z (GMT). No. of bitstreams: 1 Tozoni_DaviColli_M.pdf: 4212278 bytes, checksum: afb91e202a72e28729ff14334901884f (MD5) Previous issue date: 2014 / Resumo: Nesta dissertação, apresentamos nossa pesquisa sobre o Problema da Galeria de Arte (AGP), um dos problemas mais estudados em Geometria Computacional. O AGP, que é um problema NP-difícil, consiste em encontrar o número mínimo de guardas suficiente para garantir a cobertura visual de uma galeria de arte representada por um polígono. Na versão do problema tratada neste trabalho, usualmente chamada de Problema da Galeria de Arte com Guardas-Ponto, os guardas podem ser posicionados em qualquer lugar do polígono e o objetivo é cobrir toda a região, que pode ou não conter buracos. Nós estudamos como aplicar conceitos e algoritmos de Geometria Computacional, bem como Técnicas de Programação Inteira, com a finalidade de resolver o AGP de forma exata. Este trabalho culminou na criação de um novo algoritmo para o AGP, cuja ideia é gerar, de forma iterativa, limitantes superiores e inferiores para o problema através da resolução de versões discretizadas do AGP, que são reduzidas a instâncias do Problema de Cobertura de Conjuntos. O algoritmo foi implementado e testado em mais de 2800 instâncias, de diferentes tamanhos e classes. A técnica foi capaz de resolver, em minutos, mais de 90% de todas as instâncias consideradas, incluindo polígonos com milhares de vértices, e ampliou em muito o conjunto de casos para os quais são conhecidas soluções exatas. Até onde sabemos, apesar do extensivo estudo do AGP nas últimas quatro décadas, nenhum outro algoritmo demonstrou a capacidade de resolver o AGP de forma tão eficaz como a técnica aqui descrita / Abstract: In this dissertation, we present our research on the Art Gallery Problem (AGP), one of the most investigated problems in Computational Geometry. The AGP, which is a known NP-hard problem, consists in finding the minimum number of guards sufficient to ensure the visibility coverage of an art gallery represented as a polygon. In the version of the problem treated in this work, usually called Art Gallery Problem with Point Guards, the guards can be placed anywhere in the polygon and the objective is to cover the whole region, which may or not have holes. We studied how to apply Computational Geometry concepts and algorithms as well as Integer Programming techniques in order to solve the AGP to optimality. This work culminated in the creation of a new algorithm for the AGP, whose idea is to iteratively generate upper and lower bounds for the problem through the resolution of discretized versions of the AGP, which are reduced to instances of the Set Cover Problem. The algorithm was implemented and tested on more than 2800 instances of different sizes and classes of polygons. The technique was able to solve in minutes more than 90% of all instances considered, including polygons with thousands of vertices, greatly increasing the set of instances for which exact solutions are known. To the best of our knowledge, in spite of the extensive study of the AGP in the last four decades, no other algorithm has shown the ability to solve the AGP as effectively as the one described here / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Orientador: Hélio Pedrini / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-21T23:01:00Z (GMT). No. of bitstreams: 1 Fazanaro_DaltonIeda_M.pdf: 17180414 bytes, checksum: 024cc06fef1c6ac030cce29037783fd1 (MD5) Previous issue date: 2013 / Resumo: Inicialmente centralizadas na solução de problemas científicos em Dinâmica dos Fluidos, as interfaces evolutivas, com o advento da modelagem mais eficiente e robusta provida pelo método Level Set, expandiram os seus limites originais de aplicabilidade, proporcionando uma nova frente de pesquisa para os campos dos mais diversos, com destaque à Ciência da Computação. Especificamente à área de Processamento de Imagens, os trabalhos até então apresentados, relacionando o Level Set à reconstrução de superfícies tridimensionais, concentram-se na reconstrução a partir de uma nuvem de dados dispersos no espaço; a abordagem baseada em fatias planas paralelas e transversais ao objeto a ser reconstruído evidencia-se ainda incipiente. Esse cenário fomenta, portanto, uma análise da viabilidade do Level Set para a reconstrução de superfícies tridimensionais. Fundamentando-se nessa constatação, a dissertação propõe-se a oferecer uma metodologia que agregue, simultaneamente, as idéias comprovadamente eficientes já publicadas sobre a aproximação em questão e as propostas para contornar as limitações inerentes ao método ainda não satisfatoriamente tratadas, em particular a suavização excessiva de características finas dos contornos em evolução sob o Level Set. Relativamente a esse ponto, o emprego da variante Particle Level Set é sugerido como uma possível solução, por sua intrínseca capacidade comprovada para a conservação de massa ou volume de fronteiras dinâmicas traduzirem-se, presumivelmente, em um controle ao problema destacado. Ao final, conjuntos de dados sintéticos e reais são utilizados para avaliar a metodologia de reconstrução de superfícies tridimensionais apresentada qualitativamente / Abstract: Evolving interfaces were initially focused on solutions to scientific problems in Fluid Dynamics. With the advent of the more efficient and robust modeling provided by Level Set method, their original boundaries of applicability were extended, offering a new front of research to the more diverse fields, especially to Computer Science. Specifically to Image Processing area, the works published until then, relating Level Set to tridimensional surface reconstruction, centered themselves on reconstruction from a data cloud dispersed in space; the approach based on parallel planar slices transversal to the object to be reconstructed is still incipient. Therefore, this scenario foments a feasibility analysis of Level Set to the reconstruction of tridimensional surfaces. Basing on this fact, this dissertation proposes to offer a methodology that simultaneously integrates the proved efficient ideas already published about such approximation and the proposals to process the inherent limitations of the method not satisfactorily treated yet, in particular the excessive smoothing of fine characteristics of contours evolving under Level Set. In relation to this, the application of the variant Particle Level Set is suggested as a possible solution, for its intrinsic proved capability to preserve mass or volume of dynamic fronts manifests itself, presumably, into a control of the stressed problem. At the end, synthetic and real data sets are used to evaluate the presented tridimensional surface reconstruction methodology qualitatively / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

[pt] A confiabilidade dos dados coletados diretamente ao longo do caminho de poços de petróleo é maior que a confiabilidade de dados sísmicos e, por isto, os primeiros podem ser utilizados para ajustar o volume de aquisição sísmica. Este trabalho propõe um ajuste dos volumes de amplitudes sísmicas através de uma algoritmo de três passos. O primeiro passo é a identificação de feições comuns através de um algoritmo de reconhecimento de padrões. O segundo passo consiste em gerar e otimizar uma malha alinhada às feições de interesse do dado sísmico voluméletrico através de um novo algoritmo baseado em processamento de imagens e inteligência computacional. E o terceiro e último passo é a realização de uma deformação volumétrica pontoa- ponto usando interpolação por funções de base radial para registrar o volume sísmico aos poços. A dissertação apresenta ainda resultados de implementações 2D e 3D dos algoritmos propostos de forma a permitir algumas conclusões e sugestões para trabalhos futuros. / [en] Data acquired directly from borehole are more reliable than seismic data, and then, the first can be used to adjust the second. This work proposes the correction of a volume of seismic amplitudes through a three step algorithm. The first step is the identification of common features in both sets using a pattern recognition algorithm. The second step consists of the generation and the optimization of a mesh aligned with the features in the volumetric data using a new algorithm based on image processing and computational intelligence. The last step is the seismic-to-well registration using a point-to-point volumetric deformation achieved by a radial basis function interpolation. The dissertation also presents some results from 2D and 3D implementations allowing conclusions and suggestions for future work.