Partición binaria del espacio

La partición de espacio binario ( partición de espacio binario o BSP ) es un sistema que se utiliza para dividir el espacio en áreas convexas . Estas células están delimitadas por hiperplanos  ; en el caso de un espacio bidimensional (plano), las separaciones son líneas rectas y las celdas son cuadriláteros (a menudo rectángulos ); en el caso de un espacio tridimensional, las separaciones son planos y las celdas son poliedros (a menudo paralelepípedos rectangulares ).

Las celdas están organizadas en un árbol binario llamado árbol BSP . Esta estructura de datos facilita determinadas operaciones. Es particularmente interesante para el renderizado 3D y, por lo tanto, se utiliza para administrar los gráficos de ciertos videojuegos .

Histórico

• 1969 Schumacker y col. publique un informe que describa cómo los planos cuidadosamente colocados en un entorno virtual pueden acelerar el orden de los polígonos . La técnica utiliza la profundidad de coherencia, una noción de que un polígono ubicado en el semiplano más alejado del espectador no puede enmascarar un polígono ubicado en el semiplano más cercano. Esta noción la utilizan los simuladores de vuelo desarrollados por General Electric y Evans & Sutherland . Sin embargo, la creación de la jerarquía poligonal la realiza manualmente el diseñador de la escena.

• 1975 Bentley de la Universidad de Stanford propone la estructura de árboles k -d para la investigación multidimensional.

• 1980 Fuchs y col. extender la idea de a la representación de objetos virtuales en 3D, utilizando los planos de los polígonos y dividiendo el espacio de forma recursiva. Por lo tanto, crean un algoritmo completamente automatizado para crear una estructura de datos jerárquica para polígonos, llamado Árbol de Partición de Espacio Binario (Árbol BSP) . Este proceso tiene lugar en un paso de cálculo previo, antes de la entrega al usuario final. Cuando se ejecuta en tiempo real, el orden de los polígonos para determinar la visibilidad se realiza atravesando el árbol.

• 1981 La tesis doctoral de Naylor combina árboles BSP y teoría de grafos para determinar la visibilidad precalculada. Enfatiza el uso de árboles BSP como una estructura de investigación independiente de la dimensión espacial, con aplicaciones en la visibilidad de superficies. Usando el modelo del transbordador espacial , la tesis demuestra empíricamente que el tamaño del árbol y el número de nuevos polígonos creados es razonable.

• 1983 Fuchs y col. describen un código de árbol BSP mínimo en un sistema de búfer de tramas de Ikonas. Esta es la primera implementación de la determinación de la visibilidad de la superficie en tiempo real utilizando árboles BSP.

• 1987 Thibault y Naylor describen cómo representar poliedros utilizando árboles BSP, en contraste con el método habitual B-Rep (representación de límites) . Tenemos una representación de sólidos en contraposición a una representación de superficies (los límites de los sólidos). Las herramientas ofrecidas para poliedros permiten la renderización de sólidos descritos por Constructive Solid Geometry (CSG) en tiempo real. Es el precursor del método de diseño de niveles BSP mediante pinceles , introducido en el editor de Quake y reutilizado en el editor de Unreal .

• 1990 Naylor, Amanatides y Thibault proporcionan un algoritmo para fusionar dos árboles BSP en uno. Esto hace posible en particular: combinar objetos en movimiento, representados por árboles BSP, con un entorno estático también representado por un árbol BSP; realizar operaciones booleanas entre poliedros (CSG) de forma rápida; cálculos de colisión exacta en O (log n × log n )  ; y ordenar correctamente las superficies transparentes contenidas en objetos interpenetrantes (utilizados para el efecto de visión de rayos X).

• 1990 Teller y Séquin proponen determinar los elementos potencialmente visibles antes de la entrega del software, para acelerar la determinación de superficies visibles en entornos ortogonales 2D.

• 1991 Gordon y Chen describen un método eficaz de renderizado de adelante hacia atrás a partir de un árbol BSP, en lugar del enfoque habitual de atrás hacia adelante. Utilizan una estructura de datos dedicada para registrar, de manera eficiente, las partes de la pantalla que ya se han dibujado y las que aún no se han dibujado. Este algoritmo fue utilizado por John Carmack para crear el videojuego Doom .

