La partición binaria del espacio se desarrolló en el contexto de los gráficos por computadora en 3D en 1969. [1] [2] La estructura de un árbol BSP es útil en la renderización porque puede brindar de manera eficiente información espacial sobre los objetos en una escena, como por ejemplo, los objetos que se ordenan de adelante hacia atrás con respecto a un espectador en una ubicación determinada. 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 en 3D, trazado de rayos , simulación de paisajes virtuales, [4] y otras aplicaciones que involucran el manejo de escenas espaciales complejas.
Historia
En 1969, Schumacker et al. [1] publicaron un informe que describía cómo se podían utilizar aviones cuidadosamente posicionados en un entorno virtual para acelerar la ordenación de polígonos. La técnica hacía uso de la coherencia de profundidad, que establece que un polígono en el lado más alejado del avión no puede, de ninguna manera, obstruir 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.
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 que coinciden con polígonos para dividir recursivamente el espacio 3D. Esto proporcionó una generación algorítmica y totalmente automatizada de una estructura de datos poligonal jerárquica conocida como árbol de partición espacial binaria (á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 proporcionó un desarrollo completo de los árboles BSP y de un enfoque de teoría de grafos que utiliza componentes fuertemente conectados para el cálculo previo de la visibilidad, así como la conexión entre los dos métodos. Se hizo hincapié en los árboles BSP como una estructura de búsqueda espacial independiente de la dimensión, con aplicaciones para 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 la cantidad de polígonos nuevos eran razonables (utilizando un modelo del transbordador espacial).
1983 Fuchs et al. describieron una implementación en microcódigo del algoritmo de árbol BSP en un sistema de memoria intermedia de trama Ikonas. Esta fue la primera demostración de determinación de superficies visibles en tiempo real utilizando árboles BSP.
1987 Thibault y Naylor [3] describieron cómo se pueden representar poliedros arbitrarios utilizando un árbol BSP en lugar de la representación de límites (b-rep) tradicional. Esto proporcionó una representación sólida en lugar de una representación basada en superficies. Las operaciones de conjuntos sobre poliedros se describieron 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 utilizando " pinceles ", introducido en el editor Quake y recogido en el editor Unreal.
1990 Naylor, Amanatides y Thibault proporcionaron un algoritmo para fusionar dos árboles BSP y formar un nuevo árbol BSP a partir de los dos árboles originales. Esto ofrece muchos beneficios, entre ellos, 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 ordenamiento adecuado de superficies transparentes contenidas en dos objetos interpenetrantes (se ha utilizado para un efecto de visión de rayos X).
1990 Teller y Séquin propusieron la generación fuera de línea de conjuntos potencialmente visibles para acelerar la determinación de la superficie visible en entornos 2D ortogonales.
1991 Gordon y Chen [CHEN91] 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, 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 de gráficos por computadora estándar de la época ( Computer Graphics: Principles and Practice ), fue utilizado por John Carmack en la creación de Doom (videojuego) .
La tesis doctoral de Teller de 1992 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.
1993 Naylor respondió a la pregunta de qué caracteriza a un buen árbol BSP. Utilizó modelos de casos esperados (en lugar de análisis del peor de los casos) para medir matemáticamente el costo esperado de la búsqueda en un árbol y utilizó esta medida para construir buenos árboles BSP. Intuitivamente, el árbol representa un objeto en una forma multirresolución (más exactamente, como un árbol de aproximaciones). Se establecen paralelismos con los códigos de Huffman y los árboles de búsqueda binaria probabilísticos.
En su tesis doctoral de 1993, Hayder Radha describió métodos de representación de imágenes (naturales) utilizando árboles BSP. Esto incluye el desarrollo de un marco de construcción de árboles BSP óptimo para cualquier imagen de entrada arbitraria. Este marco se basa en una nueva transformación de imágenes, conocida como transformación de línea de partición de error de mínimos cuadrados (LSE). La tesis de H. Radha también desarrolló un marco de compresión de imágenes de tasa de distorsión (RD) óptima y enfoques de manipulación de imágenes utilizando árboles BSP.
La partición binaria del espacio es un proceso genérico de división recursiva de una escena en dos hasta que la partición satisface uno o más requisitos. Puede verse como una generalización de otras estructuras de árbol espacial como árboles k -d y árboles cuádruples , donde los hiperplanos que dividen el espacio pueden tener cualquier orientación, en lugar de estar alineados con los ejes de coordenadas como en árboles k -d o árboles cuádruples. Cuando se utiliza en gráficos de computadora para representar escenas compuestas de polígonos planos , los planos de partición se eligen 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 finalizar el proceso de partición varían 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 nodo del árbol BSP contiene solo polígonos que se pueden representar en un orden arbitrario. Cuando se utiliza la eliminación de caras posteriores , cada nodo, por lo tanto, contiene un conjunto convexo de polígonos, mientras que cuando se representan polígonos de dos lados, 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 en 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 que los gráficos por computadora dibujaran 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 desde el espectador, 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 en orden de atrás hacia adelante y la posibilidad de errores en los polígonos superpuestos. Fuchs y coautores [2] demostraron que la construcción de un árbol BSP resolvió ambos problemas al proporcionar un método rápido de 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 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 llevar mucho tiempo. Por lo tanto, normalmente se realiza una vez en la 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 costo de construir un árbol BSP hace que sea difícil e ineficiente implementar directamente objetos en movimiento en un árbol.
Generación
El uso canónico de un árbol BSP es para la representación de polígonos (que tienen dos caras, es decir, sin eliminación de la cara posterior ) con el algoritmo del pintor. Cada polígono se designa con un lado frontal y un lado posterior que se pueden elegir arbitrariamente y solo afectan la estructura del árbol, pero no el resultado requerido. [2] Un árbol de este tipo se construye a partir de una lista desordenada de todos los polígonos de una escena. El algoritmo recursivo para la construcción de un árbol BSP a partir de esa lista de polígonos es: [2]
Elija un polígono P de la lista.
Cree un nodo N en el árbol BSP y agregue P a la lista de polígonos en ese nodo.
Para cada otro polígono de la lista:
Si ese polígono está completamente frente al plano que contiene P , mueva ese polígono a la lista de nodos frente a P .
Si ese polígono está completamente detrás del plano que contiene P , mueva ese polígono a la lista de nodos 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 nodo 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.
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 de qué polígono o línea se utiliza como plano de partición (en el paso 1 del algoritmo) es importante para crear un árbol BSP eficiente.
Travesía
Un árbol BSP se recorre en un tiempo lineal, en un orden determinado por la función particular del árbol. Nuevamente, utilizando el ejemplo de renderizar polígonos de dos lados utilizando 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 utilizando el siguiente algoritmo. [2] Desde una ubicación de visualización dada V , para renderizar un árbol BSP,
Si el nodo actual es un nodo hoja, renderiza los polígonos en el nodo actual.
De lo contrario, si la ubicación de visualización V está frente al nodo actual:
Representar el árbol BSP secundario que contiene polígonos detrás del nodo actual
Representar los polígonos en el nodo actual
Representar el árbol BSP secundario que contiene polígonos delante del nodo actual
De lo contrario, si la ubicación de visualización V está detrás del nodo actual:
Representar el árbol BSP secundario que contiene polígonos delante del nodo actual
Representar los polígonos en el nodo actual
Representar el árbol BSP secundario que contiene polígonos detrás del nodo actual
De lo contrario, la ubicación de visualización V debe estar exactamente en el plano asociado con el nodo actual. Entonces:
Representar el árbol BSP secundario que contiene polígonos delante del nodo actual
Representar el árbol BSP secundario que contiene polígonos detrás del nodo actual
La aplicación de este algoritmo de forma recursiva 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 secundario que contiene 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 secundario que contiene polígonos delante de B1 :
Este árbol es solo el nodo hoja D1 , por lo que se representa el polígono D1 .
Luego renderizamos el polígono B1 .
Luego aplicamos el algoritmo al árbol BSP secundario que contiene polígonos detrás de B1 :
Este árbol es solo el nodo hoja C1 , por lo que se representa el polígono C1 .
Luego dibujamos los polígonos de A
Luego aplicamos el algoritmo al árbol BSP secundario 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 secundario que contiene polígonos delante de B2 :
Este árbol es solo el nodo hoja D2 , por lo que se representa el polígono D2 .
Luego renderizamos el polígono B2 .
Luego aplicamos el algoritmo al árbol BSP secundario que contiene polígonos detrás de B2 :
Este árbol tiene como nodo raíz C2 . V está delante de C2 , por lo que primero aplicaríamos el algoritmo al árbol BSP secundario que contiene polígonos detrás de C2 . Sin embargo, no existe dicho árbol, por lo que continuamos.
Representamos 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 representa el polígono D3 .
El árbol se recorre en tiempo lineal y representa los polígonos en un orden de lejos a cerca ( D1 , B1 , C1 , A , D2 , B2 , C2 , D3 ) adecuado para el algoritmo del pintor.
Solicitud
Los árboles BSP se utilizan a menudo en videojuegos 3D , en particular los juegos de disparos en primera persona y aquellos con entornos interiores. Los motores de juego que utilizan árboles BSP incluyen los motores Doom (id Tech 1) , Quake (variante id Tech 2) , 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 fusionar correctamente objetos móviles como puertas y personajes en la escena de fondo. Si bien la partición binaria del espacio proporciona una forma conveniente de almacenar y recuperar información espacial sobre los polígonos en 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. [5]
^ ab Schumacker, RA; Brand, B.; Gilliland, MG; Sharp, WH (1969). Estudio para la aplicación de imágenes generadas por computadora a la simulación visual (informe). Laboratorio de Recursos Humanos de la Fuerza Aérea de los EE. UU. AFHRL-TR-69-14.
^ abcdefg Fuchs, Henry; Kedem, Zvi. M; Naylor, Bruce F. (1980). "Sobre la generación de superficies visibles mediante estructuras de árbol a priori" (PDF) . SIGGRAPH '80 Actas de la 7.ª conferencia anual sobre gráficos por ordenador y técnicas interactivas . ACM. págs. 124–133. doi :10.1145/965105.807481.
^ ab Thibault, William C.; Naylor, Bruce F. (1987). "Operaciones de conjuntos en poliedros utilizando árboles de partición del espacio binario". SIGGRAPH '87 Actas de la 14.ª conferencia anual sobre gráficos por ordenador y técnicas interactivas . ACM. págs. 153–162. doi :10.1145/37402.37421.
^ Etherington, Thomas R.; Morgan, Fraser J.; O'Sullivan, David (2022). "La partición binaria del espacio genera modelos de paisaje neutros jerárquicos y rectilíneos adecuados para paisajes dominados por humanos". Ecología del paisaje . 37 (7): 1761–1769. Código Bibliográfico :2022LaEco..37.1761E. doi : 10.1007/s10980-022-01452-6 .
^ H. Radha, M. Vetterli y R. Leonardi, "Compresión de imágenes utilizando árboles de partición espacial binaria", en IEEE Transactions on Image Processing , vol. 5, núm. 12, págs. 1610-1624, diciembre de 1996, doi: 10.1109/83.544569.
Referencias adicionales
Naylor, B.; Amanatides, J.; Thibault, W. (agosto de 1990). "La fusión de árboles BSP produce operaciones de conjuntos poliédricos". ACM SIGGRAPH Computer Graphics . 24 (4): 115–124. CiteSeerX 10.1.1.69.292 . doi :10.1145/97880.97892.
Naylor, B. (mayo de 1993). "Construcción de buenos árboles de particionamiento". Interfaz gráfica . CiteSeerX 10.1.1.16.4432 .[ enlace muerto ]
Chen, S.; Gordon, D. (septiembre de 1991). "Visualización de árboles BSP de adelante hacia atrás". IEEE Computer Graphics and Applications . 11 (5): 79–85. doi :10.1109/38.90569. S2CID 19056967.
Radha, H.; Leoonardi, R.; Vetterli, M.; Naylor, B. (1991). "Representación de imágenes mediante árbol de partición espacial binaria". Revista de comunicaciones visuales y procesamiento de imágenes . 2 (3): 201–221. doi : 10.1016/1047-3203(91)90023-9 .
Radha, HMS (1993). Representación eficiente de imágenes mediante árboles de partición del espacio binario (PhD). Universidad de Columbia. OCLC 30775044.
Radha, HMS (1994). "Representación eficiente de imágenes utilizando árboles de partición espacial binarios". Procesamiento de señales . 35 (2): 174–181. Bibcode :1994SigPr..35..174R. doi :10.1016/0165-1684(94)90047-7.
Radha, H.; Vetterli, M.; Leoonardi, R. (diciembre de 1996). "Compresión de imágenes mediante árboles de partición espacial binarios". IEEE Transactions on Image Processing . 5 (12): 1610–24. Bibcode :1996ITIP....5.1610R. doi :10.1109/83.544569. PMID 18290079.https://ui.adsabs.harvard.edu/abs/1996ITIP....5.1610R/abstract
Winter, AS (abril de 1999). "Una investigación sobre la representación de polígonos 3D en tiempo real utilizando árboles bsp". CiteSeerX 10.1.1.11.9725 .
Ericson, Christer (2005). "8. Jerarquías de árboles BSP". Detección de colisiones en tiempo real . Serie de Morgan Kaufmann sobre tecnología 3D interactiva. Morgan Kaufmann. págs. 349–382. ISBN 1-55860-732-3.
Enlaces externos
Naylor, BF (2005). "Un tutorial sobre árboles de particionamiento del espacio binario".
Presentación de árboles BSP
Otra presentación de árboles BSP
Una aplicación Java que demuestra el proceso de generación de árboles.
