[pt] Esta dissertação tem por objetivo estudar um método para aproximação de dados esparços multivariados denominado o método Mínimos Quadrados Móveis por Aproximações Iteradas (Iterated Approximate Moving Least-Square Approximation – IAMLA). Este método é baseado no método de interpolação por funções de base radial (RBF) e no método de aproximação AMLS. Mas diferentemente do método RBF, ele não requer a solução de um sistema de equações lineares. O método IAMLS no limite converge para o interpolante RBF sob certas condições. / [en] The objective of this work is to study an approximation method for multivariate sparse data named Iterated Approximate Moving Least Square Approximation – IAMLS. This method is based on the Radial Basis Functions (RBF) interpolation method and on the AMLS approximation method. Differently from the RBF interpolation method, the IAMLS does not requires to solve a system of linear equations. The IAMLS method converges to the RBF interpolant under some conditions.

[pt] O presente trabalho de pesquisa, apresenta a aplicação de um novo conceito de visualização e interpretação da informação geológica. Os mapas geológicos que, até hoje em dia, são apresentados em papel, agora podem ser vistos, em computador, de forma tridimensional. Esta representação tridimensional é realizada a partir do software GOCAD (Geological Object Computer Aided Draw) (grupo de Ciência da Computação da Escola Nacional de Geologia, Nancy, França, 1989). Este software foi inicialmente desenvolvido para aplicação e representação de bacias sedimentares na indústria do petróleo. O presente trabalho de pesquisa apresenta uma extensão do GOCAD à representação tridimensional de maciços rochosos, como os encontrados na região litorânea do Estado do Rio de Janeiro. Uma área na zona sul da cidade do Rio de Janeiro foi escolhida como área piloto de estudo para a modelagem tridimensional. Esta área, o maciço Dois Irmãos, foi inicialmente caracterizada do ponto de vista da geologia estrutural e as informações coletadas foram utilizadas na modelagem geométrica usando GOCAD. Os resultados obtidos são comentados e são também mostrados o potencial e limitações do software GOCAD para este tipo particular de modelagem geométrica de maciços rochosos. / [en] The present research presents the application of a new concept in visualization and interpretation of geological information. The geological maps that until now are still represented on paper, now can be seen tridimensionally, in computer screen. This 3D representation is accomplished through the software GOCAD (Geological Object Computer Aided Draw), developped by a team of Computer Science of the National School of Geology, Nancy, France. The software was developed originally for application and representation of sedimentary basins basically for use in the petroleum industry. The present research, presents an extension of the GOCAD software to the 3D representation of rock masses found on the coastal region of the state of Rio de Janeiro. An area in the southern area of the city of Rio de Janeiro was chosen to be a pilot study area for the 3D geometrical modelling. This area, the Morro Dois Irmãos massive, was initially characterized from the structural geology point of view and the collected information was used in the 3D geometrical modelling with GOCAD . The obtained results are commented and the potential and limitations of the GOCAD software for this particular type of geometrical modelling of rock masses are discussed. / [es] Este trabajo de investigación presenta la aplicación de un nuevo concepto de visualización e interpretación de la información geológica. Los mapas geológicos que, hasta hoy en día, son presentados en papel, pueden ser vistos ahora en computador, de forma tridimensional. Esta representación tridimensional se realiza a partir del software GOCAD (Geological Object Computer Aided Draw) (grupo de Ciencias de la Computación de la Escuela Nacional de Geología, Nancy, Francia, 1989). Este software fue inicialmente desarrollado para la aplicación y representación de bacias sedimentares en la industria del petróleo. EL presente trabajo de investigación presenta una extensión del GOCAD a la representación tridimensional de macizos rocosos, como los encontrados en la región litoránea del Estado del Rio de Janeiro. Cierta área situada en la zona sul de la ciudad de Rio de Janeiro fue escogida como área piloto de estudio para la modelaje tridimensional. Esta área, el macizo Dois Irmãos, fue inicialmente caracterizada desde el punto de vista de la geología extructural y las informaciones recolectadas fueron utilizadas en el modelo geométrico usando GOCAD. Se comentan los resultados obtenidos y se muestra el potencial y limitaciones del software GOCAD para este tipo particular de modelo geométrico de macizos rocosos.

