Please use this identifier to cite or link to this item:
http://repositorio.ufc.br/handle/riufc/39116| Type: | TCC |
| Title: | Algoritmos para construção de quadtrees com base em partição binária de espaço |
| Authors: | Rocha, Francisco Wallison |
| Advisor: | 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 Brazilian 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 |
| Appears in Collections: | ENGENHARIA DE SOFTWARE - RUSSAS - Monografias |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| 2018_tcc_fwcrocha.pdf | 3,26 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.