• 1992 La tesis doctoral de Teller describe un método eficaz para determinar conjuntos potencialmente visibles, en un paso de preprocesamiento, que permite acelerar la determinación de superficies visibles en tiempo real en un entorno 3D formado por polígonos. Este método se utilizó en Quake y contribuyó significativamente al rendimiento del juego.

• 1993 Naylor determina qué caracteriza a un árbol BPS "bueno". Mide matemáticamente el costo de buscar un árbol y lo aplica a la construcción de árboles "buenos", basándose en casos probables en lugar de un análisis del peor de los casos. Intuitivamente, los árboles de la derecha representan objetos en diferentes niveles de resolución (árbol de aproximaciones). Este método tiene similitudes con la codificación de Huffman y los árboles de búsqueda de permutación aleatoria .

• 1993 La tesis doctoral de Hayder Radha describe un método de representación de imágenes (naturales) utilizando árboles BSP. Esto incluye el desarrollo de una estructura de construcción de árbol BSP óptima para una imagen arbitraria. Esta estructura se basa en una nueva transformación de imagen, la transformación por una línea de partición obtenida por regresión de mínimos cuadrados (transformación de línea de partición con error de mínimos cuadrados) . La tesis de Radha también desarrolla una estructura de compresión de imágenes con una tasa de distorsión óptima y un enfoque de manipulación de imágenes utilizando árboles BSP.

Definición

Descripción

Desde un punto de vista geométrico, los árboles BSP son la versión genérica de los plátanos para dividir el espacio. Los árboles k -d son casos especiales de árboles BSP, en los que los planos están alineados con los ejes y cuyos nodos contienen solo un punto. Los árboles BSP son estructuras más generales en las que los planos pueden tener cualquier orientación - generalmente son planos generados a partir de polígonos - y cuyos nodos pueden contener cualquier tipo de objeto geométrico - en general formas “primitivas” (formas geométricas simples: polígonos, cubos, esferas , cilindros, etc.).

El primer nodo del árbol es el espacio, contiene un plano que divide el espacio en dos. Sus dos nodos hijos son medios espacios, ellos mismos contienen planos que dividen estos subespacios en dos. Los nodos terminales del árbol ya no contienen planos y se denominan "hojas".

El “nivel de detalle” - donde nos detenemos en la construcción del árbol, lo que contienen los nodos - depende del campo de aplicación. Por ejemplo :

• para imágenes sintéticas con renderizado 3D, los nodos contienen un conjunto de polígonos que se pueden dibujar en un orden arbitrario,
  • si hay selección de cara posterior , un nodo contiene un conjunto de polígonos convexos,
  • si se pueden ver ambas caras de un polígono (según el punto de vista), un nodo contiene solo polígonos coplanares;
• en el cálculo de colisión o trazado de rayos , un nodo contiene una porción de espacio en la que las pruebas de interceptación son directas.

Construcción

La construcción de un árbol BSP puede basarse en técnicas muy diferentes.

Es muy simple cuando solo desea usarlo como una estructura de almacenamiento poligonal. Los motores de física a menudo usan BSP rudimentarios para almacenar geometría estática (generalmente árboles k -d ), su construcción se realiza muy rápidamente.

Los motores de videojuegos utilizan sistemas de construcción mucho más complejos porque el BSP debe coincidir con una estructura de tipo sector / portal para poder realizar cálculos de oclusión. Para tener la estructura más limpia posible, los árboles generalmente no se construyen a partir de una malla poligonal, sino utilizando un entrelazado de sólidos convexos, como lo hacen id Tech y Unreal Engine . El id Tech simplemente agrega un sólido convexo, el Unreal Engine presenta la excavación booleana para optimizar aún más la geometría de los árboles.

Una vez que se construye el árbol BSP, se convierte en una estructura de tipo sector / portal, una estructura sobre la que descansará la oclusión. En el motor de id Tech , los portales se generan automáticamente mediante un algoritmo de recorte , luego la oclusión se calcula previamente en una máscara de bits denominada conjuntos potencialmente visibles . En Unreal Engine , a partir de la versión 2, es el proceso inverso: los portales los construye el diseñador a mano y se añaden a la geometría del árbol BSP. La oclusión se calcula en tiempo real gracias a los portales.

Dado que este proceso de creación de mapas BSP es muy largo y costoso de desarrollar, los estudios de creación de videojuegos generalmente prefieren utilizar los estándares id Tech o Unreal .

Ejemplo de construcción