[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] Dentro dos métodos deformação de objetos tridimensionais, os que usam poliedros de controle permitem interações rápidas e intuitivas, e assim ganharam bastante interesse nos últimos anos. Essas técnicas expressam os pontos do objeto a partir dos vértices do poliedro de controle, por exemplo usando coordenadas baricêntricas e suas extensões.Assim, ao deformar o poliedro de controle, obtém-se deformações correspondentes sobre o modelo recalculando cada ponto do objeto a partir das novas posições dos vértices de controle. Devido ao grau de flexibilidade em sua construção, diferentes generalizações de coordenadas baricêntricas vem sendo propostas nos últimos anos para modelos 3D. Nesse trabalho apresentamos um estudo das recentes generalizações de coordenadas baricêntricas e as principais características das deformações em modelos em três dimensões obtidas com o uso de cada uma delas. Deduzimos desse estudo uma nova extensão de coordenadas baricêntricas que mantém a simplicidade do método original e corrige alguns dos seus defeitos. / [en] Within the thee-dimensional objects deformation techniques, the ones using control polyhedrons allow fast and intuitive interaction, and therefore gained considerable interest in recent years. Those techiques write the model points as function of the vertices of the control polyhedron, for exemple using barycentric coordinates or its extensions. This way, deforming the control polyhedron induces a corresponding strain on the model, recomputing each point of the object from the new positions of control vertices. To do so, due to the flexibility in its construction, different generalizations of barycentric coordinates has been proposed in recent years for 3D models. In this work, we present a study of recent generalizations of barycentric coordinates and the main characteristics of the resulting deformations of three-dimensional model. We deduce from this study a new extension of barycentric coordinates that retains the simplicity of the original method and fixes some of the its defects.

[pt] Muitos problemas reais em modelagem computacional requerem o uso de aproximação de funções. Em alguns casos a função a ser avaliada no computador é muito complexa, portanto seria desejável que ela fosse substituída por uma função mais simples e mais eficiente de ser calculada. Para fazer isso, calcula-se o valor da função escalar f em um conjunto de N pontos {x1, x2, . . . , XN}, onde x(i) (pertence a) R(n), e faz-se uma estimativa dos valores dessa função f em qualquer outro ponto através de um método de interpolação. Um método de interpolação é qualquer procedimento que toma um conjunto de restrições e determina uma boa função que satisfaça essas condições. O método de interpolação de Shepard originalmente calcula o valor estimado dessa função num ponto qualquer x (pertence a) R(N) como uma média ponderada dos valores da função original nas N amostras dadas. Sendo que o peso para cada amostra x(i) é função das potências negativas das distâncias euclidianas entre os pontos x e x(i). Os núcleos K: R(N) × R(N) (EM) R são funções que correspondem ao produto interno no espaço de Hilbert F da imagem dos pontos x e z por uma função phi (conjunto vazio) : R(N) (EM) F, ou seja K(x, z) = < phi (conjunto vazio) (x), phi (conjunto vazio) (z) >. Na prática, as funções núcleos representam implicitamente o mapeamento feito pela função phi (conjunto vazio) , ou seja, se define qual núcleo usar e não qual phi (conjunto vazio) usar. Esse trabalho propõe uma modificação do método de interpolação de Shepard que é uma simples substituição no método original: ao invés de usar a distância euclidiana entre os pontos x e xi sugere-se usar a distância entre as imagens dos pontos x e x(I) por phi (conjunto vazio) no espaço de Hilbert F, que pode ser calculada diretamente com o uso da função núcleo K. Os resultados mostram que essa pequena modificação gera resultados melhores quando comparados com o método de Shepard original. / [en] Several real problem in computational modeling require function approximations. In some cases, the function to be evaluated in the computer is very complex, so it would be nice if this function could be substituted by a simpler and efficient one. To do so, the function f is sampled in a set of N pontos {x1, x2, . . . , xN}, where x(i) (is an element of) R(n), and then an estimate for the value of f in any other point is done by an interpolation method. An interpolation method is any procedure that takes a set of constraints and determines a nice function that satisfies such conditions. The Shepard interpolation method originally calculates the estimate of F(x) for some x (is an element of) R(n) as a weighted mean of the N sampled values of f. The weight for each sample xi is a function of the negative powers of the euclidian distances between the point x and xi. Kernels K : R(n) ×R(n) (IN) R are functions that correspond to an inner product on some Hilbert space F that contains the image of the points x and z by a function phi (the empty set) : R(n) (IN) F, i.e. k(x, z) =< phi (the empty set) (x), phi (the empty set) (z) >. In practice, the kernels represent implicitly the mapping phi (the empty set), i.e. it is more suitable to defines which kernel to use instead of which function phi (the empty set). This work proposes a simple modification on the Shepard interpolation method that is: to substitute the euclidian distance between the points x and xi by a distance between the image of these two point by phi (the empty set) in the Hilbert space F, which can be computed directly with the kernel k. Several tests show that such simple modification has better results when compared to the original method.

