Im Rahmen der Arbeit in der damaligen DFG-Forschungsgruppe ¨Scientific Parallel Computing¨ wurde ein hierarchischer paralleler Netzgenerator fuer das Finite-Elemente- Programmpaket SPC-PM CFD unter dem Namen NETGEN69 entwickelt. Als Programmiersprache wurde seinerzeit - wie auch in den FEM-Programmen selbst - FORTRAN benutzt. Im Rahmen des Teilprojektes B2 im Sonderforschungsbereich 393 bestand nunmehr die Aufgabe, den Netzgenerator in ein objektorientiertes Layout zu fassen und in C++zu implementieren. Die Beschreibung von Ein- und Ausgabedaten kann in [3] nachgelesen werden. Die Form der Eingabedaten hat sich aus Kompatibilitaetsgruenden nicht geaendert und wird auch in Zukunft so beibehalten werden. Auch das der Assemblierung und FEM-Rechnung zuge- wandte Interface wurde vorerst nicht geaendert. Ein Wrapper, der fuer die Generierung der erwarteten Ausgabedaten aus den netzgeneratoreigenen Datenbestaenden sorgt, ist derzeit in Planung. Diese Lösung ist freilich nur voruebergehender Natur; sie ermoeglicht es uns, den Netzgenerator innerhalb der FEM-Bibliotheken zu testen.

Data-dependent triangulation (DDT) based mesh-generation schemes for image representation are studied. A flexible mesh-generation framework and a highly effective mesh-generation method that employs this framework are proposed. The proposed framework is derived from frameworks proposed by Rippa and Garland and Heckbert by making a number of key modifications to facilitate the development of much more effective mesh-generation methods. As the proposed framework has several free parameters, the effects of different choices of these parameters on mesh quality (both in terms of squared error and subjectively) are studied, leading to the recommendation of a particular set of choices for these parameters. A new mesh-generation method is then introduced that employs the proposed framework with these best parameter choices. Experimental results show our proposed mesh-generation method outperforms several competing approaches, namely, the DDT-based incremental scheme proposed by Garland and Heckbert, the COMPRESS scheme proposed by Rippa, and the adaptive thinning scheme proposed by Demaret and Iske. More specifically, in terms of PSNR, our proposed method was found to outperform these three schemes by median margins of 4.1 dB, 10.76 dB, and 0.83 dB, respectively. The subjective qualities of reconstructed images were also found to be correspondingly better. In terms of computational cost, our proposed method was found to be comparable to the schemes proposed by Garland and Heckbert and Rippa. Moreover, our proposed method requires only about 5 to 10% of the time of the scheme proposed by Demaret and Iske. In terms of memory cost, our proposed method was shown to require essentially same amount of memory as the schemes proposed by Garland and Heckbert and Rippa, and orders of magnitude (33 to 800 times) less memory than the scheme proposed by Demaret and Iske. / Graduate

