Repositório Digital

A- A A+

Árvores BSP semi-ajustáveis

.

Árvores BSP semi-ajustáveis

Mostrar registro completo

Estatísticas

Título Árvores BSP semi-ajustáveis
Outro título Semi-adjusting BSP tree
Autor Luque, Rodrigo Gheller
Orientador Comba, Joao Luiz Dihl
Co-orientador Freitas, Carla Maria Dal Sasso
Data 2005
Nível Mestrado
Instituição Universidade Federal do Rio Grande do Sul. Instituto de Informática. Programa de Pós-Graduação em Computação.
Assunto 3D
Computação gráfica
[en] BSP-tree
[en] Collision detection
[en] Semi-adjusting structures
Resumo A etapa de broad-phase para a detecção de colisão em cenas compostas de n objetos que se movimentam é um problema desafiador, pois enumerar os pares de colisão revela uma complexidade quadrática. Estruturas de dados espaciais são desenvolvidas para acelerar o processo, mas muitas vezes a natureza estática dessas estruturas dificulta o manejo de cenas dinâmicas. Nesse trabalho, é proposta uma nova estrutura chamada de árvore BSP semi-ajustável para representar cenas compostas de milhares de objetos dinâmicos. Um algoritmo de agendamento avalia onde a árvore BSP torna-se desbalanceada, usa várias estratégias para alterar os planos de corte e atualizações preguiçosas para reduzir os custos de reconstrução. É mostrado que a árvore não precisa uma total reconstrução mesmo em cenas altamente dinâmicas, ajustando-se e mantendo propriedades desejáveis de balanceamento e profundidade.
Abstract The broad-phase step of collision detection in scenes composed of n moving objects is a challenging problem because enumerating collision pairs has an inherent O(n²) complexity. Spatial data structures are designed to accelerate this process, but often their static nature makes it difficult to handle dynamic scenes. In this work we propose a new structure called Semi-Adjusting BSP-tree for representing scenes composed of thousands of moving objects. A scheduling algorithm evaluates locations where the BSP-tree becomes unbalanced, uses several strategies to alter cutting planes, and defers updates based on their re-structuring cost. We show that the tree does not require a complete re-structuring even in highly dynamic scenes, but adjusts itself while maintaining desirable balancing and height properties.
Tipo Dissertação
URI http://hdl.handle.net/10183/17349
Arquivos Descrição Formato
000715187.pdf (2.834Mb) Texto completo Adobe PDF Visualizar/abrir

Este item está licenciado na Creative Commons License

Este item aparece na(s) seguinte(s) coleção(ões)


Mostrar registro completo

Percorrer



  • O autor é titular dos direitos autorais dos documentos disponíveis neste repositório e é vedada, nos termos da lei, a comercialização de qualquer espécie sem sua autorização prévia.
    Projeto gráfico elaborado pelo Caixola - Clube de Criação Fabico/UFRGS Powered by DSpace software, Version 1.8.1.