Considere un renderizador 3D en el caso en el que es probable que se vean ambas caras de los polígonos. Podemos aplicar el siguiente algoritmo de construcción recursiva:

1. Elija un polígono P de la lista.
2. Cree un nodo N en el árbol BSP y coloque P en la lista de polígonos de este nodo.
3. Para cada polígono de la lista:
   1. Si este polígono está completamente enfrente del plano que contiene P, coloque este polígono en la lista de polígonos delante de P.
   2. Si este polígono está completamente detrás del plano que contiene P, coloque este polígono en la lista de polígonos detrás de P.
   3. Si el plano que contiene P es secante con el polígono, divida el polígono en dos por el plano de P y coloque cada uno de los medios polígonos en la lista correspondiente (delante de P, detrás de P).
   4. Si el polígono es coplanar con P, agréguelo a la lista de polígonos para el nodo N.
4. Aplique este algoritmo a la lista de polígonos delante de P.
5. Aplique este algoritmo a la lista de polígonos detrás de P.

Así podemos ordenar los polígonos desde el más lejano al más cercano al punto de vista, y así saber en qué orden dibujar los polígonos para tener en cuenta los efectos de enmascaramiento.

Más concretamente, tomemos el ejemplo de un plano (espacio bidimensional) en el que los objetos geométricos son segmentos de línea . Cada segmento tiene una orientación, por lo que tiene un “anverso” y un “reverso”, definidos al crear el segmento.

	El espacio contiene cuatro segmentos de línea {A, B, C, D}; si fuera un problema de renderizado 3D, serían polígonos formando una "escena". En el árbol, los nodos del árbol están en círculos y las listas de objetos delante o detrás están en rectángulos redondeados. El anverso de cada segmento se indica con una flecha.
I.	Aplicamos el algoritmo presentado anteriormente: Elegimos arbitrariamente un segmento, aquí el A. Creamos el nodo raíz que contiene A. Se cortan los segmentos que se cruzan con la línea que lleva A; entonces tenemos nuevos segmentos, {B1, B2, C1, C2, D1, D2}. Algunas están ubicadas frente a A, {B2, C2, D2} y otras están ubicadas detrás, {B1, C1, D1}. Procesamos, de forma recursiva, primero los segmentos ubicados delante de A (etapas ii - v), luego los ubicados detrás (etapas vi - vii).
ii.	Consideramos los segmentos ubicados frente a A, {B2, C2, D2}. Creamos un nodo hijo, elegimos un segmento arbitrario, B2, y lo agregamos a este nodo. Cortamos el segmento secante con la línea que lleva B2, lo que crea dos nuevos segmentos, {D2, D3}. Separamos los segmentos ubicados frente a B2, {D2}, y los ubicados detrás, {C2, D3}.
iii.	Consideramos los segmentos ubicados frente a B2. Solo hay un segmento, D2, por lo que creamos un nodo hijo de B2 que lo contiene, es una hoja del árbol.
iv.	Ahora consideramos los segmentos detrás de B2, {C2, D3}. Elegimos arbitrariamente un segmento, C2, y lo agregamos al nodo hijo de B2 que creamos. La lista de segmentos delante de C2 es {D3}, la lista de segmentos detrás está vacía.
v.	Consideramos la lista de segmentos frente a C2. El único segmento que contiene, D3, se agrega al nodo hijo de C2 que creamos.
vi.	Hemos procesado todos los segmentos ubicados frente a A; ahora estamos tratando con los que están detrás. Elegimos un segmento arbitrario, B1, que colocamos en el nodo hijo de A que creamos. Separamos los segmentos en dos listas: los segmentos ubicados frente a B1, {D1}, y los ubicados detrás, {C1}.
vii.	Procesamos los segmentos ubicados frente a B1. Solo hay un segmento, D1, por lo que creamos un nodo hijo de B1 para ponerlo allí.
viii.	Procesamos los segmentos detrás de B1. Solo hay un segmento, C1, por lo que creamos un nodo hijo de B1 para ponerlo allí. El árbol BSP está completo.

Agujeros BSP y HOM

Un agujero BSP, o agujero BSP , es un problema común que se encuentra al ver un gráfico almacenado como un árbol BSP. Esto se manifiesta por un agujero en el objeto representado, que puede ser negro, o dejar mostrar lo que hay detrás; en este caso, hablamos de "palacio de hielo", o HOM (por salón del espejo ), pero podemos tener un HOM sin que haya un agujero BSP.