[pt] Nas aplicações em computação gráfica e processamento de imagens, curvas e superfícies implícitas têm sido reconhecidas como a representação mais útil de objetos 2D ou 3D, principalmente porque elas permitem a descrição de formas complexas por uma fórmula. A maioria dos métodos implícitos usam curvas algébricas para aproximar globalmente a fronteira do objeto em uma imagem binária. Quando a forma do objeto é complexa, é comum elevar o grau da curva a fim de obter mais precisão na aproximação. Uma solução alternativa é decompor hierarquicamente o domínio em partes compactas e obter aproximações locais para o objeto em cada parte, e então juntar os pedaços com o objetivo de obter uma descrição global do objeto. O principal objetivo deste trabalho é apresentar um novo método de aproximação de curvas implícitas a partir de pontos esparsos que melhora o estado da arte / [en] In the field of computer vision and image analysis, implicit curves and surfaces have been recognized as the most useful representation for 2D or 3D objects, mainly because they allow description of shapes by a formula. Most of implicit methods uses algebraic curves to fit globally the frontier of the foreground in a binary image. When the foreground shape is complex, it is common to elevate the curve degree in order to obtain more precision on the approximation. An alternative solution is to decompose the domain hierarchicaly in compact parts and obtain local approximation for the object in each part, and then patch all together in order to obtain a global description of the object. The main objective of this work is to present a new method for implicit curve fitting from sparse point that improves the state of the art

[pt] Este trabalho situa-se numa das linhas de pesquisa da PUC-Rio de projeto de unidades flutuantes tais como, navios e plataformas semi-submersíveis. Nesta linha de pesquisa estão sendo desenvolvidos os programas gráficos MG (Mesh Generator) e o Sstab. O primeiro programa é um modelador geométrico por meio de seções transversais e gerador de malhas para modelos de estruturas flutuantes. O segundo programa é utilizado para a análise de estabilidade estática dos modelos gerados pelo MG. Este trabalho propõe um ambiente integrado de modelagem e de análise estática e dinâmica de estruturas flutuantes. O principal diferencial deste ambiente está no fato de possibilitar a geração automática de variantes de um determinado modelo padrão, a fim de atingir uma configuração desejada, seja no aspecto geométrico ou com relação a sua estabilidade estática. Este ambiente faz uso da linguagem Lua e é possível definir variáveis globais para serem utilizadas como parâmetros de modelagem que extraem, ou modificam, dados como comprimento, largura, altura etc. É possível parametrizar um modelo qualquer, em função de variáveis escolhidas pelo usuário, o que possibilita uma modelagem automática, com a variação de alguns destes parâmetros. Foram ainda desenvolvidas algumas ferramentas auxiliares que facilitam a modelagem de uma estrutura flutuante. Estas ferramentas verificam a consistência topológica de uma malha, gerar uma subdivisão gradativa das curvas cortadas e simplificar as novas malhas geradas. É possível também detectar se o modelo possui simetria num determinado plano e realizar, de forma automática, cortes do modelo final para diferentes calados. / [en] This work is related to the PUC-Rio research area of vessel´s designs such as ships and semi-sub platforms. In this research area two softwares have been developed: MG and Sstab. The first is a geometric modeler based on cross sections and also on a mesh generator; the second is a software for the analysis of static and dynamic stability of MG models. This work proposes an integrated environment for modeling, and static and dynamic analysis of vessels. The main advantage of the proposed environment is that it is possible to obtain automatically variants of a specific model in order to achieve a desired configuration, not only in relation to geometry but also concerning the static stability aspect. This environment uses the Lua programming language and it is possible to define global variables to be used as parameters which retrieve or modify modeling values such as length, width, height, and so on. Any model can be parameterized, as a function of user chosen variables, which allows an automatic modeling with the variation of those parameters. There has been also developed some auxiliary tools which help the modeling of floating structures. Those tools verify the topological consistency of a mesh, generate a gradual subdivision of intersected curves and simplify the new generated meshes. They are also able to detect if the model has symmetry in relation to a certain plane, and sections can be automatically obtained according to different draughts.

