Various data structures have been proposed for representing the connectivity of manifold triangle meshes. For example, the Extended Corner Table (ECT) stores V+6T references, where V and T respectively denote the vertex and triangle counts. ECT supports Random Access and Traversal (RAT) operators at Constant Amortized Time (CAT) cost. We propose two novel variations of ECT that also support RAT operations at CAT cost, but can be used to represent and process Simplicial 2-Complexes (S2Cs), which may represent star-connecting, non-orientable, and non-manifold triangulations along with dangling edges, which we call sticks. Vlist stores V+3T+3S+3(C+S-N) references, where S denotes the stick count, C denotes the number of edge-connected components and N denotes the number of star-connecting vertices. Ering stores 6T+3S+3(C+S-N) references, but has two advantages over Vlist: the Ering implementation of the operators is faster and is purely topological (i.e., it does not perform geometric queries). Vlist and Ering representations have two principal advantages over previously proposed representations for simplicial complexes: (1) Lower storage cost, at least for meshes with significantly more triangles than sticks, and (2) explicit support of side-respecting traversal operators which each walks from a corner on the face of a triangle t across an edge or a vertex of t, to a corner on a faces of a triangle or to an end of a stick that share a vertex with t, and this without ever piercing through the surface of a triangle.

Image coding is studied, with the work consisting of two distinct parts. Each part focuses on different coding paradigm. The first part of the research examines subband coding of images. An optimization-based method for the design of high-performance separable filter banks for image coding is proposed. This method yields linear-phase perfect-reconstruction systems with high coding gain, good frequency selectivity, and certain prescribed vanishing-moment properties. Several filter banks designed with the proposed method are presented and shown to work extremely well for image coding, outperforming the well-known 9/7 filter bank (from the JPEG-2000 standard) in most cases. Several families of perfect reconstruction filter banks exist, where the filter banks in each family have some common structural properties. New filter banks in each family are designed with the proposed method. Experimental results show that these new filter banks outperform previously known filter banks from the same family. The second part of the research explores normal meshes as a tool for image coding, with a particular interest in the normal-mesh-based image coder of Jansen, Baraniuk, and Lavu. Three modifications to this coder are proposed, namely, the use of a data-dependent base mesh, an alternative representation for normal/vertical offsets, and a different scan-conversion scheme based on bicubic interpolation. Experimental results show that our proposed changes lead to improved coding performance in terms of both objective and subjective image quality measures.

Title: Correspondence Problem in Geometric Morphometrics Tasks Author: Václav Krajíček Department / Institute: Department of Software and Computer Science Education Supervisor of the doctoral thesis: RNDr. Josef Pelikán Supervisor's e-mail address: pepca@cgg.mff.cuni.cz Abstract: Shape analysis in physical anthropology, biomedicine, and related disci- plines is mostly done using landmarks or by measuring distances. New techno- logical advancements allow the digitization of object's appearance in the form of triangular meshes or volume images. These digital images are especially beneficial in the cases when landmarks cannot be used to effectively describe the shape. In order to statistically analyze shape in a sample of observations, which are represented by these modalities, correspondence has to be found. Registration is a crucial tool in mapping the shape representations into a common space where correspondence is found by nearest neighbor principle in the case of triangular meshes or by overlaps in the case of volume images. B- spline based non-rigid registration is chosen because of its versatility, relative speed and ability to handle both meshes and volume images. Experiments were also performed with other alternatives - Thin-plate splines and Coherent point drift. The algorithm was modified to handle...

