Particionamiento binario del espacio

En informática , la partición binaria del espacio ( BSP , por sus siglas en inglés) es un método para la partición del espacio que subdivide recursivamente un espacio euclidiano en dos conjuntos convexos utilizando hiperplanos como particiones. Este proceso de subdivisión da lugar a una representación de los objetos dentro del espacio en forma de una estructura de datos de árbol conocida como árbol BSP .

La partición binaria del espacio se desarrolló en el contexto de los gráficos por computadora 3D en 1969. ^{[ 1 ] [ 2 ]} La estructura de un árbol BSP es útil en la renderización porque puede proporcionar eficientemente información espacial sobre los objetos en una escena, como el orden de los objetos de adelante hacia atrás con respecto a un observador en una ubicación dada . Otras aplicaciones de BSP incluyen: realizar operaciones geométricas con formas ( geometría sólida constructiva ) en CAD , ^{[ 3 ]} detección de colisiones en robótica y videojuegos 3D, trazado de rayos , simulación de paisajes virtuales, ^{[ 4 ]} y otras aplicaciones que implican el manejo de escenas espaciales complejas.

• En 1969, Schumacker et al. ^{[ 1 ]} publicaron un informe que describía cómo se podían utilizar planos cuidadosamente posicionados en un entorno virtual para acelerar la ordenación de polígonos. La técnica se basaba en la coherencia de profundidad, que establece que un polígono situado en el extremo opuesto del plano no puede, de ninguna manera, obstruir a un polígono más cercano. Esto se utilizó en simuladores de vuelo fabricados por GE, así como por Evans y Sutherland. Sin embargo, la creación de la organización de datos poligonales la realizaba manualmente el diseñador de la escena.
• En 1980, Fuchs et al. ^{[ 2 ]} extendieron la idea de Schumacker a la representación de objetos 3D en un entorno virtual mediante el uso de planos coincidentes con polígonos para particionar recursivamente el espacio 3D. Esto permitió la generación totalmente automatizada y algorítmica de una estructura de datos poligonal jerárquica conocida como Árbol de Partición Binaria del Espacio (Árbol BSP). El proceso se llevó a cabo como un paso de preprocesamiento fuera de línea que se realizó una vez por entorno/objeto. En tiempo de ejecución, el orden de visibilidad dependiente de la vista se generó recorriendo el árbol.
• En 1981, la tesis doctoral de Naylor ^{[ 5 ]} presentó un desarrollo completo tanto de los árboles BSP como de un enfoque basado en la teoría de grafos que utiliza componentes fuertemente conexas para el cálculo previo de la visibilidad, así como la conexión entre ambos métodos. Se hizo hincapié en los árboles BSP como una estructura de búsqueda espacial independiente de la dimensión, con aplicaciones a la determinación de superficies visibles. La tesis también incluyó los primeros datos empíricos que demostraban que el tamaño del árbol y el número de polígonos nuevos eran razonables (utilizando un modelo del transbordador espacial).
• En 1983, Fuchs et al. ^{[ 6 ]} describieron una implementación en microcódigo del algoritmo de árbol BSP en un sistema de búfer de trama Ikonas . Esta fue la primera demostración de determinación de superficie visible en tiempo real utilizando árboles BSP.
• En 1987, Thibault y Naylor ^{[ 3 ]} describieron cómo se podían representar poliedros arbitrarios utilizando un árbol BSP en contraposición a la representación tradicional de contorno (b-rep ). Esto proporcionó una representación sólida frente a una representación basada en superficies. Se describieron operaciones de conjuntos sobre poliedros utilizando una herramienta que permitía la geometría sólida constructiva (CSG) en tiempo real. Este fue el precursor del diseño de niveles BSP mediante " pinceles ", introducido en el editor de Quake y posteriormente adoptado en el editor de Unreal.
• En 1990, Naylor, Amanatides y Thibault ^{[ 7 ]} propusieron un algoritmo para fusionar dos árboles BSP y formar un nuevo árbol BSP a partir de los dos árboles originales. Esto ofrece numerosas ventajas, como la combinación de objetos en movimiento representados por árboles BSP con un entorno estático (también representado por un árbol BSP), operaciones CSG muy eficientes en poliedros, detección exacta de colisiones en O(log n * log n) y ordenación adecuada de superficies transparentes contenidas en dos objetos interpenetrantes (que se ha utilizado para un efecto de visión de rayos X).
• En 1991, Teller y Séquin ^{[ 8 ]} propusieron la generación fuera de línea de conjuntos potencialmente visibles para acelerar la determinación de superficies visibles en entornos 2D ortogonales.
• En 1991, Gordon y Chen ^{[ 9 ]} describieron un método eficiente para realizar renderizado de adelante hacia atrás a partir de un árbol BSP, en lugar del enfoque tradicional de atrás hacia adelante. Utilizaron una estructura de datos especial para registrar, de manera eficiente, las partes de la pantalla que se habían dibujado y las que aún no se habían renderizado. Este algoritmo, junto con la descripción de los árboles BSP en el libro de texto estándar de gráficos por computadora de la época ( Computer Graphics: Principles and Practice ), fue utilizado por John Carmack en la creación de Doom .
• En 1992, la tesis doctoral de Teller ^{[ 10 ]} describió la generación eficiente de conjuntos potencialmente visibles como un paso de preprocesamiento para acelerar la determinación de superficies visibles en tiempo real en entornos poligonales 3D arbitrarios. Esto se utilizó en Quake y contribuyó significativamente al rendimiento de ese juego.
• En 1993, Naylor ^{[ 11 ]} respondió a la pregunta de qué caracteriza a un buen árbol BSP. Utilizó modelos de casos esperados (en lugar de análisis de peor caso) para medir matemáticamente el costo esperado de la búsqueda en un árbol y empleó esta medida para construir buenos árboles BSP. Intuitivamente, el árbol representa un objeto de forma multirresolución (más precisamente, como un árbol de aproximaciones). Se establecen paralelismos con los códigos de Huffman y los árboles de búsqueda binaria probabilísticos.
• En 1993, la tesis doctoral de Hayder Radha ^{[ 12 ]} describió métodos de representación de imágenes (naturales) mediante árboles BSP. Esto incluye el desarrollo de un marco óptimo para la construcción de árboles BSP para cualquier imagen de entrada arbitraria. Este marco se basa en una nueva transformación de imagen, conocida como transformación de línea de partición de mínimos cuadrados (LPE). La tesis de Radha también desarrolló un marco óptimo de compresión de imágenes de tasa-distorsión (RD) y enfoques de manipulación de imágenes mediante árboles BSP.

