Particionamento binário de espaço

Em ciência da computação, o Particionamento binário de espaço (BSP)é um método para recursivamente subdividir um espaço em convexos definidos de hiperplanos. Esta subdivisão dá origem a uma representação de objectos dentro do espaço por meio de um estrutura de dados em árvore conhecido como árvore BSP.

O processo de fazer uma árvore BSP

Particionamento espaço binário foi desenvolvido no contexto de computação gráfica 3D,[1] onde a estrutura de uma árvore BSP permite que a informação espacial sobre os objetos em uma cena o que é útil em apresentação, tais como a sua ordem de frente para trás em relação a um observador em um determinado local e ser acedida rapidamente. Outras aplicações incluem a realização de operações com formas geométricas (geometria sólida construtiva) em CAD,[2] detecção de colisão em robótica e Video games 3D, ray tracing e outras aplicações de computador que envolvem a manipulação de cenas espaciais complexos.

Referências

  1. Fuchs, Henry; Kedem, Zvi. M; Naylor, Bruce F. (1980). «On Visible Surface Generation by A Priori Tree Structures». SIGGRAPH '80 Proceedings of the 7th annual conference on Computer graphics and interactive techniques. ACM, New York. pp. 124–133. doi:10.1145/965105.807481 
  2. Thibault, William C.; Naylor, Bruce F. (1987). «Set operations on polyhedra using binary space partitioning trees». SIGGRAPH '87 Proceedings of the 14th annual conference on Computer graphics and interactive techniques. ACM, New York. pp. 153–162. doi:10.1145/37402.37421