No description available.

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

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

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

This thesis deals with ray tracing methods and their acceleration. It gives partial study and review of algorithms from classical ray shooting algorithm to recursive approach up to distributed ray tracing algorithm. Significant part of this thesis is devoted to BSP tree structure and its subclass of k-D tree, it shows simple algorithm for its construction and traversal. The rest of thesis is dealing with k-D tree construction techniques, which are based on the right choice of the splitting plane inside the every cell of k-D tree. The techniques upon the thesis is based on are space median, object median and relatively new cost model technique named SAH, otherwise as surface area heuristic. All three techniques are put into testing and performance comparison. In the conclusion the results of tests are reviewed, from where SAH is coming out as a winner.