La partición binaria del espacio es un proceso genérico que divide recursivamente una escena en dos mediante hiperplanos ^{[ 13 ]} hasta que la partición satisface uno o más requisitos. Puede considerarse una generalización de otras estructuras de árbol espacial, como los árboles k -d y los quadtrees , donde los hiperplanos que particionan el espacio pueden tener cualquier orientación, en lugar de estar alineados con los ejes de coordenadas como en los árboles k -d o los quadtrees. Cuando se utiliza en gráficos por computadora para renderizar escenas compuestas por polígonos planos , los planos de partición suelen elegirse para que coincidan con los planos definidos por los polígonos de la escena.

La elección específica del plano de partición y el criterio para finalizar el proceso de partición varían según el propósito del árbol BSP. Por ejemplo, en la renderización de gráficos por computadora, la escena se divide hasta que cada nodo del árbol BSP contiene solo polígonos que se pueden renderizar en un orden arbitrario. Cuando se utiliza el descarte de caras posteriores , cada nodo contiene, por lo tanto, un conjunto convexo de polígonos, mientras que al renderizar polígonos de doble cara, cada nodo del árbol BSP contiene solo polígonos en un solo plano. En la detección de colisiones o el trazado de rayos, una escena se puede dividir en primitivas sobre las que las pruebas de colisión o intersección de rayos son sencillas.

