Particionamiento de espacio binario

La partición de espacio binario se implementa para subdividir recursivamente un espacio en dos conjuntos convexos mediante el uso de hiperplanos como particiones. Este proceso de subdivisión da lugar a la representación de objetos dentro del espacio en forma de estructura de datos de árbol conocida como BSP Tree.
La partición del espacio binario surgió en el contexto de los gráficos por computadora en 3D en 1969, donde la estructura de un árbol BSP permite obtener información espacial sobre los objetos en una escena que es útil en la representación, como los objetos que se ordenan de adelante hacia atrás con respecto a un espectador en una ubicación dada, para ser accedido rápidamente.

Necesidades de la partición del espacio binario

La partición del espacio binario surgió de la necesidad de gráficos por computadora para dibujar rápidamente escenas tridimensionales compuestas de polígonos. Una forma sencilla de dibujar tales escenas es el algoritmo del pintor, que produce polígonos en orden de distancia desde el espectador, de atrás hacia adelante, pintando sobre el fondo y polígonos anteriores con cada objeto más cercano. Este enfoque tiene dos desventajas: el tiempo requerido para ordenar los polígonos de atrás hacia adelante y la posibilidad de errores en los polígonos superpuestos. Fuchs y sus coautores demostraron que la construcción de un árbol BSP resolvía ambos problemas al proporcionar un método rápido para ordenar los polígonos con respecto a un punto de vista dado (lineal en el número de polígonos en la escena) y al subdividir los polígonos superpuestos para evitar errores que puede ocurrir con el algoritmo del pintor.

Descripción general de BSP

La partición de espacio binario se trata como un proceso genérico de dividir recursivamente una escena en dos hasta que la partición satisfaga uno o más requisitos. Puede verse como una generalización de otras estructuras de árboles espaciales, como los árboles kd y los árboles cuádruples, uno en el que los hiperplanos que dividen el espacio pueden tener cualquier orientación en lugar de estar alineados con los ejes de coordenadas como lo están en los árboles kd o los árboles cuádruples .
Cuando se implementa en gráficos por computadora para renderizar escenas compuestas por polígonos planos, los planos de partición se seleccionan con frecuencia para que coincidan con los planos definidos por los polígonos en la escena. La elección específica del plano de partición y el criterio para completar el proceso de partición varía según el propósito del árbol BSP.
Por ejemplo: en la representación de gráficos por computadora, la escena se divide hasta que cada Node del árbol BSP consta de solo polígonos que se pueden representar en un orden arbitrario. Cuando se implementa la selección de cara posterior, cada Node, por lo tanto, consiste en un conjunto convexo de polígonos, mientras que cuando se representan polígonos de dos lados, cada Node del árbol BSP consta solo de polígonos en un solo plano.

Algoritmo de generación de un árbol BSP a partir de una lista de polígonos

• Seleccione un polígono P de la lista.
• Haga un Node N en el árbol BSP y agregue P a la lista de polígonos en ese Node.
• Para cada otro polígono en la lista:
  • Si ese polígono está completamente frente al plano que contiene P, mueva ese polígono a la lista de Nodes frente a P.
  • Si ese polígono está completamente detrás del plano que contiene P, mueva ese polígono a la lista de Nodes detrás de P.
  • Si ese polígono es intersectado por el plano que contiene P, divídalo en dos polígonos y muévalos a las respectivas listas de polígonos detrás y delante de P.
  • Si ese polígono se encuentra en el plano que contiene P, agréguelo a la lista de polígonos en el Node N.
• Aplique este algoritmo a la lista de polígonos delante de P.
• Aplique este algoritmo a la lista de polígonos detrás de P.

Desventaja de BSP

• La generación de un árbol BSP puede llevar mucho tiempo.
• BSP no resuelve el problema de la determinación de la superficie visible.

Usos de BSP

• Se utiliza en la detección de colisiones en videojuegos 3D y robótica.
• Se utiliza en trazado de rayos.
• Está involucrado en el manejo de escenas espaciales complejas.