This work describes a method based on three stages for reconstructing a model from a given set of scanned meshes obtained from 3D scanners. Meshes scanned from different scanner s view points have their representation in local coordinate systems. Therefore, for final model reconstruction, an alignment of the meshes is required. The most popular algorithm for cloud data registration is the ICP algorithm. However, ICP requires an initial estimate of mesh alignment, which is, many times, done manually. To automate this process, this work uses a surface representation called spin-images to identify overlap areas between the meshes and to estimate their alignment. After this initial registration, the alignment is refined by the ICP algorithm, and finally the model is reconstructed using a method called VRIP. / Fundação de Amparo a Pesquisa do Estado de Alagoas / Este trabalho descreve um método baseado em três etapas para reconstrução de modelos a partir de malhas capturadas de scanners 3D. Malhas obtidas a partir de diferentes pontos de visão de um scanner têm sua representação em sistemas de coordenadas local. Portanto, para a reconstrução final do modelo, é necessário realizar um alinhamento dessas malhas, ou registro. O algoritmo mais famoso para realizar registro de nuvens de pontos é o algoritmo ICP. Porém, um dos requisitos desse algoritmo é uma estimativa inicial do alinhamento das malhas, que muitas vezes é feita manualmente. Para automatizar esse processo, este trabalho utiliza descritores spin-image para identificar regiões de sobreposição entre as malhas e estimar seus alinhamentos. Após este registro inicial, o alinhamento é refinado através do algoritmo ICP, e finalmente o modelo é reconstruído usando uma técnica chamada VRIP.

[pt] A visualização volumétrica é uma importante técnica para a exploração de dados tridimensionais complexos, como, por exemplo, o resultado de análises numéricas usando o método dos elementos finitos. A aplicação eficiente dessa técnica a malhas não-estruturadas tem sido uma importante área de pesquisa nos últimos anos. Há dois métodos básicos para a visualização dos dados volumétricos: extração de superfícies e renderização direta de volumes. Na primeira, iso-superfícies de um campo escalar são extraídas explicitamente. Na segunda, que é a utilizada neste trabalho, dados escalares são classificados a partir de uma função de transferência, que mapeia valores do campo escalar em cor e opacidade, para serem visualizados. Com a evolução das placas gráficas (GPU) dos computadores pessoais, foram desenvolvidas novas técnicas para visualização volumétrica interativa de malhas não-estruturadas. Os novos algoritmos tiram proveito da aceleração e da possibilidade de programação dessas placas, cujo poder de processamento cresce a um ritmo superior ao dos processadores convencionais (CPU). Este trabalho avalia e compara dois algoritmos para visualização volumétrica de malhas não-estruturadas, baseados em GPU: projeção de células independente do observador e traçado de raios. Adicionalmente, são propostas duas adaptações dos algoritmos estudados. Para o algoritmo de projeção de células, propõe-se uma estruturação dos dados na GPU para eliminar o alto custo de transferência de dados para a placa gráfica. Para o algoritmo de traçado de raios, propõe-se fazer a integração da função de transferência na GPU, melhorando a qualidade da imagem final obtida e permitindo a alteração da função de transferência de maneira interativa. / [en] Volume visualization is an important technique for the exploration of threedimensional complex data sets, such as the results of numerical analysis using the finite elements method. The efficient application of this technique to unstructured meshes has been an important area of research in the past few years. There are two basic methods to visualize volumetric data: surface extraction and direct volume rendering. In the first, the iso-surfaces of the scalar field are explicitly extracted. In the second, which is the one used in this work, scalar data are classified by a transfer function, which maps the scalar values to color and opacity, to be visualized. With the evolution of personal computer graphics cards (GPU), new techniques for volume visualization have been developed. The new algorithms take advantage of modern programmable graphics cards, whose processing power increases at a faster rate than the one observed in conventional processors (CPU). This work evaluates and compares two GPU- based algorithms for volume visualization of unstructured meshes: view- independent cell projection (VICP) and ray-tracing. In addition, two adaptations of the studied algorithms are proposed. For the cell projection algorithm, we propose a GPU data structure in order to eliminate the high costs of the CPU to GPU data transfer. For the raytracing algorithm, we propose to integrate the transfer function in the GPU, which increases the quality of the generated image and allows to interactively change the transfer function.

