Binary space partitioning
De Wikipedia, la enciclopedia libre
Binary space partitioning o Particionado Binario del Espacio (BSP) es un método para subdividir recursivamente un espacio en elementos convexos empleando hiperplanos. Esta subdivisión permite obtener una representación de la escena mediante un árbol conocido como Árbol BSP.
Para una descripción más general del particionado del espacio, ver particionado del espacio.
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.
Tabla de contenidos |
[editar] 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.
[editar] Generación
El particionado binario 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 particionado 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 imágen ilustra el proceso de particionado 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 G y G, que son convexos y no necesitan mayor particionado. En este caso en particular, la línea de particionado se ha tomado empleando vértices existentes del polígono y no se intersecciona con ninguno de sus segmentos. Si la línea de particionado se intersecta 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.
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 converten 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.
Hay un applet de Java que muestra el proceso de generación de un árbol en la dirección: http://symbolcraft.com/graphics/bsp/
[editar] Otras estructuras de particionado
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.
| Nombre | p | s |
|---|---|---|
| Particionado binario | 1 | 2 |
| Particionado cuaternario | 2 | 4 |
| Particionado octal | 3 | 8 |
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