Algunos agujeros BSP son aleatorios: solo aparecen desde ciertos puntos de vista. Otros son permanentes: el objeto está ausente sea cual sea el punto de vista; esto suele ser un error de edición. También puede haber un efecto de colisión contra un obstáculo invisible (ICH, casco de colisión invisible ): el motor detecta una colisión e impide que el jugador avance, pero no se muestra ningún objeto.

El agujero BSP generalmente se encuentra cuando la geometría es demasiado detallada. Su corte puede dar lugar a una escala demasiado pequeña lo que genera errores relacionados con la aproximación de los números ( error de redondeo ). Para evitar estos problemas, los programas de codificación BSP destruyen la geometría donde la escala se vuelve demasiado pequeña, provocando agujeros en el árbol.

Para evitar estos agujeros, la geometría debe simplificarse. Es por esto que las partes detalladas de un mapa deben estar hechas con elementos que no forman parte del BSP: quadpatch , trimesh , modelos y entidades para el motor id Tech , terrenos y mallas estáticas para el Unreal Engine .

Un HOM ocurre cuando el motor gráfico no tiene nada que mostrar (lo que no significa que haya un agujero BSP); para ahorrar recursos, el motor simplemente dibuja sobre la imagen anterior y no la borra, por lo que vemos elementos de la imagen que se muestran uno encima del otro como cuando hay dos espejos enfrentados, de ahí el nombre “palacio de hielo”. HOM se encuentra a menudo en los juegos de  disparos en primera persona : el punto de vista del jugador debe estar en un área limitada. Pero esta suposición puede violarse si el jugador usa un modo de “cámara virtual” (modo sin clip ); la parte mostrada del árbol BSP está incompleta y contiene agujeros BSP, que revelan elementos de la imagen anterior.

Viaje

El camino de un árbol BSP es lineal en el tiempo , O ( n ). El algoritmo de ruta depende del objetivo perseguido.

Localizar un punto es la operación más simple y se realiza en un pequeño bucle, sin la necesidad de una función recursiva. Probamos en qué lado del plano de la raíz está el punto, luego comenzamos de nuevo en el hijo correspondiente y hacemos un bucle hasta que caemos en la hoja que contiene el punto.

En el caso de un árbol que representa los polígonos que se van a mostrar, la ruta del árbol se puede utilizar para determinar el orden en el que deben mostrarse los polígonos ( algoritmo de pintor ). El siguiente algoritmo de visualización recursiva se utiliza para esto:

1. Si el nodo actual es una hoja, muestre los polígonos contenidos en el nodo actual.
2. De lo contrario, si el punto de vista V está frente al nodo actual:
   1. Muestre la rama secundaria que contiene los polígonos ubicados detrás del nodo actual.
   2. Muestra los polígonos contenidos en el nodo actual.
   3. Muestre la rama secundaria que contiene los polígonos ubicados frente al nodo actual.
3. De lo contrario, si el punto de vista V está detrás del nodo actual:
   1. Muestre la rama secundaria que contiene los polígonos ubicados frente al nodo actual.
   2. Muestra los polígonos contenidos en el nodo actual.
   3. Muestre la rama secundaria que contiene los polígonos ubicados detrás del nodo actual.
4. De lo contrario, el punto de vista V está exactamente en el plano asociado con el nodo actual. Entonces :
   1. Muestre la rama secundaria que contiene los polígonos ubicados frente al nodo actual.
   2. Muestre la rama secundaria que contiene los polígonos ubicados detrás del nodo actual.

Apliquemos este algoritmo al ejemplo anterior:

• Comenzamos en la raíz, el nodo A. V está frente al nodo (el frente está indicado por la flecha), por lo que aplicamos el algoritmo de forma recursiva a los nodos ubicados detrás, es decir, la rama B1.
  • El nodo actual es B1. V está detrás de B1, por lo que aplicamos el algoritmo de forma recursiva a los nodos ubicados al frente, es decir, la rama D1.
    • El nodo actual es D1. Es una hoja, entonces mostramos D1 .
  • Luego mostramos B1 .
  • Luego aplicamos el algoritmo de forma recursiva a los nodos ubicados detrás de B1, es decir, la rama C1.
    • El nodo actual es C1. Es una hoja, entonces mostramos C1 .
