Partición binaria del espacio

Binary space partitioning o Partición Binaria del Espacio (BSP) es un método para subdividir recursivamente un espacio en elementos convexos empleando hiperplanos. Esta subdivisión da lugar a una representación de la escena por medio de una estructura de datos del árbol conocida como árbol de BSP.

Descripción

En diseño por ordenador es deseable que el dibujo de una escena sea correcta y rápida. Una manera sencilla de dibujar una escena correctamente es el algoritmo del pintor: dibujar primero lo más lejano y después lo más cercano. Sin embargo, este sistema es muy limitado ya que se pierde tiempo pintando objetos que más tarde serán tapados por otros.

La técnica del Z-Buffer puede asegurar que las escenas se dibujarán correctamente y que se eliminará la necesidad de seguir un orden como en el algoritmo del pintor, pero es poco eficiente en términos de memoria. Los árboles BSP dividen los objetos de forma que el algoritmo del pintor los dibujará correctamente sin necesidad de emplear un Z-buffer ni de ordenar los objetos como un simple árbol transversal que los mantenga en el orden adecuado. También sirve como base para otros algoritmos, como las listas de visibilidad, que buscan evitar dibujar sin necesidad.

El problema es que necesita un pre-procesamiento de la escena, lo que hace difícil e ineficiente insertar los objetos móviles directamente en el árbol BSP. Esto se suele solucionar empleando conjuntamente un Z-Buffer, usándolo para unir correctamente los objetos móviles como puertas y enemigos con el resto de la escena.

Los árboles BSP se emplean normalmente en los videojuegos, especialmente en los de acción en primera persona y en los que tienen entornos de interior. Probablemente el primer juego que empleó esta técnica fue Doom (ver motor de Doom para más información sobre la implementación). Otros usos incluye el Ray tracing y la detección de colisiones.

Definición recursiva del árbol binario

T(S):

• Si card(S) = 1:
  • T(S) es una hoja, v;
  • En la hoja se almacena el objeto (si existe), S(v).
• Si card(S) > 1:
  • La raíz v de T(S) almacena:
    • una recta (plano) hv,
    • conjunto S(v) de objetos contenidos en hv.
  • Hijo izquierdo de v: raíz de un árbol T(S-), con S − = {hv- instp S : s ? S}.
  • Hijo derecho de v: raíz de un árbol T(S+), con S + = {hv+ instp S : s ? S}.

instp: interceptado

Generación

La partición binaria del espacio es un proceso genérico que divide una escena recursivamente en dos hasta que satisface uno o más requisitos. El método específico empleado varía dependiendo del objetivo final. Por ejemplo, en un árbol BSP empleado para la detección de colisiones el objeto original sería dividido hasta que cada parte sea lo suficientemente sencilla como para ser individualmente comprobada, y en el renderizaje interesa que cada parte sea convexa, de forma que el algoritmo del pintor pueda ser usado.

El número final de objetos crecerá inevitablemente ya que las líneas y caras que se crucen con el plano de partición serán divididas en dos, y también es deseable que el árbol final esté razonablemente balanceado. De hecho, el algoritmo para crear un árbol BSP correcta y eficientemente es la parte más difícil de implementar. En un espacio de tres dimensiones, se emplean planos para dividir las caras de un objeto; en un espacio de dos se emplean líneas.

La siguiente imagen ilustra el proceso de partición de un polígono irregular en una serie de polígonos convexos. Destacar cómo cada paso produce polígonos con menos segmentos hasta que se llega a F y G, que son convexos y no necesitan mayor partición. En este caso en particular, la línea de partición se ha tomado empleando vértices existentes del polígono y no se intersecciona con ninguno de sus segmentos. Si la línea de partición se intersecciona con un segmento, o una cara en un modelo tridimensional, el/los segmento/s o cara/s tienen que ser divididas en dos dado que cada partición debe ser un objeto completo e independiente.

1. A es la raíz del árbol y de todo el polígono.
2. Se divide A en B y C
3. Se divide B en D y E.
4. Se divide D en F y G, que son convexos y se convierten en hojas del árbol.

Dado que la utilidad de un árbol BSP depende de cómo se generó, un buen algoritmo es esencial. La mayoría de los algoritmos prueban muchas posibilidades para cada partición hasta que se encuentra un resultado lo suficientemente bueno, y también mantienen la información necesaria en memoria para poder retroceder en caso de que una rama del árbol no sea satisfactoria y probar otras opciones. Por eso generar un árbol necesita mucho tiempo de computación.

Usos del Árbol BSP

Inicialmente, esta idea se propuso para los gráficos 3D por ordenador para incrementar la eficiencia de renderizado. Otros usos son el procesamiento geométrico con formas, Constructive Solid Geometry en herramientas CAD, detección de colisiones en robótica y videojuegos 3D, y otras aplicaciones informáticas que incluyen el manejo de estructuras espaciales complejas. la eliminación de caras ocultas ya que gracias a los planos divisorios del árbol conoceríamos qué polígonos están detrás o delante, teniendo solamente que considerar determinadas ramas del árbol a través de la posición desde la que nos estemos posicionando en él.

El uso más común de los árboles de BSP es probablemente retiro superficial ocultado en tres dimensiones. Los árboles de BSP proporcionan un método elegante, eficiente para clasificar polígonos vía una primera caminata del árbol de la profundidad: algoritmo “del pintor delantero” o Algoritmo del pintor.

Objetivos de los árboles BSP

• Permiten determinar el orden en que deben ser dibujados los polígonos para lograr el retiro superficial ocultado.
• Permiten determinar si un punto determinado está en una parte sólida del modelo o no.
• Permiten detectar las colisiones con el modelo.

Construcción de un árbol BSP

El algoritmo para construir un árbol de BSP es muy simple:

• Seleccionar un plano de la partición.
• Repartir el sistema de polígonos en el plano.
• Recubrir con cada uno de los dos nuevos sistemas.

Uso del BSPT

El uso más común de los árboles de BSP es probablemente retiro superficial ocultado en tres dimensiones. Los árboles de BSP proporcionan un método elegante, eficiente para clasificar polígonos vía una primera caminata del árbol de la profundidad: algoritmo “del pintor delantero” o algoritmo del pintor.

Algoritmo del pintor

• El Algoritmo “del pintor conocido” refiere a un pintor simple-importado que pinte las partes distantes de una escena al principio y después las cubra por esas piezas que sean más cercanas. El algoritmo del pintor clasifica todos los polígonos en una escena por su profundidad y después los pinta en esta orden.

Detección de Colisiones

La escena queda representada en un árbol binario BSP. Las hojas de dicho árbol representan a un objeto, mientras que los nodos no-hojas representan planos-ejes separadores. Un eje/semiplano divide la subdivisión representada por el padre en dos partes, una a la izquierda y otra a la derecha (considerando el semieje con base en el semieje padre, por ejemplo)

Otras estructuras de partición

Los árboles BSP dividen una región del espacio en dos subregiones en cada nodo. Estos están relacionados con los árboles cuaternarios y los octales, que dividen cada región en cuatro u ocho subregiones respectivamente.

donde p es el número de planos empleados para dividir, y s el número de regiones obtenidas.

Los árboles BSP pueden ser usados en espacios con cualquier número de dimensiones, pero los cuaternarios y los octales son más útiles en la división de espacios de 2 y 3 dimensiones respectivamente. Otro tipo de árbol que es como un árbol cuaternario u octal, pero que es útil en cualquier número de dimensiones, es el árbol kd.

Enlaces externos

• FAQ de BSP
• Presentación de árboles BSP
• Otra presentación de árboles BSP (PDF)
• Árboles BSP