A priori decomposition technique for parallel generation of two-dimensional meshes

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.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