• A continuación, muestra A .
• Luego aplicamos el algoritmo de manera recursiva a los nodos ubicados frente a A, es decir la rama B2.
  • El nodo actual es B2. V está detrás de B2, por lo que aplicamos el algoritmo de forma recursiva a los nodos ubicados al frente, es decir, la rama D2.
    • El nodo actual es D2. Es una hoja, entonces mostramos D2 .
  • Luego mostramos B2 .
  • Luego aplicamos el algoritmo de forma recursiva a los nodos ubicados detrás de B2, es decir, la rama C2.
    • El nodo actual es C2. V está delante de C2, por lo que aplicamos el algoritmo de forma recursiva a los nodos detrás de él.
      • No hay nudo.
    • Luego mostramos C2 .
    • Luego, el algoritmo se aplica de forma recursiva a los nodos ubicados frente a C2, es decir, la rama D3.
      • El nodo actual es D3. Es una hoja, entonces mostramos D3 .

El nodo se atraviesa linealmente en el tiempo y los polígonos se muestran en orden de más lejano a más cercano (D1, B1, C1, A, D2, B2, C2, D3) según lo requiera el algoritmo del pintor.

Usar en videojuegos

En los videojuegos, ciertos objetos o sujetos son móviles. Por lo tanto, la construcción del árbol BSP debe realizarse cada vez que se actualiza la imagen. Es un paso precalculatorio.

Debido a la complejidad de construir árboles BSP adecuados para motores de juegos, muchas empresas no desarrollan su propio formato de mapa, sino que utilizan motores existentes, en particular, los estándares Unreal e id Tech ( Quake ) . Por ejemplo, el motor Half-Life se basa en el motor Quake 1 . El estándar actual es Unreal Engine . El id Tech , más allá de la comunidad de código abierto , se ha convertido en el formato estándar utilizado por los desarrollos BSP aficionados o independientes.

Por lo tanto, las diversas observaciones que se presentan a continuación se basan esencialmente en el estudio de estos dos formatos estándar.

Oclusión / colisiones / proyecciones de sombras

Estas son las principales funciones de los árboles BSP: optimizar los cálculos de colisión, oclusión y sombras.

El motor de Doom calculó la oclusión en tiempo real, directamente en la rutina de visualización, recortando las caras ordenadas usando el BSP. El motor de Quake y sus derivados calculan previamente la oclusión en listas de grupos de hojas que se pueden ver entre sí ( conjunto potencialmente visible ) . En los motores más modernos, la oclusión se basa en puertas y anti-puertas, el BSP pierde su función oclusiva pero aún sirve como una estructura de almacenamiento para el interior .

En los motores más antiguos, los cálculos de colisión se basaban directamente en las escobillas (sólidos convexos) utilizados para construir el eje. En el motor de Doom , estos cepillos fueron construidos por el propio árbol. En los motores más recientes, las colisiones se basan en un motor de física, cuyo mapa de colisiones puede ser completamente independiente de la estructura del árbol.

Las sombras proyectadas se introdujeron en Unreal Engine o Doom 3 . Doom 3 usa un algoritmo muy similar al que usa la cámara para renderizar rostros, completamente basado en el BSP (ver el reverso de Carmack ).

Evolución matemática en los videojuegos clásicos

BSP se ha utilizado en casi todos los juegos 3D desde Doom , Unreal , Quake y Half-Life .

El motor de Doom construyó BSP a partir de sectores poligonales. El motor de Quake / Half-Life construye BSP a partir de sólidos convexos. El sistema de modelado de árboles BSP utilizado por Unreal Engine llamado geometría sólida constructiva introduce la noción de excavación booleana  : se utilizan sólidos "invertidos", que hacen que la construcción de BSP sea más eficiente, este sistema tiene la ventaja de reducir el riesgo de HOM o Orificio BSP (ver arriba ), errores de diseño comunes a todos los motores.

Evolución visual

Utilizado por primera vez en dos dimensiones para todos los niveles bajo Doom , el BSP 2d originalmente no permitía crear piezas superpuestas en el eje Z (eje de altura). Sin embargo, esta era una limitación inherente del motor, el Doom Engine , que, revolucionario para el momento, ahora parece extremadamente limitado.

