Partición del espacio binario: Explorando la partición del espacio binario: fundamentos y aplicaciones en visión por computadora

Capítulo 1: Particionamiento de espacio binario

El particionamiento de espacio binario (BSP) es un método para el particionamiento de espacio en ciencias de la computación que subdivide recursivamente un espacio euclidiano en dos conjuntos convexos utilizando hiperplanos como particiones. Este procedimiento genera una representación de objetos dentro del espacio en forma de árbol BSP, una estructura de datos similar a un árbol.

En 1969 se desarrolló la partición del espacio binario en el contexto de los gráficos por ordenador en 3D. La detección de colisiones en robótica y videojuegos 3D, trazado de rayos y otras aplicaciones que implican la manipulación de situaciones espaciales complicadas.

El proceso genérico de separar recursivamente una escena en dos hasta que la partición satisfaga uno o más requisitos se conoce como particionamiento de espacio binario. Se puede ver como una generalización de otras estructuras de árbol espacial, como los árboles k-d y los árboles cuádruples, en los que los hiperplanos que dividen el espacio no están alineados con los ejes de coordenadas. En gráficos por ordenador, al renderizar escenarios formados por polígonos planos, los planos de división se eligen normalmente para que coincidan con los planos definidos por los polígonos de la escena.

La selección precisa del plano de particionamiento y los criterios para detener el proceso de particionamiento varían en función del uso previsto del árbol BSP. En el renderizado de gráficos por computadora, por ejemplo, la escena se subdivide hasta que cada nodo del árbol BSP incluye solo polígonos que se pueden dibujar en cualquier secuencia. Cuando se emplea la selección de cara posterior, cada nodo tiene un conjunto convexo de polígonos, sin embargo, cuando se representan polígonos de doble cara, cada nodo del árbol BSP contiene solo polígonos basados en planos. En la detección de colisiones o el trazado de rayos, una escena se puede dividir en primitivas para las que las pruebas de colisión o intersección de rayos son simples.

Los gráficos por computadora requerían la partición del espacio binario para renderizar rápidamente escenas tridimensionales hechas de polígonos. El algoritmo del pintor produce polígonos en orden de distancia del observador, de atrás hacia adelante, pintando sobre el fondo y los polígonos anteriores con cada objeto que está más cerca del espectador. Este método tiene dos inconvenientes: el tiempo necesario para ordenar los polígonos en orden inverso y la probabilidad de errores en los polígonos que se superponen. Fuchs y sus coautores demostraron que la construcción de un árbol BSP resolvió ambos problemas al proporcionar un método rápido de ordenación de polígonos con respecto a un punto de vista dado (lineal en el número de polígonos en la escena) y al subdividir polígonos superpuestos para evitar errores relacionados con el algoritmo del pintor. Una desventaja de la partición de espacios binarios es el tiempo necesario para generar un árbol BSP. Por lo tanto, antes de renderizar u otras operaciones en tiempo real en una escena, normalmente se realiza una vez en geometría estática como fase de cálculo previo. Mover objetos directamente a un árbol es desafiante e ineficiente debido al costo de crear un árbol BSP.

Los árboles BSP se utilizan con frecuencia en videojuegos 3D, especialmente en juegos de disparos en primera persona y títulos con escenarios interiores. Doom (id Tech 1), Quake (variación id Tech 2), GoldSrc y Source son motores de juego que utilizan árboles BSP. En ellos, los árboles BSP que contienen la geometría estática de la escena se utilizan con frecuencia junto con un búfer Z para combinar correctamente elementos móviles como puertas y personajes en la escena de fondo. Si bien la partición del espacio binario facilita el almacenamiento y la recuperación de información espacial sobre los polígonos de una escena, no resuelve el problema de la determinación de la superficie visible.

La aplicación estándar de un árbol BSP es renderizar polígonos de doble cara sin selección de la cara posterior utilizando el método del pintor. Cada polígono tiene un anverso y un reverso que se pueden elegir libremente y solo afectan a la estructura del árbol, no al resultado deseado.

Seleccione un polígono de la lista P.

Agregue P a la lista de polígonos en el nodo N en el árbol BSP.

Para cada polígono adicional de la lista:

Si ese polígono está completamente delante del plano que contiene P, agréguelo a la lista de nodos delante de P.

Si este polígono está completamente detrás del plano que contiene P, agréguelo a la lista de nodos detrás de P.

Si el polígono está atravesado por el plano que contiene P, divídelo en dos polígonos y agrégalos a las listas de polígonos detrás y delante de P, respectivamente.

Agregue este polígono a la lista de polígonos en el nodo N si se encuentra en el plano que contiene P.

Aplique este procedimiento a la lista de polígonos que precede a P.

Aplicando este método a la lista de polígonos detrás de P.

Este diagrama muestra cómo se puede utilizar este enfoque para convertir una lista de líneas o polígonos en un árbol BSP. En cada uno de los ocho pasos (i.-viii), se aplica el método anterior a la lista de líneas y se agrega un nuevo nodo al árbol.

Dado que las líneas o polígonos que cruzan el plano de partición deben dividirse en dos, el número final de polígonos o líneas de un árbol suele ser mayor (y a veces considerablemente mayor) que la lista inicial. Es preferible limitar este crecimiento preservando un equilibrio justo en el árbol final. La decisión de qué polígono o línea utilizar como plano de partición (en el paso 1 del método) es crucial para la creación efectiva de un árbol BSP.

Un árbol BSP se atraviesa en tiempo lineal, en un orden dado por la función específica del árbol. Para crear correctamente el polígono P, utilizando el ejemplo de la representación de polígonos de doble cara utilizando la técnica del pintor, se deben dibujar primero todos los polígonos detrás del plano en el que se encuentra P, seguidos del polígono P y, por último, los polígonos delante de P. Si todos los polígonos de una escena se adhieren a este orden de dibujo, la escena se renderizará en el orden correcto. Con el siguiente algoritmo, este procedimiento se puede implementar atravesando iterativamente un árbol BSP. Desde un punto de vista V dado, represente un árbol BSP, si el nodo actual es un nodo hoja, dibuje los polígonos del nodo actual.

Si el sitio de visualización V está delante del nodo actual, el algoritmo continúa:

Represente el árbol BSP secundario que contiene polígonos detrás del nodo actual.

Renderizar polígonos ubicados en el nodo actual

Represente el árbol BSP secundario que contiene polígonos delante del nodo actual.

Si la ubicación de visualización V se encuentra detrás del nodo actual:

Represente el árbol BSP secundario que contiene polígonos delante del nodo actual.

Renderizar polígonos ubicados en el nodo actual

Represente el árbol BSP secundario que contiene polígonos detrás del nodo actual.

La posición de visualización V debe estar exactamente en el plano conectado con el nodo actual si este no es el caso. Entonces:

Represente el árbol BSP secundario que contiene polígonos delante del nodo actual.

Represente el árbol BSP secundario que contiene polígonos detrás del nodo actual.

Las siguientes etapas provienen de la aplicación iterativa de esta técnica al árbol BSP producido anteriormente:

El procedimiento se aplica inicialmente al nodo raíz del árbol, A. V está delante de A, por lo tanto, el procedimiento se aplica inicialmente al árbol BSP secundario