[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] Fenômenos de propagação de fraturas e fragmentação em sólidos podem ser descritos por Modelos de Zona Coesiva e simulados com o Método dos Elementos Finitos. Entre as abordagens computacionais de recente interesse para a representação de fraturas em malhas de elementos finitos, encontram-se as baseadas em elementos coesivos. Nelas, o comportamento de fraturas é representado por elementos coesivos inseridos nas interfaces entre elementos volumétricos da malha original. Os modelos de elementos coesivos podem ser classificados como intrínsecos ou extrínsecos. Modelos intrínsecos requerem elementos coesivos pré-inseridos em todas as interfaces volumétricas passíveis de fraturas. Por outro lado, modelos extrínsecos requerem que elementos coesivos sejam inseridos de forma adaptativa, apenas onde e quando necessários. Porém, a representação de malhas tradicional (elementos e nós) não é suficiente para tratar malhas adaptativas eficientemente, o que faz necessário um suporte topológico apropriado. Em geral, modelos coesivos de fratura também requerem um alto nível de refinamento de malha, para que resultados precisos sejam obtidos. Isso implica em um consumo de memória e processamento que pode ser proibitivo a estações de trabalho tradicionais. Assim, ambientes paralelos tornam-se importantes na solução de problemas de fraturas. Entretanto, devido às dificuldades de paralelização de modelos extrínsecos, as abordagens existentes utilizam modelos intrínsecos ou implementam simulações extrínsecas baseadas em elementos coesivos pré-inseridos ou representados como atributos de elementos volumétricos. Com o objetivo de viabilizar a simulação de fraturas e fragmentação extrínsecas em grandes modelos de forma simples e eficiente, esta tese propõe o sistema ParTopS, um suporte topológico em paralelo para malhas de elementos finitos em análises dinâmicas de fratura e fragmentação. Em especial, é apresentada uma representação compacta e eficiente de malhas de fraturas distribuídas. Elementos coesivos são representados explicitamente e tratados como elementos regulares da malha. Com base na representação de malha distribuída, propõe-se um algoritmo paralelo escalável para a inserção adaptativa de elementos coesivos em malhas bidimensionais e tridimensionais. Operações topológicas simétricas são exploradas para reduzir a comunicação entre partições de malha. O sistema ParTopS foi empregado na paralelização de simulações sequenciais extrínsecas existentes. A escalabilidade e a corretude do suporte topológico em paralelo são demonstradas através de experimentos computacionais realizados em um ambiente massivamente paralelo. Os resultados alcançados mostram que o sistema ParTopS pode ser aplicado de forma eficaz para viabilizar simulações de grandes modelos. / [en] Fracture propagation and fragmentation phenomena in solids can be described by Cohesive Zone Models and simulated with the Finite Element Method. Among the computational approaches of recent interest for fracture representation in finite element meshes are those based on cohesive elements. In those approaches, fracture behavior is represented by cohesive elements inserted at the interfaces between volumetric (bulk) elements of the original mesh. Cohesive element models can be classified into intrinsic or extrinsic. Intrinsic models require pre-inserted cohesive elements at every volumetric interface in which fracture is allowed to happen. On the other hand, extrinsic models require that cohesive elements be adaptively inserted, wherever and whenever necessary. However, the traditional mesh representation (elements and nodes) is not sufficient for handling adaptive meshes, which makes an appropriate topological support necessary. In general, cohesive models of fracture also require a high level of mesh refinement near crack tips, such that accurate results can be achieved. This implies in memory and processor consumption that may be prohibitive for traditional workstations. Thus, parallel environments become important for the solution of fracture problems. However, due to the difficulties for the parallelization of extrinsic models, the existing approaches use intrinsic models or implement extrinsic simulations based on pre-inserted cohesive elements or cohesive elements represented as attributes of volumetric elements. In order to allow fracture and fragmentation simulations of large models in a simple and efficient way, this thesis proposes the ParTopS system, a parallel topological support for finite element meshes in dynamic fracture and fragmentation analyses. Specifically, a compact and efficient representation of distributed fracture meshes is presented. Cohesive elements are explicitly represented and treated as regular elements in the mesh. Based on the distributed mesh representation, we propose a scalable parallel algorithm for adaptive insertion of cohesive elements in both bidimensional and tridimensional meshes. Symmetrical topological operations are exploited in order to reduce communication among mesh partitions. The ParTopS system has been employed in order to parallelize existing serial extrinsic simulations. The scalability and correctness of the parallel topological support is demonstrated through computational experiments executed on a massively parallel environment. The achieved results show that ParTopS can be effectively applied in order to enable simulations of large models.