Es con su variación en 3d en el motor de Quake y sus sucesores Quake II o Quake III , y sus competidores Unreal , o un poco más tarde Half-Life que el BSP alcanza su máximo uso, las decoraciones son enriquecedoras gracias a la multiplicación de la potencia de los motores pero también de la velocidad de procesamiento y de la potencia de cálculo de los microprocesadores , y la aparición de tarjetas gráficas cada vez más potentes. El BSP constituyó entonces la mayor parte de la arquitectura general de los niveles en 3D. Fue en esta época que empezaron a aparecer los actores de la decoración, no conformados por BSP, sino escasos en número y de ardua creación. Los sistemas prefabricados permiten crear estructuras complejas, guardarlas independientemente del nivel actual y reutilizarlas posteriormente sin cesar. Estos "prefabricados" se prefieren entonces a los actores de la decoración, pero al estar compuestos por BSP, tienen todas las desventajas.

Combinación de BSP con estructuras de visualización detalladas

El BSP tiene la desventaja de ser adecuado para arquitectura con bajo número de polígonos (polígono bajo) , es necesario agregar elementos que no sean BSP para obtener detalles.

En juegos recientes (alrededor de la década de 2000), el BSP tiende a acoplarse, para detalles arquitectónicos y decoraciones complejas, con sistemas mejor optimizados.

El ejemplo más revelador es sin duda el de las mallas estáticas  (en) y los terrenos del Unreal Engine , que apareció con la segunda versión del motor en 2002, en el juego Unreal II . Estos objetos son la evolución de los jugadores de decoración ajenos al BSP que suelen ocupar la mayoría de las funciones asignadas anteriormente al BSP: objetos móviles, detalles arquitectónicos y, cada vez más, grandes formas generales de habitaciones.

El id Tech 3 introdujo quadpatch (curvas) y mallas cualquiera. Sistemas cercanos a los terrenos / malla estática de Unreal , pero menos optimizados.

Las razones de este reemplazo son simples: las mallas estáticas (y sus equivalentes en otros motores) son insensibles a todos los problemas relacionados con el BSP: HOM, “fantasmas sólidos” (bajo Half-Life ), etc. También mejoran la velocidad de los niveles de carga: se puede instanciar una malla estática . Esto significa que el motor solo necesita cargar el objeto una vez y luego duplicarlo tantas veces como sea necesario con los cambios apropiados aplicados.

Por otro lado, esto no mejora la velocidad de visualización: cada objeto así "clonado" debe mostrarse individualmente. Sin embargo, la reducción del número de accesos a los discos duros puede mejorar el rendimiento de algunos juegos.

Los niveles exteriores

Los niveles exteriores usan muy poco BSP y prefieren estructuras más adaptadas como canchas y octárboles .

Como los sistemas de terreno BSP requieren grandes cantidades de BSP muy deformados que causan cada vez más problemas y errores , se introdujeron generadores de terreno al mismo tiempo que mallas estáticas , para crear piezas grandes con geometrías muy altas, optimizadas para este tipo de renderizados. El uso combinado de mallas estáticas y generadores de terreno cada vez más poderosos conduce a la creación de niveles que a veces comprenden una cantidad irrisoria de objetos BSP: en Unreal Tournament 2004 , estos sistemas te permiten crear niveles que comprenden dos grandes cubos vacíos, uno que contiene el terreno y el mallas estáticas , y el otro es un Skybox . Juegos como Unreal y Half-Life usaban terreno BSP, que era muy angular y difícil de optimizar.

Iluminación de superficie

La iluminación de las superficies BSP ha pasado por tres etapas principales. Primero fue la iluminación simple y estática utilizada en Doom y Doom II: Hell on Earth  : varios niveles de iluminación definidos permiten que el nivel se ilumine de manera casi uniforme.

Los juegos de próxima generación permitían atmósferas muy animadas gracias a la iluminación dinámica y contrastada como ciertos niveles de Unreal , Unreal Tournament , Half-Life . En Quake 3, puedes elegir entre este sistema de iluminación dinámica, o un sistema Lightmap  : texturas de colores aplicadas por transparencia a la geometría del nivel para simular las diferencias de luz. Este proceso prohíbe cualquier luz dinámica, pero permite sombras muy precisas y marcadas. Bajo UT2003 y su sucesor directo UT2004 , los Lightmaps constituyen casi toda la iluminación del BSP. Algunos sistemas de iluminación dinámica persisten, pero son muy costosos en recursos, lo que obliga al motor a actualizar los Lightmaps en todo momento. Además, las luces no pueden proyectar sombras tan realistas y detalladas como las luces estáticas.