[pt] Os desafios de estudar formas levaram matemáticos a criar abstrações, em particular através da geometria diferencial. Porém, formas simples como cubos não se adequam a ferramentas diferenciáveis. Este trabalho é uma tentativa de usar avanços recentes da análise, no caso a teoria das distribuições, para estender quantidades diferenciáveis a objetos singulares. Como as distribuições generalizam as funções e permitem derivações infinitas, substituição das parametrizações de subvariedades clássicas por distribuições poderia naturalmente generalizar as subvariedades suaves. Isso nos leva a definir D-imersões. Esse trabalho demonstra que essa formulação, de fato, generaliza as imersões suaves. Extensões para outras classes de subvariedades são discutidas através de exemplos e casos particulares. / [en] The challenge of studying shapes has led mathematicians to create powerful abstract concepts, in particular through Differential Geometry. However, differential tools do not apply to simple shapes like cubes. This work is an attempt to use modern advances of the Analysis, namely Distribution Theory, to extend differential quantities to singular objects. Distributions generalize functions, while allowing infinite differentiation. The substitution of classical immersions, which usually serve as submanifold parameterizations, by distributions might thus naturally generalize smooth immersion. This leads to the concept of D-immersion. This work proves that this formulation actually generalizes smooth immersions. Extensions to non-smooth of immersions are discussed through examples and specific cases.

[pt] Este trabalho apresenta uma nova abordagem para o balanceamento de seções geológicas baseada em modelagem física e simulação numérica. O objetivo principal é introduzir alguns conceitos da Mecânica do Contínuo no processo de restauração geológica, de forma a considerar as propriedades físicas dos materiais geológicos durante a simulação do movimento de um bloco de rocha sobre uma falha. A estratégia adotada utiliza-se de um algoritmo de Relaxação Dinâmica acoplado ao Método dos Elementos Finitos para resolver sistemas de equações, com condições de contorno específicas para a movimentação do bloco sobre a falha.Foi adotado como ambiente de desenvolvimento um sistema de balanceamento de seções geológicas composto por um conjunto de transformações geométricas comuns na abordagem clássica do problema. O sistema utiliza uma tecnologia de modelagem geométrica baseada em uma estrutura de dados que permite a representação topológica completa de uma subdivisão planar.A simulação numérica do balanceamento de seções geológicas proposta é implementada dentro desse ambiente e integra três módulos distintos: um módulo de pré- processamento no qual os dados requeridos podem ser facilmente gerados, um módulo de análise onde o método de Relaxação Dinâmica foi implementado e, finalmente, um módulo de pósprocessamento em que podem ser visualizados os resultados obtidos da simulação numérica. Considera-se ainda a natureza palinspática do problema de restauração através de uma interface gráfica amigável do ponto de vista do usuário. Neste sentido, foi realizada uma reorganização completa da interface gráfica e das classes de atributos geológicos associados às entidades topológicas (linhas e regiões) da seção geológica. Esta organização teve dois objetivos: o primeiro, implementar um processo gráfico baseado em uma árvore de decisões para o gerenciamento das tarefas do balanceamento, que envolve passos arbitrários de tentativa e erro, e, o segundo, possibilitar a implementação da simulação numérica dentro do processo de balanceamento.As idéias propostas podem ser consideradas como o primeiro passo para o desenvolvimento de um sistema de balanceamento de seções geológicas, cujas medidas de deformação representem de forma mais aproximada o comportamento mecânico das rochas, além de ser mais automatizado, o que sugere futuramente a implementação de um sistema tridimensional, no qual seja menos exigida a interação com o usuário. / [en] This work presents a new approach for the restoration of geological cross-sections that is based on physical modeling and numerical simulation. The main purpose is to introduce Continuum Mechanics concepts into the geological restoration process in order to consider physical properties of the materials during the simulation of the movement of a rock block along a fault. The adopted strategy uses a dynamic relaxation algorithm to solve the equation system that arises from the numerical simulation based on the Finite Element Method, together with some specific boundary conditions to represent the movement of the rock block over the fault.As development environment, a cross-section restoration system was adopted, composed by a group of usual geometric transformations from the classical approach of the problem. This system adopts a geometric modeling technology based on a data structure that is capable of completely representing the topology of a planar subdivision. The proposed numerical simulation is implemented inside this system and integrates with three different modules: a pre-processing module, where the required input data can be easily generated; an analysis module, in which the dynamic relaxation method has been implemented; and a post- processing module, where the results of the numerical simulation can be viewed. The palinspatic nature of the restoration problem is taken into account by means of a user-friendly graphics interface that was specifically designed for the system. The graphics interface and the geological attribute classes were completely re-organized with two purposes. First, to implement a graphical interface based on a decision tree to manage user tasks involved in the restoration process, which includes trial- and-error steps. Second, to provide support for the implementation of numerical simulation in the restoration process.The ideas proposed herein can be considered as a first step towards a complete geological cross-section restoration system in which more consistent deformation measures can be incorporated into the governing equations to better represent the mechanical behavior of the rocks, and is also an expansion of the presented system to a three-dimensional environment, currently under investigation.

