Use este identificador para citar ou linkar para este item: http://repositorio.ufc.br/handle/riufc/39116
Tipo: TCC
Título: Algoritmos para construção de quadtrees com base em partição binária de espaço
Autor(es): Rocha, Francisco Wallison
Orientador: Freitas, Markos Oliveira
Palavras-chave: Quadtree;Programação paralela;Binary Space Partitioning
Data do documento: 2018
Citação: ROCHA, Francisco Wallison. Algoritmos para construção de quadtrees com base em partição binária de espaço. 2018. 75 f. Monografia (Graduação em Engenharia de Software) – Campus de Russas, Universidade Federal do Ceará, Russas, 2018.
Resumo: Técnicas de subdivisão de espaço, como quadtrees e octrees, são amplamente utilizadas como estruturas auxiliares para diversas aplicações. Em particular, elas são utilizadas na geração de malhas de elementos finitos. Para geração de grandes malhas refinadas, faz-se necessária a utilização de programação paralela. Assim, este trabalho apresenta uma técnica para construção paralela de quadtrees com base em Partição Binária do Espaço, do inglês Binary Space Partitio-ning-BSP. Dado um modelo discretizado em vértices e arestas, é possível extrair informações para realizar uma estimativa de carga que serve como guia para o particionamento do modelo entre os processos usando a BSP. Este particionamento visa equilibrar o trabalho de geração e de armazenamento da quadtree realizado por cada processo. Essa técnica foi aplicada em três modelos para 2 a 16 processos, apresentando bons resultados para modelos uniformemente distribuídos
Abstract: Space subdivision techniques, such as quadtrees and octrees, are widely used as auxiliary structures for various applications. In particular, they are used in the generation of finite element meshes. For generation of large refined meshes, it is necessary to use parallel programming. Thus, this work presents a technique for parallel construction of quadtrees based on Binary Space Partitioning (BSP). Given a discrete model in vertices and edges, it is possible to extractinformation to perform a load estimate that serves as a guide for partitioning the model between processes using BSP. This partitioning aims to balance the work of generation and storage of the quadtree performed by each process. This technique was applied in three models for 2 to 16 processes, presenting good results for uniformly distributed models
URI: http://www.repositorio.ufc.br/handle/riufc/39116
Aparece nas coleções:ENGENHARIA DE SOFTWARE - RUSSAS - Monografias

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
2018_tcc_fwcrocha.pdf3,26 MBAdobe PDFVisualizar/Abrir


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.