Los juegos más nuevos como Doom 3 están altamente optimizados y sus sistemas de iluminación, tanto detallados como dinámicos, te permiten proyectar sombras muy bien administradas en el BSP, pero también en los actores de decoración.

Otras aplicaciones

Generalmente, las estructuras de árbol se utilizan para muchos algoritmos. Por ejemplo, podemos usar una partición binaria para encontrar los vecinos más cercanos de un punto o la búsqueda por rango  : la construcción del árbol consume muchos recursos, pero su ruta es mucho más rápida que un barrido sistemático de todos los puntos. El árbol k -d es interesante a este respecto porque los algoritmos de partición permiten construir árboles aproximadamente equilibrados con pocas celdas vacías y una dimensión grande / celda pequeña favorable para la investigación.

Abandono de BSP en tuberías de gráficos modernos

El BSP se utilizó durante mucho tiempo en motores de videojuegos como las versiones antiguas de Quake o Unreal, porque tenía dos ventajas: ordenar las caras en el momento en que el 3d no era renderizado por la gpu, y generar automáticamente una Gráfica muy fina de celdas y portales que permitió calcular una oclusión al polígono más cercano.

Sin embargo, la estructura BSP tenía el inconveniente de generar muchos errores: "agujeros", "fugas", "distorsiones", "hojas planas" y árboles pobremente optimizados debido a los muchos planes casi confusos.

En los motores 3d modernos, la oclusión se realiza objeto por objeto ("chunk" o "lote"), por lo que se utilizan celdas más gruesas, que se pueden modelar manualmente (cry engine), o incluso cubos generados automáticamente (unreal 4, biblioteca umbra utilizada por unidad y tecnología de identificación 6). Luego utilizamos estructuras de almacenamiento derivadas de la bsp (octrees y kd-trees, basados ​​en planos ortogonales, por lo tanto normales no aproximados) que tienen la ventaja de ser estables y no producir errores durante su construcción.

El BSP, por otro lado, sigue siendo utilizado como una herramienta de modelado para acelerar la "geometría constructiva sólida", la construcción de sólidos complejos a partir de sólidos simples.

Notas y referencias

1. (en) Robert A. Schumacker , Brigitta Brand , Maurice G. Gilliland y Werner H. Sharp , Estudio para la aplicación de imágenes generadas por computadora a la simulación visual , Laboratorio de Recursos Humanos de la Fuerza Aérea de EE. UU.1969, 142  p..
2. (in) Jon Louis Bentley , "  Árboles de búsqueda binarios multidimensionales utilizados para búsquedas asociativas  " , Comunicaciones de la ACM , vol.  18, n o  9,1975, p.  509-517 ( DOI  10.1145 / 361002.361007 ).
3. (en) Henry Fuchs , M. Zvi Kedem y Bruce F Naylor , “  En superficie visible Generación de estructuras a priori del árbol  ” , SIGGRAPH '80 Actas de la séptima conferencia anual sobre gráficos por ordenador y técnicas interactivas , Nueva York, ACM,1980, p.  124-133 ( DOI  10.1145 / 965105.807481 ).
4. (in) William C. Thibault y Bruce F. Naylor , "  Las operaciones de conjuntos son poliedros utilizando árboles de partición de espacio binario  " , Actas de SIGGRAPH '87 de la 14a conferencia anual sobre gráficos por computadora y tecnología interactiva , Nueva York, ACM,1987, p.  153–162 ( DOI  10.1145 / 37402.37421 ).
5. (en) S. Chen y D. Gordon , "  Visualización de adelante hacia atrás de árboles BSP  " , Gráficos y algoritmos informáticos IEEE ,Septiembre de 1991, p.  79–85 ( leer en línea [PDF] ).
6. ver, por ejemplo, el uso de un árbol k -d para este propósito: (en) “  Re: Distancia por pares de una gran cantidad de puntos  ” , en Usuarios de Scilab - Archivos de listas de correo , 29 de agosto de 2014, 4:38 pm
7. en particular con el método de partición de punto medio deslizante

Artículos relacionados

• Algoritmo del pintor
• Octree
• Quadtree
• Archivo de mapa compilado para Valve Hammer Editor ( Half-Life , Counter-Strike …) o Doom and Quake .