O que é uma Árvore BSP?

Uma Árvore de Particionamento Espacial Binário (ou Árvore BSP) é uma estrutura de dados utilizada para organizar objetos dentro de um espaço. No campo da Computação Gráfica, tem aplicações na remoção de superfícies ocultas e em “ray tracing”. Uma árvore BSP é uma subdivisão recursiva do espaço que trata cada segmento de linha (ou polígono, em 3D) como um plano de corte, o qual é usado para classificar todos os objetos restantes no espaço como estando na “frente” ou “atrás” desse plano. Em outras palavras, quando uma partição é inserida na árvore, esta é primeiro classificada em relação ao nodo raiz e então recursivamente em relação a cada filho apropriado. Para mais informações sobre árvores BSP, veja o BSP Tree FAQ.

Desculpe, o seu navegador não suporta applets Java.

Como Usar este Applet

Você pode desenhar segmentos de linha no primeiro painel de desenho (a primeira linha, quando desenhada, obriga Java a realizar algumas inicializações, demorando mais para aparecer do que as próximas). Os segmentos são numerados em ordem, e a árvore é construída inserindo-se cada segmento na ordem definida. Se uma partição precisa ser dividida, as partes frontal e traseira da partição terão um “f” e um “b” adicionados aos seus respectivos nomes. Por exemplo, se a partição 1 atravessa o plano de corte formado pela partição 0, a parte da partição 1 que está na frente da partição 0 será denominada “1f” e a parte atrás será denominada “1b”.

Você pode mover o observador (em magenta) clicando e arrastando a seta. Se você clicar e arrastar a ponta da seta, poderá rotacionar a câmera que visualiza a cena pseudo-3D.

Se o tempo de reposta estiver muito lento quando movendo segmentos de linha, desmarque a caixa “interactive” para desabilitar a natureza interativa do applet. No modo não-interativo, a árvore BSP só será reconstruída quando um segmento tiver sido deslocado para uma nova posição e o botão do mouse for solto.

Se o gráfico da árvore se tornar grande demais para o seu painel de desenho, clique e arraste nesse painel para deslocar a árvore.

Mais Informações sobre Árvores BSP

Provavelmente o melhor local para se obter informações sobre árvores BSP é o BSP Tree FAQ.

Esta página foi traduzida para o Português pelo Prof. Marcelo Cohen da Pontifícia Universidade Católica do Rio Grande do Sul.