CoordenaÃÃo de AperfeiÃoamento de NÃvel Superior / Este trabalho descreve uma tÃcnica de decomposiÃÃo de domÃnios bidimensionais para geraÃÃo em paralelo de malhas. Esta tÃcnica funciona tanto para memÃria distribuÃda quanto compartilhada, alÃm de permitir que se utilize qualquer estrutura de dados que gere regiÃes quadrangulares paralelas aos eixos para decompor o domÃnio dado como entrada. Pode se utilizar por exemplo, uma Ãrvore quaternÃria (quadtree) ou uma partiÃÃo binÃria do espaÃo (bsp). AlÃm disso, qualquer processo de geraÃÃo de malha que respeite os prÃ-requisitos estabelecidos pode ser empregado nos subdomÃnios criados, como as tÃcnicas de Delaunay ou AvanÃo de Fronteira, dentre outras. A tÃcnica proposta à dita a priori porque a malha de interface entre os subdomÃnios à gerada antes das suas malhas internas. A estimativa de carga de processamento associada a cada subdomÃnio à feita nesse trabalho com a ajuda de uma quadtree refinada, cujo nÃvel de refinamento orienta a criaÃÃo das arestas que sÃo definidas a partir da discretizaÃÃo das fronteiras das cÃlulas internas. Essa maneira de estimar carga produz resultados que representam, com boa precisÃo, o nÃmero de elementos a serem gerados em cada subdomÃnio. Isso contribui para um bom particionamento do domÃnio, fazendo com que a geraÃÃo de malha em paralelo seja significativamente mais rÃpida do que a geraÃÃo serial. AlÃm disso, a qualidade da malha gerada em paralelo à qualitativamente equivalente Ãquela gerada serialmente, dentro de limites aceitÃveis. / This work describes a technique of two-dimensional domain decomposition for parallel mesh generation. This technique works for both distributed and shared memory and has the freedom to use any data structure that manages rectangular regions parallel to the axes to decompose the domain given as input, such as a quaternary tree (quadtree) or a binary space decomposition (bsp), for example. Any process of mesh generation that respects the prerequisites established can be used in the subdomains created, for instance, Delaunay or Advancing Front, among others. This technique is called a priori because the mesh on the interface of the subdomains is generated prior to the their internal meshes. The load estimation for each sub-domain in this work is performed with the aid of a refined quadtree, whose level of refinement guides the creation of edges that are defined from the bounderies of only inner cells. This way of estimate load produces results that accurately represent the number of elements to be generated in each subdomain. That contributes to a good partitioning of the domain, making the mesh generation in parallel be significantly faster than the serial generation. Furthermore, the quality of the generated mesh in parallel is qualitatively equivalent to that generated serially within acceptable limits.

CoordenaÃÃo de AperfeÃoamento de Pessoal de NÃvel Superior / 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.