La partición del espacio binario 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 información espacial de manera eficiente sobre los objetos en una escena, como los objetos que se ordenan. de adelante hacia atrás con respecto a un espectador en un lugar determinado. 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 involucran el manejo de estructuras complejas. escenas espaciales.
Historia
1969 Schumacker y cols. [1] publicó un informe que describía cómo se podrían utilizar planos cuidadosamente colocados en un entorno virtual para acelerar el orden de los polígonos. La técnica utilizó la coherencia de profundidad, que establece que un polígono en el lado más alejado del plano 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 poligonal la realizó manualmente el diseñador de la escena.
1980 Fuchs et al. [2] extendió 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 de espacio binario (á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ó atravesando el árbol.
1981 Doctorado de Naylor. La tesis proporcionó un desarrollo completo de ambos árboles BSP y un enfoque teórico de grafos que utiliza componentes fuertemente conectados para la visibilidad previa al cálculo, así como la conexión entre los dos métodos. Se hizo hincapié en los árboles BSP como estructura de búsqueda espacial independiente de las dimensiones, con aplicaciones para la determinación de la superficie visible. La tesis también incluyó los primeros datos empíricos que demostraban que el tamaño del árbol y el número de nuevos polígonos eran razonables (utilizando un modelo del transbordador espacial).
1983 Fuchs et al. describieron una implementación de microcódigo del algoritmo de árbol BSP en un sistema de buffer de cuadros Ikonas. Esta fue la primera demostración de determinación de la superficie visible 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 del tradicional b-rep (representación de límites). Esto proporcionó una representación sólida frente a una representación basada en la superficie. Se describieron operaciones de conjuntos sobre poliedros mediante una herramienta que permite realizar geometría sólida constructiva (CSG) en tiempo real. Este fue el precursor del diseño de niveles BSP usando " pinceles ", introducido en el editor Quake y retomado en Unreal Editor.
1990 Naylor, Amanatides y Thibault proporcionaron un algoritmo para fusionar dos árboles BSP para formar un nuevo árbol BSP a partir de los dos árboles originales. Esto proporciona muchos beneficios, incluida 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 transparencias. Superficies contenidas en dos objetos interpenetrados (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 desde 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 han dibujado y las que aún no se han 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: Principios y práctica ), fue utilizado por John Carmack en la realización de Doom (videojuego) .
1992 Doctorado de Teller . La tesis describió la generación eficiente de conjuntos potencialmente visibles como un paso de preprocesamiento para acelerar la determinación de la superficie visible en tiempo real en entornos poligonales 3D arbitrarios. Esto se usó en Quake y contribuyó significativamente al rendimiento de ese juego.
1993 Naylor respondió a la pregunta de qué caracteriza a un buen árbol BSP. Usó modelos de casos esperados (en lugar de análisis del peor de los casos) para medir matemáticamente el costo esperado de buscar un árbol y usó esta medida para construir buenos árboles BSP. Intuitivamente, el árbol representa un objeto en forma de resolución múltiple (más exactamente, como un árbol de aproximaciones). Se establecen paralelos con los códigos de Huffman y los árboles de búsqueda binaria probabilística.
1993 Doctorado de Hayder Radha. La tesis describió métodos de representación de imágenes (naturales) utilizando árboles BSP. Esto incluye el desarrollo de un marco de construcción de árbol BSP óptimo 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 (LPE) de error de mínimos cuadrados (LSE). La tesis de H. Radha también desarrolló un marco óptimo de compresión de imágenes de tasa de distorsión (RD) y enfoques de manipulación de imágenes utilizando árboles BSP.
Descripción general
La partición del espacio binario es un proceso genérico de dividir recursivamente 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 árboles espaciales, como los árboles k -d y los quadtrees , en las 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 k -d o árboles cuádruples. Cuando se utilizan en gráficos por computadora para representar escenas compuestas de polígonos planos , los planos de partición se eligen frecuentemente 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 terminar 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 nodo del árbol BSP contiene solo polígonos que se pueden representar en orden arbitrario. Cuando se utiliza la selección de la cara posterior , cada nodo, por lo tanto, contiene un conjunto convexo de polígonos, mientras que cuando se renderizan 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 en las que las pruebas de colisión o intersección de rayos son sencillas.
La partición del espacio binario surgió de los gráficos por computadora que necesitaban dibujar rápidamente escenas tridimensionales compuestas de polígonos. Una forma sencilla de dibujar este tipo de escenas es el algoritmo del pintor , que produce polígonos en orden de distancia del 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 necesario para ordenar los polígonos de atrás hacia adelante y la posibilidad de errores al superponer polígonos. Fuchs y sus coautores [2] demostraron que la construcción de un árbol BSP resolvió 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 en Evite errores que puedan ocurrir con el algoritmo del pintor. Una desventaja de la partición del espacio binario es que generar un árbol BSP puede llevar mucho tiempo. Por lo tanto, normalmente se realiza una vez en geometría estática, como paso de cálculo previo, antes de renderizar 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 renderizar polígonos (que son de doble cara, es decir, sin eliminación de la cara posterior ) con el algoritmo del pintor. Cada polígono está designado con un lado frontal y un lado posterior que pueden elegirse 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 uno de los demás polígonos de la lista:
Si ese polígono está completamente delante del plano que contiene P , mueva ese polígono a la lista de nodos delante de 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.
El recorrido
Un árbol BSP se recorre en un tiempo lineal, en un orden determinado por la función particular del árbol. Nuevamente usando 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 cumple para todos los polígonos de una escena, entonces toda la escena se representa en el orden correcto. Este procedimiento se puede implementar atravesando recursivamente un árbol BSP utilizando el siguiente algoritmo. [2] Desde una ubicación de visualización determinada V , para representar un árbol BSP,
Si el nodo actual es un nodo hoja, renderice los polígonos en el nodo actual.
De lo contrario, si la ubicación de visualización V está frente al nodo actual:
Renderice el árbol BSP secundario que contiene polígonos detrás del nodo actual
Renderizar los polígonos en el nodo actual
Renderice 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:
Renderice el árbol BSP secundario que contiene polígonos delante del nodo actual
Renderizar los polígonos en el nodo actual
Renderice 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:
Renderice el árbol BSP secundario que contiene polígonos delante del nodo actual
Renderice 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 el nodo raíz B1 . V está detrás de B1 , así 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 el nodo raíz B2 . V está detrás de B2 , así 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 el 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 tal árbol, así que continuamos.
Representamos el polígono C2 .
Aplicamos el algoritmo al árbol BSP secundario 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 lejano a cercano ( 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 , especialmente en los de disparos en primera persona y en aquellos con entornos interiores. Los motores de juegos 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 Z-buffer , para fusionar correctamente objetos móviles como puertas y personajes en la escena de fondo. Si bien la partición del espacio binario proporciona una manera 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 . Sin embargo, se han aplicado árboles BSP a la compresión de imágenes. [5]
^ ab Schumacker, RA; Marca, B.; Gilliland, MG; Afilado, WH (1969). Estudio para aplicar imágenes generadas por computadora a la simulación visual (Reporte). Laboratorio de Recursos Humanos de la Fuerza Aérea de EE. UU. AFHRL-TR-69-14.
^ abcdefgFuchs , Henry; Kedem, Zvi. METRO; Naylor, Bruce F. (1980). "Sobre la generación de superficie visible mediante estructuras de árboles a priori" (PDF) . SIGGRAPH '80 Actas de la séptima conferencia anual sobre gráficos por computadora y técnicas interactivas . ACM. págs. 124-133. doi : 10.1145/965105.807481.
^ ab Thibault, William C.; Naylor, Bruce F. (1987). "Establecer operaciones en poliedros utilizando árboles de partición de espacio binario". SIGGRAPH '87 Actas de la 14ª conferencia anual sobre gráficos por computadora 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 del espacio binario 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 Bib : 2022LaEco..37.1761E. doi : 10.1007/s10980-022-01452-6 .
^ H. Radha, M. Vetterli y R. Leonardi, "Compresión de imágenes mediante árboles de partición de espacio binario", 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.; Amanátides, J.; Thibault, W. (agosto de 1990). "La fusión de árboles BSP produce operaciones de conjuntos poliédricos". Gráficos por computadora ACM SIGGRAPH . 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 divisorios". Interfaz gráfica . CiteSeerX 10.1.1.16.4432 .[ enlace muerto ]
Chen, S.; Gordon, D. (septiembre de 1991). "Visualización de adelante hacia atrás de árboles BSP". Aplicaciones y gráficos por computadora IEEE . 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 en árbol de partición de espacio binario". 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 de espacio binario (Doctor). Universidad de Colombia. OCLC 30775044.
Radha, HMS (1994). "Representación eficiente de imágenes utilizando árboles de partición de espacio binario". Procesamiento de la señal . 35 (2): 174–181. 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 de espacio binario". Transacciones IEEE sobre procesamiento de imágenes . 5 (12): 1610–24. Código Bib : 1996ITIP....5.1610R. doi : 10.1109/83.544569. PMID 18290079.https://ui.adsabs.harvard.edu/abs/1996ITIP....5.1610R/abstract
Invierno, 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 Morgan Kaufmann sobre tecnología interactiva 3-D. Morgan Kaufman. págs. 349–382. ISBN 1-55860-732-3.
enlaces externos
Naylor, BF (2005). "Un tutorial sobre árboles de partición de espacios binarios".
Presentación de árboles BSP
Otra presentación de árboles BSP.
Un subprograma de Java que demuestra el proceso de generación de árboles.