VIEIRA, Rafael Siqueira Telles. Técnicas para geração de malhas de quadriláteros convexos e sua aplicação em reservatórios naturais. 2011. 169 f. Dissertação (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2011. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-07-12T15:46:11Z No. of bitstreams: 1 2011_dis_rstvieira.pdf: 3132905 bytes, checksum: e4b5cfff20b3d685dc1674c91df9babc (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-07-21T15:26:34Z (GMT) No. of bitstreams: 1 2011_dis_rstvieira.pdf: 3132905 bytes, checksum: e4b5cfff20b3d685dc1674c91df9babc (MD5) / Made available in DSpace on 2016-07-21T15:26:34Z (GMT). No. of bitstreams: 1 2011_dis_rstvieira.pdf: 3132905 bytes, checksum: e4b5cfff20b3d685dc1674c91df9babc (MD5) Previous issue date: 2011 / This work describes four methods implemented to achieve a convex quadrilaterization of the two- -dimensional space that may have polygonal lines or holes. Two of these methods, midpoint and ortoquad make use of guide elements, the centroid of a region or the locus of maximum tangent circles inside a geometry, to produce a mesh for the domain. The other two methods, triquad and incremental quadrilatezation use a implicit and explicit triangulation while combining elements in pairs to generate a mesh. All these methods are made through domain decomposition which assure quadrilaterization at the end, since the domain is always partitioned at each iteration. These techniques are compared by a criterion of geometry and topology in order to make clear its advantages and disadvantages and as means of promoting future improvements. The techniques are applied to some samples, including a natural reservoir, in order to view its operation in a real environment or near reality according to the sample used. Also it intends to present throughout this work the requirements, according to the experience with the theme of this author, to develop a technique for quadrilateral mesh generation. / Esta dissertação descreve quatro métodos implementados para realizar uma quadrilaterização convexa do espaço bidimensional que pode conter linhas poligonais ou buracos. Dois destes métodos, ponto médio e ortoquad, utilizam de elementos guia, o baricentro de uma região ou o locus de círculos máximos tangentes e internos a geometria, para produzir uma malha conforme o domínio. Os outros dois, triquad e quadrilaterização incremental, utilizam de uma triangulação explícita e implícita combinando elementos aos pares para realizar a geração da malha. Todas as técnicas são feitas por decomposição de regiões o que garante uma quadrilaterização final, já que o domínio é sempre segmentado a cada iteração. Estas técnicas são comparadas por um critério de geometria e topologia de forma a tornar evidentes suas vantagens e desvantagens assim como promover melhorias futuras. As técnicas são aplicadas a alguns exemplos, incluindo-se um reservatório natural, a fim de exibir seu funcionamento em um ambiente real ou próximo do mesmo, conforme as amostras utilizadas. Também se pretende apresentar ao longo deste trabalho os requisitos necessários, segundo a experiência deste autor com o tema, para o desenvolvimento de uma técnica de geração de malha quadrilateral.

FREITAS, Markos Oliveira. Geração em Paralelo de Malhas Tetraédricas com Fraturas por Decomposição Espacial Binária. 2015. 129 f. Tese (Doutorado em Ciência da Computação)-Universidade Federal do Ceará, Fortaleza, 2015. / Submitted by Vitor Campos (vitband@gmail.com) on 2016-09-27T23:47:57Z No. of bitstreams: 1 2015_tese_mofreitas.pdf: 15114037 bytes, checksum: 7028f6c9f4d930ab2cc67a73f135ff47 (MD5) / Approved for entry into archive by Jairo Viana (jairo@ufc.br) on 2016-09-27T23:51:14Z (GMT) No. of bitstreams: 1 2015_tese_mofreitas.pdf: 15114037 bytes, checksum: 7028f6c9f4d930ab2cc67a73f135ff47 (MD5) / Made available in DSpace on 2016-09-27T23:51:14Z (GMT). No. of bitstreams: 1 2015_tese_mofreitas.pdf: 15114037 bytes, checksum: 7028f6c9f4d930ab2cc67a73f135ff47 (MD5) Previous issue date: 2015 / This work describes a technique for generating three-dimensional tetrahedral meshes using parallel computing, with shared, distributed, or hybrid memory processors. The input for the algorithm is a triangular mesh that models the surface of one of several objects, that might have holes in its interior or internal or boundary cracks. A binary tree structure for spatial partitioning is proposed in this work to recursively decompose the domain in as many subdomains as processes or threads in the parallel system, in which every subdomain has the geometry of a rectangular parallelepiped. This decomposition attempts to balance the amount of work in all the subdomains. The amount of work, known as load, of any mesh generator is usually given as a function of its output size, i.e., the size of the generated mesh. Therefore, a technique to estimate the size of this mesh, the total load of the domain, is needed beforehand. This work uses a refined octree, generated from the surface mesh, to estimate this load, and the decomposition is performed on top of this octree. Once the domain is decomposed, each process/thread generates the mesh in its subdomain by means of an advancing front technique, in such a way that it does not overpass the limits defined by its subdomain, and applies an improvement on it. Some of the processes/threads are responsible for generating the meshes connecting the subdomains, i.e., the interface meshes, in order to generate the whole mesh. This technique presented good speed-up results, keeping the quality of the mesh comparable to the quality of the serially generated mesh. / Este trabalho descreve uma técnica para gerar malhas tridimensionais tetraédricas utilizando computação paralela, com processadores de memória compartilhada, memória distribuída ou memória híbrida. A entrada para o algoritmo é uma malha triangular que modela a superfície de um ou vários objetos, que podem conter buracos no interior ou fraturas internas ou na borda. Uma estrutura em forma de árvore binária de partição espacial é proposta neste trabalho para, recursivamente, decompor o domínio em tantos subdomínios quantos forem os processos ou threads no sistema paralelo, em que cada subdomínio tem a geometria de um paralelepípedo retangular. Esta decomposição tenta equilibrar a quantidade de trabalho em todos os subdomínios. A quantidade de trabalho, conhecida como carga, de qualquer gerador de malha é geralmente dada em função do tamanho da saída do algoritmo, ou seja, do tamanho da malha gerada. Assim, faz-se necessária uma técnica para estimar previamente o tamanho dessa malha, que é carga total do domínio. Este trabalho faz uso de uma octree refinada, gerada a partir da malha de superfície dada como entrada, para estimar esta carga, e a decomposição é feita a partir dessa octree. Uma vez decomposto o domínio, cada processo/thread gera a malha em seu subdomínio por uma técnica de avanço de fronteira, de forma que ela não ultrapasse os limites definidos pelo seu subdomínio, e aplica um melhoramento nela. Alguns dos processos/threads ficam responsáveis por gerar as malhas conectando os subdomínios, ou seja, as malhas de interface, até que toda a malha tenha sido gerada. Esta técnica apresentou bons resultados de speed-up, mantendo a qualidade da malha comparável à qualidade da malha gerada sequencialmente.

Este trabalho apresenta um estudo sobre segmentação de volumes médicos e uma solução para se obter malhas poligonais de pacientes específicos para uso em simulações de cirurgia. Malhas de pacientes específicos são importantes para planejamento de intervenções cirúrgicas e permitem uma melhor visualização de condições patológicas em um paciente, coisa não obtível em malhas geradas artisticamente. Nós analisamos quais são os fatores complicantes para se obter estas malhas de um paciente específico usando apenas imagens médicas obtidas em exames padrões. Para isso, nós revisamos diversos métodos existentes para segmentação de volumes médicos. Isso nos levou a definir os problemas com as técnicas existentes, e a desenvolver um método que não sofra destes problemas, utilizando pouca interação humana e não tendo dependências de mais dados que não o exame do paciente. Nosso alvo para obter malhas especificas foram órgãos de tecido mole, que são um caso especialmente complicado da área, graças a várias questões relacionadas às imagens médicas e à anatomia humana. Atacamos esse problema aplicando modificações geométricas em malhas especiais, que deformam até atingir a forma dos órgãos que se deseja segmentar. Os resultados mostram que nossa técnica conseguiu obter malhas específicas de pacientes a partir de volumes médicos com qualidade superior a de outros algoritmos de mesma classe. Graças a simplicidade do método desenvolvido, nossos resultados são facilmente implementáveis e reproduzidos. / This work presents a study about medical-volume segmentation and a solution to generate patient-specific meshes to use in patient-specific surgery simulations. Patientspecific meshes are useful assets for surgery planning and to allow better visualization of certain pathological conditions of a given patient, which are not obtainable by artistically designed meshes. We analyzed what are the complications to obtain a patient-specific mesh using only standard medical imagery exams. For that, we reviewed several medical volume segmentation techniques. It led us to define the problems within the existing techniques and to develop a method that does not suffer from these problems, with the least possible user interaction or relying on any other data other then the patient exam. Our target for obtaining specific meshes were soft tissue organs, which are a specially complicated case due to various issues related to the medical images and human anatomy. This is accomplished by geometrical operations over special meshes that deform until achieving the shape of the desired organ. Results show that our technique was able to obtain patient-specific meshes from medical images with superior quality than algorithms of the same class. Thanks to the simplicity of the developed approach, its also easy to implement and to reproduce our obtained results.

Este trabalho apresenta um estudo sobre segmentação de volumes médicos e uma solução para se obter malhas poligonais de pacientes específicos para uso em simulações de cirurgia. Malhas de pacientes específicos são importantes para planejamento de intervenções cirúrgicas e permitem uma melhor visualização de condições patológicas em um paciente, coisa não obtível em malhas geradas artisticamente. Nós analisamos quais são os fatores complicantes para se obter estas malhas de um paciente específico usando apenas imagens médicas obtidas em exames padrões. Para isso, nós revisamos diversos métodos existentes para segmentação de volumes médicos. Isso nos levou a definir os problemas com as técnicas existentes, e a desenvolver um método que não sofra destes problemas, utilizando pouca interação humana e não tendo dependências de mais dados que não o exame do paciente. Nosso alvo para obter malhas especificas foram órgãos de tecido mole, que são um caso especialmente complicado da área, graças a várias questões relacionadas às imagens médicas e à anatomia humana. Atacamos esse problema aplicando modificações geométricas em malhas especiais, que deformam até atingir a forma dos órgãos que se deseja segmentar. Os resultados mostram que nossa técnica conseguiu obter malhas específicas de pacientes a partir de volumes médicos com qualidade superior a de outros algoritmos de mesma classe. Graças a simplicidade do método desenvolvido, nossos resultados são facilmente implementáveis e reproduzidos. / This work presents a study about medical-volume segmentation and a solution to generate patient-specific meshes to use in patient-specific surgery simulations. Patientspecific meshes are useful assets for surgery planning and to allow better visualization of certain pathological conditions of a given patient, which are not obtainable by artistically designed meshes. We analyzed what are the complications to obtain a patient-specific mesh using only standard medical imagery exams. For that, we reviewed several medical volume segmentation techniques. It led us to define the problems within the existing techniques and to develop a method that does not suffer from these problems, with the least possible user interaction or relying on any other data other then the patient exam. Our target for obtaining specific meshes were soft tissue organs, which are a specially complicated case due to various issues related to the medical images and human anatomy. This is accomplished by geometrical operations over special meshes that deform until achieving the shape of the desired organ. Results show that our technique was able to obtain patient-specific meshes from medical images with superior quality than algorithms of the same class. Thanks to the simplicity of the developed approach, its also easy to implement and to reproduce our obtained results.

Dans cette thèse, nous nous sommes intéressés au problème de l'extraction d'une surface à partir de la représentation volumique d'un objet. Dans ce but, nous nous sommes concentrés sur les méthodes de division spatiale. Ces approches divisent le volume afin de construire une approximation par morceaux de la surface de l'objet. L'idée générale consiste à faire des approximations surfaciques locales qui seront ensuite combinées pour extraire une surface unique représentant l'objet. Les approches basées sur l'algorithme " Marching Cubes " (MC) présentent des défaut par rapport à la qualité et l'adaptativité de la surface produite. Même si une considérable quantité d'améliorations ont été apportées à la méthode originale, la plus grande partie des algorithmes fournissent la solution à un ou deux défauts mais n'arrivent pas à surmonter toutes ses limitations.Les méthodes duales sont plus adaptées pour utiliser un échantillonnage adaptatif sur le volume d'intérêt. Ces méthodes reposent sur la génération de surfaces duales à celles construites par MC ou se basent sur des grilles duales. Elles construisent des maillages moins denses et en même temps capables de mieux approcher les détails de l'objet. De plus, des améliorations récentes garantissent que les maillages extraits ont de bonnes propriétés topologiques et géométriques.Nous avons étudié les caractéristiques spécifiques des objets volumiques par rapport à leur géométrie et à leur topologie. Nous avons exploré l'état de l'art sur les approches de division spatiale afin d'identifier leurs avantages et leurs inconvénients ainsi que les implications de leur utilisation sur des objets volumiques. Nous avons conclu qu'une approche duale était la mieux adaptée pour obtenir un bon compromis entre qualité du maillage et qualité de l'approximation. Dans un second temps, nous avons proposé et développé un pipeline de génération de surfaces basé sur une combinaison d'une approche duale et de la recherche de composantes connexes n-dimensionnels pour mieux reproduire la topologie et la géométrie des objets originels. Dans un troisième temps, nous avons présenté une extension "out-of-core" de notre chaîne de traitements pour l'extraction des surfaces à partir de grands volumes. Le volume est divisé pour générer des morceaux de surface de manière indépendante et garde l'information nécessaire pour les connecter afin de produire une surface unique topologiquement correcte.L'approche utilisée permet de paralléliser le traitement pour accélérer l'obtention de la surface. Les tests réalisés ont permis de valider la méthode sur des données volumiques massives. / In this document, we have been interested in the surface extraction from the volumetric representation of an object. With this objective in mind, we have studied the spatial subdivision surface extraction algorithms. This approaches divide the volume in order to build a piecewise approximation of the surface. The general idea is to combine local and simple approximations to extract a complete representation of the object's surface.The methods based on the Marching Cubes (MC) algorithm have problems to produce good quality and to handle adaptive surfaces. Even if a lot of improvements to MC have been proposed, these approaches solved one or two problems but they don't offer a complete solution to all the MC drawbacks. Dual methods are more adapted to use adaptive sampling over volumes. These methods generate surfaces that are dual to those generated by the Marching Cubes algorithm or dual grids in order to use MC methods. These solutions build adaptive meshes that represent well the features of the object. In addition, recent improvements guarantee that the produced meshes have good geometrical and topological properties.In this dissertation, we have studied the main topological and geometrical properties of volumetric objects. In a first stage, we have explored the state of the art on spatial subdivision surface extraction methods in order to identify theirs advantages, theirs drawbacks and the implications of theirs application on volumetric objects. We have concluded that a dual approach is the best option to obtain a good compromise between mesh quality and geometrical approximation. In a second stage, we have developed a general pipeline for surface extraction based on a combination of dual methods and connected components extraction to better capture the topology and geometry of the original object. In a third stage, we have presented an out-of-core extension of our surface extraction pipeline in order to extract adaptive meshes from huge volumes. Volumes are divided in smaller sub-volumes that are processed independently to produce surface patches that are later combined in an unique and topologically correct surface. This approach can be implemented in parallel to speed up its performance. Test realized in a vast set of volumes have confirmed our results and the features of our solution.

Apresenta-se um pré-processador para análise de pavimentos de edifícios via método dos elementos finitos desenvolvido como um aplicativo do ambiente Windows. O programa é interativo, permitindo identificar problemas de imediato na criação do modelo a ser estudado. Possui recursos gráficos básicos para a definição geométrica da estrutura. A saída de dados é programável para que o pré-processador não se prenda a um só programa de cálculo. Assim, os mesmos dados de uma estrutura podem ser analisados por diferentes programas de cálculo o que possibilita a escolha do programa mais adequado, dependendo do tipo de análise desejado. O aplicativo tem recursos para definir elementos finitos de barra e placa. Como o número desses elementos normalmente é grande, eles são gerados de uma forma automatizada. / lt is presenting a Windows preprocessar for building slab analysis by Finite Element Method. lt is an interactive program, allowing problems to be identified while the model is generated. It has graphical resources to define the structure. The program output is defined by the user; therefore it is possible to use the preprocessar with many other finite element programs. This allows the engineer to choose the appropriate program depending on the kind of analysis is wanted. The program can define frame and shell finite elements. As slabs usually need large numbers of these elements to be properly analyzed, they are generated using automatic meshing.

Estruturas de dados (ED) topológicas oferecem diversas vantagens quando se deseja executarumadeformação sobreumamalha. Essas EDs permitem movimentar os nós da malha sem modificar sua topologia, são relativamente simples de seremimplementadas e também são passíveis de serem incorporadas a um ciclo simulação/deformação de forma completamente automática e eficiente. O primeiro objetivo deste trabalho é a concepção de uma ED topológica para representação de malhas elásticas. Tais malhas podem ser do tipo superficial ou volumétrica, e ainda simples ou mista. Para melhor desempenho, confiabilidade e menor consumo de memória, deseja-se que a ED seja implícita quanto à representação de componentes incidentes e adjacentes dos elementos presentes na malha. Outro objetivo deste trabalho é abordar o problema de geração de malhas em domínios arbitrários definidos por uma função implícita. O método proposto é uma extensão do algoritmo de Partição da Unidade Implícita (PUI). Para isso, o método proposto é baseado numa abordagem de preenchimento de superfícies. Este método proposto gera adaptativamente tetraedros em diferentes níveis de refinamento de acordo com o nível de detalhe presente na região do domínio. Diferentemente de trabalhos anteriores, esta característica é feita naturalmente sem necessitar de uma estrutura auxiliar. Para este fim, usa-se uma estrutura algébrica chamada de triangulação Ja1 que é capaz de lidar com tais refinamentos. Além do mais, a triangulação Ja1 permite que se percorra a estrutura simplesmente através de regras algébricas que é uma outra vantagem do método proposto / Topological data Structures (DS) oer several advantages when performing a deformation on a mesh. These DSs allow movement throughout the mesh without modifying its topology, are relatively simple to implement, and there is always the possibility of merging it to simulation/deformation cycle on a completely automatic and ecient form. The main goal of this work is to design and implement a topological DS to represent elastic meshes. These meshes can be either of surface or volume kind, and even simple or mixed. For better performance, more reliability and lower memory consumption, it is necessary that the DSs allow the representation of incident and adjacent components of a given element to be implicit. The second objective to this work is to tackle the problem of mesh generation on arbitrary domains defined by implicit functions. The proposed method is an extension to the algorithm of Partition of Unity Implicits (PUI). For this the proposed method is based on an isosurface stung approach. It adaptively generates the tetrahedra in dierent levels of refinement accordingly to the level of detail presented by the regions of the domain. Dierently to previous work, this feature is done naturally without the aid of an auxiliary data structure. To this end, we use an algebraic structure, named Ja1 triangulation, which is capable of dealing with such refinements. In addition, the Ja1 triangulation permits traversing through the mesh by simply using algebraic rules which is another advantage to the proposed method

Dois métodos distintos são descritos e implementados. O primeiro método, proposto por Ruppert, possui garantias teóricas de qualidade quando a fronteira do domínio obedece certas restrições. O segundo método, proposto por Persson, possibilita um maior controle na densidade dos elementos que discretizam o domínio. As vantagens, desvantagens e particularidades de cada um dos métodos são descritas e detalhadas / Two distinct methods are described and implemented. The first method, proposed by Ruppert, has theoretical guarantees on the quality of elements when the domain boundaries respect certain restrictions. The second method, proposed by Persson, makes it possible to have greater control over the density of the elements that make up the domain. The advantages, disadvantages and specific points about each method are described and detailed