Cette thèse aborde différents aspects de la résolution numérique des Equations aux Dérivées Partielles.Le premier chapitre est consacré à l'étude de la méthode Mixed High-Order (MHO). Il s'agit d'une méthode mixte de dernière génération permettant d'obtenir des approximations d'ordre arbitraire sur maillages généraux. Le principal résultat obtenu est l'équivalence entre la méthode MHO et une méthode primale de type Hybrid High-Order (HHO).Dans le deuxième chapitre, nous appliquons la méthode MHO/HHO à des problèmes issus de la mécanique des fluides. Nous considérons d'abord le problème de Stokes, pour lequel nous obtenons une discrétisation d'ordre arbitraire inf-sup stable sur maillages généraux. Des estimations d'erreur optimales en normes d'énergie et L2 sont proposées. Ensuite, nous étudions l'extension au problème d'Oseen, pour lequel on propose une estimation d'erreur en norme d'énergie où on trace explicitement la dépendance du nombre de Péclet local.Dans le troisième chapitre, nous analysons la version hp de la méthode HHO pour le problème de Darcy. Le schéma proposé permet de traiter des maillages généraux ainsi que de faire varier le degré polynomial d'un élément à l'autre. La dépendance de l'anisotropie locale du coefficient de diffusion est tracée explicitement dans l'analyse d'erreur en normes d'énergie et L2.La thèse se clôture par une ouverture sur la réduction de problèmes de diffusion à coefficients variables. L'objectif consiste à comprendre l'impact du choix de la formulation (mixte ou primale) utilisée pour la projection sur l'espace réduit sur la qualité du modèle réduit. / This Ph.D. thesis deals with different aspects of the numerical resolution of Partial Differential Equations.The first chapter focuses on the Mixed High-Order method (MHO). It is a last generation mixed scheme capable of arbitrary order approximations on general meshes. The main result of this chapter is the equivalence between the MHO method and a Hybrid High-Order (HHO) primal method.In the second chapter, we apply the MHO/HHO method to problems in fluid mechanics. We first address the Stokes problem, for which a novel inf-sup stable, arbitrary-order discretization on general meshes is obtained. Optimal error estimates in both energy- and L2-norms are proved. Next, an extension to the Oseen problem is considered, for which we prove an error estimate in the energy norm where the dependence on the local Péclet number is explicitly tracked.In the third chapter, we analyse a hp version of the HHO method applied to the Darcy problem. The resulting scheme enables the use of general meshes, as well as varying polynomial orders on each face.The dependence with respect to the local anisotropy of the diffusion coefficient is explicitly tracked in both the energy- and L2-norms error estimates.In the fourth and last chapter, we address a perspective topic linked to model order reduction of diffusion problems with a parametric dependence. Our goal is in this case to understand the impact of the choice of the variational formulation (primal or mixed) used for the projection on the reduced space on the quality of the reduced model.