La partición binaria del espacio surgió de la necesidad de los gráficos por computadora de dibujar rápidamente escenas tridimensionales compuestas de polígonos. Una forma sencilla de dibujar dichas escenas es el algoritmo del pintor , que produce polígonos en orden de distancia al observador, de atrás hacia adelante, pintando sobre el fondo y los 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 polígonos superpuestos. Fuchs y coautores ^{[ 2 ]} demostraron que la construcción de un árbol BSP resolvía ambos problemas al proporcionar un método rápido para ordenar 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 los errores que pueden ocurrir con el algoritmo del pintor. Una desventaja de la partición binaria del espacio es que generar un árbol BSP puede ser lento. Por lo tanto, normalmente se realiza una sola vez en geometría estática, como un paso de precálculo, antes de la renderización u otras operaciones en tiempo real en una escena. El elevado coste de construir un árbol BSP hace que sea difícil e ineficiente implementar directamente el movimiento de objetos dentro de un árbol.

El uso canónico de un árbol BSP es para renderizar polígonos (que son de doble cara, es decir, sin eliminación de caras posteriores ) con el algoritmo del pintor. Cada polígono se designa con una cara frontal y una cara posterior que pueden elegirse arbitrariamente y solo afectan la estructura del árbol, pero no el resultado requerido. ^{[ 2 ]} Dicho árbol se construye a partir de una lista no ordenada de todos los polígonos en una escena. El algoritmo recursivo para la construcción de un árbol BSP a partir de esa lista de polígonos es: ^{[ 2 ]}

1. Elige un polígono P de la lista.
2. Crea un nodo N en el árbol BSP y agrega P a la lista de polígonos en ese nodo.
3. Para cada otro polígono de la lista:
   1. Si ese polígono está completamente delante del plano que contiene a P , mueva ese polígono a la lista de nodos delante de P.
   2. Si ese polígono está completamente detrás del plano que contiene a P , mueva ese polígono a la lista de nodos detrás de P.
   3. Si ese polígono es intersectado por el plano que contiene a P , divídalo en dos polígonos y muévalos a las respectivas listas de polígonos detrás y delante de P.
   4. Si ese polígono se encuentra en el plano que contiene a P , agréguelo a la lista de polígonos en el nodo N.
4. Aplique este algoritmo a la lista de polígonos que se encuentra frente a P.
5. Aplique este algoritmo a la lista de polígonos detrás de P.

El siguiente diagrama ilustra el uso de este algoritmo para convertir una lista de líneas o polígonos en un árbol BSP. En cada uno de los ocho pasos (i.-viii.), el algoritmo anterior se aplica a una lista de líneas y se agrega un nuevo nodo al árbol.

El número final de polígonos o líneas en un árbol suele ser mayor (a veces mucho mayor ^{[ 2 ]} ) que la lista original, ya que las líneas o polígonos que cruzan el plano de partición deben dividirse en dos. Es deseable minimizar este aumento, pero también mantener un equilibrio razonable en el árbol final. Por lo tanto, la elección del polígono o línea que se utiliza como plano de partición (en el paso 1 del algoritmo) es importante para crear un árbol BSP eficiente.

Un árbol BSP se recorre en tiempo lineal, en un orden determinado por la función particular del árbol. Usando nuevamente el ejemplo de renderizar polígonos de doble cara usando el algoritmo del pintor, para dibujar un polígono P correctamente se requiere que todos los polígonos detrás del plano en el que se encuentra P se dibujen primero, luego el polígono P , y finalmente los polígonos delante de P. Si este orden de dibujo se satisface para todos los polígonos en una escena, entonces toda la escena se renderiza en el orden correcto. Este procedimiento se puede implementar recorriendo recursivamente un árbol BSP usando el siguiente algoritmo. ^{[ 2 ]} Desde una ubicación de visualización dada V , para renderizar un árbol BSP,

1. Si el nodo actual es un nodo hoja, renderiza los polígonos en el nodo actual.
2. De lo contrario, si la ubicación de visualización V está frente al nodo actual:
   1. Renderiza el árbol BSP hijo que contiene polígonos detrás del nodo actual.
   2. Renderiza los polígonos en el nodo actual.
   3. Renderiza el árbol BSP hijo que contiene polígonos delante del nodo actual.
