Árbol BSP
| ||||||
Arbol de BSP. Un Arbol de Partición Binaria del Espacio o Binary space partitioning Tree (BSP Tree) 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 [Arbol kd|árbol]] conocida como árbol de BSP.
Sumario
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.
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 dimensiones se emplean líneas
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.
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.
| Nombre | secciones |
|---|---|
| Partición binaria | 2 |
| Partición cuaternaria | 4 |
| Partición octal | 8 |
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.
Fuente
Generalidades de Arboles BSP
Learning about BSP Trees
Enlaces externos