[pt] Pesquisas na área de estrutura de dados são fundamentais para aumentar a generalidade e eficiência computacional da representacão de modelos geometricos. Neste trabalho, apresentamos duas estruturas de dados topológicas escalonáveis, uma para superfícies triânguladas, chamada CHE (Compact Half--Edge), e outra para malhas de tetraedros, chamada CHF (Compact Half--Face). Tais estruturas são compostas de diferentes níveis, que nos possibilitam alterar a quantidade de dados armazenados com objetivo de melhorar sua eficiência computacional. O uso de APIs baseadas no conceito de objeto, e de haran»ca de classes, possibilitam uma interface única para cada função em todos os níveis das estruturas. A CHE e a CHF requerem pouca memória e são simples de implementar já que substituem o uso de ponteiros pelo de contêineres genéricos e regras aritméticas. / [en] Research in data structure area are essential to increase the generality and computational effciency of geometric models` representation. In this work, we present two new scalable topological data structures, one for triangulated surfaces, called CHE (Compact Half { Edge ), and the another for tetrahedral meshes, called CHF (Compact Half { Face ). Such structures are composed of different levels, that enable us to modify the amount of data stored with the objective to improve its computational effciency. The use of APIs based in the object concept and class inheritance, makes possible an unique interface for each function at any level. CHE and CHF requires very few memory and are simple to implement since they substitute the use of pointers by generic containeres and arithmetical rules.

[pt] Séries temporais são ferramentas importantes para análise de eventos que ocorrem em diferentes domínios do conhecimento humano, como medicina, física, meteorologia e finanças. Uma tarefa comum na análise de séries temporais é a busca por eventos pouco frequentes que refletem fatos de interesse sobre o domínio de origem da série. Neste trabalho, buscamos desenvolver técnicas para detecção de eventos raros em séries temporais. Formalmente, uma série temporal A igual a (a1, a2,..., an) é uma sequência de valores reais indexados por números inteiros de 1 a n. Dados dois números, um inteiro t e um real d, dizemos que um par de índices i e j formam um evento-(t, d) em A se, e somente se, 0 menor que j - i menor ou igual a t e aj - ai maior ou igual a d. Nesse caso, i é o início do evento e j o fim. Os parâmetros t e d servem para controlar, respectivamente, a janela de tempo em que o evento pode ocorrer e a magnitude da variação na série. Assim, nos concentramos em dois tipos de perguntas relacionadas aos eventos-(t, d), são elas: - Quais são os eventos-(t, d) em uma série A? - Quais são os índices da série A que participam como inícios de ao menos um evento-(t, d)? Ao longo desse trabalho estudamos, do ponto de vista prático e teórico, diversas estruturas de dados e algoritmos para responder às duas perguntas listadas. / [en] Time series are important tools for the anaylsis of events that occur in different fields of human knowledge such as medicine, physics, meteorology and finance. A common task in analysing time series is to try to find events that happen infrequently as these events usually reflect facts of interest about the domain of the series. In this study, we develop techniques for the detection of rare events in time series. Technically, a time series A equal to (a1, a2,..., an) is a sequence of real values indexed by integer numbers from 1 to n. Given an integer t and a real number d, we say that a pair of time indexes i and j is a (t, d)-event in A, if and only if 0 less than j - i less than or equal to t and aj - ai greater than or equal to d. In this case, i is said to be the beginning of the event and j is its end. The parameters t and d control, respectively, the time window in which the event can occur and magnitude of the variation in the series. Thus, we focus on two types of queries related to the (t, d)-events, which are: - What are the (t, d)-events in a series A? - What are the indexes in the series A which are the beginning of at least one (t, d)-event? Throughout this study we discuss, from both theoretical and practical points of view, several data structures and algorithms to answer the two queries mentioned above.

[pt] Num modelador de sólidos, uma das ferramentas mais poderosas para a criação de objetos tridimensionais de qualquer nível de complexidade geométrica é a aplicação das operações booleanas. Elas são formas intuitivas e populares de combinar sólidos, baseadas nas operações aplicadas a conjuntos. Os tipos principais de operações booleanas comumente aplicadas a sólidos são: união, interseção e diferença. Havendo interesse prático, para garantir que os objetos resultantes possuam a mesma dimensão dos objetos originais, sem partes soltas ou pendentes, o processo de regularização é aplicado. Regularizar significa restringir o resultado de tal forma que apenas volumes preenchíveis possam existir. Na prática, a regularização é realizada classificando-se os elementos topológicos e eliminando-se estruturas de dimensão inferior. A proposta deste trabalho é o desenvolvimento de um algoritmo genérico que permita a aplicação do conjunto de operações booleanas em um ambiente de modelagem geométrica aplicada à análise por elementos finitos e que agregue as seguintes funcionalidades: trabalhar com um número indefinido de entidades topológicas (conceito de Grupo), trabalhar com objetos de dimensões diferentes, trabalhar com objetos non-manifold, trabalhar com objetos não necessariamente poliedrais ou planos e garantir a eficiência, robustez e aplicabilidade em qualquer ambiente de modelagem baseado em representação B-Rep. Neste contexto, apresenta-se a implementação do algoritmo num modelador geométrico pré- existente, denominado MG, seguindo o conceito de programação orientada a objetos e mantendo a interface com o usuário simples e eficiente. / [en] In a solid modeler, one of the most powerful tools to create threedimensional objects with any level of geometric complexity is the application of the Boolean set operations. They are intuitive and popular ways to combine solids, based on the operations applied to sets. The main types of Boolean operations commonly applied to solids are: union, intersection and difference. If there is practical interest, in order to assure that the resulting objects have the same dimension of the original objects, without loose or dangling parts, the regularization process is applied. To regularize means to restrict the result in a way that only filling volumes are allowed. In practice, the regularization is performed classifying the topological elements and removing the lower dimensional structures. The objective of this work is the development of a generic algorithm that allows the application of the Boolean set operations in a geometric modeling environment applied to finite element analysis, which aggregates the following functionalities: working with an undefined number of topological entities (Group concept), working with objects of different dimensions, working with nonmanifold objects, working with objects not necessarily plane or polyhedrical and assuring the efficiency, robustness and applicability in any modeling environment based on B-Rep representation. In this context, the implementation of the algorithm in a pre-existing geometric modeler named MG is presented, using the concept of object oriented programming and keeping the user interface simple and efficient.

[pt] Apresenta-se uma metodologia para modelagem de cascas para elementos finitos definidas em superfícies paramétricas. A metodologia consiste na criação de curvas e geração de malhas sobre os retalhos paramétricos constru´ıdos com base nestas curvas, que também são usadas para a conexão de malhas adjacentes. O modelo final é uma representação de todas as malhas combinadas em uma única estrutura de dados. As ferramentas básicas para geração de tais malhas são uma interface para modelagem de curvas espaciais e os algoritmos geom´etricos para construcão de mapeamentos nos domínios elementares. O problema central em modelagens compostas é o tratamento dado às malhas em superfícies que se interceptam. Um algoritmo capaz de modelar com precisão as curvas de interseção e de ajustar as duas malhas para as novas restrições geradas é apresentado neste trabalho. O algoritmo é parte de um programa completo para modelagem interativa de cascas, que tem sido usado no projeto de grandes sistemas flutuantes para explotação de petróleo em águas profundas. O uso de uma variante da estrutura de dados DCEL, que usa árvores de ordenação espacial para armazenar as entidades topol´ogicas ao invés de listas ou vetores, permite que malhas bastante refinadas sejam reconstru´ıdas em tempo compatível com o trabalho interativo. Estas árvores aceleram os cálculos de interseção necessários à determinação dos pontos de interpolação das curvas de trimming, permitindo tamb´em a reconstrução das malhas usando-se apenas consultas locais. / [en] We present a methodology for modeling finite-element meshes defined on parametric surface patches. The idea is to build curves and generate meshes over the parametric patches built with these curves, which also connect adjacent meshes. The final model is a representation of all meshes combined into a single data structure. The basic tools to generate such meshes are the user interface to model space curves and the geometric algorithms to construct the elementary domain mappings. The main problem in composite modeling is how to handle mesh surfaces that intersect each other. We present an algorithm that models the intersection curves precisely and adjusts both meshes to the newly formed borders. The algorithm is part of an interactive shell modeling program, which has been used in the design of large offshore oil structures. We avoid unacceptable interaction delays by using a variant of the DCEL data structure that stores topological entities in spatial indexing trees instead of linked lists. These trees speed up the intersection computations required to determine points of the trimming curves, and also allows mesh reconstruction using only local queries.

[pt] O Homem constrói estradas desde a Antigüidade. A técnica de projeto utilizada nos dias de hoje é resultado de um longo caminho de aperfeiçoamento que culminou em uma metodologia que procura atingir os melhores índices técnicos ao menor custo de execução possível. Pode-se dizer que esta tecnologia está bem definida desde o início da década de 40. Por sua vez, esta metodologia para ser otimizada requer uma quantidade enorme de cálculos que só podem ser feitos em tempo hábil com a ajuda de um computador. O trabalho a seguir é uma tentativa de se fazer uma aplicação para auxiliar o projetista na tarefa de projeto geométrico de estradas simplesmente implementando uma técnica consagrada há mais de 50 anos. / [en] Mankind has built roads since antiquity. The road planing techniques used today have been obtained throughout improvements which culminated with a methodology that seeks to combine best technical indexes with the lowest possible execution costs. One can say that this technology has been established since the early forties. However, to be optimized, this methodology requires a whole lot of calculation, that can only be afforded with the aid of computers. The research that follows is a system application with the purpose of making the task of road designing easier, by simply implementing techniques that have been known for over 50 years. / [es] El hombre construye carreteras desde la Antigüedad. La técnica de proyecto utilizada hoy em día es resultado de un largo camino de perfeccionamiento que culminó en una metodología que intenta alcanzar los mejores índices técnicos al menor costo de ejecución posible. Se puede decir que esta tecnología está bien definida desde el início de la década de 40. Por outra parte, esta metodología para ser optimizada requiere una cantidad enorme de cálculos que solo pueden ser realizados en tiempo hábil con ayuda de un computador. Este trabajo constituye um intento de realizar una aplicación para auxiliar al projetista en la tarea de proyecto geométrico de carreteras implementando una técnica consagrada há más de 50 años.

[pt] Este trabalho apresenta uma estratégia de modelagem aberta e extensível, desenvolvida em Python, para a criação de modelos de subdivisões planares. A estratégia se dá na forma de uma biblioteca de modelagem geométrica, denominada HETOOL, desenvolvida no trabalho e de uso genérico, baseada na conhecida e consagrada estrutura de dados topológica Half-Edge. Além de considerar os aspectos topológicos e geométricos da modelagem, a estratégia também permite a configuração pelo usuário final dos atributos de simulação. Essas características, somadas à disponibilização do código fonte, conferem um caráter útil e relevante para o desenvolvimento de ferramentas educacionais para modelagem em mecânica computacional. Para demonstrar a aplicabilidade da estratégia proposta, foi desenvolvido um aplicativo, denominado de Finite Element Method Educational Computer Program (FEMEP), que permite a criação de modelos bidimensionais de elementos finitos, com geração de malhas por região, para diversos tipos de simulação de mecânica computacional. O pacote desenvolvido apresenta uma modelagem iterativa e dinâmica que realiza a interseção automática entres os elementos geométricos modelados. O HETOOL oferece várias funcionalidades e facilidades ao usuário, permitindo o uso do pacote mesmo sem o usuário ter conhecimento sobre os conceitos topológicos envolvidos na implementação dessa estrutura de dados. O pacote possibilita a criação e configuração atributos de forma simples e rápida a partir de um arquivo no formato JSON. Essa versatilidade na criação atributos permite a aplicação deste pacote na resolução de vários problemas presentes na engenharia e em outras áreas do meio científico. / [en] This work presents an open and extensible modeling strategy, developed in Python, for creating planar subdivision models. The strategy takes the form of a geometric modeling library called HETOOL, developed in the work and of general use, based on the well-known and renowned Half-Edge topological data structure. In addition to considering the topological and geometric aspects of the modeling, a strategy also allows for an end-user configuration of simulation attributes. These characteristics, added to the availability of the source code, provide a useful and relevant tool for the development of educational tools for modeling computational mechanics. To demonstrate the applicability of the proposed strategy, an application was developed, called the Finite Element Method Educational Computer Program (FEMEP), which allows the creation of two-dimensional finite element models, with mesh generation per region, for various types of mechanics simulation computational. The developed package presents iterative and dynamic modeling that performs an automatic intersection between the modeled geometric elements. HETOOL offers several functions and facilities to the user, allowing the use of the package even without the user having knowledge about the topological concepts involved in the implementation of this data structure. The package makes it possible to create and configure attributes simply and quickly from a file in JSON format. This versatility in creating attributes allows the application of this package to solve several problems present in engineering and in other areas of the scientific environment.