3. De lo contrario, si la ubicación de visualización V está detrás del nodo actual:
   1. Renderiza el árbol BSP hijo que contiene polígonos delante del nodo actual.
   2. Renderiza los polígonos en el nodo actual.
   3. Renderiza el árbol BSP hijo que contiene polígonos detrás del nodo actual.
4. De lo contrario, la ubicación de visualización V debe estar exactamente en el plano asociado con el nodo actual. Entonces:
   1. Renderiza el árbol BSP hijo que contiene polígonos delante del nodo actual.
   2. Renderiza el árbol BSP hijo que contiene polígonos detrás del nodo actual.

La aplicación recursiva de este algoritmo al árbol BSP generado anteriormente da como resultado los siguientes pasos:

• El algoritmo se aplica primero al nodo raíz del árbol, el nodo A. V está delante del nodo A , por lo que aplicamos el algoritmo primero al árbol BSP hijo que contiene los polígonos detrás de A.
  • Este árbol tiene como nodo raíz B1 . V está detrás de B1 , por lo que primero aplicamos el algoritmo al árbol BSP hijo que contiene polígonos delante de B1 :
    • Este árbol es solo el nodo hoja D1 , por lo que se renderiza el polígono D1 .
  • Luego renderizamos el polígono B1 .
  • Luego aplicamos el algoritmo al árbol BSP hijo que contiene polígonos detrás de B1 :
    • Este árbol es solo el nodo hoja C1 , por lo que se renderiza el polígono C1 .
• Luego dibujamos los polígonos de A.
• Luego aplicamos el algoritmo al árbol BSP hijo que contiene polígonos delante de A.
  • Este árbol tiene como nodo raíz B2 . V está detrás de B2 , por lo que primero aplicamos el algoritmo al árbol BSP hijo que contiene polígonos delante de B2 :
    • Este árbol es solo el nodo hoja D2 , por lo que se renderiza el polígono D2 .
  • Luego renderizamos el polígono B2 .
  • Luego aplicamos el algoritmo al árbol BSP hijo que contiene polígonos detrás de B2 :
    • Este árbol tiene como nodo raíz C2 . V está delante de C2 , así que primero aplicaríamos el algoritmo al árbol BSP hijo que contiene polígonos detrás de C2 . Sin embargo, no existe tal árbol, así que continuamos.
    • Renderizamos el polígono C2 .
    • Aplicamos el algoritmo al árbol BSP hijo que contiene polígonos delante de C2.
      • Este árbol es solo el nodo hoja D3 , por lo que se renderiza el polígono D3 .

El árbol se recorre en tiempo lineal y genera los polígonos en un orden de lejos a cerca ( D1 , B1 , C1 , A , D2 , B2 , C2 , D3 ) adecuado para el algoritmo del pintor.

Los árboles BSP se utilizan con frecuencia en videojuegos 3D , especialmente en juegos de disparos en primera persona y aquellos con entornos interiores. Entre los motores de juego que utilizan árboles BSP se encuentran Doom , Quake , GoldSrc y Source . En ellos, los árboles BSP que contienen la geometría estática de una escena se utilizan a menudo junto con un búfer Z para integrar correctamente objetos móviles, como puertas y personajes, en el fondo de la escena. Si bien la partición binaria del espacio proporciona una forma práctica de almacenar y recuperar información espacial sobre los polígonos de una escena, no resuelve el problema de la determinación de la superficie visible . Los árboles BSP también se han aplicado a la compresión de imágenes. ^{[ 14 ]}

• poliedro de Chazelle
• árbol kd
• Octree
• Árbol cuatripartito
• La agrupación jerárquica es una forma alternativa de dividir los datos de modelos 3D para una representación eficiente.
• Corte con guillotina

• Naylor, BF (2005). "Un tutorial sobre árboles de partición de espacio binario" .
• Presentación de los árboles de BSP
• Otra presentación sobre árboles de BSP
• Un applet de Java que demuestra el proceso de generación de árboles.
• Una tesis de maestría sobre la generación de BSP
• Árboles BSP: Teoría e implementación
• BSP en el espacio 3D
• Joyas gráficas V: Un recorrido por los árboles de BSP