Please use this identifier to cite or link to this item: http://www.repositorio.ufc.br/handle/riufc/39116
Title in Portuguese: Algoritmos para construção de quadtrees com base em partição binária de espaço
Author: Rocha, Francisco Wallison
Advisor(s): Freitas, Markos Oliveira
Keywords: Quadtree
Programação paralela
Binary Space Partitioning
Issue Date: 2018
Citation: 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.
Abstract in Portuguese: 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
metadata.dc.type: TCC
Appears in Collections:ENGENHARIA DE SOFTWARE - RUSSAS - Monografias

Files in This Item:
File Description SizeFormat 
2018_tcc_fwcrocha.pdf3,26 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.