[pt] Muitas são as aplicações onde se faz necessário transmitir modelos 3D via Internet. Entre eles merece destaque o compartilhamento de dados entre ambientes colaborativos situados em diferentes localidades. Este compartilhamento permite a sua análise e visualização, porém restrições de largura de banda da rede (Internet/Intranet) assim como o custo de armazenamento limitam a complexidade do modelo a ser transmitido/armazenado. As malhas geométricas são utilizadas em diferentes áreas da computação gráfica e visualização científica, como exemplos podem se citar elementos finitos os quais são utilizados em modelos CAD, jogos, modelagem de terrenos, geometria computacional entre outros. Devido à grande complexidade das malhas, estas são processadas por meios computacionais usando alguma estrutura de dados que represente da melhor forma o modelo em questão. A principal motivãção deste trabalho é verificar a viabilidade do uso de uma nova estrutura de dados para representar e comprimir malhas irregulares (triângulos e quadrângulos). Nesta nova abordagem será apresentada a estrutura de dados CHalfEdge. Ela usa os conceitos e idéias da representação HalfEdge e esta por sua vez possui um baixo custo de armazenamento e mantém um alto poder de expressão. Neste trabalho é desenvolvido tambem um algoritmo de compressão de malhas triangulares e/ou quadrangulares com suporte a alças. Este novo algoritmo proposto é uma extensão da compressão de malhas triangulares EdgeBreaker. / [en] Many applications need to transmit 3D models over the Internet, among those data sharing between collaborative environments situated in different locations. Those data sharing aim to analyze and visualize them but bandwidth constraints and storage costs limit the complexity of models than can be transmitted/stored. Polygonal meshes are used in different areas of Computer Graphics and Scientific Visualization. For instance, finite elements and boundary representations are used in CAD models, games, terrain modelling, etc. Due the great complexity of those meshes, they must be represented by a specific data structure that suits them. The main motivation of this work is to verify the feasibility of the use of a new data structure to represent and to compress irregular meshes (triangles and quads). It is introduced the CHalfEdge data structure based on the ideas of the HalfEdge data structure, which are used to represent models by boundary representation. In this work it is also proposed a new algorithm to compress and decompress irregulars meshes with genus, this new algorithm is an extension of the EdgeBreaker compression for regular meshes.