As análises de erros são conduzidas antes de qualquer projeto a ser desenvolvido. A necessidade do conhecimento do comportamento do erro numérico em malhas estruturadas e não-estruturadas surge com o aumento do uso destas malhas nos métodos de discretização. Desta forma, o objetivo deste trabalho foi criar uma metodologia para analisar os erros de discretização gerados através do truncamento na Série de Taylor, aplicados às equações de Poisson e de Advecção-Difusão estacionárias uni e bidimensionais, utilizando-se o Método de Volumes Finitos em malhas do tipo Voronoi. A escolha dessas equações se dá devido a sua grande utilização em testes de novos modelos matemáticos e função de interpolação. Foram usados os esquemas Central Difference Scheme (CDS) e Upwind Difference Scheme(UDS) nos termos advectivos. Verificou-se a influência do tipo de condição de contorno e a posição do ponto gerador do volume na solução numérica. Os resultados analíticos foram confrontados com resultados experimentais para dois tipos de malhas de Voronoi, uma malha cartesiana e outra triangular comprovando a influência da forma do volume finito na solução numérica obtida. Foi percebido no estudo que a discretização usando o esquema CDS tem erros menores do que a discretização usando o esquema UDS conforme literatura. Também se percebe a diferença nos erros em volumes vizinhos nas malhas triangulares o que faz com que não se tenha uma uniformidade nos gráficos dos erros estudados. Percebeu-se que as malhas cartesianas com nó no centróide do volume tem menor erro de discretização do que malhas triangulares. Mas o uso deste tipo de malha depende da geometria do problema estudado / The analyses of errors are conducted before any project to be developed. The necessity of studying the behavior of the numerical error on structured and unstructured grids comes up with the increasing use of these methods of discretization meshes. Thus, the objective was to create a methodology to analyze the errors generated by discretization of the truncation in the Taylor series, applied to the equations of Poisson and Advection-Diffusion stationary and uni and bi-dimensional, using the Finite Volume Method on Voronoi mesh. The choice of these equations is due to its wide use in testing new mathematical models and interpolation function. The schemes used were the Central Difference Scheme (CDS) and the Upwind Difference Scheme (UDS) in the advective terms. There was the influence of boundary condition and position of the generator in the numerical solution of the volume. The analytical results were compared with experimental results for two types of Voronoi meshes, a Cartesian mesh and a triangular shape showing the influence of finite volume in the numerical solution obtained. It was perceived that the discretization in the study using the CDS scheme has smaller errors than the discretization scheme using the UDS as literature. Also notice the difference in the errors in neighboring volumes in triangular meshes which means that there has been no uniformity in the graphs of errors studied. It was noticed that the Cartesian meshes with node at the centroid of the volume is smaller than discretization error triangular meshes. But using this type of meshes depends on the geometry of the problem studied

[pt] O mapeamento manual de falhas em dados sísmicos tridimensionais é uma tarefa que consome muito tempo do intérprete. Uma grande quantidade de atributos sísmicos tem sido proposta para realçar medidas de descontinuidades associadas com as falhas. Entretanto, as falhas vistas através desses atributos aparecem mais como tendências do que como superfícies contínuas bem definidas, o que torna difícil a automatização da construção de modelos de falhas. Esta tese explora técnicas de Aprendizado Competitivo aplicadas aos problemas de extração e visualização de falhas em dados sísmicos. A estratégia proposta parte de um atributo de falha previamente calculado e consiste de três etapas. Na primeira, os dados tridimensionais uniformemente amostrados do atributo de falha são convertidos em um grafo com uso do algoritmo de aprendizado competitivo Growing Neural Gas. Na segunda etapa, o grafo sofre um processo de segmentação de forma a extrair um conjunto de subgrafos, cada um compatível com uma superfície de falha. Na terceira etapa, é utilizado o algoritmo Malhas Neurais Abertas para construir uma malha triangular para cada uma das superfícies identificadas. Malhas Neurais Abertas é um algoritmo de Aprendizado Competitivo que é proposto nesta tese, o qual constrói uma malha a partir de uma função de probabilidades com topologia de uma superfície aberta sem buracos. Exemplos com dados bidimensionais e tridimensionais, sintéticos e reais, são apresentados. Outra aplicação de Aprendizado Competitivo introduzida nesta tese é a geração de malhas geológicas, isto é, malhas que podem ser utilizadas na simulação do comportamento de fluidos em subsuperfície. / [en] Manual fault mapping from 3D seismic data is a time-consuming task. A plethora of seismic attributes has been proposed to enhance the discontinuity measures associated with faults. However, faults viewed through these attributes appear more like trends than well-defined, continuous surfaces, posing obstacles to the automation of the fault modeling process. This thesis explores the use of Competitive Learning techniques in fault extraction and visualization. The proposed strategy starts with a pre-computed fault attribute and consists of three steps. In the first, the uniformly sampled 3D fault attribute data are converted into a graph using Growing Neural Gas, a Competitive Learning algorithm. In the second step, the graph is submitted to a segmentation process in order to extract a set of subgraphs, each one compatible with a fault surface. In the third step, the Open Neural Meshes algorithm is used to build a triangulated mesh for each previously identified surface. Open Neural Meshes is a Competitive Learning algorithm proposed in this thesis, which builds a mesh from a probability function with no-hole open surface topology. Examples with 2D and 3D, synthetic and real data are presented. Another Competitive Learning application introduced in this thesis is the generation of geologic meshes. These meshes can be used to simulate fluid flows in subsurface reservoirs.

