Qué es un árbol BSP?

Un “Binary Space Partitioning Tree” (o “BSP Tree” o “árbol binario para la partición de espacio”) es una estructura de datos usados para organizar objetos dentro de un espacio. Dentro del campo de gráfica de computadores, tiene aplicaciones en la remoción de areas ocultas y en el trazado de rayos. Un árbol BSP es una sub-división de espacio recursiva que trata cada segmento conectado (o polígono tridimensional) como un plano cortante que se emplea para categorizar todos los objetos restantes en el espacio como estando “enfrente” o “detrás” del plano. Es decir, cuando una partición es insertada dentro del árbol, se categoriza primero con respecto al nodo de la raíz y luego recursivamente con respecto a cada hijo apropiado. Para más información sobre árboles BSP, vea BSP Tree FAQ.

Desafortunadamente su navegador no apoya Java.

Cómo usar este applet (término Java–aplicación incrustrada en una página)

Puede dibujar segmentos conectados en la primera ventanilla (mientras la primera línea se dibuja, Java comienza una inicialización, de modo que toma mucho más tiempo dibujar la primera línea que líneas subsecuentes.) Segmentos están numerados en orden, y el árbol se construye insertando cada segmento en orden numérico. Si una partición necesita ser dividida, el frente y posterior de la partición tendrán una “f” y una “b” adjuntadas a sus respectivos nombres. Por ejemplo, si partición 1 cruza el plano cortante formado por partición 0, la parte de partición 1 que está en frente de partición 0 se llamará “1f” y la parte en el posterior se llamará “1b”.

Puede mover el punto de la flecha en color magenta, chasqueándolo y arrastrándolo. Si chasquea y lleva arrastrada la cabeza de la flecha podrá rotar la cámara que produce la escena pseudo-tridimensional.

Si el dibujo del árbol se convierte en algo demasiado grande para su ventanilla, chasquee y lleve arrastrada la ventanilla para mover el árbol.

El algoritmo del árbol BSP

El árbol BSP es creado insertando cada segmento en orden numérico dentro del árbol. Para que el usuario mejor entienda la demostración, ningún intento se hace para seleccionar el árbol BSP que produzca la mínima separación de segmentos. Esto se hace normalmente porque mantiene el tamaño del árbol a un mínimo y lo convierte en un árbol mas eficiente. Además, ningún intento se hace para producir un árbol balanceado, que también sería normalmente deseable ya que previene casos degenerativos, tales donde la hondura del árbol es aproximadamente el equivalente al número de particiones. Porque cada partición necesita ser clasificada con respecto a O(lg(n)) otras particiones, el tiempo esperado para la construcción de este árbol BSP es O(n*lg(n)).

El algoritmo de gráfica

El gráfico es dibujado usando el algoritmo nombrado “Reingold and Tilford Rooted Tree Drawing Algorithm” (algoritmos para dibujar árboles de raíz). Más información acerca de ese algoritmo se puede encontrar en la página 6 de este documento de PostScript. Si ese documento no es disponible, aquí tiene la descripción pertinente de ese algoritmo:

Después de haber dibujado el subárbol izquierdo y derecho, coloque los dibujos de los subárboles a distancia horizontal 2. Coloque la raíz un nivel por encima, y en medio de los hijos. Sin embargo, si hay sólo un hijo, coloque la raíz a distancia horizontal 1 del hijo.

El algoritmo de expresión

La escena pseudo-tridimensional se rinde clasificando el punto de la flecha con respecto al segmento de raíz, dibujando recursivamente todos los segmentos al otro lado de ese segmento, dibujando ese segmento, y luego dibujando recursivamente todos los segmentos en el mismo lado de ese segmento. Si el punto de la flecha cruza un segmento, lo estamos viendo de filo, así que no está dibujado. Porque cada segmento es visitado exactamente una vez mientras que se dibuja la escena, la escena puede ser rendida en O(n) tiempo. Aquí tiene pseudocódigo para un método en una clase de nodo de árbol BSP que ejecuta este algoritmo:

draw3DScene()
  if location(eye.point) == frontSide
    back.draw3DScene()
    drawPolygon()
    front.draw3DScene()
  else if location(eye.point) == backSide
    front.draw3DScene()
    drawPolygon()
    back.draw3DScene()
  else
    front.draw3DScene()
    back.draw3DScene()

Cuando estamos listos para dibujar la escena, el punto de la flecha y la flecha se utilizan para determinar el sistema de coordenadas para el espacio de cámara. Luego, cada polígono es dibujado usando el siguiente algoritmo:

drawPolygon()
  transform segment endpoints to camera space
  clip segment to view frustrum
  convert segment to polygon:
    set the width to the x values scaled down by the y values
    set the height to a constant value scaled down by the y values

Más información sobre árboles BSP

Probablemente el mejor sitio para encontrar información sobre árboles BSP es en el BSP Tree FAQ.

Translation performed by María Farmer Green. For information on translation services see UseSpanish.com.
Traducción ejecutada por María Farmer Green. Para información sobre servicios de traducción visite UseSpanish.com.