Particionamento binário de espaço

Espaço Binário de Particionamento (Binary Space Partitioning) é um método para dividir recursivamente um espaço em pedaços convexos de hiperplanos. Esse tipo de subdivisão dá luz a uma representação de cena a partir de uma Árvore de dados conhecida como Árvore BSP (BSP tree).

Esta implementação foi inicialmente posposta para aumentar a eficiência da renderização de gráficos 3D. As aplicações gráficas que trabalham com operações com formas geométricas se beneficiam desta implementação de renderização.

Resumo

Na computação gráfica é desejável que uma cena seja desenhada tanto precisamente quanto rapidamente. Um dos meios de se desenhar uma cena corretamente é usando o algoritmo do pintor, que desenha a cena na ordem dos objetos mais distantes até os mais próximos na visão da câmera. Este algoritmo tem uma limitação: muita performance é perdida desenhando objetos que estão atrás de outros, e caso um objeto coincida com a mesma distância da câmera de outro eles confundem o algoritmo.

Com ajuda de um Z-buffer e um espaço reservado na memória, o desenho da cena pode ser acelerado, já que toda a informação da distância dos objetos está gravada no z-buffer. O grande problema é que o z-buffer costuma exigir muita memória para cenas com muitos objetos.

Por outro lado a árvore BSP corta os objetos em pedaços pré-calculados, eliminando a necessidade do z-buffer e da ordenação dos objetos antes de desenhar a cena.

O efeito colateral das árvores BSP é o tempo consumido no pré-cálculo das cenas, o que o torna inviável no cálculo de objetos móveis que mudam constantemente de posição. Porém uma combinação de BSP e z-buffer consegue superar essa limitação.

Devido a essa natureza pré-calculada e da geometria usada, as árvores BSP são mais eficientes e mais comuns em cenas de ambientes fechados.

Referências

FUCHS, Henry, KEDEM Zvi M., NAYLOR, Bruce F.. "On Visible Surface Generation by a Priori Tree Structures" (PDF). Acessado em 21/07/2007.