Este trabalho apresenta uma análise comparativa com três tipos de ligações entre paredes de alvenaria estrutural submetidas a ações verticais. O primeiro tipo de ligação é feito através de amarração direta de paredes de alvenaria. O segundo por amarração indireta solidarizada por telas metálicas e o terceiro, também com amarração indireta, porém, enrijecida por grampos metálicos ancorados em furos grauteados. O estudo é baseado em resultados obtidos por meio de um programa experimental realizado no laboratório de estruturas da EESC-USP. Os modelos utilizados são paredes em formato H, com cinco fiadas, em escala reduzida 1:3, os quais foram propostos por Capuzzo Neto (2005). A partir da análise experimental é obtida a resistência ao cisalhamento da interface no plano vertical de ligação entre a parede central e o flange todos os modelos ensaiados. Conclui-se que os modelos com amarração direta possuem maiores resistências ao cisalhamento, o que reforça o fenômeno da interação de paredes submetidas a ações verticais, além de apresentarem forma de ruptura caracterizada como frágil. Os modelos com amarração indireta, tanto com telas quanto com grampos, possuem resistências ao cisalhamento aproximadamente igual a 60% da encontrada para amarração direta, contudo, apresentam ruptura dúctil, com destaque para a ligação com grampos. / This work presents a comparative analysis of three types of connections between structural masonry walls under vertical loads. The first type is a set of running bond interconnected masonry walls. The second connection is obtained by means of steel meshes and the third, also stack bond, is hardened by metallic staples anchored in grouted holes. The study is based on an experimental program carried out in the laboratory of structures of the EESC-USP. The test specimens are H shaped third scale walls, with five courses, as proposed by Capuzzo Neto (2005). The experimental analysis allows for the evaluation of the shear strength of the vertical interface between the central wall and the flanges. The study shows that the models with running bond provide the largest shear strength, which corroborates the phenomenon of the walls’ interaction under vertical loads, and a fragile failure type. Both the stack bond specimens present a shear strength of roughly 60% of the running bond type, with ductile failure, specially for the stapled connection.

O objetivo desta dissertação de mestrado é estudar técnicas numéricas para simular escoamentos incompressíveis multifásicos e implementar uma ferramenta computacional utilizando malhas hierárquicas e discretizações por diferenças finitas. São apresentados a formulação matemática e o desenvolvimento do método numérico, levando em consideração o caráter multifásico do escoamento. Foi adotado o modelo de força superficial contínua e a representação da interface foi feita pelo método de acompanhamento de fronteira. São expostos todos os testes realizados durante o desenvolvimento da ferramenta para checar cada etapa do método. Finalmente, testes visando verificar o código foram feitos e os resultados obtidos foram considerados satisfatórios para a verificação da ferramenta aqui desenvolvida. / The objective of this masters degree essay is to study numerical techniques to simulate incompressible multiphase flows and to implement a computational tool using hierachical meshes and discretizations by finite diferences. We introduce the mathematical formulation and the development of the numerical method, for the multiphase flow problem. A continuum surface force model is employed with the interface representation by the front tracking method. We show all tests performed to verify each stage of the methods development. Finally, results obtained in classical benchmark flow tests show good agreement with previous published results, corroborating the validity of this newly developed numerical tool.